Примеры --- Линейное программирование --- Транспортная задача (метод потенциалов)
Розв’язати методом потенціалів транспортну задачу:
|
|
Q1 |
Q2 |
Q3 |
Q4 |
Q5 |
a |
|
P1 |
6 |
1 |
7 |
3 |
3 |
20 |
|
P2 |
7 |
4 |
4 |
8 |
4 |
90 |
|
P3 |
8 |
2 |
3 |
5 |
7 |
80 |
|
P4 |
3 |
4 |
2 |
8 |
5 |
60 |
|
b |
70 |
40 |
30 |
60 |
50 |
|
Розв'язок
Так як 70+40+30+60+50=20+90+80+60, то маємо закриту Т-задачу, отже фіктивних пунктів вводити не треба
Побудуємо опорний план задачі методом найменшого елементу
|
|
Q1 |
Q2 |
Q3 |
Q4 |
Q5 |
A |
|
P1 |
6
|
1 20 |
7
|
3
|
3 |
20 |
|
P2 |
7 40 |
4 |
4 |
8 |
4 50 |
90 |
|
P3 |
8 |
2 20 |
3 |
5 60 |
7 |
80 |
|
P4 |
3 30 |
4 |
2 30 |
8 |
5 |
60 |
|
b |
70 |
40 |
30 |
60 |
50 |
|
Кількість
заповнених клітин 7<5+4-1, отже опорний план вироджений, тому
треба вводити додатову фіктивну перевозку. Введемо її у клітину 
.
Приймемо потенціал 
рівним 0 і на основі
цього розставимо потенціали всіх рядків та стопців, а також розставимо
псевдовартості кожної клітини
|
|
Q1 |
Q2 |
Q3 |
Q4 |
Q5 |
A |
|
|
P1 |
3 6
|
1 1 20 |
2 7
|
4 3
|
0 3 |
20 |
-4 |
|
P2 |
7 7 40 |
5 4
|
6 4
|
8 8 |
4 4 50 |
90 |
0 |
|
P3 |
4 8 |
2 2 20 |
3 3
|
5 5 60 |
1 7 |
80+ε |
-3 |
|
P4 |
3 3 30 |
1 4 |
2 2 30-ε |
4 8 |
0 5 |
60-ε |
-4 |
|
b |
70 |
40 |
30 |
60 |
50 |
|
|
|
|
7 |
5 |
6 |
8 |
4 |
|
|
Вартість перевезень 20*1+40*7+50*4+20*2+60*5+30*3+30*2=990
Маємо
три клітини з від'ємною ціною циклу. Побудуемо цикл 
. Зменшення
вартості 20*1=20. Після переміщення 20 одиниць вантажу по циклу отримаємо
|
|
Q1 |
Q2 |
Q3 |
Q4 |
Q5 |
A |
|
|
P1 |
2 6
|
0 1
|
1 7
|
3 3 20 |
-1 3 |
20 |
-2 |
|
P2 |
7 7 40 |
5 4
|
6 4
|
8 8 |
4 4 50 |
90 |
3 |
|
P3 |
4 8 |
2 2 40 |
3 3
|
5 5 40 |
1 7 |
80+ε |
0 |
|
P4 |
3 3 30 |
1 4 |
2 2 30-ε |
4 8 |
0 5 |
60-ε |
-1 |
|
b |
70 |
40 |
30 |
60 |
50 |
|
|
|
|
4 |
2 |
3 |
5 |
1 |
|
|
Вартість перевезень 20*3+40*7+50*4+40*2+40*5+30*3+30*2=970
Приймаємо
потенціал 
рівним 0, і
розставлємо потенціали і псевдовартості. Маємо 2 клітини з від'ємною ціною
циклу. Організуємо цикл 
. Зменшення вартості
перевезень 30*2=60. Після переміщення 30-ε одиниць вантажу по циклу отримаємо
|
|
Q1 |
Q2 |
Q3 |
Q4 |
Q5 |
A |
|
|
P1 |
4 6
|
0 1
|
1 7
|
3 3 20 |
1 3 |
20 |
-3 |
|
P2 |
7 7 10+ ε |
3 4
|
4 4 30-ε
|
6 8 |
4 4 50 |
90 |
0 |
|
P3 |
6 8 |
2 2 40 |
3 3
|
5 5 40 |
3 7 |
80+ε |
-1 |
|
P4 |
3 3 60-ε |
-1 4 |
0 2
|
2 8 |
0 5 |
60-ε |
-4 |
|
b |
70 |
40 |
30 |
60 |
50 |
|
|
|
|
7 |
3 |
4 |
6 |
4 |
|
|
Вартість перевезень 20*3+10*7+30*4+50*4+40*2+40*5+60*3=910
Приймаємо
потенціал рівним 0, і розставлємо
потенціали і псевдовартості. Бачимо, що клітини з від'ємною ціною циклу
відсутні, отже отриманий план є оптимальним
Відповідь: 
Вартість 910
