Алгоритм решения транспортной задачи

Задачу, рассмотренную в 4.1, можно решить, используя алгоритм решения транспортной задачи. Применение этого алгоритма требует соблюдения ряда предпосылок:

1. Должна быть известна стоимость перевозки единицы продукта из каждого пункта производства в каждый пункт назначения.

2. Запас продуктов в каждом пункте производства должен быть известен.

3. Потребности в продуктах в каждом пункте потребления должны быть известны.

4. Общее предложение должно быть равно общему спросу.

Приведенная в примере 4.1 задача удовлетворяет условиям 1-3, однако условие 4 для этой задачи не выполняется. Тем не менее, можно ввести фиктивный завод, потребность которого определяется разностью между общим предложением и общим спросом. Потребность фиктивного завода по данным примера 4.1 составила бы (11500-8500) = 3000 бутылок. Любые продукты, которые подлежат распределению в фиктивный пункт назначения, на деле не вывозятся из пункта производства. В случае, если общее предложение меньше общего спроса, поступают аналогичным образом, т.е. в модель вводится фиктивный поставщик, максимальный объем поставок которого равен величине неудовлетворенного спроса. Количество товаров, вывозимых из фиктивного пункта производства, характеризует величину недостающих поставок.

Алгоритм решения транспортной задачи состоит из четырех этапов:

Этап I. Представление данных в форме стандартной таблицы и поиск любого допустимого распределения ресурсов. Допустимым называется такое распределение ресурсов, которое позволяет удовлетворить весь спрос в пунктах назначения и вывезти весь запас продуктов из пунктов производства.

Этап 2. Проверка полученного распределения ресурсов на оптимальность

Этап 3. Если полученное распределение ресурсов не является оптимальным, то ресурсы перераспределяются, снижая стоимость транспортировки.

Этап 4. Повторная проверка оптимальности полученного распределения ресурсов.

Данный итеративный процесс повторяется до тех пор, пока не будет получено оптимальное решение.