Алгоритм методу потенціалів

1. Знаходимо опорний план транспортної задачі, який би задовольняв пер­шу умову потенціальності плану для базисних клітинок, загальна кіль­кість яких m+n-1, тобто a_i+b_j=с_ij.

2. Утворена система рівнянь містить m+n невідомих a_i , , та b_j, . Оскільки рівнянь на одне менше ніж змінних, то значення однієї із незалежних змінних обираємо довільно (наприклад, беремо, що воно дорівнює нулю) і знаходимо розв’язок системи.

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

4. Якщо існують небазисні клітинки, де умови потенціальності порушуються, то ознакою змінної, яку слід ввести в базис, є максимум порушення умови потенціальності (за модулем). Тобто, в базис вводиться та клітинка, де вико­ну­ється mіn (-g_ij) =min (). Ця клітинка разом з базисними утворює цикл, за яким треба перемістити найменше перевезення q з від’ємного півциклу.

5. Для нового опорного плану знову проводимо перевіркуна по­тенціальність згідно із кроками 1-3.

6. Кроки 1-5 повторюємо поки не дістанемо оптимальний план.

Зауваження 3.1. Розв’язок транспортної задачі при цілочислових значеннях за­пасів і потреб завжди буде цілочисловим.

Зауваження 3.2. Скінченність алгоритму методу потенціалів випливає із його монотонності і скінченності числа опорних планів задачі.

Зауваження 3.3. Якщо маємо відкриту транспортну задачу, то для її розв’язу­вання існує метод фіктивних пунктів, за допомогою якого задача формально зводиться до закритої, що дає змогу розв’язати її методом потенціалів.

Для задачі з перевищенням суми запасів над сумою потреб вводиться фіктивний пункт доставки B_ф=B_n+1 з потребою

,

при цьому усі величини с_i.n-1=0, .

Якщоє задача з перевищенням потреб над запасами,то аналогічно,вводячи фіктивний пункт відправлення A_ф=A_m+1 з фік­тивним запасом

,

і, поклавши с_m+1.j=0, приходимо до закритої транспортної задачі.

Зауваження 3.4. Якщо маємо вироджений опорний план, то для розв’я­зування транспортної задачі методом потенціалів слід деякі вільні клі­тинки таблиці вважати за базиси, щоб загальна кількість базисних клітинок була m+n -1. Для цього вводяться в ці клітинки значення перевезень h, 2 h,..., де h = 0 в оптимальному плані.

Зауваження 3.5. Для кожної небазисної клітинки транспортної таблиці завжди існує цикл (тільки один), одна клітинка якого небазисна, а всі інші – базисні.

Зауваження 3.6. Якщо в кінцевій таблиці транспортної задачі можна знайти небазисну клітинку, ціна циклу для якої дорівнює нулю, то це свідчить про те, що транспортна задача має ще один оптимальний розв’язок з тією самою загальною вартістю перевезень. Формули за якими знаходимо новий план, як і раніше, мають вигляд:

Приклад 3.1. Знайти методом потенціалів оптимальний план перевезень для транспортної задачі, початковий опорний план якої, поєднаний з матрицею вартостей перевезень та запасів і потреб, наведено в табл. 3.5. Складемо систему рівнянь для визначення потенціалів:

Поклавши , дістанемо розв’язок:

a₁⁽⁰⁾= –4, a₂⁽⁰⁾= –2, b₁⁽⁰⁾= 3, b₂⁽⁰⁾= 8, b₃⁽⁰⁾= 6, b₄⁽⁰⁾= 6.

Перевіряємо,чи задовольняє знайдений розв’язок умови потенці­альності для небазисних клітинок таблиці. Для цього порівнюємо відпо­відні суми потенціалів з елементами матриці вартостей перевезень:

Найбільшу невідповідність (за модулем) дає клітинка таблиці (3.4):

Отже, її треба ввести в базис. Складемо цикл із клітинок (2,4), (3,4), (3,1), (2,1) і визначимо q = 10 (табл. 3.6). Знайдемо нові значення перевезень циклу: x₂₁ =50-10=40, x₄₂ =0+10=10, x₃₁ =40+10=50, x₃₃ =10–10=0.

Таблиця 3.6

ПВ	ПД	ai	ai(0)
B1	B2	B3	B4
A1	– 1 7	4 4 30	2 2 20	2 3		– 4
A2	1 (–) 1 50	6 5	4 6	4 (+) 2		– 2
A3	3 (+) 3	8 8	6 7	6 (–) 6
bj
bj(0)

Новий опорний план, де клітинка (2,4) буде базисною, а клітинка (3,4) – вільною, наведено у табл. 3.7.

Знаходимо нову систему чисел-потенціалів і . Їх нові значення записані у табл. 3.7. Як легко побачити, умову потенціальності порушено тільки в одній клітинці (2,2), де

Складаємо цикл із клітинок (2,2), (3,2), (3,1), (2,1) і визначаємо q = = 40. Змінюючи на цю величину значення перевезень у клітинкахвизначеного циклу,отримаємо опорний план, що наведений у табл. 3.8. А знайшовши нові значення потенціалів і , записуємо їх в табл. 3.8, де наведено оптимальний план, у чому легко переконатися, перевіривши його на умови потенціальності.

Таблиця 3.7

ПВ	ПД	ai	ai(0)
B1	B2	B3	B4
A1	– 1 7	4 4 30	2 2 20	0 3		– 4
A2	1 (–) 1 40	6 (+) 5	4 6	2 2		– 2
A3	3 (+) 3	8 (–) 8	6 7	4 6
bj
bj(0)

Таблиця 3.8

ПВ	ПД	ai	ai(0)
B1	B2	B3	B4
A1	– 1 7	4 4 30	2 2 20	1 3
A2	0 1	5 5	3 6	2 2
A3	3 3	8 8	6 7	5 6
bj
bj(0)	–5		–2	–3

Зауваження до методу потенціалів:

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

2. У випадку виродженого ОП слід ввести фіктивні перевезення з таким розрахунком, щоб однозначно обчислити всі потенціали.

3. Цикл завжди існує та єдиний для кожної вільної клітинки таблиці (для невиродженого ОП).

4. Якщо для якоїсь вільної клітинки (x_ij = 0) оптимального ОП у співвідношеннях досягається строга рівність, то це говорить про не одиничність оптимального ОП.

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