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

 = 136

 

Ці потенціали такі, що для кожної базисної змінної сума потенціалів дорівнює питомій вартості:

                                                        (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

 = 136

 

Новому допустимому розв’язку відповідає транспортна матриця табл. 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

 = 134,5

 

У цьому розв’язку вільні змінні ‑ х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+Ujij.

4. Довільно задавшись значенням одного з потенціалів, за виразом Vi+Ujij, який є справедливий для базисних змінних, обчислюються значення інших потенціалів.

5. Для всіх вільних змінних перевіряється співвідношення суми потенціалів з питомою вартістю. Якщо для всіх вільних змінних Vi+Ujij, то отриманий розв’язок є оптимальним.

6. Якщо є вільні змінні, для яких Vi+Ujij, то вибирається кожна із цих вільних змінних і переводиться в базис. Для цього будується цикл перерахунку (замкнута ламана лінія), початкова вершина якого лежить у клітинці обраної вільної змінної. Інші вершини циклу лежать у клітинках, які відповідають базисним змінним. Початковій вершині циклу привласнюється знак "+", що відповідає збільшенню змінної. Далі знаки вершин циклу чергуються. Знаки "+" відповідають збільшенню базисних змінних, знаки "‑" ‑ їхньому зменшенню.

7. З від’ємних вершин циклу вибирається вершина з найменшим значенням базисної змінної й на цю величину змінюються всі змінні, які лежать у вершинах циклу. В додатних вершинах змінні збільшуються, в від’ємних ‑ зменшуються. При цьому обрана вільна змінна стає базисною, а найменша за величиною базисна змінна в від’ємній вершині циклу стає вільною (рівною нулю).

8. Для знову отриманого розв’язку обчислювальна процедура повторюється, починаючи з пункту 3.