- •Реферат
- •Часть II (примеры)
- •Оглавление
- •Пример № 1. Транспортная задача закрытого типа без ограничений пропускной способности, представленная в матричной форме
- •Методы построения исходного опорного плана перевозок
- •Пример № 2. Транспортная задача закрытого типа, представленная в сетевой форме, без ограничений пропускной способности
- •Пример № 3. Транспортная задача закрытого типа, представленная в матричной форме, с ограничениями пропускной способности
- •Пример № 4. Транспортная задача открытого типа, представленная в матричной форме без ограничений пропускной способности
- •Алгоритм решения транспортной задачи открытого типа методом условно-оптимальных планов
- •Пример № 5.
- •Литература
Методы построения исходного опорного плана перевозок
Исходный опорный план перевозок может быть построен различными методами. Здесь приводятся наиболее распространенные из них.
Метод северо-западного угла (диагональный). Построение начального опорного плана начинается с левой верхней клетки (называемой северо-западным углом) матрицы и продолжается, двигаясь далее вправо по строке и вниз по столбцу (табл. 2).
Таблица 2
Исходный опорный план, построенный методом северо-западного угла
-
Станция отправления
Избыток пустых вагонов
Станция назначения
5
6
7
8
9
10
11
Недостаток пустых вагонов
70
50
60
30
50
70
90
1
100
15
70
23
30
28
13
12
16
21
2
120
24
17
20
24
60
11
30
11
10
12
18
3
150
8
19
16
18
9
40
17
70
15
40
4
50
12
28
18
16
21
20
25
50
Значение целевой функции составит
L = 15·70 + 23· 30 + 17· 20 + 24· 60 + 11· 30 + 11· 10 + 9· 40 + 17· 70 + 15 · 40 + 25· 50 = = 7360 ваг-км
Метод минимального элемента. Построение начального опорного плана начинается с клетки, имеющей минимальное расстояние перевозки в таблице. Эта клетка исключается из дальнейшего рассмотрения матрицы, потом заполняется клетка с очередным минимальным элементом и т.д. (табл. 3).
Таблица 3
Исходный опорный план, построенный методом “минимального элемента”
-
Станция отправления
Избыток пустых вагонов
Станция назначения
5
6
7
8
9
10
11
Недостаток пустых вагонов
70
50
60
30
50
70
90
1
100
15
23
30
28
10
13
12
16
21
60
2
120
24
17
20
24
11
30
11
12
70
18
3
150
8
70
19
16
18
9
50
17
15
30
4
50
12
28
18
50
16
21
20
25
Значение целевой функции составит
L = 23· 30 + 28· 10 + 21· 60 + 17· 20 + 11· 30 + 12· 70 + 8 · 70 + 9· 50 + 15· 30 + 18· 50 = 6100 ваг-км.
Метод наименьшего критерия в столбце. Построение начального опорного плана начинается с клетки с минимальным расстоянием перевозки в столбце и далее по столбцу (табл. 4).
Таблица 4
Исходный опорный план, построенный методом наименьшего критерия в столбце
Станция отправления |
Избыток пустых вагонов |
Станция назначения |
||||||
5 |
6 |
7 |
8 |
9 |
10 |
11 |
||
Недостаток пустых вагонов |
||||||||
70 |
50 |
60 |
30 |
50 |
70 |
90 |
||
1 |
100 |
15 |
23 |
28 |
13 |
12 |
16 60 |
21 40 |
2 |
120 |
24 |
17 50 |
24 |
11 30 |
11 30 |
12 10 |
18 |
3 |
150 |
8 70 |
19 |
16 60 |
18 |
9 20 |
17 |
15 |
4 |
50 |
12 |
28 |
18 |
16 |
21 |
20 |
25 50 |
Значение целевой функции составит
L = 16· 60 + 21· 40 + 17· 50 + 11· 30 + 11· 30 + 12· 10 + 8· 70 + 16· 60 + 9· 20 + 25· 50 = 6380 ваг-км.
Метод наименьшего критерия в строке. Построение начального опорного плана начинается с клетки с минимальным расстоянием перевозки в строке и далее по строке (табл. 5).
Таблица 5
Исходный опорный план, построенный методом наименьшего критерия в строке
-
Станция отправления
Избыток пустых вагонов
Станция назначения
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
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
Значение целевой функции составит
L = 15· 20 + 13· 30 + 12· 50 + 17· 50 + 12· 70 + 8· 50 + 16· 10 +15· 90 + 18· 50 = 5790 ваг-км.
Метод двойного предпочтения. Сначала просматривают все строки матрицы и в каждой из них (строк) отмечают элемент с минимальной стоимостью (*). Затем просматривают столбцы и также отмечают в них элемент с минимальной стоимостью (+). В клетки с двумя знаками помещают максимально возможные перевозки. Затем заполняются клетки, отмеченные один раз и клетки с возможно меньшей стоимостью (табл. 6).
Таблица 6
Исходный опорный план, построенный методом двойного предпочтения
Станция отправления |
Избыток пустых вагонов |
Станция назначения |
||||||
5 |
6 |
7 |
8 |
9 |
10 |
11 |
||
Недостаток пустых вагонов |
||||||||
70 |
50 |
60 |
30 |
50 |
70 |
90 |
||
1 |
100 |
15 |
23 30 |
28 10 |
13 |
12 * |
16 |
21 60 |
2 |
120 |
24 |
17 + 20 |
24 |
11 *+ 30 |
11 * |
12 + 70 |
18 |
3 |
150 |
8 * + 70 |
19 |
16 + |
18 |
9 + 50 |
17 |
15 + 30 |
4 |
50 |
12 * |
28 |
18 50 |
16 |
21 |
20 |
25 |
Значение целевой функции составит
L = 23· 30 + 28· 10 + 21· 60 + 17· 20 + 11· 30 + 12· 70 + 8· 70 + 9· 50 + 15· 30 + 18· 50 = 6100 ваг-км.
Более подробно эти методы рассмотрены в.
Как видно из приведенных расчетов наименьшее значение целевой функции (суммарный пробег пустых вагонов) получено при построении начального опорного плана методом наименьшего критерия в строке (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 условных единиц и т.д. Стоимости, найденные таким образом для всех пунктов, носят условный характер и называются потенциалами. В дальнейшем, потенциалы строк будут обозначаться Ui , а потенциалы столбцов – Vj.
В примере присваивается п отенциал первой строке U1 = 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. Через занятые клетки определяются потенциалы столбцов, связанных с первой строкой по формуле
Vj = Ui + cij, (7)
где cij – критерий расстояния (или другой показатель критерия оптимизации) в заданной клетке.
4. Через занятые клетки определяются потенциалы строк, связанных со столбцами, получившими потенциал, по формуле
Ui = Vj - cij. (8)
5. Пункты 3 и 4 повторяются до тех пор, пока все столбцы и строки не получат потенциал. Это всегда возможно, если выполняется условие «вырождения» Кз = m + n - 1. Клетки с фиктивными перевозками рассматриваются как занятые.
6. Проверка на оптимальность. План считается оптимальным, если соблюдаются следующие условия:
Vj - Ui cij, при xij = 0 (клетка свободна), (9)
Vj - Ui = cij, при xij > 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. Транспортная задача закрытого типа, представленная в сетевой форме, без ограничений пропускной способности
Сетевой способ решения задачи не требует составления матрицы перевозок, а позволяет вести расчет прямо на схеме путей сообщения – сети.
Сеть состоит из вершин и звеньев. Квадратами обозначены вершины (станции) отправления. Числитель внутри квадрата – номер вершины (станции) отправления, знаменатель – объем отправляемых вагонов (продукции). Кружками обозначены вершины (станции) назначения, числитель – номер вершины, знаменатель – объем потребления. Числа на звеньях – расстояние перевозок (или другой критерий оптимизации) ci,j+1 между станциями i и j+1.