10.6.5. Метод потенціалів оптимізації опорного плану.
Якщо
план
транспортної задачі оптимальний, то
йому відповідає система із
чисел
та
,
що задовольняють умовам:
1)
,
для
;
2)
,
для
[10.8]
Числа та називаються потенціалами відповідно постачальників і споживачів.
Якщо хоч би одна не занята клітинка не задовольняє [10.8], то опорний план не оптимальний і його можна покращити, введенням в цю клітинку перевозку.
За первісний приймемо план одержаний методом найменшої вартості:
Так
як маємо лише 7 заповнених комірок
таблиці (
),
то план являється виродженим – рівнянь
на одне менше, ніж невідомих. Тому придамо
перевозці
нульове значення.
Приймемо
і по заштрихованим коміркам проведемо
розрахунок значень потенціалів:
Після
перевірки умови
у вільних комірках опинилися з порушенням
умови клітинки
Тому включимо в базис комірку
,
в якій таке порушення найбільше, тобто
в цю клітинку потрібно зробити занятою
перевозкою. Для цього будуємо цикл
(позначено пунктирною лінією). Із комірок,
де стоять знаки «мінус» вибираємо
найменше
.
В комірку внесемо нульову перевозку. Подальші перетворення таблиць подаються без коментарів.
.
.
Одержали
оптимальний базис
.
Одержання розв’язку транспортної задачі в ЕТ Excel здійснюється по тій же технології, що і для симплекс-методу.
ПРИКЛАД
Варіанти транспортної задачі
№ вар |
Запаси |
Споживання |
Вартості перевозок |
||||||||||||||||
З1 |
З2 |
З3 |
С1 |
С2 |
С3 |
С4 |
В11 |
В12 |
В13 |
В14 |
В21 |
В22 |
В23 |
В24 |
В31 |
В32 |
В33 |
В34 |
|
1 |
300 |
400 |
300 |
100 |
200 |
300 |
400 |
1 |
2 |
3 |
7 |
12 |
8 |
4 |
2 |
1 |
5 |
2 |
4 |
2 |
300 |
200 |
500 |
400 |
300 |
200 |
100 |
7 |
2 |
4 |
3 |
2 |
1 |
5 |
2 |
4 |
3 |
1 |
2 |
3 |
200 |
400 |
400 |
100 |
200 |
400 |
300 |
8 |
12 |
3 |
4 |
2 |
1 |
3 |
2 |
5 |
7 |
10 |
6 |
4 |
250 |
350 |
400 |
150 |
200 |
250 |
400 |
2 |
7 |
3 |
2 |
1 |
8 |
5 |
10 |
12 |
6 |
7 |
5 |
5 |
450 |
150 |
400 |
280 |
120 |
350 |
250 |
7 |
6 |
4 |
2 |
15 |
8 |
2 |
5 |
4 |
12 |
8 |
7 |
6 |
280 |
220 |
500 |
300 |
200 |
250 |
250 |
2 |
4 |
3 |
2 |
1 |
7 |
5 |
4 |
3 |
2 |
7 |
6 |
7 |
480 |
120 |
400 |
250 |
250 |
250 |
250 |
8 |
7 |
6 |
5 |
2 |
4 |
3 |
1 |
4 |
5 |
7 |
6 |
8 |
270 |
230 |
500 |
170 |
330 |
200 |
300 |
7 |
8 |
2 |
4 |
3 |
4 |
5 |
7 |
4 |
3 |
2 |
8 |
9 |
190 |
210 |
600 |
150 |
450 |
150 |
250 |
8 |
7 |
2 |
1 |
3 |
4 |
8 |
7 |
12 |
3 |
15 |
2 |
10 |
210 |
590 |
200 |
280 |
220 |
200 |
300 |
7 |
8 |
9 |
12 |
14 |
2 |
4 |
7 |
5 |
2 |
1 |
5 |
11 |
450 |
350 |
200 |
180 |
220 |
250 |
350 |
8 |
9 |
7 |
6 |
4 |
1 |
2 |
4 |
8 |
9 |
10 |
7 |
12 |
700 |
100 |
200 |
350 |
400 |
100 |
150 |
2 |
7 |
4 |
2 |
1 |
5 |
4 |
3 |
7 |
9 |
12 |
5 |
13 |
800 |
100 |
100 |
400 |
350 |
150 |
100 |
5 |
6 |
7 |
8 |
2 |
4 |
5 |
8 |
2 |
1 |
5 |
10 |
14 |
750 |
50 |
200 |
300 |
300 |
300 |
100 |
7 |
2 |
4 |
5 |
7 |
8 |
9 |
12 |
5 |
4 |
3 |
5 |
15 |
250 |
250 |
500 |
600 |
150 |
150 |
100 |
2 |
4 |
7 |
8 |
4 |
5 |
2 |
1 |
3 |
5 |
7 |
6 |
16 |
150 |
100 |
750 |
200 |
200 |
300 |
300 |
7 |
8 |
2 |
1 |
4 |
3 |
7 |
2 |
5 |
4 |
3 |
9 |
17 |
200 |
300 |
500 |
100 |
200 |
400 |
300 |
8 |
9 |
7 |
4 |
5 |
2 |
1 |
4 |
5 |
6 |
7 |
9 |
18 |
800 |
100 |
100 |
150 |
350 |
100 |
400 |
7 |
8 |
9 |
5 |
3 |
4 |
7 |
6 |
1 |
5 |
4 |
3 |
19 |
700 |
50 |
250 |
110 |
490 |
100 |
300 |
5 |
7 |
9 |
2 |
1 |
4 |
8 |
7 |
5 |
6 |
2 |
4 |
20 |
280 |
320 |
400 |
250 |
250 |
400 |
100 |
4 |
5 |
6 |
8 |
7 |
3 |
4 |
9 |
2 |
1 |
5 |
7 |
21 |
480 |
220 |
300 |
150 |
250 |
350 |
250 |
5 |
9 |
2 |
4 |
5 |
6 |
7 |
9 |
2 |
1 |
5 |
7 |
22 |
550 |
150 |
300 |
250 |
350 |
200 |
200 |
9 |
8 |
7 |
4 |
5 |
6 |
8 |
7 |
5 |
3 |
2 |
1 |
23 |
650 |
200 |
150 |
300 |
300 |
300 |
100 |
8 |
7 |
6 |
9 |
10 |
14 |
12 |
7 |
5 |
4 |
6 |
7 |
24 |
120 |
580 |
300 |
100 |
200 |
300 |
400 |
5 |
7 |
2 |
5 |
4 |
7 |
9 |
12 |
9 |
3 |
7 |
5 |
25 |
170 |
430 |
400 |
150 |
350 |
250 |
250 |
6 |
7 |
3 |
4 |
8 |
9 |
5 |
4 |
3 |
7 |
6 |
5 |