3.1 ПОСТАНОВКА И ОСНОВНЫЕ СВОЙСТВА ТРАНСПОРТНОЙ ЗАДАЧИ
Транспортная задача (Т-задача) является одной из наиболее распространенных специальных задач ЛП. Частные постановки задачи рассмотрены рядом специалистов по транспорту, например О. Н. Толстым [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 полностьюудовлетворены, весь продукт из пунктов производства вывезен и суммарные транспортные издержки минимальны.
Условия Т-задачи удобно представить в виде табл. 3.1.
Таблица. 3.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 |
Объем произ- водства Объем |
Пусть 
количество продукта, перевозимого из пункта Ai в пункт Вj .
Требуется определить множество переменных 
, i = 1,..,m , j = 1,..,n , удовлетворяющих условиям
(3.1.1)
(3.1.2)
и таких, что целевая функция
(3.1.3)
достигает минимального значения.
Условие (3.1.1) гарантирует полный вывоз продукта из всех пунктов производства, а (3.1.2) означает полное удовлетворение спроса во всех пунктах потребления.
Таким образом, Т-задача представляет собой задачу ЛП с 
числом переменных, и ( m + n ) числом ограничений равенств.
Переменные удобно задавать в виде матрицы
(3.1.4)
Матрицу X, удовлетворяющую условиям Т-задачи (3.1.1) и (3.1.2) называют планом перевозок, а переменные - перевозками. План 
, при котором целевая функция минимальна, называется оптимальным, а матрица С= 
- матрицей транспортных затрат.
Графический способ задания Т-задач показан на рис. 3.1
Рис. 3.1
Отрезок AiBj называют коммуникацией. На всех коммуникациях ставят величины перевозок xij.
Вектор Pij, компоненты которого состоят из коэффициентов при переменных xij в ограничениях (3.1.1) и (3.1.2), называют вектором коммуникаций:
Вводят также вектор производства-потребления P0, где
.
Тогда ограничение (3.1.1) и (3.1.2) можно записать в векторной форме
, (3.1.5)
Свойства транспортной задачи
1. Для разрешимости Т-задачи необходимо и достаточно, чтобы вяполнялось условие баланса
, (3.1.6)
то есть, чтобы суммарный объем производства равнялся объему потребления.
Доказательство. Пусть переменные xij, i = 1,..,m; j = 1,..,n удовлетворяют условиям (3.1.1), (3.1.2). Суммируя (3.1.1) по 
, а (3.1.2) по 
,получим:
.я
Отсюда , что и доказывает необходимость условия баланса Т-задачи.
Пусть справедливо условие (3.1.6). Обозначим 
, где 
.
Нетрудно доказать, что хij составляет план задачи. Действительно
Таким образом, доказана достаточность условия баланса для решения Т-задачи.
2. Ранг системы ограничений (3.1.1), (3.1.2) равен 
Доказательство. Так как количество уравнений (3.1.1), (3.1.2) равно 
, то ранг этой системы 
. Пусть, набор 
удовлетворяет всем уравнениям, кроме первых. Покажем, что он удовлетворяет также и первому уравнению.
Очевидно
Так как
то
отсюда
,
Учитывая условие баланса (3.1.6), получим
,
т.е. первое уравнение системы (3.1.1) тоже удовлетворяется.
Таким образом, ранг системы уравнений (3.1.1), (3.1.2) 
.
Докажем, что ранг системы уравнений (3.1.1), (3.1.2) равен точно 
. Для этого составим матрицу из первых ( ) компонентов векторов 
Очевидно, что эта матрица не вырождена. Поэтому векторы {
} образуют базис. Так как базис систе-
мы состоит из ( ) векторов, то и ранг системы (3.1.1), (3.1.2) .
Двойственная транспортная задача (
-задача). Для Т-задачи, как и для любой задачи ЛП, существует двойственная задача к ней -задача.
Переменные -задачи обозначим v1, v 2, ., v n, -u1, -u2, ., -um...
Теорема 3.1. -задача имеет решение и если Xопт = 
,
- оптимальные решенияT и -задачи соответственно, то
. (3.1.7)
Если учесть, что ui - стоимость единицы продукции в пункте Аі , а vj - стоимость после перевозки в пункт Bj , то смысл теоремы будет такой:
Суммарные транспортные расходы при оптимальном плане перевозок равны приращению суммарной стоимости продукции после ее перевозки в пункты потребления.
Переменные ui и vj называют потенциалами пунктов Ai и Bj для Т-задачи.
Таким образом, теорема 3.1. утверждает, что при оптимальных решениях значения целевой функции прямой и двойственной Т-задач равны между собой.
Справедливость теоремы 3.1. следует из основной теоремы двойственной ЛП (теорема 2.5).
Сформулируем необходимые и достаточные условия оптимальности плана Т-задачи.
Теорема 3.2. Для оптимальности плана Х0 Т-задачи необходимо и достаточно существование таких чисел v1, v2, ., vn, -u1, -u2, .,-um , что
vj - ui 
cij , i = 1,.,m;j=1,.,n... (3.1.8)
При этом, если
это vj - ui = cij.
Cправедливость этой теоремы вытекает из общих идей теории двойственности линейного программирования (в частности, теоремы 2.5, 2.7).
Дадим экономическую интерпретацию условий теоремы 3.2.
Разность между потенциалами пунктов Bj и Ai , т.е. величину vj - ui , можно рассматривать как приращение ценности единицы продукции при перевозке из пункта Ai в пункт Bj . Поэтому, если vj - ui < cij , то перевозка по коммуникации Ai Bj нерентабельна, и 
. Если vj - ui = cij, то такая перевозка рентабельна, и 
(см. Теорему 2.7).
Транспортная задача с ограниченными пропускными способностями.
Важной в практическом отношении является Тd - задача, в которой существуют ограничения на пропускные способности коммуникаций.
Пусть 
- пропускная способность коммуникации Ai Bj.
Тогда 
(3.1.9)
Т-задача состоит в минимизации Ц.Ф. (3.1.3) при условиях (3.1.1), (3.1.2), (3.1.9). Даже в случае разрешимости Т-задачи, Тd - задача может оказаться неразрешимой, поскольку величины пропускных способностей будут недостаточны для полного вывоза продукта из п. Аі, и полного ввоза продукта в п. Вj. Поэтому для Тd - задачи вводят еще два условия:
(3.1.10)
(3.1.11)
Но и при добавочных условиях (3.1.10), (3.1.11) Тd - задача не всегда разрешима. Для установления совместимости всех условий делают попытку построить любой план Т-задачи. Если удается, то система уравнений (3.1.1), (3.1.2), (3.1.9) - (3.1.11) совместна. В противном случае Тd - задача неразрешима.
Теорема 3.3. Для оптимальности плана Х0 Тd - задачи необходимо и достаточно существование таких чисел v1, v2, ., vn, -u1, -u2, .,-um , при которых
если 
, (3.1.12)
если 0 <
, (3.1.13)
если
. (3.1.14)
Смысл условий оптимальности (3.1.12) - (3.1.14) состоит в следующем:
если приращение стоимости продукта vj - uj меньше транспортных расходов cij , то такая перевозка убыточна, а потому . Если же приращение стоимости продукта vj - uj больше транспортных расходов cij (3.1.14), то эта перевозка прибыльна, а потому ее величина должна быть максимальной, т.е. .
Таким образом, теорема 3.3 по существу выражает принцип рентабельности для Td- задачи.
Открытые транспортные модели. Существует ряд практических задач, в которых условие баланса не выполняется. Такие модели называются открытыми. Возможные два случая:
1)
2)
В первом случае полное удовлетворение спроса невозможно.
Такую задачу можно привести к обычной транспортной задаче следующим образом. Обозначим через 
величину штрафа из-за неудовлетворения запросов на единицу продукта в пункте Bj.
Тогда требуется минимизировать
(3.1.15)
при условиях
где 
- неудовлетворенный спрос.
Задачу (3.1.15) приводят к обычной Т-задаче введением фиктивного пункта производства Аm+1 , с объемом производства 
и транспортными издержками 
В таком случае Т-задача будет иметь вид
минимизировать 
при условиях
В найденном решении хопт полагаем все перевозки из фиктивного пункта Аm+1 равными нулю, т.е. 
.
Рассмотрим теперь второй случай. Введем фиктивный пункт Bn+1 с объемом спроса 
. Пусть 
- это убытки (штраф) в пункте Аі за единицу невывезенного продукта. Обозначим через сии,n+1 = удельные транспортные издержки на перевозку единицы продукта с Аі в Вn+1 . Тогда соответствующая Т-задача запишется так:
минимизировать 
(3.1.16)
при условиях
(3.1.17)-(3.1.18)
В найденном решении 
все перевозки 
в фиктивный пункт Вn+1 считают равными нулю.
Опорные планы Т-задачи
Опорным (базисным) планом Т-задачи называют любое ее допустимое, базисное решение. Понятие опорного плана имеет наглядную геометрическую интерпретацию.
Последовательность коммуникаций
(3.1.19)
называют маршрутом, соединяющим пункты 
( рис. 3.2 ).
. . . 
 |
|||
 |
|||
. 
Рис. 3.2
Используя маршрут, составленный из коммуникаций, можно осуществить перевозку продукта из пункта 
в пункт 
, проходя через пункты 
.
В процессе этого движения коммуникации, стоящие на четных местах в (3.1.19), будут пройдены в противоположном направлении.
Маршрут (3.1.19), к которому добавлена коммуникация 
называется замкнутым маршрутом или циклом.
Способ проверки произвольного плана Т-задачи на опорность, основан на следующих двух теоремах (прямой и обратной).
Теорема 3.4. Система, составленная из векторов 
Т-задачи, является линейно независимой тогда и только тогда, когда из коммуникаций, соответствующих этим векторам, нельзя составить замкнутый маршрут.
Доказательство. Необходимость. Пусть векторы 
линейно независимы. Если бы существовал замкнутый маршрут из коммуникаций 
и , то, очевидно, начиная движение из пункта и последовательно проходя все пункты 
по последней коммуникации 
мы вернемся в начальный пункт . Тогда справедливое равенство
(3.1.20)
которое указывает на линейную зависимость векторов
.
Полученное противоречие доказывает необходимость условий теоремы 3.4.
Достаточность. Допустим, что из коммуникаций, отвечающих векторам 
системы R, нельзя составить замкнутый маршрут. Докажем, что в таком случае R - линейно независимая система. Если предположить противное, т.е. линейную зависимость векторов системы R, то существуют такие числа 
, среди которых не все нули, для которых выполняется условие
. (3.1.21)
Пусть, например 
. Перенесем тогда соответствующий вектор вправо и получим
, (3.1.22)
где Е1 образуется вычеркиванием в Е пары индексов (
). Компонента с номером 
в правой части ( 3.1.22 ) не равна нулю.
Следовательно, это же относится и к левой части этого равенства, т.е. среди
векторов 
найдется хотя бы один вектор вида 
с
коэффициентом 
. Перенеся его в правую чатсть равенства (3.1.22), получим
, (3.1.23)
где 
. Но поскольку 
, компонента с номером 
правой части (3.1.23) отлична от нуля. Поэтому среди векторов левой части (3.1.23) найдется хотя бы один вектор вида 
, для которого 
. Перенося его в правую часть (3.1.23), находим
(3.1.24)
где 
Этот процесс переноса векторов в правую часть можно продолжить аналогичным образом и дальше. Допустим, что уже проведено (2k-1) шагов. Тогда имеет место соотношение
(3.1.25)
где 
Возможные два случая:
1) 
при некотором 
2) 
.
В первом случае процесс переноса заканчивается, причем из векторов в правой части (3.1.25) можно образовать замкнутый маршрут. Таким маршрутом является
Во втором случае процесс переноса продолжается, и поскольку 
, среди векторов Рij, где (i,j) 
обязательно найдется вектор 
с коэффициентом 
.
Описанный процесс переноса не может длится бесконечно, так как все вектора, переносимые вправо, различны. Поэтому через конечное число шагов мы обязательно столкнемся со случаем 1, который, как показано више, ведет к образованию замкнутого маршрута.
Итак, допустив, что система векторов 
линейно зависима, мы пришли к противоречию с условием теоремы, согласно которому из коммуникаций системы R нельзя составить замкнутый маршрут. Остается принять, что система R состоит из линейно независимых векторов.
Достаточность условий теоремы доказана.
Назовем коммуникацию 
Т-задачи основной коммуникацией плана Х, если 
Тогда, используя теорему 3.4, можно сформулировать следующий признак проверки произвольного плана на опорность.
План 
Т-задачи является опорным (базисным), если из его основных коммуникаций нельзя составить замкнутый маршрут.
Теорема 3.5. Вектор 
является линейной комбинацией векторов системы R тогда и только тогда, когда из векторов этой системы можно составить маршрут, соединяющий пункты Ak и 
. Если этот маршрут имеет вид
то
. (3.1.26)
Доказательство этой теоремы основано на теореме 3.4. Пусть выражен в виде линейной комбинации векторов системы R. Добавив к ней вектор , получим систему линейно зависимых векторов. Тогда в силу теоремы 3.4 появляется замкнутый маршрут 
. Этот замкнутый маршрут должен содержать коммуникацию 
и, следовательно, все остальные коммуникации должны соединить 
и .
Тогда
.
Перенеся 
в правую часть, получим выражение (3.1.26), что и требовалось доказать.
|
1 |
2 |
3 |
4 |
5 |
6 |
i /j |
|
|
|
1 |
|
|
1 |
|||
|
|
1 |
2 |
|||||
|
X = |
|
|
3 |
||||
|
|
1 |
4 |
|||||
|
|
1 |
1 |
5 |
||||
|
Рис. 3.3. |
|||||||
Рассмотрим произвольную матрицу 
. Между позициями матрицы Х и векторами 
можно установить следующее соответствие. Вектор соответствует элементу 
матрицы Х. Тогда можно задать систему из векторов 
, выделив единицами соответствующие элементы матрицы Х. Рассмотрим матрицу на рис 3.3. Здесь единицами отмечена система векторов R:
.
При использовании матрицы Х критерий проверки линейной независимости формулируется так: для линейной независимости системы векторов необходимо и достаточно, чтобы из ненулевых элементов матрицы Х, отвечающих этим векторам, невозможно было составить замкнутый маршрут (цикл).
Так как из выделенных единицами позиций на рис. 3.3 нельзя составить замкнутый маршрут, то данная система линейно независима и образует базис.
Введем теперь в систему 
вектор 
, отметив его знаком '+'. Чтобы разложить по векторам системы R, составим цепочку из выделенных элементов, которая замыкается на элементе 
:
.
При небольших размерах матрицы Х визуальное отыскание замкнутых цепочек в ней представляет значительные трудности. В таком случае прибегают к формализованному методу вычеркивания. Метод вычеркивания позволяет выделить в произвольном плане Х Т-задачи замкнутую цепочку, если она существует.
Этот метод состоит в следующем. Выделив в плане Х множество ненулевых элементов, обозначаемое через S, выясним, существуют ли во множестве элементов S циклы. Для этого просматриваем одну за другой строки плана Х и вычеркиваем строки, не содержащие элементов S, и строки, которые содержат не более одного элемента S (ненулевой элемент). Просмотрев все строки плана Х, переходим к столбцам и вычеркиваем те из них, которые содержат не более одного элемента S.
При этом элементы, содержащиеся в ранее вычеркнутых строках, в расчет не принимают. Далее повторяем весь этот процесс, просматривая сначала строки, а потом столбцы оставшейся после вычеркивания строк и столбцов подматрицы.
После конечного числа шагов этот процесс заканчивается одним из следующих двух исходов: 1) все строки (столбцы) матрицы вычеркнуты; 2) получена подматрица, в каждой строке и столбце которой содержится не менее двух элементов S.
В первом случае из элементов множества S составить цикл невозможно. Следовательно, соответствующий план Х является опорным.
Во втором случае множество S содержит цикл (циклы) и соответствующий план Х не является опорным (базисным). На рис 3.4 показаны два плана
Т-задачи: небазисный (рис. 3.4, а) и базисный (рис 3.4, б). Номера линий указывают порядок вычеркивания. Звездочками отмечены элементы, которые вычеркнуть нельзя. Они образуют цикл.
1* *1 1* 1* 1 1 *1 *1 Рис. 3.4. а) |
1 1 9 1 1 2 1 10 1 1 1 3 1 4 1 Рис 3.4. б) |
Нахождение начальных опорных планов
Существует несколько методов построения начальных опорных планов Т-задачи. Из них самый распространенный метод северо-западного угла и метод минимального элемента [18].
Метод северо-западного угла. Основную идею метода рассмотрим на конкретном примере.
Пусть дана Т-задача с четырьмя пунктами производства А1, А2, А3, А4 с объемами производства 
и пунктами потребления 
с объемами потребления соответственно 
.
Построим матрицу Х размером 4х4, причем для удобства вычислений снизу от нее оставим строку bj, справа столбец ai. Кроме того, снизу от bj образуем строки 
, где будем записывать неудовлетворенные потребности, а справа от ai- столбцы 
, где будем записывать остатки невывезенного продукта (табл. 3.2).
Заполнение таблицы начинают с левого верхнего элемента таблицы X - x11, что и обусловило название метода. Сравнив 
с 
и выбрав меньшее из них, получим x11=1. Записываем это значение в матрицу Х0. Так как первый выбор произведен по строке, то остальная часть первой строки должна быть заполнена нулями. Во вспомогательном столбце 
записываем остатки невывезенного продукта, 
, а в строке 
- неудовлетворенные потребности после одного шага заполнения.
Переходим к второй строке и начинаем заполнение с элемента 
(новый северо-западный угол незаполненной части таблицы 3.2). Сравнивая 
выбираем меньшее из них, и потому 
. Остальную часть второй строки заполняем нулями. Далее заполняем таблицу аналогично. После окончания процесса заполнения будем иметь начальный план Х0. Полученный план является базисным (опорным), так как из его ненулевых элементов нельзя составить цикл. Кроме того, он удовлетворяет условиям задачи, так как
.
Таблица 3.2
|
Х |
|
|
|
|
|
|
|||||
|
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
2 |
0 |
0 |
0 |
2 |
2 |
0 |
0 |
0 |
0 |
0 |
|
|
2 |
1 |
0 |
0 |
3 |
3 |
3 |
1 |
0 |
0 |
0 |
|
|
0 |
0 |
2 |
2 |
4 |
4 |
4 |
4 |
4 |
2 |
0 |
|
|
|
5 |
1 |
2 |
2 |
|||||||
|
|
4 |
1 |
2 |
2 |
|||||||
|
|
0 |
1 |
2 |
2 |
|||||||
|
|
0 |
0 |
2 |
2 |
|||||||
|
|
0 |
0 |
0 |
2 |
|||||||
|
|
0 |
0 |
0 |
0 |
|||||||
Формальное описание алгоритма. I. Определяют верхний левый элемент матрицы Х:
.
Возможные три случая: а) если 
то 
и всю первую строку, начиная со второго элемента, заполняют нулями; б) если 
, то 
, а все оставшиеся элементы первого столбца заполняют нулями; в) если
то 
и все оставшиеся элементы первых столбцов и строки заполняют нулями.
Находим
на этом один шаг метода заканчивается.
2. Пусть уже проделано k шагов. (k+1)-й шаг состоит в следующем. Определяют верхний левый элемент незаполненной части матрицы Х. Пусть это будет элемент
причем
, (3.1.27)
где
(3.1.28)
Если 
, то заполняем нулями строку 
, начиная с (
+1)-го элемента. В противном случае заполняем нулями столбец 
, начиная с элемента ( +1). Если 
, то заполняем нулями остаток строки и столбца . Далее вычисляем 
. На этом (k+1)-й шаг заканчивается. Описанный процесс повторяется до тех пор, пока матрица Х не будет заполнена полностью.
Метод минимального элемента.
Этот метод является вариантом метода северо-западного угла, учитывающим специфику матрицы транспортных затрат С=
. В отличие от метода северо-западного угла данный метод позволяет сразу получить достаточно экономичный план, сокращая общее количество итераций по его дальнейшей оптимизации.
Формальное описание алгоритма. Элементы матрицы нумеруют, начиная от минимального в порядке возрастания, а затем в этом же порядке заполняют матрицу Х0.
Пусть элементом с минимальным порядковым номером оказался 
. Возможные три случая: а) если 
, то оставшуюся часть 
-й строки заполняем нулями; б) если 
, то оставшуюся часть 
-го столбца заполняем нулями; в) если 
, то оставшуюся часть -й строки и -го столбца заполняем нулями.
Дале этот процесс повторяют с незаполненной частью матрицы Х1.
Пример 3.1. Найти начальный базисный план методом минимального элемента для Табл. 3.3. следующей задачи.
Таблица. 3.3.
|
Ai \ Bj |
1 |
2 |
3 |
4 |
Bj / ai |
|
1 |
7(10) |
8(11) |
5(7) |
3(5) |
11 |
|
2 |
2(3) |
4(4) |
5(8) |
9(12) |
11 |
|
3 |
6(9) |
3(4) |
1(1) |
2(2) |
8 |
|
Ai / bj |
5 |
9 |
9 |
7 |
bj \ ai |
Цифры в скобках указывают порядок заполнения элементов в матрице Х0 (табл. 3.4).
Соответствующее значение целевой функции равно
3*8 + 1*5 + 3*7 + 5*2 + 6*4 + 8*1 = 92
Таблица 3.4
|
Х0 |
|
|
|
||||||
|
0 |
3 |
1 |
7 |
11 |
4 |
3 |
0 |
||
|
5 |
6 |
0 |
0 |
11 |
6 |
0 |
|||
|
0 |
0 |
8 |
0 |
8 |
0 |
||||
|
|
5 |
9 |
9 |
7 |
|||||
|
|
0 |
3 |
1 |
0 |
|||||
|
|
0 |
0 |
|||||||
