Тема 3. Транспортная задача.

Транспортная задача (ТЗ) – одна из распространенных задач линейного программирования. Она возникает при планировании наиболее рациональных перевозок грузов. В одних случаях это означает определение такого плана перевозок, при котором стоимость последних была бы минимальной, в других = более важным является выигрыш во времени.

Первая задача получила название транспортной задачи по критерию стоимости, а вторая – транспортной задачи по критерию времени.

Первая задача является частным случаем ЗЛП и может быть решена симплексным методом. Однако в силу ее особенностей она решается проще.

В общем виде ТЗ можно представить следующим образом:

В m пунктах производства имеется однородный груз в количестве соответственно . Этот груз необходимо доставить в n пунктов назначения в количестве соответственно . Стоимость перевозки груза (тариф) из пункта в пункт равна . Требуется составить план перевозок, позволяющий вывести все грузы и имеющий минимальную стоимость.

В зависимости от соотношения между суммарными запасами груза и суммарными потребностями в нем ТЗ могут быть закрытыми и открытыми.

Если , то ТЗ называется закрытой.

Если , то ТЗ называется открытой.

Обозначим через количество груза, перевозимого из пункта в пункт . Рассмотрим закрытую ТЗ. Ее условия запишем в распределительную таблицу, которую будем использовать для нахождения решения:

Математическая модель закрытой ТЗ имеет вид: min при ограничениях , , .

Оптимальным решением задачи является матрица , удовлетворяющая системе ограничений и доставляющая минимум целевой функции.

Для решения ТЗ разработан специальный метод, имеющий те же этапы, что и симплексный метод, а именно:

• нахождение исходного опорного решения;

• проверка этого решения на оптимальность;

• переход от одного опорного решения к другому.