Решение транспортной задачи

Теоретические основы

В общем виде транспортную задачуможно сформулировать следующим образом: в m пунктах отправления A₁, …, A_m находится однородный груз, количество которого равно соответственно a₁, …, a_m единиц. Данный груз необходимо доставить потребителям B₁, …B_n, спрос которых – b₁,…b_n. Стоимость перевозки единицы груза из i-го () пункта отправления в j-й () пункт назначения равен с_ij. Необходимо составить план перевозок, который полностью удовлетворяет спрос потребителей в грузе, и при этом суммарные транспортные издержки минимальны.

Математически транспортную задачу можно записать так:

Таким образом, даны система ограничений (2) при условии (3) и линейная функция (1). Требуется среди множества решений системы (2) найти такое неотрицательное решение, которое доставляет минимум линейной функции (1).

Модель транспортной задачи называют закрытой (сбалансированной), если суммарный объем груза, имеющегося у поставщика, равен спросу потребителей, т.е. выполняется равенство:

.

Если для транспортной задачи выполняется одно из условий:

,

то модель задачи называют открытой (несбалансированной).

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

Если выполняется условие , то необходимо ввести фиктивный (n+1) –й пункт назначения B_n+1,т.е. в матрицу задачи вводится дополнительный столбец. Спрос фиктивного потребителя принимается равным . Стоимость перевозок продукции полагается одинаковой, чаще всего равной нулю (если не задана стоимость складирования продукции), т.е. .

Если выполняется условие , то необходимо ввести фиктивного (m+1)-го поставщика A_m+1,т.е. в матрицу задачи вводится дополнительная строка. Запас груза данного поставщика принимается равным . Стоимость перевозок продукции полагается одинаковой, чаще всего равной нулю (если не задана стоимость штрафов за недопоставку продукции), т.е. .

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