3.4. Рішення задачі про призначення

Згадаємо модель призначень, докладно розглянуту в розділі 2.2:

мінімізувати (3.18)

при обмеженнях

, i = 1, 2, …, n, (3.19)

, j = 1, 2, …, n, (3.20)

x_ij = 0 або 1 при всіх i та j. (3.21)

Через характер задачі допустиме рішення містить рівно n перемінних, що дорівнюють одиниці, тоді як будь-яке базисне рішення включає перемінних. Отже, при застосуванні симплексного алгоритму рішення мережних задач до моделі призначень (3.18) – (3.21) кожен базис містить нульових перемінних (маршрутів). Ця обставина приводить до висновку, що застосування симплексного алгоритму не забезпечує повною мірою обліку особливої структури моделі призначень. У даному розділі будуть викладені три відмінних від симплексного методу рішення задачі про призначення.

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

Симплексний алгоритм. Розглянемо задачу про призначення, умови якої приведені на рис. 3.8. Відзначимо, що три маршрути (у другому рядку) мають нульові значення перемінних, що вказує на вырожденность. Можна простежити за всіма ітераціями, розглянувши рис. 3.9 – 3.14, що містять послідовність отриманих оцінок і спробні рішення. Відзначимо також, що значення цільової функції не міняється аж до відшукання останнього рішення.

Рис. 3.8. Вихідне базисне рішення задачі про призначення. (Загальні витрати – 54)

Метод, що ґрунтується на алгоритмі максимального потоку.

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

Алгоритм зводиться до наступних кроків.

Крок 1. При заданих оцінках рядків v_i, i = 1, 2, ..., n, стовпців w_j, j = 1, 2, ..., n, що дають ненегативні відносні оцінки (с_ij – v_i – w_i) 0, визначається, чи існує допустиме рішення, у котре входять тільки маршрути з відносними оцінками. У випадку позитивної відповіді на це питання – останов, через те, що рішення є оптимальним. У противному випадку здійснюється перехід до кроку 2.