Блоґ одного кібера

Історія хвороби контуженого інформаційним вибухом

Угорський метод

with 3 comments

Угорський метод

Лаболаторна робота з дослідження операцій aka методи оптимізації

В цій статті я хочу розказати про розв’язування задачі про виконавців угорським методом. Тут буде тільки відповідь на запитання: “Як розв’язати задачу”, а не “Чому і як цей метод працює?”. Записано на семінарі в Богдана Валерійовича Довгая.

Умова задачі:

ми маємо n завдань, і n виконавців. При чому кожен виконавець для свого завдання хоче певний розмір зарплати. Потрібно поділити завдання між виконавцями з мінімальними витратами. Крім того один виконавець має робити одне завдання. Не більше і не менше. Запишемо витрати i-того виконавця на j-ту роботу як Ci,j. Наприклад:

3 10 5 9 16
6 8 11 8 18
7 13 10 3 4
5 9 6 21 12
5 4 12 6 13

Розв’язок:

Знаходимо мінімальний елемент кожного рядка:

3 10 5 9 16 3
6 8 11 8 18 6
7 13 10 3 4 3
5 9 6 21 12 5
5 4 12 6 13 4

І віднімаємо від кожного елементу рядка:

0 7 2 6 13
0 2 5 2 12
4 10 7 0 1
0 4 1 16 7
1 0 7 2 9

Далі таке саме робимо для стовпців. Наша мета – зробити хоча б один нуль в кожному рядку і кожному стовпцю:

0 7 2 6 13
0 2 5 2 12
4 10 7 0 1
0 4 1 16 7
1 0 7 2 9

0 0 1 0 1

Отримуємо:

0 7 1 6 12
0 2 4 2 11
4 10 6 0 0
0 4 0 16 6
1 0 6 2 8

Тепер підготовчий етап пройдено. Можна розставляти позначки. Позначки розставляються за таким правилом: “Якщо в рядку є єдиний непозначений нуль, то позначаємо його (символ *). Всі нулі того стовпчика який щойно позначили – викреслюємо (символ ^)”.

0* 7 1 6 12
0^ 2 4 2 11
4 10 6 0 0
0^ 4 0* 16 6
1 0* 6 2 8

Таке саме робимо для стовпців, тобто “Якщо в стовпці є єдиний непозначений нуль, то позначаємо його. Всі нулі того рядка який щойно позначили – викреслюємо”.

0* 7 1 6 12
0^ 2 4 2 11
4 10 6 0* 0^
0^ 4 0* 16 6
1 0* 6 2 8

Тепер рахуємо скільки нулів позначено. Якщо позначено 5 нулів (кількість виконавців і робіт), то ці нулі показують кому яку роботу дати. В нас позначено тільки чотири нулі, тому розв’язок не оптимальний. З матрицею потрібно робити перетворення.

  1. Позначимо символом # (“дієз”) рядки, в яких є непозначені нулі (без *).
    0* 7 1 6 12
    # 0^ 2 4 2 11
    4 10 6 0* 0^
    0^ 4 0* 16 6
    1 0* 6 2 8
  2. Позначимо стовпчики в яких в позначених рядочках є викреслений нуль.
    0* 7 1 6 12
    # 0^ 2 4 2 11
    4 10 6 0* 0^
    0^ 4 0* 16 6
    1 0* 6 2 8
    #
  3. Позначимо рядочки, де в позначених стовпчках є позначений нулик.
    # 0* 7 1 6 12
    # 0^ 2 4 2 11
    4 10 6 0* 0^
    0^ 4 0* 16 6
    1 0* 6 2 8
    #

Тепер викреслюємо непозначені рядки і позначені стовпчики. Але я краще просто підкреслю те що має залишитись.

# 0* 7 1 6 12
# 0^ 2 4 2 11
4 10 6 0* 0^
0^ 4 0* 16 6
1 0* 6 2 8
#

Серед невикреслених (читай “підкреслених”) рядків шукаємо мінімальний емент. В нас він дорівнює 1. Віднімаємо його від невикреслених рядків,

-1 6 0 5 11
-1 1 3 1 10
4 10 6 0 0
0 4 0 16 6
1 0 6 2 8

і додаємо до викреслених стовпчиків. (Важливо, щоб усі елементи залишились додатніми). В нашому випадку додаємо в перший стовпчик.

0 6 0 5 11
0 1 3 1 10
5 10 6 0 0
1 4 0 16 6
2 0 6 2 8

В нашій новій матриці знову починаємо позначати нулі. Якщо їх буде п’ять завершимо роботу.

# 0^ 6 0^ 5 11
# 0* 1 3 1 10
5 10 6 0* 0^
# 1 4 0* 16 6
2 0* 6 2 8
# #

Позначених нулів знову чотири, тому віднімаємо 1 (мінімальний невикреслений елемент) від невикреслених рядків і додаємо в викреслені стовпчики. З новою матрицею знов продовжимо позначення

0* 5 0^ 4 10
0^ 0^ 3 0* 9
6 10 7 0^ 0*
1 3 0* 15 5
3 0* 7 2 8

Опа. В нас 5 позначених нулів. При чому в кожному рядку і кожному стовпці лише один позначений нуль. Наприклад позначений нуль в першому стовпці першого рядка означає, що першому виконавцю будем давати першу роботу. І так далі. Тепер записуємо матрицю розв’язку X. В ній якщо і-тому робітнику дають j-те завдання то елемент в і-тому рядку і j-тому стовпці буде містити одиничку. Всі інші елементи нульові. Отже X:

1 0 0 0 0
0 0 0 1 0
0 0 0 0 1
0 0 1 0 0
0 1 0 0 0

І звісно насамкінець обчислюємо цільову функцію (витрати). Для цього знаходимо суму всіх елементів по i,j=[1..n] Xi,j*Ci,j. Тобто тільки тих де X ненульове. В нас Z(X)=3+8+4+6+4=25.

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

Advertisements

Written by bunyk

Лютий 19, 2009 at 15:24

Оприлюднено в Всяке, Конспекти

Tagged with ,

Відповідей: 3

Subscribe to comments with RSS.

  1. Згадав предмет “методи оптимізації” – дуже любив лабораторні роботи з цього предмету – особливо задачу про комівояжера.

    illusions

    Травень 22, 2009 at 11:39

  2. Дуже гарно дякую, сильно помогло, коли запрограмовував на Delphi

    Sandy

    Травень 5, 2012 at 17:41


Залишити відповідь

Заповніть поля нижче або авторизуйтесь клікнувши по іконці

Лого WordPress.com

Ви коментуєте, використовуючи свій обліковий запис WordPress.com. Log Out / Змінити )

Twitter picture

Ви коментуєте, використовуючи свій обліковий запис Twitter. Log Out / Змінити )

Facebook photo

Ви коментуєте, використовуючи свій обліковий запис Facebook. Log Out / Змінити )

Google+ photo

Ви коментуєте, використовуючи свій обліковий запис Google+. Log Out / Змінити )

З’єднання з %s

%d блогерам подобається це: