- •Транспортная задача закрытого типа без ограничений пропускной способности, представленная в матричной форме
- •Исходные данные транспортной задачи
- •Методы построения исходного опорного плана перевозок
- •Метод наименьшего критерия в столбце. Построение начального опорного плана начинается с клетки с минимальным расстоянием перевозки в столбце и далее по столбцу (табл. 4).
- •Исходный опорный план, построенный методом наименьшего критерия в столбце
- •Метод наименьшего критерия в строке. Построение начального опорного плана начинается с клетки с минимальным расстоянием перевозки в строке и далее по строке (табл. 5).
- •Исходный опорный план, построенный методом двойного предпочтения
- •Алгоритм решения транспортной задачи закрытого типа, представленной в матричной форме, без ограничений пропускной способности методом потенциалов
- •1. Исходный опорный план проверяется на условие "вырождения".
Методы построения исходного опорного плана перевозок
Метод северо-западного угла (диагональный). Построение начального опорного плана начинается с левой верхней клетки матрицы и продолжается, двигаясь далее вправо по строке и вниз по столбцу (табл. 2).
Таблица 2
Исходный опорный план, построенный методом северо-западного угла
Станция Отправления |
Избыток порожних вагонов |
Станция назначения и недостаток порожних вагонов |
||||||
B1=65 |
B2=35 |
B3=50 |
B4=30 |
B5=45 |
B6=35 |
B7=40 |
||
А1 |
100 |
46
65 |
36
35 |
51
|
43
|
48
|
54
|
41
|
А2 |
100 |
40
|
35
|
46
50 |
42
30 |
46
20 |
28
|
37
|
А3 |
60 |
44
|
47
|
40
|
34
|
37
25 |
57
35 |
45
|
А4 |
40 |
45
|
29
|
38
|
38
|
42
|
52
|
42
40 |
Значение целевой функции составит:
L = 46*65+36*35+46*50+42*30+46*20+37*25+57*35+42*40 = 13330 ваг-км
Метод минимального элемента. Построение начального опорного плана начинается с клетки, имеющей минимальное расстояние перевозки в таблице. Эта клетка исключается из дальнейшего рассмотрения матрицы, потом заполняется клетка с очередным минимальным элементом и т.д. (табл.3).
Таблица 3
Исходный опорный план, построенный методом «минимального элемента»
Станция Отправления |
Избыток порожних вагонов |
Станция назначения и недостаток порожних вагонов |
||||||
B1=65 |
B2=35 |
B3=50 |
B4=30 |
B5=45 |
B6=35 |
B7=40 |
||
А1 |
100 |
46
40 |
36
|
51
45 |
43
|
48
15 |
54
|
41
|
А2 |
100 |
40
25 |
35
|
46
|
42
|
46
|
28
35 |
37
40 |
А3 |
60 |
44
|
47
|
40
|
34
30 |
37
30 |
57
|
45
|
А4 |
40 |
45
|
29
35 |
38
5 |
38
|
42
|
52
|
42
|
Значение целевой функции составит:
L = 46*40+40*25+29*35+51*45+38*5+34*30+48*15+37*30+28*35+37*40 = 11650 ваг-км