Транспортная задача (Т-задача) является одной из наиболее распространенных специальных задач ЛП. Частные постановки задачи рассмотрены рядом специалистов по транспорту, например О.Н. Толстым [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
|
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, удовлетворяющих условиям
(1.1)
(1.2)
и таких, что целевая функция
(1.3)
достигает минимального значения.
Условие (1.1) гарантирует полный вывоз продукта из всех пунктов производства, а (1.2) означает полное удовлетворение спроса во всех пунктах потребления.
Таким образом, Т-задача представляет собой задачу ЛП с 
числом переменных, и (m + n) числом ограничений равенств.
Переменные 
удобно задавать в виде матрицы
(1.4)
Матрицу X
, удовлетворяющую условиям Т-задачи (1.1) и (1.2) называют планом перевозок, а переменные
– перевозками. План 
, при котором целевая функция минимальна, называется оптимальным, а матрица С
= 
– матрицей транспортных затрат.
Графический способ задания Т-задач показан на рис. 1
Рис. 1
Отрезок A
i
B
j
называют коммуникацией. На всех коммуникациях ставят величины перевозок xij
.
Вектор P
ij
, компоненты которого состоят из коэффициентов при переменных xij
в ограничениях (3.1.1) и (3.1.2), называют вектором коммуникаций:
Вводят также вектор производства-потребления P
0
, где
.
Тогда ограничение (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
, что
vj
– ui
cij
, i = 1., m; j=1., n… (1.8)
При этом, если
это vj
–
ui
=
cij
.
Cправедливость этой теоремы вытекает из общих идей теории двойственности линейного программирования (в частности, теоремы 2.5, 2.7).
Дадим экономическую интерпретацию условий теоремы 2.
Разность между потенциалами пунктов Bj
иAi
,
т.е. величину vj
– ui
, можно рассматривать как приращение ценности единицы продукции при перевозке из пункта Ai
в пункт Bj
. Поэтому, если vj
– ui
< cij
, то перевозка по коммуникации Ai
Bj
нерентабельна, и 
. Если vj
– ui
= cij
, то такая перевозка рентабельна, и 
(см. Теорему 2.7).
Транспортная задача с ограниченными пропускными способностями.
Важной в практическом отношении является Тd
- задача, в которой существуют ограничения на пропускные способности коммуникаций.
Пусть 
- пропускная способность коммуникации Ai
Bj
.
Тогда 
(1.9)
Т-задача состоит в минимизации Ц.Ф. (1.3) при условиях (1.1), (1.2), (1.9). Даже в случае разрешимости Т-задачи, Тd
– задача может оказаться неразрешимой, поскольку величины пропускных способностей будут недостаточны для полного вывоза продукта из п. Аі
, и полного ввоза продукта в п. Вj
. Поэтому для Тd
– задачи вводят еще два условия:
(1.10)
(1.11)
Но и при добавочных условиях (1.10), (1.11) Тd
– задача не всегда разрешима. Для установления совместимости всех условий делают попытку построить любой план Т-задачи. Если удается, то система уравнений (1.1), (1.2), (1.9) – (1.11) совместна. В противном случае Тd
– задача неразрешима.
Теорема 3.
Для оптимальности плана Х0
Тd
– задачи необходимо и достаточно существование таких чисел v1
, v2
., vn
, – u1
, – u2
., – um
, при которых
если 
, (1.12)
если 0 <
, (1.13)
если
. (1.14)
Смысл условий оптимальности (1.12) – (1.14) состоит в следующем:
если приращение стоимости продукта vj
– uj
меньше транспортных расходов cij
, то такая перевозка убыточна, а потому
. Если же приращение стоимости продукта vj
– uj
больше транспортных расходов cij
(3.1.14), то эта перевозка прибыльна, а потому ее величина должна быть максимальной, т.е.
.
Таким образом, теорема 3.3 по существу выражает принцип рентабельности для Td
– задачи.
Открытые транспортные модели.
Существует ряд практических задач, в которых условие баланса 
не выполняется. Такие модели называются открытыми. Возможные два случая:
1)
2)
В первом случае полное удовлетворение спроса невозможно.
Такую задачу можно привести к обычной транспортной задаче следующим образом. Обозначим через 
величину штрафа из-за неудовлетворения запросов на единицу продукта в пункте Bj
.
Тогда требуется минимизировать
(1.15)
при условиях
где 
- неудовлетворенный спрос.
Задачу (3.1.15) приводят к обычной Т-задаче введением фиктивного пункта производства А
m+1
, с объемом производства 
и транспортными издержками 
В таком случае Т-задача будет иметь вид
минимизировать 
при условиях
В найденном решении хопт
полагаем все перевозки из фиктивного пункта А
m+1
равными нулю, т.е. 
.
Рассмотрим теперь второй случай. Введем фиктивный пункт B
n+1
с объемом спроса 
. Пусть 
- это убытки (штраф) в пункте Аі
за единицу невывезенного продукта. Обозначим через сии,n+1
=
удельные транспортные издержки на перевозку единицы продукта с А
і
в В
n+1
. Тогда соответствующая Т-задача запишется так:
минимизировать 
(1.16)
при условиях
(1.17) – (1.18)
В найденном решении 
все перевозки 
в фиктивный пункт Вn+1
считают равными нулю.
Опорные планы Т-задачи
Опорным (базисным) планом Т-задачи называют любое ее допустимое, базисное решение. Понятие опорного плана имеет наглядную геометрическую интерпретацию.
Последовательность коммуникаций
(1.19)
называют маршрутом, соединяющим пункты 
(рис. 2).
     
… 
. 
Рис. 2
Используя маршрут, составленный из коммуникаций, можно осуществить перевозку продукта из пункта 
в пункт 
, проходя через пункты 
.
В процессе этого движения коммуникации, стоящие на четных местах в (1.19), будут пройдены в противоположном направлении.
Маршрут (1.19), к которому добавлена коммуникация 
называется замкнутым маршрутом или циклом.
Способ проверки произвольного плана Т-задачи на опорность, основан на следующих двух теоремах (прямой и обратной).
Теорема 4.
Система, составленная из векторов 
Т-задачи, является линейно независимой тогда и только тогда, когда из коммуникаций, соответствующих этим векторам, нельзя составить замкнутый маршрут.
    Доказательство. Необходимость
. Пусть векторы 
линейно независимы. Если бы существовал замкнутый маршрут из коммуникаций 
и
, то, очевидно, начиная движение из пункта
и последовательно проходя все пункты 
по последней коммуникации 
мы вернемся в начальный пункт
. Тогда справедливое равенство
(1.20)
которое указывает на линейную зависимость векторов
.
Полученное противоречие доказывает необходимость условий теоремы 4.
Достаточность
. Допустим, что из коммуникаций, отвечающих векторам 
системы R, нельзя составить замкнутый маршрут. Докажем, что в таком случае R – линейно независимая система. Если предположить противное, т.е. линейную зависимость векторов системы R
, то существуют такие числа 
, среди которых не все нули, для которых выполняется условие
. (1.21)
Пусть, например 
. Перенесем тогда соответствующий вектор вправо и получим
, (1.22)
где Е1
образуется вычеркиванием в Е пары индексов (
). Компонента с номером 
в правой части (3.1.22) не равна нулю.
Следовательно, это же относится и к левой части этого равенства, т.е. среди
векторов 
найдется хотя бы один вектор вида 
с
коэффициентом 
. Перенеся его в правую чатсть равенства (1.22), получим
 
, (1.23)
где 
. Но поскольку 
, компонента с номером 
правой части (1.23) отлична от нуля. Поэтому среди векторов левой части (1.23) найдется хотя бы один вектор вида 
, для которого 
. Перенося его в правую часть (1.23), находим
(1.24)
где 
Этот процесс переноса векторов в правую часть можно продолжить аналогичным образом и дальше. Допустим, что уже проведено (2k-1) шагов. Тогда имеет место соотношение
(1.25)
где 
Возможные два случая:
1) 
при некотором 
2) 
.
В первом случае процесс переноса заканчивается, причем из векторов в правой части (1.25) можно образовать замкнутый маршрут. Таким маршрутом является
Во втором случае процесс переноса продолжается, и поскольку 
, среди векторов Р
ij
, где (i, j) 
обязательно найдется вектор 
с коэффициентом 
.
Описанный процесс переноса не может длится бесконечно, так как все вектора, переносимые вправо, различны. Поэтому через конечное число шагов мы обязательно столкнемся со случаем 1, который, как показано выше, ведет к образованию замкнутого маршрута.
Итак, допустив, что система векторов 
линейно зависима, мы пришли к противоречию с условием теоремы, согласно которому из коммуникаций
системы R нельзя составить замкнутый маршрут. Остается принять, что система R состоит из линейно независимых векторов.
Достаточность условий теоремы доказана.
Назовем коммуникацию 
Т-задачи основной коммуникацией плана Х
, если 
Тогда, используя теорему 3.4, можно сформулировать следующий признак проверки произвольного плана на опорность.
План 
Т-задачи является опорным (базисным), если из его основных коммуникаций нельзя составить замкнутый маршрут.
Теорема 5.
Вектор 
является линейной комбинацией векторов системы R
тогда и только тогда, когда из векторов этой системы можно составить маршрут, соединяющий пункты Ak
и 
. Если этот маршрут имеет вид
то
. (1.26)
Доказательство этой теоремы основано на теореме 3.4. Пусть
выражен в виде линейной комбинации векторов системы R. Добавив к ней вектор
, получим систему линейно зависимых векторов. Тогда в силу теоремы 3.4 появляется замкнутый маршрут 
. Этот замкнутый маршрут должен содержать коммуникацию 
и, следовательно, все остальные коммуникации должны соединить 
и
.
Тогда
.
Перенеся 
в правую часть, получим выражение (1.26), что и требовалось доказать.
| 1 |
2 |
3 |
4 |
5 |
6 |
i /j |
 |
1 |
 |
 + |
1 |
  1 |
1 |
2 |
| X = |
  1 |
 1 |
3 |
 1 |
1 |
4 |
 1 |
1 |
1 |
5 |
| Рис. 3.3. |
Рассмотрим произвольную матрицу 
. Между позициями матрицы Х
и векторами 
можно установить следующее соответствие. Вектор
соответствует элементу 
матрицы Х.
Тогда можно задать систему из векторов 
, выделив единицами соответствующие элементы матрицы Х.
Рассмотрим матрицу на рис3. Здесь единицами отмечена система векторов R:
.
При использовании матрицы Х
критерий проверки линейной независимости формулируется так: для линейной независимости системы векторов
необходимо и достаточно, чтобы из ненулевых элементов матрицы Х
, отвечающих этим векторам, невозможно было составить замкнутый маршрут (цикл).
Так как из выделенных единицами позиций на рис. 3 нельзя составить замкнутый маршрут, то данная система линейно независима и образует базис.
Введем теперь в систему 
вектор 
, отметив его знаком '+'. Чтобы разложить
по векторам системы R, составим цепочку из выделенных элементов, которая замыкается на элементе 
:
.
При небольших размерах матрицы Х
визуальное отыскание замкнутых цепочек в ней представляет значительные трудности. В таком случае прибегают к формализованному методу вычеркивания. Метод вычеркивания позволяет выделить в произвольном плане Х
Т-задачи замкнутую цепочку, если она существует.
Этот метод состоит в следующем. Выделив в плане Х
множество ненулевых элементов, обозначаемое через S, выясним, существуют ли во множестве элементов S циклы. Для этого просматриваем одну за другой строки плана Х
и вычеркиваем строки, не содержащие элементов S, и строки, которые содержат не более одного элемента S (ненулевой элемент). Просмотрев все строки плана Х
, переходим к столбцам и вычеркиваем те из них, которые содержат не более одного элемента S.
При этом элементы, содержащиеся в ранее вычеркнутых строках, в расчет не принимают. Далее повторяем весь этот процесс, просматривая сначала строки, а потом столбцы оставшейся после вычеркивания строк и столбцов подматрицы.
После конечного числа шагов этот процесс заканчивается одним из следующих двух исходов: 1) все строки (столбцы) матрицы вычеркнуты; 2) получена подматрица, в каждой строке и столбце которой содержится не менее двух элементов S.
В первом случае из элементов множества S составить цикл невозможно. Следовательно, соответствующий план Х
является опорным.
Во втором случае множество S содержит цикл (циклы) и соответствующий план Х
не является опорным (базисным). На рис. 4 показаны два плана Т-задачи: небазисный (рис. 4, а) и базисный (рис. 4, б). Номера линий указывают порядок вычеркивания. Звездочками отмечены элементы, которые вычеркнуть нельзя. Они образуют цикл.
1* *1
1* 1*
1 1
*1 *1
Рис. 4. а)
|
 5 6 11 7 8
1 1
9 1
1
2 1
10 1 1 1
3 1
4 1
Рис. 4. б)
|
Нахождение начальных опорных планов
Существует несколько методов построения начальных опорных планов Т-задачи. Из них самый распространенный метод северо-западного угла и метод минимального элемента.
Метод северо-западного угла.
Основную идею метода рассмотрим на конкретном примере.
Пусть дана Т-задача с четырьмя пунктами производства А1
, А2
, А3
, А4
с объемами производства 
и пунктами потребления 
с объемами потребления соответственно 
.
Построим матрицу Х
размером 4х4, причем для удобства вычислений снизу от нее оставим строку bj
, справа столбец ai
. Кроме того, снизу от bj
образуем строки 
, где будем записывать неудовлетворенные потребности, а справа от ai
– столбцы 
, где будем записывать остатки невывезенного продукта (табл. 2).
Заполнение таблицы начинают с левого верхнего элемента таблицы X –
x11
, что и обусловило название метода. Сравнив 
с 
и выбрав меньшее из них, получим x11
=1. Записываем это значение в матрицу Х0
. Так как первый выбор произведен по строке, то остальная часть первой строки должна быть заполнена нулями. Во вспомогательном столбце 
записываем остатки невывезенного продукта, 
, а в строке 
– неудовлетворенные потребности после одного шага заполнения.
Переходим к второй строке и начинаем заполнение с элемента 
(новый северо-западный угол незаполненной части таблицы 2). Сравнивая 
выбираем меньшее из них, и потому 
. Остальную часть второй строки заполняем нулями. Далее заполняем таблицу аналогично. После окончания процесса заполнения будем иметь начальный план Х0
. Полученный план является базисным (опорным), так как из его ненулевых элементов нельзя составить цикл. Кроме того, он удовлетворяет условиям задачи, так как
.
Таблица 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) – й шаг состоит в следующем. Определяют верхний левый элемент незаполненной части матрицы Х.
Пусть это будет элемент
причем
, (1.27)
где
(1.28)
Если 
, то заполняем нулями строку 
, начиная с (
+1) – го элемента. В противном случае заполняем нулями столбец 
, начиная с элемента (
+1). Если 
, то заполняем нулями остаток строки
и столбца
. Далее вычисляем 
. На этом (k+1) – й шаг заканчивается. Описанный процесс повторяется до тех пор, пока матрица Х
не будет заполнена полностью.
Метод минимального элемента
Этот метод является вариантом метода северо-западного угла, учитывающим специфику матрицы транспортных затрат С
=
. В отличие от метода северо-западного угла данный метод позволяет сразу получить достаточно экономичный план, сокращая общее количество итераций по его дальнейшей оптимизации.
Формальное описание алгоритма.
Элементы матрицы нумеруют, начиная от минимального в порядке возрастания, а затем в этом же порядке заполняют матрицу Х
0
.
Пусть элементом с минимальным порядковым номером оказался 
. Возможные три случая: а) если 
, то оставшуюся часть 
-й строки заполняем нулями; б) если 
, то оставшуюся часть 
-го столбца заполняем нулями; в) если 
, то оставшуюся часть
-й строки и
-го столбца заполняем нулями.
Дале этот процесс повторяют с незаполненной частью матрицы Х
1
.
Пример 1.
Найти начальный базисный план методом минимального элемента для Табл. 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
Таблица 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 |
Решение транспортной задачи при вырожденном опорном плане
Опорный план называется вырожденным, если число его ненулевых перевозок k меньше ранга матрицы ограничений. В процессе построения начального плана или при его улучшении очередной план может оказаться вырожденным.
Рассмотрим два случая.
1. Вырожденный план является начальным Х
0
. Тогда выбирают некоторые нулевые элементы матрицы Х
0
в качестве базисных так, чтобы при этом не нарушалось условие базисного плана. Число этих элементов равняется 
. Далее данные элементы заменяют на 
(где 
– произвольное, бесконечно малое число) и рассматривают их как обычные базисные элементы плана. Задачу решают как невырожденную, а в последнем оптимальном плане Х
k
вместо
пишут нули.
2. Вырожденный план получается при построении плана Х
k+1
на базе Х
k
, если цепочка в плане Х
k
содержит не менее двух минимальных нечетных элементов. В таком случае в матрице Х
k+1
полагают равным нулю только один из этих элементов, а остальные заменяют на
, и далее решают задачу как невырожденную. Если на k-м шаге 
, то при переходе от Х
k
к Х
k+1
значение целевой функции не изменяется, а в базис вводится элемент 
, для которого перевозка станет равной
.
Пример 2.
Решим Т-задачу со следующими условиями (см. Табл.6)
Проверим условие баланса 
Предварительный этап. Методом минимального элемента строим начальный базисный план Х
0
(Табл. 5)
Таблица 5
| C
= |
ai
bj
|
4 |
6 |
8 |
6 |
| 6 |
2(5)
|
2(4)
|
3(6)
|
4(11)
|
| 8 |
6(12)
|
4(10)
|
3(9)
|
1(3)
|
| 10 |
1(1)
|
2(6)
|
2(7)
|
1(2)
|
Так как m + n – 1 = 6; k = 4, то план х0
– вырожденный; l = m+ n -1 – k = 2.
Два нулевых элемента Х
0
делаем базисными так, чтобы не нарушить условие опорности. Выберем в качестве базисных элементов 
, 
и положим их равными .
Схема перевозок для плана Х
0
показана на рис. 6.
Рис. 6.
Для вычисления предварительных потенциалов выберем начальный пункт А
1
и допустим, что 
. Потенциалы всех остальных пунктов вычисляем по формулам
, 
Для проверки оптимальности плана х0
строим матрицу С
1
, элементы которой вычисляем по соотношению
Так как в матрице С
1
элемент С
23
= – 3 < 0, то план Х
0
– неоптимальный.
Первая итерация. Второй этап.
 |
 |
 |
 |
 |
|
*
 |
6*
|
0 |
0 |
|
6 |
0 |
0 |
| X0
= |
 |
 0*
|
*
|
8 |
0+
|
 |
X1
= |
0 |
0 |
6 |
|
| 4 |
0 |
0 |
6*
|
1
= |
4 |
0 |
0 |
6 |
 |
В результате построения Х
1
в базис вводим
. План Х
1
является вырожденным (в цепочке есть два минимальных элемента). Поэтому один из этих элементов, например 
, в плане Х
1
заменяем на .
Вторая итерация. Первый этап
 |
 |
|
|
 |
|
0 |
2 |
2 |
0 |
0 |
-1 |
2 |
 С1
= |
2 |
0 |
|
-3 |
 +3 |
С2
= |
5 |
3 |
0 |
0 |
| 0 |
1 |
2 |
0 |
0 |
1 |
-1 |
0 |
| -3 |
Второй этап.
 |
 |
 |
 |
 |
 |
6 |
0 |
0 |
|
6 |
0 |
0 |
| X1
= |
 |
0 |
0 |
8*
|
*
|
X2
= |
0 |
0 |
2 |
6 |
| 4 |
0 |
0+
|
6*
|
3
=min {8, 6}= 6 |
4 |
0 |
6 |
0 |
 |
Третья итерация. Первый этап.
 |
|
|
|
 |
 |
|
|
-1 |
2 |
+1 |
0 |
0 |
0 |
3 |
| С2
= |
5 |
3 |
|
|
 |
С2
= |
4 |
2 |
0 |
0 |
 |
|
1 |
-1 |
0 |
+1 |
0 |
1 |
0 |
1 |
| -1 |
-1 |
Так как в матрице С
3
нет отрицательных элементов, план Х
2
– оптимальный.
Венгерский метод для транспортной задачи
Рассмотренная выше задача о назначениях представляет собой частный случай Т-задачи, когда 
. Поэтому венгерский метод, применимый для решения транспортной задачи специального вида, можно распространить на общий случай Т-задачи.
Пусть требуется решить Т-задачу следующего вида
минимизировать 
при условиях
Алгоритм решения Т-задачи, основанный на венгерском методе, состоит из предварительного этапа и конечного числа однотипных итераций.
В результате предварительного этапа вычисляют матрицу 
, элементы которой удовлетворяют следующим условиям:
, (1.3.1)
. (1.3.2)
Если в условиях (1.3.1), (1.3.2) строгие равенства, то матрица Х
0
является решением Т-задачи.
Матрицу, построенную в результате k-й итерации, обозначим 
. Обозначим также
. (1.3.3)
Величина 
называется суммарной невязкой для матрицы 
. Она характеризует близость
к искомому плану Т-задачи. Итерации проводятся до тех пор, пока величина
не станет равна нулю.
Описание алгоритма Венгерского метода
Предварительный этап. В каждом из столбцов матрицы транспортных издержек 
отыскивают минимальный элемент, который вычитают из всех элементов этого столбца. Получают матрицу С
'. Далее в каждой строке матрицы С
' выбирают минимальный элемент и вычитают его из всех элементов рассматриваемой строки. Приходят к матрице С
0
(С
0
~ C
), все элементы которой неотрицательны, причем в каждой строке и столбце С
0
имеем по крайней мере, один нуль. Строят матрицу Х
0
так, чтобы ее ненулевые элементы были расположены в позициях нулей матрицы С
0
.
Пусть 
- номер строки, в которой расположен k-й нуль j-го столбца матрицы С
0
. Тогда элементы первого столбца матрицы Х
0
определяют по рекуррентной формуле
(3.3.4)
Т.е. все элементы первого столбца 
, которым соответствуют ненулевые элементы в матрицы С
0
, заполняют нулями, а остальные элементы этого столбца заполняют по методу северо-западного угла.
Допустим, что столбцы Х
0
от первого до (j-1) – го включительно уже заполнены. Тогда элементы j-го столбца определяют в соответствии с формулой
(3.3.5)
Если 
, то Х
0
– оптимальный план Т-задачи. Если 
, то переходим к первой итерации.
(k+1) – я итерация. Каждая итерация состоит из двух или трех этапов. Итерация начинается первым этапом, а заканчивается вторым. Между первым и вторым этапами в общем случае несколько раз могут быть проведены третий и первый этапы.
Допустим, что уже проведено k итераций, причем 
. В этом случае необходимо, используя матрицы С
k
и Х
k
, провести следующую (k+1) – ю итерацию. Перед началом итерации выделяют знаком '+' те столбцы матрицы С
k
, для которых невязки по столбцам равны
.
Первый этап. Если все ненулевые элементы матрицы С
k
окажутся в выделенных столбцах, то переходят к третьему этапу. В противном случае пусть некоторый невыделенный нуль находится в 
-й строке и в 
-м столбце. Тогда вычисляют значения невязки
-й строки:
.
Возможен один из двух случаев: 1)
, 2)
. В первом случае
-ю строку С
k
отмечают знаком '+' справа от нее, а сам невыделенный нуль отмечают штрихом. Далее просматривают элементы
-й строки, которые лежат в выделенных столбцах и ищут среди них существенные нули (напомним, что существенным нулем С
k
называется такой элемент 
, для которого 
). Если таким существенным нулем оказался элемент 
, а сам столбец – выделен, то знак выделения '+' над столбцом уничтожают, а сам этот нуль отмечают звездочкой.
Затем просматривают -й столбец и отыскивают в нем нуль (нули), расположенные в отличных от 
-й строках. Если такой нуль имеется, то отмечают его штрихом и анализируют невязку его строки.
Далее процесс поиска нулей и выделение их (штрихами или звездочками) продолжается аналогично, и за несколько шагов он заканчивается одним из следующих исходов:
1) найдем очередной невыделенный нуль матрицы С
k
, для которого невязкая в строке 
. Тогда отметив его штрихом, переходим ко второму этапу;
2) все нули матрицы С
k
оказались выделенными, причем для каждого из нулей, выделяемых штрихом, невязка 
. Тогда переходим к третьему этапу.
Во втором случае, отметив этот нуль штрихом, сразу переходим к третьему этапу.
Второй этап. Состоит в построении цепочки из нулей матрицы С
k
, отмеченных штрихами и звездочками, и в последующем переходе к новой матрице Х
k+1
Пусть для некоторого нуля со штрихом матрицы С
k
, расположенного, например, в позиции (
), невязка строки 
. Начиная с этого элемента 
, строят цепочку из отмеченных нулей матрицы С
k
: двигаясь по столбцу 
, выбирают нуль со звездочкой 
, далее двигаясь от него по строке 
, находят нуль со штрихом 
. Потом движутся от него по столбцу 2
к следующему нулю со звездочкой и т.д. Такой последовательный переход от 0' к 0*
по столбцу и от 0*
к 0' по строке осуществляют до тех пор, пока это возможно.
Можно доказать, что процесс построения цепочки однозначный и законченный, цепочка не имеет циклов, начинается и заканчивается нулем со штрихом.
После того как цепочка вида
построена, осуществляют переход к матрице 
от матрицы Х
k
по формулам
(1.3.7)
где 
(1.3.8)
Таким образом, 
-минимальный элемент среди совокупности четных элементов цепочки, невязки строки, где начинается цепочка, и столбца, где она заканчивается.
Вычисляем невязку для 
На этом (k+1) – я итерация заканчивается.
Третий этап. Итак, допустим, что все нули выделены. Третий этап заключается в переходе от матрицы С
k
к эквивалентной матрице С′
k
, в которой появляется новый невыделенный нуль (или нули). Пусть 
, где минимум выбирают из всех невыделенных элементов матрицы С
k
. Тогда из всех элементов невыделенных строк матрицы С
k
вычитают h, а ко всем элементам выделенных столбцов прибавляют h. В результате получают матрицу С
'k
(С
'k
~ C
k
), в которой все существенные нули матрицы С
k
остаются нулями, и кроме того, появляются новые невыделенные нули.
Далее переходят к первому этапу, и в зависимости от его результата либо переходят ко второму этапу, либо снова возвращаются к третьему этапу. За конечное число повторов пары этапов третий – первый обязательно перейдем ко второму этапу.
Если после выполнения второго этапа 
то Х
k+1
– оптимальный план. В противном случае переходим к (k+2) итерации.
Отметим некоторые важные особенности венгерского метода.
Поскольку данный метод в отличие от метода потенциалов не использует опорных планов, то явление вырожденности плана для него отсутствует. Это устраняет возможность зацикливания, связанного с вырожденностью планов Т-задачи, которая облегчает программирование метода и его реализацию на ЭВМ.
Метод позволяет на каждой итерации по величине невязки
оценить близость Х
k
к оптимальному плану, а также верхнюю границу необходимого числа оставшихся итераций Nост
:
. (1.3.9)
Эта формула справедлива для целочисленных значений всех переменных 
и 
.
Список литературы
1. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа.
2. Вентцель Е.С. Исследование операций. – М.: Наука, 1976.
3. Горелик В.А., Ушаков И.А. Исследование операций. – М: Машиностроение, 1986. – 286 с.
4. Давыдов Э.Т. Исследование операций: Учебное пособие для студентов вузов. – М.: Высшая школа, 1990. – 383 с.
5. Ермолаев Ю.М. Математические методы исследования операций. – К.: Наука, 1979.
6. Кузнецов Ю.Н. Математическое программирование. – М.: Наука, 1976.
7. Минц М. Математическое программирование. Теория и алгоритмы. – М.: Наука, 1990.
8. Таха Х. Введение в исследование операций. – м.: Мир, 1985.
9. Толбатов Ю.А. Эконометрика в Excel. – К.: Четверта хвиля, 1997.
|
