Постановка и основные свойства транспортной задачи
Метод минимального элемента
Этот
метод является
вариантом
метода северо-западного
угла, учитывающим
специфику
матрицы транспортных
затрат С=
.
В отличие от
метода северо-западного
угла данный
метод позволяет
сразу получить
достаточно
экономичный
план, сокращая
общее количество
итераций по
его дальнейшей
оптимизации.
Формальное описание алгоритма. Элементы матрицы нумеруют, начиная от минимального в порядке возрастания, а затем в этом же порядке заполняют матрицу Х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.

|
|
|||||||
Для
вычисления
предварительных
потенциалов
выберем начальный
пункт А1
и допустим, что
.
Потенциалы
всех остальных
пунктов вычисляем
по формулам
,
![]()
Для проверки оптимальности плана х0 строим матрицу С1, элементы которой вычисляем по соотношению
![]()

Так как в матрице С1 элемент С23 = – 3 < 0, то план Х0 – неоптимальный.
Первая итерация. Второй этап.
|
|
|
|
|
|
|
|||||||||
|
* |
6* |
0 |
0 |
|
6 |
0 |
0 |
|||||||
|
X0 = |
|
|
* |
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 |
||||||
|
|
2 |
0 |
|
-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
~ Ck),
в которой все
существенные
нули матрицы
С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.