Транспортная задача по критерию издержек

Постановка задачи: На m станциях отправления А₁, А₂,..., А_i,..., А_m имеется a₁, а₂,..., а_i,..., а_m единиц однородного груза соответственно. Этот груз необходимо перевезти n потребителям В₁, В₂,..., В_j,..., B_n в количествах, соответственно равных b₁, b₂,..., b_j,..., b_n. Известны величины С_ij, характеризующие затраты по перевозке единицы груза из пункта А_i в пункт B_j. Требуется определить оптимальный план перевозок, при котором минимизируются общие суммарные затраты на перевозки.

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

Пусть x_ij – объём перевозки груза из пункта А_i в пункт B_j (от i-гo поставщика до j-гo потребителя), тогда

; (4.26)

; (4.27)

;

(4.28)

Система ограничений (4.26) характеризует ограничения по ресурсам, (4.27) – ограничения по потребностям.

Составим таблицу для решения данной задачи (таблица 4.2).

А1	b2 B2 B1	b1		bj Bj	Bn	bn
а1	x11 x12 C11	C12	x1i	C1j	x1n	C1n
А2 а2 x21	x22 C12	C22	x2j	C2j	x2n	C2n
Аi
аi	xi2 xi1 Ci1	Ci2		xij Cij	xin	Cin
Аm
аm	xm2 xm1 Cm1	Cm2		xmj Cmj	xmi	Cmn

Если для задачи (4.26) – (4.28) выполнено условие баланса

(4.29)

то транспортная задача называется закрытой.

Если условие баланса не выполняется, то задача называется открытой. Задача приводится к закрытой введением фиктивного поставщика с мощностью (если ) или фиктивного потребителя со спросом (если ). Для фиктивного поставщика или потребителя С_ij = 0.

Необходимое и достаточное условие для разрешимости задачи сводится к выполнению условия баланса (4.29).

Исходный опорный план можно найти по методу северо-западного угла или минимального элемента. Невырожденный план задачи содержит (m + n – 1) базисных переменных, которым соответствуют занятые клетки в таблице решения. Решение задачи обычно находится по методу потенциалов, который основывается на следующей теореме.

Теорема о потенциалах. Если план х* = (х_ij*) транспортной задачи (4.26) – (4.28) является оптимальным, то ему соответствует система из (m + n) чисел U_i* и V_j*, удовлетворяющих условиям:

1) U_i* + V_j* = С_ij, для х_ij* > 0; (4.30)

2) U_i* + V_j* ≤ С_ij, для х_ij* = 0; (4.31)

Из условия (3.31) получается, что в оптимальном плане для свободных клеток E_ij = С_ij – (U_i* + V_j*) ≥ 0. Числа E_ij называются характеристиками свободных клеток (i, j). E_ij показывает, насколько изменится значение целевой функции при перемещении в клетку (i, j) единицы груза. Если в оптимальном плане для свободных клеток E_ij = 0, то оптимальный план не единственный.