Метод Мака для задачі вибору.

Засновник метода К.Мак .Розглядається задача вибору розмірності n x n.Вибирем по мінімальному елементу в кожній строкі. Підкреслемо кожний з цих елементів. Якщо в кожному стобчику є рівно по одному підкресленому елементу, то підкреслені елементи - базис -визначають оптимальний вибор.

Початок

Розділемо множину стобчиків на дві множини А і А^’ ,А-вибрана множина , А^’ - невибрана множина.На початку (і при подальшому поверненню до Початоку ) вибраних стобчиків нема,тому що множина А пуста, а множина А^’ має всі стобчики.

Шаг 1

Вибрати з множини А^’ стобчик, який має більш ніж один підкреслений елемент. Перевести цей стобчик з множини А^’ в множину А.

Шаг 2

Нехай елемент множини А з строки i дорівнює b_i ,а мінімальний елемент множини А^’ з строки i дорівнює a_i . Нехай

min(a_i^’ -b_i) =a_r^’-b_r

i

Шаг 3

Збільшити всі елементи множини А на a_r^’-b_{r .}

Шаг 4

Відмітити a_r^’ крапками внизу. Тепер a_r^’ -”відмічений крапками елемент”.

Шаг 5

Нехай С-стобчик ,який має а_r^’ .Якщо в С більш двох підкреслених елементів, перевести С з множини А^’ в множину А і перейти до шагу 2. В противному випадку перейти до наступного шагу.

Тепер можна підкреслити елементи ще в одному стобчику.

Шаг 6

Підкреслити останій а_r^’ повністю. Це новий підкреслений елемент.

Шаг 7

Найти початковий підкреслений елемент в тій же строкі,що a_r^’ .

Прибрати підкреслювання. Позначити стобчик, в якому є цей елемент D.

Шаг 8

Якщо D не має двох підкреслених елементів , він повинен мати елемент помічений крапками. Позначимо цей елемент a_r^’ повернемося до шагу 6.

Якщо D має ще один підкреслений елемент ,то повністю підкреслені елементи утворюють базис.

Якщо зостався ще стобчик без підкреслених елементів,повернутися до початку.

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

6.2 Порядок виконання роботи

6.2.1. Ознайомитися з матеріалом даних методичних вказівок.

6.2.2. Опрацювати лекційний матеріал та літературні джерела з проблематики задач призначення.

6.2.3. Розробити математичну модель визначеного викладачем варіанту задачі про призначення.

6.2.4. Засвоїти інструкцію по використанню пакету прикладних програм “ZON.PAS”.

6.2.5. Вирішити вихідну задачу за допомогою транспортної моделі.

6.2.6. Вирішити задачу про призначення методом Мака за умови:

a) m=n; b) m<n; c) m>n .

6.2.7. Провести аналіз отриманих результатів.

6.2.8. Зробити висновки по роботі.

6.3 Завдання до роботи

В одному з цехів приладобудівного заводу виникла необхідність виконати визначені види робіт на наявному парку верстатів. На кожному з наявних верстатів може виконуватися лише одна робота. Робота i (i=1,2...m),яка виконується на верстаті j (j=1,2...n) пов’язана з витратами с_ij .Необхідно розподілити m робіт по n станкам таким чином ,щоб сумарні витрати були мінімальними.