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

6.1. Математическая постановка задачи

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления (склады) в n пунктов назначения (потребители). При этом в качестве критерия оптимальности обычно принимается минимальная суммарная стоимость перевозок всего запаса грузов ко всем потребителям (либо минимальное время его доставки). Рассмотрим первый вид постановки задачи.

Обозначим через c_ij тарифы перевозки единицы груза из i – го пункта отправления в j – й пункт назначения (рис. 9а), через a_i – запасы груза в i – ом пункте отправления, через b_j - потребность в грузе в j – ом пункте назначения, а через x_ij – количество единиц груза, перевозимого из i –го пункта отправления в j – й пункт назначения (рис.9b).

Рис.9. К обоснованию математической модели транспортной задачи

Тогда математическая постановка задачи состоит в определении минимального значения функции

или → min (i=1…m; j=1…n) (20)

при условиях ,

,

……………………………

или (j=1…n), (21)

а также ,

,

…………………………..

,

или , (i=1…m), (22)

.

О п р е д е л е н и е 1. Всякое неотрицательное решение систем линейных уравнений (21) и (22), определяемое матрицей (i=1…m; j=1…n), называется планом транспортной задачи.

О п р е д е л е н и е 2. План (i=1…m; j=1…n), при котором функция (20) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные транспортной задачи записывают в табличной форме (табл.15).

Таблица 15

Форма записи условий транспортной задачи

Поставщик	Объемы поставок и тарифы по потребителям						Запасы
	В1	В2	…….	Вj	……	Вn
А1	c11 x11	c12 x12	…….	c1j x1j	…….	c1n x1n	a1
А2	c21 x21	c22 x22	…….	c2j x2j	…….	c2n x2n	a2
………	…….	…….	…….	…….	……..	…….	…….
Аi	ci1 xi1	ci2 xi2	…….	cij xij	…….	cin xin	ai
………	…….	…….	…….	…….	…….	…….	…….
Аm	cm1 xm1	cm2 xm2	…….	cmj xmj	…….	cmn xmn	am
Потребность	b1	b2	……	bj	…….	bn	Σ

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

, (23)

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

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

В случае, если запас превышает потребность, т.е.

,

то вводится фиктивный (n+1) –й пункт назначения с потребностью

а соответствующие тарифы считаются равными нулю с_in+1=0 (i=1…m). Аналогично, если запасы меньше потребностей, вводится фиктивный (m+1) –й пункт отправления с запасом груза

и тарифы полагаются равными нулю c_m+1=0 (j=1…n). Так открытая задача сводится к закрытой транспортной задаче.

Как и в производстенной ЗЛП, в транспортной задаче существует множество опорных планов и один из них - оптимальный.

Решение транспортной задачи имеет свои особенности:

- решение задачи начинают с нахождения одного из опорных планов; его

нахождение – самостоятельная проблемная задача (см. ниже);

- план должен быть оценен на предмет подтверждения его оптимальности;

- количество базисных (ненулевых) переменных в опорном плане должно

быть равно (n+m-1). Такой план называется невырожденным. Если их

меньше, то такой план называется вырожденным и оптимизации не под-

лежит, или его надо преобразовать в невырожденный (см. ниже).