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