Методические указания по решению транспортной задачи
В общем виде транспортную задачу можно сформулировать следующим образом: в m пунктах отправления A1, …, Am находится однородный груз, количество которого равно соответственно a1, …, am единиц. Данный груз необходимо доставить потребителям B1, …Bn, спрос которых – b1, …bn. Стоимость перевозки единицы груза из i-го ( 
) пункта отправления в j-й ( 
) пункт назначения равен сij. Необходимо составить план перевозок, который полностью удовлетворяет спрос потребителей в грузе, и при этом суммарные транспортные издержки минимальны.
Математически транспортную задачу можно записать так:
(5.1.)
(5.2)
(5.3)
Таким образом, даны система ограничений (5.2) при условии (5.3) и линейная функция (5.1). Требуется среди множества решений системы (5.2) найти такое неотрицательное решение, которое доставляет минимум линейной функции (5.1).
Модель транспортной задачи называют закрытой (сбалансированной), если суммарный объем груза, имеющегося у поставщика равен спросу потребителей, т.е. выполняется равенство:
Если для транспортной задачи выполняется одно из условий:
то модель задачи называют открытой (несбалансированной).
Для разрешимости транспортную задачу с открытой моделью следует преобразовать в закрытую.
Если выполняется условие 
, то необходимо ввести фиктивный (n+1) –й пункт назначения Bn+1, т.е. в матрицу задачи вводится дополнительный столбец. Спрос фиктивного потребителя принимается равным 
. Стоимость перевозок продукции полагается одинаковой, чаще всего равной нулю (если не задана стоимость складирования продукции), т.е. 
.
Если выполняется условие 
, то необходимо ввести фиктивного (m+1)-го поставщика Am+1, т.е. в матрицу задачи вводится дополнительная строка. Запас груза данного поставщика принимается равным 
. Стоимость перевозок продукции полагается одинаковой, чаще всего равной нулю (если не задана стоимость штрафов за недопоставку продукции), т.е. 
.
При преобразовании открытой задачи в закрытую целевая функция не меняется, т.к. все слагаемые, соответствующие дополнительным перевозкам, равны нулю.
F Пример.Производство продукции осуществляется на 4-х предприятиях, а затем развозится в 5 пунктов потребления. Предприятия могут выпускать в день 235, 175, 185 и 175 единиц продукции. Пункты потребления готовы принимать ежедневно 125, 160, 60, 250 и 175 единиц продукции. Хранение на предприятии единицы продукции обходится в 2 у.е. в день, штраф за недопоставленную продукцию – 3,5 у.е. в день. Стоимость перевозки единицы продукции (в у.е.) с предприятий в пункты потребления приведена в таблице 5.1.
Таблица 5.1