Транспортная задача. Метод потенциалов

- Пропустить и перейти к материалам
- Пропустить и перейти к главной навигации
- Пропустить и перейти к первому столбцу
- Пропустить и перейти ко второму столбцу

# Библиотека учебных материалов

для студентов

Home Примеры решения задач Линейное программирование Транспортная задача. Метод потенциалов

## Транспортная задача. Метод потенциалов

Транспортная задача. Метод потенциалов
Розв’язати методом потенціалів транспортну задачу:

| 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