3.4 Метод потенціалів
Розглянутий вище розподільний метод одержання
оптимального розв’язку є досить трудомістким. У кожному допустимому розв’язку
для кожної вільної змінної необхідно будувати цикли й визначати зміни цільової
функції. Нижче розглянута модифікація розподільного методу, що одержала назву методу потенціалів. Цей метод розглянемо
як подальше продовження прикладу 3.3.
Відповідно до методу потенціалів кожному рядку й кожному
стовпцю транспортної матриці привласнюється свій потенціал: рядкам ‑ потенціали
Vi
(i=1, 2, ... n), стовпцям ‑ потенціали Uj (j=1, 2, ... m), як показано в табл. 3.6 для розглянутого прикладу.
Таблиця 3.6
|
|
|
|
Запаси |
|
1,2 15 |
1,8 0 |
1,5 35 |
А1 = 50 |
|
1,6 5 |
2,3 25 |
2,1 0 |
А2 = 30 |
Потреби |
В1 = 20 |
В2 = 25 |
В3 = 35 |
|
Ці потенціали такі, що для кожної базисної змінної сума
потенціалів дорівнює питомій вартості:
(3.6)
Повернемося до співвідношення (3.4), за яким обчислена
зміна цільової функції при збільшенні на одиницю вільної змінної х21, і замінимо в цьому
співвідношенні потенціалами питомі вартості базисних змінних:
З останнього
співвідношення видно, що за умови
перехід вільної змінної х21
у базис зменшить цільову функцію Z.
Аналогічно в співвідношенні (3.5), за яким обчислено
зміну цільової функції при збільшенні на одиницю вільної змінної х12, замінимо потенціалами
питомі вартості базисних змінних:
З останнього співвідношення видно, що за умови
перехід вільної змінної х12
у базис збільшує цільову функцію Z.
У загальному випадку, за умови
(3.7)
перехід вільної змінної xij у базис зменшує цільову функцію Z, а за умови
(3.8)
перехід вільної змінної хij
у базис збільшує цільову функцію Z.
Кількість невідомих потенціалів становить (n+m), а кількість базисних змінних (n+m-1). У системі рівнянь (3.6)
кількість невідомих потенціалів на одиницю більше кількості рівнянь. Отже,
система (3.6) є невизначеною й має нескінченну кількість розв’язків.
Для одержання одного з розв’язків системи (3.6) довільно
задамося величиною одного з потенціалів, наприклад U1=1. Після цього всі інші потенціали однозначно
визначаться за виразом (3.6).
У розглянутому випадку маємо (табл. 3.6):
Перевіримо умови (3.7) і (3.8) для вільних змінних в
транспортній матриці табл. 3.6. Для вільної змінної х23:
Отже, вільну змінну х23
переводити в базис не треба, оскільки це переведення приведе до збільшення
цільової функції Z. Для вільної
змінної х12:
Отже, вільну змінну х12
варто перевести в базис, оскільки це переведення приведе до зменшення цільовий
функції Z.
Для вільної змінної х12
будуємо цикл перерахунку (табл. 3.7) і з від’ємних вершин циклу вибираємо меншу
базисну змінну х11=15. Ця
змінна перейде в розряд вільних х11=0,
а змінна х12 стане
базисною х12=15. У
відповідності зі знаками у вершинах циклу базисна змінна х21 збільшиться на 15 одиниць і стане рівною х21=5+15=20, а базисна змінна
х22 зменшиться на 15
одиниць і стане рівною х22=25-15=10.
Таблиця 3.7
|
|
|
|
Запаси |
|
- 1,2 15 |
+ 1,8 0 |
1,5 35 |
А1 = 50 |
|
+ 1,6 5 |
- 2,3 25 |
2,1 0 |
А2 = 30 |
Потреби |
В1 = 20 |
В2 = 25 |
В3 = 35 |
|
Новому допустимому розв’язку відповідає транспортна матриця
табл. 3.8.
Таблиця 3.8
|
|
|
|
Запаси |
|
1,2 0 |
1,8 15 |
1,5 35 |
А1 = 50 |
|
1,6 20 |
2,3 10 |
2,1 0 |
А2 = 30 |
Потреби |
В1 = 20 |
В2 = 25 |
В3 = 35 |
|
У цьому розв’язку вільні змінні ‑ х11=0, х23=0; базисні змінні х12=15, х13=35,
х21=20, х22=10 о.п. Значення цільової
функції:
Перевіримо цей розв’язок на оптимальність. Довільно задамося
значенням одного з потенціалів U1=1.
Відповідно до рівняннями (3.6) інші потенціали будуть рівні:
Для вільних змінних х11
і х23 суму потенціалів
зіставимо з питомою вартістю:
Рис. 3.5. Оптимальна схема електричної
мережі
Відповідно до умови (3.8) переведення кожної із цих
змінних у базис приведе до збільшення цільової функції Z. Отже, отриманий розв’язок є оптимальним. Схема електричної
мережі, що відповідає оптимальному рішенню, показана на рис. 3.5.
Алгоритм розв’язку
транспортної задачі.
1. Відповідно до вихідних даних складається транспортна
матриця розмірністю nхm, де n ‑ кількість джерел живлення, m ‑ кількість споживачів.
2. Знаходиться допустимий розв’язок, наприклад методом
найменшої питомої вартості.
3. Для допустимого розв’язку кожному i-му рядку й кожному j-му
стовпцю транспортної матриці привласнюється значення потенціалу Vi і Uj (i=1,2,...n;
j=1,2,...m). Для кожної базисної змінної сума потенціалів дорівнює питомій
вартості Vi+Uj=сij.
4. Довільно задавшись значенням одного з потенціалів, за
виразом Vi+Uj=сij,
який є справедливий для базисних змінних, обчислюються значення інших
потенціалів.
5. Для всіх вільних змінних перевіряється співвідношення
суми потенціалів з питомою вартістю. Якщо для всіх вільних змінних Vi+Uj<сij,
то отриманий розв’язок є оптимальним.
6. Якщо є вільні змінні, для яких Vi+Uj>сij, то вибирається кожна
із цих вільних змінних і переводиться в базис. Для цього будується цикл перерахунку
(замкнута ламана лінія), початкова вершина якого лежить у клітинці обраної
вільної змінної. Інші вершини циклу лежать у клітинках, які відповідають
базисним змінним. Початковій вершині циклу привласнюється знак "+",
що відповідає збільшенню змінної. Далі знаки вершин циклу чергуються. Знаки
"+" відповідають збільшенню базисних змінних, знаки "‑"
‑ їхньому зменшенню.
7. З від’ємних вершин циклу вибирається вершина з
найменшим значенням базисної змінної й на цю величину змінюються всі змінні,
які лежать у вершинах циклу. В додатних вершинах змінні збільшуються, в
від’ємних ‑ зменшуються. При цьому обрана вільна змінна стає базисною, а
найменша за величиною базисна змінна в від’ємній вершині циклу стає вільною
(рівною нулю).
8. Для знову отриманого розв’язку обчислювальна процедура
повторюється, починаючи з пункту 3.