Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

5.5.5. Угорський метод розв’язування транспортної задачі

Ідея цього методу розв’язання транспортної задачі вперше була запропонована угорським математиком Є. Егерварі 1931 року, тобто ще до розроблення загальної теорії лінійного програмування. Спочатку цей метод був розроблений для розв’язування специфічного виду транспортної задачі, а згодом узагальнений. Нині угорський метод є одним з найпоширеніших методів розв’язання транспортних задач.

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

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

Назвемо умовно-оптимальним планом (псевдопланом) транспортної задачі (5.1)—(5.4) таку сукупність невід’ємних чисел , яка задовольняє задану систему нерівностей:

(5.27)

(5.28)

і такі наступні умови для змінних двоїстої задачі — потенціалів:

, якщо ;

, якщо .

Мірою недопустимості (умовою неоптимальності) умовно-оптимального плану може бути наявність різниці між сумою всіх запасів (чи потреб, що те саме) і сумою всіх перевезень умовно-оптимального плану, тобто:

(5.29)

Зрозуміло, що чим менша нев’язка D, тим ближче умовно-оптимальний план до найкращого плану транспортної задачі, а у разі, коли D = 0, він збігається з оптимальним планом.

Звідси легко збагнути ідею розглядуваного методу розв’язування транспортної задачі: починаючи з деякого початкового плану задачі, подвійної до транспортної , можна знайти послідовність оптимальних планів ряду допоміжних задач на мінімізацію (5.29) за обмежень (5.27) і (5.28), кожний наступний план якої надає нев’язці (5.29) меншого значення у зіставленні з попереднім, а останній план цієї послідовності надає нев’язці нульового значення, збігаючись у такий спосіб з оптимальним планом транспортної задачі.

Отже, кожна ітерація методу означатиме розв’язування допоміжної задачі (5.27)—(5.28) і зменшення при цьому значення цільової функції (5.29) порівняно з попереднім розв’язком цієї задачі.

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

, (5.30)

причому даний план задовольняє умову:

+, (5.31)

а також у кожному рядку матриці перевезень унаслідок такого вибору потенціалів виконуватиметься хоча б одна рівність виду (5.31). Справді, взявши для -го рядка в правій частині (5.31) , дістанемо:

.

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

Наведені вище обмеження для змінних двоїстої задачі:

, якщо ;

, якщо

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

Зауважимо, що мінімізація цільової функції (5.29) рівнозначна максимізації другого її доданка

(5.32)

при тій самій системі обмежень. Зрозуміло, що , а при матимемо: .

Виходячи з наведених теоретичних засад, розглянемо алгоритм угорського методу:

1. Побудова допоміжної задачі з цільовою функцією (5.32) та умовами (5.27), (5.28).

2. Побудова початкового опорного плану допоміжної задачі, що отримана на попередньому кроці алгоритму, одним з відомих методів.

3. Відшукання оптимального плану допоміжної задачі.

3.1. Збільшення значення . Визначають рядки, де сума перевезень по рядку менша від запасів, а за допомогою них — стовпці, які мають у вибраному рядку не заборонені для перевезень клітини. Вибрані рядки і стовпці позначають так:

, , (5.33)

та . (5.34)

Потім , . (5.35)

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

.

У знайденому ланцюзі позначаємо першу його клітину з кінця знаком «плюс», а інші за чергою знаками «плюс» і «мінус». Знайдемо величину:

. (5.36)

Як видно з алгоритму, дорівнює меншій з двох величин: найменшого елемента ланцюга, що позначений знаком «мінус», і невикористаного запасу в позначеному першим пунктом відправленні. Величина є незадоволеною потребою в позначеному наприкінці пункті доставки. Зсуву по ланцюгу підлягає менша з цих величин, що й приводить до наведеної формули розрахунку q (5.36).

4. Перехід до наступної допоміжної задачі, оптимальний план якої буде ближчим до оптимального плану початкової транспортної задачі.

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

Позначимо множину позначених рядків через , а множину позначених колонок — через J (у кінцевій таблиці, що містить розв’язок допоміжної задачі). Знайдемо величину:

, (5.37)

тобто найменше значення різниці, що стоїть у дужках серед заборонених клітин, які містяться в позначених рядках і непозначених колонках; строго більше від нуля, оскільки в іншому разі відповідна клітина не була б забороненою для перевезень, і її колонку можна було б позначити за допомогою того позначеного рядка, якому належить ця клітина, що суперечить умові . Зрозуміло, що, збільшивши, наприклад, потенціал , який входить у формулу (5.37), на величину , тим самим перетворюють відповідну клітину (в якій ) у вільну для перевезень. Звичайно, таких клітин, що задовольняють умову (5.26), може бути більше, ніж одна. Тому в усіх позначених рядках збільшуємо потенціали на , а щоб зберегти попередню множину клітин вільних для перевезень, величину віднімаємо від потенціалів позначених колонок . Решту потенціалів залишаємо незмінною. Тут слід підкреслити, що згідно з алгоритмом розв’язання допоміжної задачі всі вільні для перевезень клітини, які є в позначених рядках, обов’язково містяться і в позначених колонках. Отже, нову систему потенціалів знаходимо, змінюючи попередню за формулами:

(5.38)

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

, .

Визначивши , знову формулюємо і розв’язуємо допоміжну задачу.

5. Повторення кроків 2—4 до відшукання оптимального плану початкової транспортної задачі.

Сформулюємо правила розв’язування допоміжної задачі, одночасно демонструючи їх на відповідному прикладі, і даючи в разі потреби відповідні пояснення.

Розв’яжемо угорським методом транспортну задачу, наведену в табл. 5.14:

Таблиця 5.14

Розв’язання. Визначаємо початкову систему потенціалів для побудови першої допоміжної задачі, використовуючи (5.23):

, .

Маємо:

,

,

,

.

,

,

,

.

Розраховуємо величини і записуємо їх у вигляді таблиці:

Клітини побудованої таблиці з елементами (різницями), відмінними від нуля, будуть забороненими для перевезень, чим гарантується виконання умов стосовно потенціалів, а клітини з нулями можна використати для знаходження плану допоміжної задачі.

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

Таблиця 5.15

Загальний обсяг перевезень за початковим планом менший на 50 одиниць від обсягу всіх запасів (потреб): .

Спробуємо змінити визначений план для збільшення значення . Це можна зробити лише за рахунок тих рядків, де запас залишився невикористаним. Отже, позначимо ті рядки, де сума перевезень по рядку згідно з початковим планом менша від відповідного запасу: . Позначаємо їх двома числами. Одне з них відповідає значенню і позначається символом , а друге є нулем і позначається символом , де і — номер вибраного рядка. У нашому прикладі таким буде лише один — четвертий рядок. Отже, і, оскільки нуль відповідатиме четвертому рядку, то маємо: .

Взагалі таких рядків може бути кілька. За допомогою кожного позначеного рядка (в нашому прикладі четвертого) позначаємо колонки, які мають у позначеному рядку не заборонені для перевезень клітини, двома символами (5.31): та .

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

Позначення відповідають умові (5.35): , .

У такий спосіб далі позначаємо перший рядок числами:

, ,

а третій , .

Таблиця 5.16

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

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

, .

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

У нашому прикладі такою послідовністю клітин є: А4В2, А1В2, А1В4,

а .

Далі використовуємо формулу:

Отже, до перевезень x42 і x14 додаємо q = 40, а від перевезення x12 віднімаємо цю саму величину. Матимемо табл. 5.17:

Таблиця 5.17

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

Зауважимо, що оптимальне значення лінійної функції задачі на 40 одиниць більше від початкового; збільшення лінійної функції забезпечується ациклічністю ланцюга і більшою на одиницю кількістю додатних (позначених знаком «плюс») клітин у ньому.

Перейдемо до нової допоміжної задачі, оптимальний план якої буде ближчим до оптимального плану заданої транспортної задачі; цільова функція допоміжної задачі , яка визначає загальний обсяг перевезених вантажів, при цьому збільшується. Для нашого прикладу цілком зрозуміло, що рівності (тобто повного перевезення вантажу) можна було б досягти, якби, наприклад, зняти з А4В1 або з якоїсь іншої клітини першої колонки заборону на перевезення і здійснити перевезення (і = 1, 3, 4). Оскільки згадана заборона накладена попередньою системою потенціалів , то зняти її можна, лише замінивши попередню систему потенціалів новою, але такою, щоб зберігалася сукупність незаборонених для перевезень клітин, знайдена на попередньому етапі.

Для наведеного прикладу множина клітин (i, j), для яких , , така: А1В1, А3В1, А4В1, причому досягається в клітині А3В1.

Знайдемо нову систему потенціалів:

,

,

,

,

,

,

,

.

Отже, тепер забороненими для перевезень клітинами будуть ті, де , що запишемо в таблицю:

Визначаємо початковий план і розв’язуємо нову допоміжну задачу (табл. 5.18):

Таблиця 5.18

Зробивши зсув на 40 одиниць по ланцюгу А4В2, А1В2, А1В4, матимемо такий план:

.

Цей план оптимальний, оскільки , тобто .

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