Постановка и основные свойства транспортной задачи (стр. 1 из 7)
Транспортная задача (Т-задача) является одной из наиболее распространенных специальных задач ЛП. Частные постановки задачи рассмотрены рядом специалистов по транспорту, например О.Н. Толстым [18; 59].
Первая строгая постановка Т-задачи принадлежит Ф. Хичкоку, поэтому в зарубежной литературе ее называют проблемой Хичкока.
Первый точный метод решения Т-задачи разработан Л.В. Канторовичем и М.К. Гавуриным.
Постановка Т-задачи. Пусть в пунктах А1,…,Am производят некоторый однородный продукт, причем объем производства в пункте Ai составляет ai единиц, i = 1,…, m. Допустим, что данный продукт потребляют в пунктах B1., Bn, a объем потребления в пункте Вj составляет bj одиниць j = 1., n. Предположим, что из каждого пункта производства возможно транспортировка продукта в любой пунктпотребления. Транспортные издержки по перевозке единицы продукции из пункта Ai в пункт Вj равны cij (i = 1., m; j = 1., n). Задача состоит в определении такого плана перевозок, при котором запросы всех потребителей Вj полностью удовлетворены, весь продукт из пунктов производства вывезен и суммарные транспортные издержки минимальны.
Условия Т-задачи удобно представить в виде табл. 1.1.
Таблица. 1.1.
| Пункт потребленияПункт производства | B1 | B2 | . | Bn | Bjai |
| A1 | C11 | C12 | . | C1n | a1 |
| A2 | C21 | C22 | . | C2n | a2 |
| Am | Cm1 | Cm2 | . | Cmn | am |
| Aibj | b1 | b2 | . | bn | Объем производстваОбъем потребления |
Пусть 
количество продукта, перевозимого из пункта Ai в пункт В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
Отрезок AiBj называют коммуникацией. На всех коммуникациях ставят величины перевозок xij.
Вектор Pij, компоненты которого состоят из коэффициентов при переменных xij в ограничениях (3.1.1) и (3.1.2), называют вектором коммуникаций:
Вводят также вектор производства-потребления P0, где
.
Тогда ограничение (3.1.1) и (3.1.2) можно записать в векторной форме
, (1.5)
Свойства транспортной задачи
1. Для разрешимости Т-задачи необходимо и достаточно, чтобы выполнялось условие баланса
, (1.6)
то есть, чтобы суммарный объем производства равнялся объему потребления.
Доказательство. Пусть переменные xij, 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) .
Двойственная транспортная задача ( 
– задача). Для Т-задачи, как и для любой задачи ЛП, существует двойственная задача к ней -задача.
Переменные -задачи обозначим v1, v 2., v n, – u1, – u2., – um…
Теорема 1. -задача имеет решение и если Xопт = 
,
– оптимальные решения T и -задачи соответственно, то
. (1.7)
Если учесть, что ui – стоимость единицы продукции в пункте Аі, а vj – стоимость после перевозки в пункт Bj, то смысл теоремы будет такой:
Суммарные транспортные расходы при оптимальном плане перевозок равны приращению суммарной стоимости продукции после ее перевозки в пункты потребления.
Переменные uiиvj называют потенциалами пунктов AiиBj для Т-задачи.
Таким образом, теорема 1. утверждает, что при оптимальных решениях значения целевой функции прямой и двойственной Т-задач равны между собой.
Справедливость теоремы 1. следует из основной теоремы двойственной ЛП (теорема 2.5).
Сформулируем необходимые и достаточные условия оптимальности плана Т-задачи.
Теорема 2. Для оптимальности плана Х0 Т-задачи необходимо и достаточно существование таких чисел v1, v2., vn, – u1, – u2., – um, что