1.Алгоритм методу потенціалів
складається з таких етапів:
Визначення типу транспортної задачі (відкрита чи закрита). За необхідності слід звести задачу до закритого типу.
Побудова першого опорного плану транспортної задачі одним з відомих методів.
Перевірка опорного плану задачі на виродженість. За необхідності вводять нульові постачання.
Перевірка плану транспортної задачі на оптимальність.
4.1. Визначення потенціалів для кожного рядка і стовпчика таблиці транспортної задачі. Потенціали опорного плану визначають із системи рівнянь ui + vj = cij, які записують для всіх заповнених клітинок транспортної таблиці, кількість яких дорівнює , а кількість невідомих — . Кількість рівнянь на одне менша, ніж невідомих, тому система є невизначеною, і одному з потенціалів надають нульове значення. Після цього всі інші потенціали розраховують однозначно.
4.2. Перевірка виконання умови оптимальності для пустих клітин. За допомогою розрахованих потенціалів перевіряють умову оптимальності ui + vj ? cij для незаповнених клітинок таблиці. Якщо хоча б для однієї клітини ця умова не виконується, тобто ui + vj > cij, то поточний план є неоптимальним, і від нього необхідно перейти до нового опорного плану.
4.3. Вибір змінної для введення в базис на наступному кроці. Загальне правило переходу від одного опорного плану до іншого полягає в тому, що з попереднього базису виводять певну змінну (вектор), а на її місце вводять іншу змінну (вектор), яка має покращити значення цільової функції. Аналогічна операція здійснюється і в алгоритмі методу потенціалів.
Перехід від одного опорного плану до іншого виконують заповненням клітинки, для якої порушено умову оптимальності. Якщо таких клітинок кілька, то для заповнення вибирають таку, що має найбільше порушення, тобто .
4.4. Побудова циклу і перехід до наступного опорного плану. Вибрана порожня клітина разом з іншими заповненими становить , отже, з цих клітин обов’язково утвориться цикл (теореми та наслідок § 5.2). У межах даного циклу здійснюють перерахування, які приводять до перерозподілу постачань продукції. Кожній вершині циклу приписують певний знак, причому вільній клітинці — знак «+», а всім іншим — за черговістю знаки «–» та «+». У клітинках зі знаком «–» вибирають значення q і переносять його у порожню клітинку. Одночасно це число додають до відповідних чисел, які містяться в клітинках зі знаком «+», та віднімають від чисел, що позначені знаком «–». Якщо значенню q відповідає кілька однакових перевезень, то при відніманні залишаємо у відповідних клітинках нульові величини перевезень у такій кількості, що дає змогу зберегти невиродженість опорного плану.
Внаслідок наведеного правила вибору q дістаємо новий опорний план, який не містить від’ємних перевезень і задовольняє умови транспортної задачі. Оскільки кількість всіх клітин таблиці, що входять у цикл, є парною і до половини з них те саме число q додається, а від половини віднімається, то загальна сума перевезень по всіх колонках і рядках залишається незмінною.
2. Ручнее розв»язання задачы за вихыдними даними Л.Р. №5
Вартість доставки одиниці вантажу з кожного пункту відправлення у відповідні пункти призначення задана матрицею тарифів
1
2
3
4
Запаси

1
10
9
7
5
185

2
3
4
6
8
135

3
10
12
14
3
150

Потреби
230
120
70
50



Перевіримо необхідна і достатня умова розв'язання задачі.
?a = 185 + 135 + 150 = 470
?b = 230 + 120 + 70 + 50 = 470
Занесемо вихідні дані в розподільну таблицю.
1
2
3
4
Запаси

1
10
9
7
5
185

2
3
4
6
8
135

3
10
12
14
3
150

Потреби
230
120
70
50



Етап I. Пошук перший опорного плану.
1. Використовуючи метод північно-західного кута, побудуємо перший опорний план транспортної задачі.
1
2
3
4
Запаси

1
10[185]
9
7
5
185

2
3[45]
4[90]
6
8
135

3
10
12[30]
14[70]
3[50]
150

Потреби
230
120
70
50



У результаті отриманий перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.
2. Підрахуємо число зайнятих клітин таблиці, їх 6, а має бути m + n - 1 = 6. Отже, опорний план є невиродженим.
Значення цільової функції для цього опорного плану одно:
F(x) = 9*115 + 7*70 + 3*130 + 4*5 + 10*100 + 3*50 = 3085
Етап II. Поліпшення опорного плану.
Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин, для яких ui + vi > cij
Вибираємо максимальну оцінку вільної клітини (1;3): 0
Для цього в перспективну клітку (1;3) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-».
Цикл наведено в таблиці (1,3; 1,1; 2,1; 2,2; 3,2; 3,3; ).
З вантажів хij стоять у мінусових клітинах, вибираємо найменше, тобто у = min (3, 3) = 70. Додаємо 66 до обсягів вантажів, що стоять у плюсових клітинах і віднімаємо 66 з Хij, стоять у мінусових клітинах. У результаті отримаємо новий опорний план.
1
2
3
4
Запаси

1
10[115]
9
7[70]
5
185

2
3[115]
4[20]
6
8
135

3
10
12[100]
14
3[50]
150

Потреби
230
120
70
50



Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин, для яких ui + vi > cij
Вибираємо максимальну оцінку вільної клітини (1;4): 0
Для цього в перспективну клітку (1;4) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-».
Цикл наведено в таблиці (1,4; 1,1; 2,1; 2,2; 3,2; 3,4; ).
З вантажів хij стоять у мінусових клітинах, вибираємо найменше, тобто у = min (2, 2) = 20. Додаємо 16 до обсягів вантажів, що стоять у плюсових клітинах і віднімаємо 16 з Хij, стоять у мінусових клітинах. У результаті отримаємо новий опорний план.
1
2
3
4
Запаси

1
10[95]
9[20]
7[70]
5
185

2
3[135]
4
6
8
135

3
10
12[100]
14
3[50]
150

Потреби
230
120
70
50



Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин, для яких ui + vi > cij
Вибираємо максимальну оцінку вільної клітини (3;1): 0
Для цього в перспективну клітку (3;1) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-».
Цикл наведено в таблиці (3,1; 3,4; 1,4; 1,1; ).
З вантажів хij стоять у мінусових клітинах, вибираємо найменше, тобто у = min (3, 4) = 10. Додаємо 10 до обсягів вантажів, що стоять у плюсових клітинах і віднімаємо 30 з Хij, стоять у мінусових клітинах. У результаті отримаємо новий опорний план.
1
2
3
4
Запаси

1
10
9[115]
7[70]
5
185

2
3[135]
4
6
8
135

3
10[95]
12[5]
14
3[50]
150

Потреби
230
120
70
50



Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин, для яких ui + vi > cij
Вибираємо максимальну оцінку вільної клітини (1;2): 0
Для цього в перспективну клітку (1;2) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-».
Цикл наведено в таблиці (1,2; 1,1; 3,1; 3,2; ).
З вантажів хij стоять у мінусових клітинах, вибираємо найменше, тобто у = min (1, 1) = 95. Додаємо 69 до обсягів вантажів, що стоять у плюсових клітинах і віднімаємо 69 з Хij, стоять у мінусових клітинах. У результаті отримаємо новий опорний план.
1
2
3
4
Запаси

1
10
9[115]
7[70]
5
185

2
3[135]
4
6
8
135

3
10[95]
12[5]
14
3[50]
150

Потреби
230
120
70
50



Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин, для яких ui + vi > cij
Вибираємо максимальну оцінку вільної клітини (2;3): 0
Для цього в перспективну клітку (2;3) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-».
Цикл наведено в таблиці (2,3; 2,1; 3,1; 3,2; 1,2; 1,3; ).
З вантажів хij стоять у мінусових клітинах, вибираємо найменше, тобто у = min (3, 2) = 5. Додаємо 47 до обсягів вантажів, що стоять у плюсових клітинах і віднімаємо 47 з Хij, стоять у мінусових клітинах. У результаті отримаємо новий опорний план.
1
2
3
4
Запаси

1
10[177]
9
7
5
177

2
3[53]
4[74
6
8
127

3
10
12[38]
14[62]
3[42]
142

Потреби
230
112
62
42



Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план є оптимальним, оскільки всі оцінки вільних клітин задовольняють умові ui + vi <= cij.
Мінімальні витрати складуть:
F(x) = 9*115 + 7*70 + 3*130 + 4*5 + 10*100 + 3*50 = 3085