Решение транспортных задач методами линейного программирования

Как видно из приведенных  расчетов наименьшее значение целевой  функции (суммарный пробег пустых вагонов) получено при построении начального опорного плана методом наименьшего  критерия в строке (L = 5790 ваг-км). Так  как целью данной задачи является получение минимального суммарного пробега пустых вагонов, то для дальнейшего рассмотрения выбирается исходный опорный план, построенный именно этим методом.

Наиболее известным методом  решения транспортных задач закрытого  типа является метод потенциалов, разработанный академиками Л.А. Канторовичем и М.В. Говуриным.

 

Алгоритм решения транспортной задачи закрытого типа, представленной в матричной форме, без ограничений  пропускной способности методом  потенциалов

1. Исходный опорный  план проверяется на условие «вырождения».

Согласно теореме  Данцига количество занятых клеток в оптимальном плане не должно превышать суммарного числа строк  и столбцов (суммы количества пунктов  отправления и назначения):

К_з = m + n – 1 ,                (6)

где К_з – число занятых клеток; m – число строк матрицы (пунктов отправления); n – число столбцов (пунктов назначения).

 

Естественно, этому  же условию должен отвечать исходный опорный план. Если это условие  не выполняется, то исходный опорный  план составлен неверно.

 

Если К_з = m + n – 1 , задача решается обычным порядком.

 

Если К_з < m + n – 1 , задача называется «вырожденной» и распадается на несколько самостоятельных задач. Чтобы этого избежать, назначаются дополнительные фиктивные перевозки (перевозки равные 0). В нашем примере условие «вырождения» выполняется во всех случаях (К_з ?  10), однако, в случае построения начального опорного плана методом наименьшего критерия в строке, задача является «вырожденной» (9<10). Для устранения “вырождения” назначаем фиктивную перевозку в клетку на пересечении строки 2 и столбца 9 (табл. 7). Теперь количество занятых клеток равно сумме строк и столбцов.

 

Таблица 7

Скорректированный исходный опорный план, построенный  методом наименьшего критерия в  строке

Станция отправления	Избыток пустых вагонов	Станция назначения
		5	6	7	8	9	10	11
		Недостаток  пустых вагонов
		70	50	60	30	50	70	90
1	100	15 20	23	28	13 30	12 50	16	21
2	120	24	17 50	24	11	11 0	12 70	18
3	150	8 50	19	16 10	18	9	17	15 90
4	50	12	28	18 50	16	21	20	25

2. Одной из  строк присваивается произвольный  потенциал. Удобнее всего начать  со строки, имеющей наибольшее  число занятых клеток, а величину  потенциала выбрать больше, чем  любое расстояние (или другой  показатель критерия оптимизации)  в матрице условий.

 

Экономическая сущность метода потенциалов. Предположим, что в каком-либо пункте отправления, например “1”, стоимость единицы продукции равняется 100 условным единицам. Тогда в пунктах потребления “5”, “8”, “9” стоимость единицы продукции, с учетом стоимости перевозки, будет соответственно равна 100 + 15 = 115, 100 + 13 =113, 100 + 12 =112 условным единицам. Пункт потребления “5” также “связан” с пунктом производства “3” (табл. 8), поэтому он может получать продукцию по своей цене. Тогда стоимость продукции в пункте “3”, с учетом стоимости доставки, будет составлять 115 – 8 = 107 условных единиц и т.д. Стоимости, найденные таким образом для всех пунктов, носят условный характер и называются потенциалами. В дальнейшем, потенциалы строк будут обозначаться U_i , а потенциалы столбцов – V_j.

В примере присваивается  потенциал первой строке U₁ = 100 (табл.8).

Таблица 8

План перевозок пустых вагонов (начальный) 

 

Начальное значение целевой  функции составит

L_нач = 15· 20 + 13 · 30 + 12· 50 + 17· 50 + 11· 0 + 12· 70 + 8· 50 + 16· 10 +15· 90 +  18· 50 = 5790 ваг-км.

3. Через занятые клетки  определяются потенциалы столбцов, связанных с первой строкой  по формуле

V_j = U_i + c_ij,                             (7)

где c_ij – критерий расстояния (или другой показатель критерия оптимизации) в заданной клетке.

4. Через занятые клетки  определяются потенциалы строк,  связанных со столбцами, получившими  потенциал, по формуле 

U_i = V_j - c_ij.                             (8)

5. Пункты 3 и  4 повторяются до тех пор, пока  все столбцы и строки не получат потенциал. Это всегда возможно, если выполняется условие «вырождения» К_з = m + n - 1. Клетки с фиктивными перевозками рассматриваются как занятые.

6. Проверка на оптимальность.  План считается оптимальным, если  соблюдаются следующие условия:

V_j - U_i £ c_ij, при x_ij = 0 (клетка свободна),                     (9)

V_j - U_i = c_ij, при x_ij > 0 (в клетке назначена перевозка).

В табл. 8 для  клетки (1,11) 122 – 100 = 22 >21, т.е. нарушение  в данной клетке составляет 1. Для  клетки (2, 8) 113 – 101 = 12 >11, нарушение 1. Аналогично, в клетке (2,11) нарушение составляет 3 (122 – 101 = = 21 > 18). Для остальных свободных и занятых клеток условия оптимальности [см. формулу (9)] выполняются. Результаты проверки приведены в табл.8. Так как в матрице перевозок имеются нарушения условий оптимальности, данный начальный опорный план не является оптимальным. Он может быть улучшен за счет клеток с нарушениями. Рекомендуется выбирать клетки с наибольшим нарушением, хотя это не гарантирует упрощения решения. В данном примере можно выбрать клетку (2,11) с нарушением

Формальное правило  улучшения плана:

а) начиная с  клетки, имеющей нарушение, ходом  “шахматной ладьи” строится замкнутый  контур с вершинами в занятых  клетках;

б) начиная с  клетки, имеющей нарушение, нумеруются вершины контура (направление обхода контура значения не имеет). Вершине в клетке (2,11) присваивается номер 1, в клетке (3,11) – номер 2, в клетке (3,5) – номер 3, (1,5) – 4, (1,9) – 5, (2,9) – 6;

в) в четных вершинах находится минимальная перевозка: min {90;20;0} = 0 в вершине (2,9);

г) для балансировки матрицы в нечетные клетки найденное  значение прибавляется, из четных –  вычитается. Получается новый, улучшенный план (табл.9). При этом значение целевой  функции составит

L = 15· 20 + 13·30 + 12· 50 + 17· 50 + 12· 70 +18· 0 + 8· 50 + 16· 10 +15· 90 +  18· 50 = 5790 ваг-км.Значение целевой функции осталось неизменным, так как по контуру была перенесена фиктивная перевозка, равная 0.

Таблица 9

План перевозок  пустых вагонов (первая корректировка)

Для нового плана перевозок (табл.9) повторяются пункты 1 – 6 алгоритма решения методом потенциалов. Условие “вырождения” [см. формулу (6)] в новой матрице (табл.9) выполняется. Присваиваются потенциалы всем строкам и столбцам [см. формулы (7) и (8)]. Как видно из табл.8 и 9 изменились потенциалы во 2-й строке и в 6-м и 10-м столбцах. Проверяется новая матрица на условие оптимальности [см. формулу (9)]. В новой матрице нарушение имеется только в одной клетке (1,11) и равно 122 – 100 = 22 > 21. Строится новый контур (1,11) – (3,11) – (3,5) – (1,5). Присваиваются номера вершинам контура и определяется минимальная перевозка в четных вершинах. Это будет min {20; 90} = 20 в вершине (1,5). Данная перевозка переносится по контуру.

Таблица 10

Оптимальный план перевозок пустых вагонов 

Станция отправления	Избыток пустых вагонов	Станция назначения							Ui
		5	6	7	8	9	10	11
		Недостаток  пустых вагонов
		70	50	60	30	50	70	90
1	100	15	23	28	13 30	12 50	16	21 20	100
2	120	24	17 50	24	11	11	12 70	18 0	103
3	150	8 70	19	16 10	18	9	17	15 70	106
4	50	12	28	18 50	16	21	20	25	104
Vj		114	120	122	113	112	115	121

Полученный  новый план перевозок (табл.10) имеет  конечное значение целевой функции

L_кон = 13· 30 + 12· 50 + 21· 20 + 17· 50 + 12· 70 + 18· 0 + 8· 70 + 16· 10 + 15· 70 +  18· 50 = 5770 ваг-км.

Проверяем новый  план перевозок (табл.10) согласно пунктам 1– 6 алгоритма решения методом  потенциалов.

Условие “вырождения” [см. формулу (6)] выполняется. После присвоения потенциалов всем столбцам и строкам  новой матрицы (табл.10) нарушений условия оптимальности [см. формулу (9)] нет, значит данный план перевозок является оптимальным.

В результате решения  данной задачи методом потенциалов  и проведенных преобразований получен  оптимальный план перевозок, который  приводит к уменьшению значения целевой функции (суммарное расстояние пе

2. Транспортная задача закрытого типа, представленная в сетевой форме, без ограничений пропускной способности

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

Сеть состоит  из вершин и звеньев. Квадратами обозначены вершины (станции) отправления. Числитель  внутри квадрата – номер вершины (станции) отправления, знаменатель  – объем отправляемых вагонов (продукции). Кружками обозначены вершины (станции) назначения, числитель – номер вершины, знаменатель – объем потребления. Числа на звеньях – расстояние перевозок (или другой критерий оптимизации) c_i,j+1 между станциями i и j+1.

Пример № 2.

Транспортная задача закрытого  типа, представленная в сетевой форме, без ограничений пропускной способности

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

Сеть состоит из вершин и звеньев. Квадратами обозначены вершины (станции) отправления. Числитель внутри квадрата – номер вершины (станции) отправления, знаменатель – объем отправляемых вагонов (продукции). Кружками обозначены вершины (станции) назначения, числитель – номер вершины, знаменатель – объем потребления. Числа на звеньях – расстояние перевозок (или другой критерий оптимизации) c_i,j+1 между станциями i и j+1.

 Условия  задачи взяты из примера №  1. Схема (сеть) дороги с указанием  объема отправления, прибытия  вагонов и расстояния между  станциями указаны на рис.1.

	Рис. 1. Исходные данные к примеру № 2 Эта задача закрытого  типа, так как суммарное количество избыточных пустых вагонов равно  суммарному количеству требующихся  вагонов (420 = 420). Математическая модель задачи будет выглядеть следующим  образом. Общее суммарное расстояние перевозки (целевая функция) Система ограничений:
			(i=1,2,3,4)	(j= 1,2..7)

x_ij ? 0, (i = 1,2,...,4; j = 1,2,...,7), где a_i – ресурсы i-го пункта отправления; b_j – потребность j-го пункта назначения.

Решение транспортной задачи в сетевой форме начинают с составления исходного плана.

Точных алгоритмов составления исходного опорного плана не существует. Рекомендуется  начать составление исходного опорного плана с вершины, имеющей наибольший объем отправления, и выбирать звенья с наименьшим расстоянием (затратами), назначая на них максимально возможные перевозки. Следует избегать встречных перевозок.

Распределение перевозок необходимо осуществлять таким образом, чтобы обеспечить отправление всех вагонов со всех станций отправления и удовлетворить потребность в пустых вагонах всех станций назначения. Возможный исходный план перевозок приведен на рис.2.

Рис. 2. Исходный план перевозок

Начальное значение целевой  функции (общее суммарное расстояние перевозки) для исходного плана  перевозок составит

L_нач = 70· 15 +30· 70 + 50· 17 + 30· 11 + 40· 18 + 50· 25 + 30· 11 + 20· 9 + 60· 16 + 70· 17 = 7370 ваг-км.

Звенья называются базисными (занятыми), если по ним осуществляются перевозки. Направление перевозки  указывается стрелкой, число около стрелки – объем перевозки по данному звену (количество вагонов) x_j,j+1.

 

Алгоритм решения  транспортной задачи, представленной в сетевой форме, методом потенциалов  такой же, как и транспортной задачи, представленной в матричной форме:

1. Исходный опорный план проверяется на условие «вырождения».

К_з£ S – 1 ,                    (10)

где К_з – число занятых звеньев сети; S – число вершин, вошедших в полигон сети.

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

Если К_з = S – 1 , задача решается обычным порядком.

Если К_з < S – 1 , задача называется “вырожденной” и распадается на несколько самостоятельных задач. Чтобы этого избежать, на свободные звенья назначаются дополнительные фиктивные перевозки (перевозки равные 0). В нашем примере условие вырождения выполняется (10 = 11 – 1), поэтому задача не является “вырожденной “ и решается обычным порядком.

2.  Начальный потенциал выбирается произвольно и присваивается произвольной вершине (рекомендуется начинать с наиболее удаленной вершины).