Свойства транспортной задачи

Постановка и основные свойства транспортной задачи

 

Транспортная задача (Т-задача) является одной из наиболее распространенных специальных задач ЛП. Частные постановки задачи рассмотрены рядом специалистов по транспорту, например О.Н. Толстым [18; 59].

Первая строгая постановка Т-задачи принадлежит Ф. Хичкоку, поэтому в зарубежной литературе ее называют проблемой Хичкока.

Первый точный метод решения Т-задачи разработан Л.В. Канторовичем и М.К. Гавуриным.

Постановка Т-задачи. Пусть в пунктах А₁,…,A_m производят некоторый однородный продукт, причем объем производства в пункте A_i составляет a_i единиц, i = 1,…, m. Допустим, что данный продукт потребляют в пунктах B₁., B_n, a объем потребления в пункте В_j составляет b_j одиниць j = 1., n. Предположим, что из каждого пункта производства возможно транспортировка продукта в любой пунктпотребления. Транспортные издержки по перевозке единицы продукции из пункта A_i в пункт В_j равны c_ij (i = 1., m; j = 1., n). Задача состоит в определении такого плана перевозок, при котором запросы всех потребителей В_j полностью удовлетворены, весь продукт из пунктов производства вывезен и суммарные транспортные издержки минимальны.

Условия Т-задачи удобно представить в виде табл. 1.1.

Таблица. 1.1.

Пункт потребления Пункт производства	B1	B2	.	Bn	Bj ai
A1	C11	C12	.	C1n	a1
A2	C21	C22	.	C2n	a2
Am	Cm1	Cm2	.	Cmn	am
Ai bj	b1	b2	.	bn	Объем производства Объем потребления

Пусть количество продукта, перевозимого из пункта A_i в пункт В_j.

Требуется определить множество переменных , i = 1., m, j = 1., n, удовлетворяющих условиям

 

 (1.1)

 (1.2)

 

и таких, что целевая функция

 

 (1.3)

 

достигает минимального значения.

Условие (1.1) гарантирует полный вывоз продукта из всех пунктов производства, а (1.2) означает полное удовлетворение спроса во всех пунктах потребления.

Таким образом, Т-задача представляет собой задачу ЛП с числом переменных, и (m + n) числом ограничений равенств.

Переменные удобно задавать в виде матрицы

 

 (1.4)

 

Матрицу X, удовлетворяющую условиям Т-задачи (1.1) и (1.2) называют планом перевозок, а переменные – перевозками. План , при котором целевая функция минимальна, называется оптимальным, а матрица С= – матрицей транспортных затрат.

Графический способ задания Т-задач показан на рис. 1

 

Рис. 1

 

Отрезок A_iB_j называют коммуникацией. На всех коммуникациях ставят величины перевозок x_ij.

Вектор P_ij, компоненты которого состоят из коэффициентов при переменных x_ij в ограничениях (3.1.1) и (3.1.2), называют вектором коммуникаций:

 

 

Вводят также вектор производства-потребления P₀, где

 

.

 

Тогда ограничение (3.1.1) и (3.1.2) можно записать в векторной форме

 

, (1.5)

 

Свойства транспортной задачи

1. Для разрешимости Т-задачи необходимо и достаточно, чтобы выполнялось условие баланса

 

, (1.6)

 

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

Доказательство. Пусть переменные x_ij, i = 1., m; j = 1., n удовлетворяют условиям (1.1), (1.2). Суммируя (1.1) по , а (1.2) по , получим:

 

.я

 

Отсюда , что и доказывает необходимость условия баланса Т-задачи.

Пусть справедливо условие (1.6). Обозначим , где .

Нетрудно доказать, что х_ij составляет план задачи. Действительно

 

 

Таким образом, доказана достаточность условия баланса для решения Т-задачи.

2. Ранг системы ограничений (1.1), (1.2) равен

Доказательство. Так как количество уравнений (1.1), (1.2) равно , то ранг этой системы . Пусть, набор удовлетворяет всем уравнениям, кроме первых. Покажем, что он удовлетворяет также и первому уравнению.

Очевидно

 

 

Так как

 

_, то

_, отсюда

,

 

Учитывая условие баланса (1.6), получим

 

,

 

т.е. первое уравнение системы (1.1) тоже удовлетворяется.

Таким образом, ранг системы уравнений (1.1), (1.2) .

Докажем, что ранг системы уравнений (1.1), (1.2) равен точно . Для этого составим матрицу из первых ( ) компонентов векторов

 

Очевидно, что эта матрица не вырождена. Поэтому векторы { } образуют базис. Так как базис системы состоит из ( ) векторов, то и ранг системы (1.1), (1.2) .

Двойственная транспортная задача ( – задача). Для Т-задачи, как и для любой задачи ЛП, существует двойственная задача к ней -задача.

Переменные -задачи обозначим v₁, v ₂., v _n, – u₁, – u₂., – u_m…

Теорема 1. -задача имеет решение и если X_опт = ,

– оптимальные решения T и -задачи соответственно, то

 

. (1.7)

 

Если учесть, что u_i – стоимость единицы продукции в пункте А_і, а v_j – стоимость после перевозки в пункт B_j, то смысл теоремы будет такой:

Суммарные транспортные расходы при оптимальном плане перевозок равны приращению суммарной стоимости продукции после ее перевозки в пункты потребления.

Переменные u_iиv_j называют потенциалами пунктов A_iиB_j для Т-задачи.

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

Справедливость теоремы 1. следует из основной теоремы двойственной ЛП (теорема 2.5).

Сформулируем необходимые и достаточные условия оптимальности плана Т-задачи.

Теорема 2. Для оптимальности плана Х₀ Т-задачи необходимо и достаточно существование таких чисел v₁, v₂., v_n, – u₁, – u₂., – u_m, что

 

v_j – u_i c_ij, i = 1., m; j=1., n… (1.8)

 

При этом, если

 

это v_j – u_i = c_ij.

 

Cправедливость этой теоремы вытекает из общих идей теории двойственности линейного программирования (в частности, теоремы 2.5, 2.7).

Дадим экономическую интерпретацию условий теоремы 2.

Разность между потенциалами пунктов B_jиA_i, т.е. величину v_j – u_i, можно рассматривать как приращение ценности единицы продукции при перевозке из пункта A_i в пункт B_j. Поэтому, если v_j – u_i < c_ij, то перевозка по коммуникации A_i B_j нерентабельна, и . Если v_j – u_i = c_ij, то такая перевозка рентабельна, и (см. Теорему 2.7).