Транспортная задача
Задание 1. Есть три поставщика с мощностями a, b,c и пять потребителей (их спрос f,g,h,m,n соответственно). Стоимость доставки единицы груза от каждого поставщика к каждому потребителю задается матрицей 
. Найти оптимальный план поставок.
| a | ||||||||||
| b | ||||||||||
| c | ||||||||||
| f | ||||||||||
| g | ||||||||||
| h | ||||||||||
| m | ||||||||||
| n | ||||||||||
| i | ||||||||||
| p | ||||||||||
| s | ||||||||||
| w | ||||||||||
| x | ||||||||||
| k | ||||||||||
| q | ||||||||||
| t | ||||||||||
| e | ||||||||||
| y | ||||||||||
| l | ||||||||||
| r | ||||||||||
| v | ||||||||||
| d | ||||||||||
| z |
Выполнение работы
Построение первоначального плана перевозок методом «северо-западного угла»
| Поставщик | Потребитель | Запас | ||||
| f1 | g2 | h3 | m4 | n5 | ||
| a1 | ||||||
| b2 | ||||||
| c3 | ||||||
| Потребность |
Стоимость перевозки по этому плану:
z = 24 * 5 + 26 * 5 + 20 * 4 + 20 * 3 + 12 * 6 + 28 * 1 = 490
Построение первоначального плана перевозок методом минимального элемента
| Поставщик | Потребитель | Запас | ||||
| f1 | g2 | h3 | m4 | n5 | ||
| a1 | ||||||
| b2 | ||||||
| c3 | ||||||
| Потребность |
Стоимость перевозки по этому плану:
z = 24 * 5 + 5 * 6 + 20 * 4 + 4 * 8 + 32 * 3 + 28 + 24 = 410
Метод потенциалов
(начальное распределение рассчитано по методу «северо-западного угла»)
| Поставщик | Потребитель | Запас | ||||
| f1 | g2 | h3 | m4 | n5 | ||
| a1 | 26 - | + | u1 = 0 | |||
| b2 | 20 - | 20 + | u2 = 0 | |||
| c3 | + | 12 - | u3 = 3 | |||
| Потребность | v1 = 5 | V2 = 5 | v3 = 4 | V 4 = 3 | v5 = -2 |
Получили новое решение
| Поставщик | Потребитель | Запас | ||||
| f1 | g2 | h3 | m4 | n5 | ||
| a1 | ||||||
| b2 | ||||||
| c3 | ||||||
| Потребность |
Стоимость перевозки по этому плану:
z = 14 * 5 + 12 * 2 + 12 * 4 + 8 * 4 + 32 * 3 = 270 (т.е. меньше, чем было 410)
Проверим, является ли полученное решение оптимальным.
Последовательно найдем значения потенциалов.
| Поставщик | Потребитель | Запас | ||||
| f1 | g2 | h3 | m4 | n5 | ||
| a1 | 24 - | 12 + | u1 = 0 | |||
| b2 | + | 8 - | u2 = -1 | |||
| c3 | u3 = -3 | |||||
| Потребность | v1 = 5 | V2 = 5 | v3 = 4 | V 4 = 4 | v5 = 4 |
Получили новое решение
| Поставщик | Потребитель | Запас | ||||
| f1 | g2 | h3 | m4 | n5 | ||
| a1 | ||||||
| b2 | ||||||
| c3 | ||||||
| Потребность |
Стоимость перевозки по этому плану:
z = 16 * 5 + 14 * 5 + 4 * 20 + 8 * 4 + 32 * 3 + 12 * 2 + 28 * 1 = 410
| Практическая работа № 5 | Фамилия И. О. | Дата | Подпись |
| Работу выполнил: | Студент | ||
| Выполнение на ЭВМ: | Преподаватель | ||
| Ручной счет: | Преподаватель |