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

Нульові елементи матрицi та процес за кінцеве число кроків. Угорський метод один з найцікавіших і найпоширеніших методів рішення транспортних завдань. Застосовування угорських методiв для рішення завдань про призначення. Алгоритм та завдання вибору.

Рубрика Программирование, компьютеры и кибернетика
Вид контрольная работа
Язык украинский
Дата добавления 20.11.2010
Размер файла 357,6 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

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

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

Зміст

Вступ

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

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

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

Висновок

Література

Вступ

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

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

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

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

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

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

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

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

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

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

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

Введемо наступні поняття.

Нульові елементи матриці називаються незалежними нулями, якщо для будь-якого Cij рядок і стовпець, на перетинанні яких розташований елемент, не містять інші такі елементи.

Дві прямокутні матриці С и D називаються еквівалентними (C ~ D), якщо Cij ~Dij для всіх i,j . Завдання про призначення, обумовлені еквівалентними матрицями, є еквівалентними (тобто оптимальні рішення однієї з них будуть оптимальними й для другий, і навпаки). Блок-схема алгоритму угорського методу:

Попередній етап. Розшукують максимальний елемент в j-му стовпці й всі елементи цього стовпця послідовно віднімають із максимального. Цю операцію проробляють над всіма стовпцями матриці С. У результаті утвориться матриця з ненегативними елементами, у кожному стовпці якої є, принаймні, один нуль.

Далі розглядають i-тий рядок отриманої матриці, розшукують її мінімальний елемент і з кожного елемента цього рядка віднімають мінімальний. Цю процедуру повторюють із усіма рядками. У

результаті одержимо матрицю З00 ~ C), у кожному рядку й стовпці якої є, принаймні, один нуль. Описаний процес перетворення С у С0 називається приведенням матриці.

Знаходимо довільний нуль у першому стовпці й відзначаємо його зірочкою. Потім переглядаємо другий стовпець, і якщо в ньому є нуль, розташований у рядку, де немає нуля із зірочкою, то відзначаємо його зірочкою. Аналогічно переглядаємо один за іншим всі стовпці матриці З0 і відзначаємо, якщо можливо, що випливають нулі знаком '*'. Очевидно, що нулі матриці З0, відзначені зірочкою, є незалежними. На цьому попередній етап закінчується.

(k+1)-а ітерація. Припустимо, що k-та ітерація вже проведена й у результаті отримана матриця Сk. Якщо в ній є рівно n нулів із зірочкою, то процес рішення закінчується. У противному випадку переходимо до (k+1) -ої ітерації.

Кожна ітерація починається першим і закінчується другим етапом. Між ними може кілька разів проводитися пари етапів: третій - перший. Перед початком ітерації знаком '+' виділяють стовпці матриці Сk, які містять нулі із зірочками.

Перший етап. Переглядають невиділені стовпці Сk. Якщо серед них не виявиться нульових елементів, то переходять до третього етапу. Якщо ж невиділений нуль матриці Сk виявлений, то можливо один із двох випадків:

1) рядок, що містить невиділений нуль, містить також і нуль із зірочкою;

2) цей рядок не містить нуля із зірочкою.

У другому випадку переходимо відразу до другого етапу, відзначивши цей нуль штрихом.

У першому випадку цей невиділений нуль відзначають штрихом і виділяють рядок, у якій він утримується (знаком '+' праворуч від рядка). Переглядають цей рядок, знаходять нуль із зірочкою й знищують знак '+' виділення стовпця, у якому втримується даний нуль.

Далі переглядають цей стовпець (який уже став невиділеним) і відшукують у ньому невиділений нуль (або нулі), у якому він перебуває. Цей нуль відзначають штрихом і виділяють рядок, що містить такий нуль (або нулі). Потім переглядають цей рядок, відшукуючи в ній нуль із зірочкою.

Цей процес за кінцеве число кроків закінчується одним з наступних результатів:

1) всі нулі матриці Сk виділені, тобто перебувають у виділених рядках або стовпцях. При цьому переходять до третього етапу;

2) є такий невиділений нуль у рядку, де немає нуля із зірочкою. Тоді переходять до другого етапу, відзначивши цей нуль штрихом.

Другий етап. На цьому етапі будують наступний ланцюжок з нулів матриці Сk: вихідний нуль зі штрихом, нуль із зірочкою, розташований в одному стовпці з першим нулем зі штрихом в одному рядку з попереднім нулем із зірочкою й т.д. Отже, ланцюжок утвориться пересуванням від 0' до 0* по стовпці, від 0* до 0' по рядку й т.д.

Можна довести, що описаний алгоритм побудови ланцюжка однозначний і кінцевий, при цьому ланцюжок завжди починається й закінчується нулем зі штрихом.

Далі над елементами ланцюжка, що знаходяться на непарних місцях ( 0' ) ставимо зірочки, знищуючи їх над парними елементами (0*). Потім знищуємо всі штрихи над елементами Сk і знаки виділення '+'. Кількість незалежних нулів буде збільшено на одиницю. На цьому (k+1)-а ітерація закінчена.

Третій етап. До цього етапу переходять після першого, якщо всі нулі матриці Сk виділені. У такому випадку серед невиділених елементів Сk вибирають мінімальний і позначають його h (h>0). Далі віднімають h із всіх елементів матриці Сk, розташованих у невиділених рядках і додають до всіх елементів, розташованим у виділених стовпцях. У результаті одержують нову матрицю С'k, еквівалентну Сk. Помітимо, що при такому перетворенні, всі нулі із зірочкою матриці Сk залишаються нулями й у С'k, крім того, у ній з'являються нові невиділені нулі. Тому переходять знову до першого етапу. Завершивши перший етап, залежно від його результату або переходять до другого етапу, або знову повертаються до третього етапу.

Після кінцевого числа повторень черговий перший етап обов'язково закінчиться переходом на другий етап. Після його виконання кількість незалежних нулів збільшиться на одиницю й (k+1)-а ітерація буде закінчена.

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

Вирішити завдання про призначення з наступною матрицею:

Операціії

Обладнання

1

2

3

4

1

3

78

58

3

2

57

6

16

61

3

16

16

25

87

4

45

82

32

75

При рішенні завдання використаємо наступні позначення:

Знак виділення '+', що підлягає знищенню, обводимо кружком; коло, як і раніше, указуємо стрілками.

Попередній етап. Відшукуємо максимальний елемент першого стовпця - 73. Віднімаємо з нього всі елементи цього стовпця. Аналогічно для одержання другого, третього й четвертого стовпців нової матриці віднімаємо всі елементи цих стовпців від 82, 58, і 87 відповідно. Одержимо матрицю С'(C'~C).

0

4

0

84

16

76

42

26

57

66

33

0

28

0

26

12

Тому що в кожному рядку С' крім другого є нуль, то віднімаємо лише мінімальний елемент другого рядку (16) від усіх елементів цього рядку і отримуємо матрицю З0 ~ С' і на цьому процес приведення матриці закінчується.

Далі шукаємо й відзначаємо знаком '*' незалежні нулі в З0, починаючи з першого рядка.

0*

4

0

84

0

60

26

10

57

66

33

0*

28

0*

26

12

Перша ітерація. Перший етап. Виділяємо знаком '+' перший, другий, і четвертий стовпці матриці З0, які містять 0*.

Переглядаємо невиділений третій стовпець, знаходимо в ньому невиділений нуль ІЗ13 = 0, відзначаємо його штрихом і виділяємо знаком '+' перший рядок. Переглядаємо цей рядок, знаходимо в ній елемент ІЗ11 = 0* і знищуємо знак виділення першого стовпця, що містить 0*.

0*

4

0'

84

0

60

26

10

57

66

33

0*

28

0*

26

12

Шукаємо мінімальний елемент у невиділеній частині матриці З0 (тобто елементи, які лежать у стовпцях і рядках, не відзначених знаком '+').

Друга ітерація. Перший етап. Переглядаючи всі невиділені елементи, знаходимо серед них невиділений нуль ІЗ12 = 0, відзначаємо його знаком штрих та переходимо до другого етапу.

0*

4

0'

84 +

0'

60

26

10

57

66

33

0*

28

0*

26

12

Другий етап. Починаючи з елемента ІЗ12 = 0', будуємо коло, рухаючись від нього по стовпці. Знаходимо нуль із зірочкою ІЗ11= 0*, далі від нього рухаємося уздовж першого рядка й знаходимо 0'(ІЗ13).

0*

4

0'

84 +

0'

60

26

10

57

66

33

0*

28

0*

26

12

Таким чином, коло побудоване: 0'21-0*11-0'13. Заміняємо штрих на зірочку й знищуємо зірочки над парними елементами кола, а також всі знаки виділення стовпців і рядків. Після цієї ітерації кількість незалежних нулів (0*) стало дорівнювати 4 (розмірності матриці З) і тому алгоритм закінчує роботу. Шукані елементи призначення відповідають позиціям незалежних нулів матриці З3 (тобто 0*).

0'

4

0*

84

0*

60

26

10

57

66

33

0*

28

0*

26

12

Висновок

Відповідне значення цільової функції:

F = C12+C24+C31+C43 = 57+82+58+87=284

Література

1. Системы автоматизированного проектирования. В 9-ти кн.Учебное пособие для вузов. Под редакцией Норенкова И.П. М.: Высш. шк., 1986.

2. Норенков И.П. Введение в автоматизированное проектирование технических устройств и систем. Учебное пособие для вузов. - М.: Высш. шк., 1986.

3. П. Шеннен и др. Математика и САПР. т.1. М.: Мир, 1988.

4. Батищев Д.И. Методы оптимального проектирования. М.: Радио и связь, 1984.

5.Системы автоматизированного проектирования в радиоэлектронике. Справочник. М.: Радио и связь, 1986.

6. Погребной В.К. О декомпозиции графов на классы изоморфных подграфов. В кн.: Вопросы программирования и автоматизации проектирования. Изд. ТГУ, 1979, с. 82-96.

7. Петренко А.И. Основы автоматизации проектирования. К.: Техника, 1982. - 295 с.

8. Ильин В.Н.. Основы автоматизации схемотехнического проектирования. Г.: Энергия, 1979. - 392 с.

9. Демидович Б.П., Марон И.А. Основы вычислительной математики. Г.: Изд-во «Наука», 1966. - 664 с.

10.Разевиг В.Д. Система сквозного проектирования электронных устройств DesignLab 8.0.- М.: Изд-во «Солон»,1999. - 698 с.


Подобные документы

  • Загальний вид двовимірного завдання лінійного програмування. Алгоритм рішення задач графічним методом. Максимізація (мінімізація) цільової функції. Послідовність рішення завдань лінійного програмування симплексом-методом. Принцип перетворення Гауса.

    контрольная работа [149,8 K], добавлен 24.11.2010

  • Розробка, дослідження та реалізація методів вирішення завдань аналізу, розпізнавання і оцінювання зображень як один із провідних напрямків інформатики. Класифікація та аналіз існуючих методів розпізнавання образів, переваги та недоліки їх застосування.

    статья [525,8 K], добавлен 19.09.2017

  • Огляд та аналіз методів розв’язання системи диференціальних рівнянь та вибір методів рішення. Алгоритми методів Ейлера. Вибір методу рішення задачі Коші. Рішення диференціальних рівнянь. Отримання практичних навиків програмування на мові Паскаль.

    курсовая работа [174,3 K], добавлен 06.03.2010

  • Постановка лінійної цілочисленної задачі. Теоретичні основи методів відсікання. Задача з булевими змінними. Перший та другий алгоритми Гомори. Алгоритм Дальтона й Ллевелина. Поняття припустимого й оптимального рішення. Область пошуку екстремума.

    курсовая работа [187,8 K], добавлен 27.01.2011

  • Розробка методів вирішення завдань аналізу, розпізнавання, оцінювання зображень як одних з провідних напрямків інформатики. Описання методу пошуку співпадіння об’єкту-цілі з міткою-прицілом на заданому відеоряді. Виявлення об’єкта на цифровому зображенні.

    статья [138,7 K], добавлен 21.09.2017

  • Основні елементи блок-схеми алгоритмів з розгалуженням. Команди обчислення значення логічного виразу. Вибір тих чи інших дій для продовження алгоритму. Прийняття рішення залежно від результату перевірки вказаної умови. Виконання команди перевірки умови.

    презентация [166,9 K], добавлен 23.11.2014

  • Загальне поняття про метод Якобі. Мова програмування C++ Builder, її призначення. Оператор do-while, його використання. Динамічний розподіл пам’яті. Загальний вигляд інтерфейсу програми, інформація про метод. Реалізація програми, модуль мain.cpp та dfm.

    курсовая работа [320,6 K], добавлен 17.06.2012

  • Опис актуальності, цілей, завдань розроблюваного ПЗ, його призначення та галузь застосування. Огляд програмних продуктів, що мають аналогічні цілі й призначення. Розробка інтерфейсу ПО й короткий опис основних елементів керування грою у п`ятнашки.

    курсовая работа [806,3 K], добавлен 20.10.2012

  • Призначення та вимоги до функціональних характеристик при розробці мультимедійного посібника. Алгоритм побудови учбового курсу, установка загальних параметрів курсу, розробка практичних завдань та тестування, глосарія та довідки, опис інтерфейсу.

    курсовая работа [2,8 M], добавлен 23.11.2010

  • Опис предметної області по темі "Перевантаження методів". Методика розробки тестових завдань. Проектування та розробка програми. Опис елементів управління, які використовуються в проекті. Опис текстів процедур та опрацювання подій. Отримані результати.

    курсовая работа [620,9 K], добавлен 06.08.2013

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.