2.2 АЛГОРИТМЫ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ
должна быть известна стоимость перевозки единицы продукта из каждого пункта производства в пункт назначения;
запас продуктов в каждом пункте производства должен быть известен;
потребности в продуктах в каждом пункте производства должны быть известны;
общее предложение должно быть равно общему спросу, то есть задача должна быть транспортной.
Задача 1 не являлась транспортной как раз по тому, что не удовлетворяла предпосылке 4).
Тем не менее,можно ввести фиктивный завод, потребность которого определяется разностью между общим предложением и общим спросом. Потребность фиктивного завода по данным задачи 2.1 составила бы (11 500 — 8500) = 3000 бутылок. Любые продукты, которые подлежат распределению в фиктивный пункт назначения, на деле не вывозятся из пункта производства. В случае, если общее предложение меньше общего спроса, поступают аналогичным образом, то есть в модель вводится фиктивный поставщик, максимальный объем поставок которого равен величине неудовлетворенного спроса. Количество товаров, вывозимых из фиктивного пункта производства, характеризует величину недостающих поставок.
Алгоритм решения транспортной задачи состоит из четырех этапов:
Этап 1. Представление данных в форме стандартной таблицы и поиск любого допустимого распределения перевозок. Допустимым называется такое распределение перевозок, которое позволяет удовлетворить весь спрос в пунктах назначения и вывезти весь запас продуктов из пунктов производства.
Этап 2. Проверка полученного распределения перевозок на оптимальность.
Этап 3. Если полученное распределение перевозок не является оптимальным, то ресурсы перераспределяются, снижая стоимость транспортировки.
Этап 4. Повторная проверка оптимальности полученного распределения перевозок.
Данный итеративный процесс повторяется до тех пор, пока не будет получено оптимальное решение.