Задача №2. Транспортная задача линейного программирования

Постановка задачи. Пусть имеется  пунктов производства некоторого однородного продукта и  пунктов его потребления. Известно: запас продукта в каждом пункте-поставщике, спрос в каждом пункте-потребителе и расходы на перевозку единицы груза от каждого отправителя к каждому потребителю. Требуется составить план перевозок продукта от производителей к пунктам назначения, при котором общие транспортные расходы минимальны.

Условные обозначения:

– количество пунктов отправления;

– порядковый номер пункта отправления ;

– количество пунктов потребления;

– порядковый номер пункта потребления ;

– количество единиц груза в -м пункте отправления;

– потребность в единицах груза в -ом пункте назначения;

– расходы на перевозку единицы груза из -го пункта отправления в -й пункт назначения.

– искомый объём перевозки продукта из -го пункта отправления в  -й пункт назначения.

Математическая модель задачи:

, (17)

(18)

. (19)

Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления , т.е.:

, (20)

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

Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления были равны потребностям в грузе в пунктах назначения. Поэтому, приступая к нахождению оптимального плана транспортной задачи, следует проверить выполнение равенства (20).

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

Благодаря особенностям ограничений системы (18) для определения оптимального плана транспортной задачи разработаны специальные методы. Один из них – метод потенциалов. Общий принцип нахождения опти­мального плана транспортной задачи методом потенциалов аналогичен принципу решения задачи линейного программирования симплекс-методом, а именно: сначала строят опорный план транспортной задачи, затем его последовательно улучшают до получения оптимального плана.

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

При построении первого опорного плана составляют таблицу 5.

Таблица 5.

Таблица условий транспортной задачи

Пункты отправления	Пункты назначения					Запасы
		…		…
		…		…
…	…	…	…	…	…	…
		…		…
…	…	…	…	…	…	…
		…		…
Потребности		…		…

Вначале полагают все переменные  равными 0, при этом клетки таблицы условий считаются свободными. После того, как определено значение какой-либо переменной  , оно заносится в соответствующую клетку  , которая теперь будет называться занятой.

Рассматриваемые методы построения первого опорного плана гаран­тируют получение в исходном плане  занятых клеток. Это озна­чает, что опорный план является невырожденным.