Найти оптимальный план транспортной задачи, описываемый соответствующей таблицею, удовлетворяет указанным ниже условиям.
Поставщик (Аi) | Потребитель (Bj) | Запасы | |||
B1 | B2 | B3 | B4 | ||
А1 | |||||
А2 | |||||
А3 | |||||
Потребности | 100/90 |
Общие суммарные затраты, которые связаны с перевозками, можно представить функцией
в нашем случае
Построим функцию :
Переменные отвечают условиям граничным по запасам и потребностям
Дополнительное удовольствие
Наша задача представляет собой открытую модель транспортной задачи. Причем . Для того, чтобы решить эту задачу, введем фиктивного поставщика, дополнительную строку, где , а
Тогда задачи примет вид
Используя метод меньшей цены, найдем опорный план.
Метод наименьшей цены заключается в том, что выбирается из таблицы минимальный за исключением 4 строки, в нашем случаи.
Шаг первый выбираем минимальный элемент. , тогда . В результате запасы 3 поставщика использованы, поэтому исключаем из дальнейшего рассмотрения третью строку., .Получаем новую таблицу:
- | - | - | |||
Шаг второй. Минимальный элемент , тогда , но с учётом условия задачи . Поэтому допустим . , .Получаем новую таблицу:
- | - | - | ||||
Продолжаем таким же образом, находим опорный план:
- | - | |||||||
- | - | |||||||
- | - | - | ||||||
- | - |
ден. ед.
Применяя метод потенциалов, мы можем убедиться, что данный опорный план оптимален.
Для этого нужно вычислить потенциалы , которые удовлетворяют условие
| |||||||||||||
- | - | ||||||||||||
- | - | ||||||||||||
- | - | - | |||||||||||
- | - | ||||||||||||
Для определения потенциалов, мы можем допустить, что один из коэффициентов равен нулю и найти другие.
| |||||||||||||
- | - | ||||||||||||
- | - | ||||||||||||
- | - | - | |||||||||||
- | - | ||||||||||||
Проведем оценку потенциалов по формуле и запишем их в левый угол каждой ячейки.
| ||||||||||||||||
- | - | |||||||||||||||
- | -1 | - | ||||||||||||||
- | - | - | ||||||||||||||
- | -3 | - | ||||||||||||||
Поскольку есть , данное решение не является оптимальным.
Отыскиваем, какую циклическую замену можно произвести:
(4,4) (1,4) (1,2) (2,4). Такая замена приведет к увеличению значение , а это недопустимо, согласно наложенному условию. Поэтому данное решение является оптимальным.
Ответ: