Категория
Информатика
Тип
реферат
Страницы
8 стр.
Дата
14.09.2014
Формат файла
.html — Html-документ
Архив
1042203.zip — 5.58 kb
  • ugorskij-metod-rshennja-zavdan-pro-priznachennja_1042203_1.html — 19.25 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо


Текст работы

К онтрольн а робот а

“Угорський метод рішення завдань про призначення”

Зміст

Вступ

1 Постановка завдання

2 Розв’язання завдання

3 Приклад розв’язання задачі за допомогою угорського методу

Висновок

Література

Вступ

Тема контрольної роботи «Угорський метод рішення завдань про призначення».

Мета роботи: навчитися застосовувати угорський метод для рішення завдань про призначення, а саме:

алгоритм угорського методу;

завдання вибору.

Угорський метод є одним з найцікавіших і найпоширеніших методів рішення транспортних завдань. Основна ідея цього методу була вперше висловлена угорським математиком Е. Егерварі (звідси й назва методу) задовго до виникнення теорії лінійного програмування.

Розглянемо спочатку основні ідеї угорського методу на прикладі рішення завдання вибору (завдання про призначення), що є окремим випадком Т-задачі, а потім узагальнимо цей метод для довільної Т-задачі.

1 Постановка завдання

Припустимо, що єрізні роботи імеханізми, кожний з яких може виконувати будь-яку роботу, але з неоднаковою ефективністю. Продуктивність кожного i-го механізмупри виконанні j-тої роботипозначимо Cij, і = 1,...,n; j = 1,...,n. Потрібно так розподілити механізми по роботах, щоб сумарний ефект від їхнього використання був максимальний. Таке завдання називається завданням вибору або завданням про призначення.

Формально вона записується так. Необхідно вибрати таку послідовність елементів /> з матриці

/>

щоб сума /> була максимальна й при цьому з кожного рядка й стовпця був обраний тільки один елемент.



Ваше мнение



CAPTCHA