Математическое моделирование систем и процессов
ФГБОУ ВПО
ДВГУПС
Кафедра «Управление эксплуатационной
работой».
КОНТРОЛЬНАЯ РАБОТА
Математическое моделирование систем и
процессов
Гр.232
Выполнил: Илларионова Е.В
Проверил: Широков А.П.
ХАБАРОВСК
2013
Транспортная задача закрытого типа, представленная в
матричной форме, с ограничениями пропускной способности.
Условие: Для заданного варианта транспортной задачи в матричной форме с
ограничениями пропускной способности необходимо найти оптимальный план, при
котором будет выполняться условие наименьшего суммарного пробега порожних
вагонов. Для этого необходимо:
1) Составить математическую модель задачи;
2) Составить начальный план, проверить по условию вырождения,
рассчитать суммарные вагоно-километры порожнего пробега;
) Решить задачу методом потенциалов, рассчитать суммарные
вагоно-километры порожнего пробега оптимального плана;
) Сравнить начальный и оптимальный варианты.
Исходные данные транспортной задачи с ограничениями
|
Станция отправления
|
Ресурсы, тыс.т
|
Станция
назначения(потребности)
|
|
|
В1
|
В2
|
В3
|
В4
|
В5
|
В6
|
В7
|
В8
|
В9
|
|
|
Объем потребления, тыс.т
|
|
|
18
|
20
|
12
|
15
|
10
|
15
|
20
|
25
|
15
|
|
А1
|
40
|
25 10
|
30 7
|
45
|
60
|
35
|
55
|
60
|
90
|
75
|
|
А2
|
25
|
45
|
58
|
46
|
75
|
48
|
54
|
65
|
58
|
95
|
|
А3
|
25
|
35 8
|
35
|
40
|
65
|
40
|
80
|
35
|
65
|
55
|
|
А4
|
15
|
48
|
50
|
30 6
|
55
|
45
|
45
|
55
|
50
|
40
|
|
А5
|
45
|
40
|
52
|
38
|
40
|
70
|
37 8
|
30 10
|
75
|
45
|
|
|
|
|
|
|
|
|
|
|
|
|
математическое моделирование транспортная задача
Транспортная задача является закрытой, так как суммарные запасы ресурсов
равны суммарным потребностям:
+25+25+15+45=18+20+12+15+10+15+20+25+15
=150
Математическая модель задачи:
. Целевая функция:
2. Система ограничения
3. Условие не отрицательности
Для
решения задачи необходимо составить опорный план. Исходный опорный план
составляется с помощью метода наименьшего критерия в столбце.
Начальный
опорный план, построенный методом наименьшего критерия в столбце.
|
Станция отправления
|
Ресурсы, тыс.т
|
Станция
назначения(потребности)
|
|
|
В1
|
В2
|
В3
|
В4
|
В5
|
В6
|
В7
|
В8
|
В9
|
|
|
Объем потребления, тыс.т
|
|
|
18
|
20
|
12
|
15
|
10
|
15
|
20
|
25
|
15
|
|
А1
|
40
|
25 10 10
|
30 7 7
|
45
|
60
|
35 10
|
55
|
60 4
|
90
|
75 9
|
|
А2
|
25
|
45
|
58
|
46
|
75
|
48
|
54
|
65
|
58 25
|
95
|
|
А3
|
25
|
35 8 8
|
35 13
|
40
|
65
|
40
|
80
|
35 4
|
65
|
55
|
|
А4
|
15
|
48
|
50
|
30 6 6
|
55
|
45
|
45 7
|
55 2
|
50
|
40
|
|
А5
|
45
|
40
|
52
|
38 6
|
40 15
|
70
|
37 8 8
|
30 10 10
|
75
|
45 6
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Значение целевой функции составит:
F=25*10+30*7+35*10+60*4+75*9+58*25+35*8+35*13+35*4+30*6+45*7+55*2+38*6+40*15+37*8+30*10+45*6=6349
(ваг-км)
Скорректированный начальный план, построенный методом наименьшего
критерия в столбце
|
Станция отправления
|
Ресурсы тыс.т
|
Станция назначения
(потребности)
|
Ui
|
|
|
В1
|
В2
|
В3
|
В4
|
В5
|
В6
|
В7
|
В8
|
В9
|
|
|
|
Недостаток порожних вагонов
|
|
|
|
|
|
18
|
20
|
12
|
15
|
10
|
15
|
20
|
25
|
15
|
|
|
А1
|
40
|
25 10 10
|
30 7 7
|
45Н23
|
60Н10
|
35 10
|
55
|
60 4
|
90
|
75 9
|
50
|
|
А2
|
25
|
45 Н3
|
58
|
46 0
|
75
|
48
|
54
|
65
|
58 25
|
95
|
72
|
|
А3
|
25
|
35 8 8
|
35 13
|
40 Н3
|
65
|
40
|
80
|
35 4
|
65
|
55
|
75
|
|
А4
|
15
|
48Н17
|
50 Н5
|
30 6 6
|
55Н10
|
45
|
45 7
|
55 2
|
50Н25
|
40Н30
|
55
|
|
А5
|
45
|
40 0
|
52
|
38 6
|
40 15
|
70
|
37Н17 8
8
|
30 10 10
|
75
|
45 6
|
80
|
|
Vj
|
120
|
110
|
118
|
120
|
85
|
100
|
110
|
130
|
125
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1.F=25*10+30*7+35*10+60*4+75*9+46*0+58*25+35*8+35*13+35*4+30*6+45*7+55*2+40*0+38*6+40*15+37*8+30*10+45*6=6349
(ваг-км)
.Проверка исходного опорного плана на условие «вырождения».
Кзб≤m+n-1
Где Кзб - число занятых базисных клеток; m- число строк
матрицы (пунктов отправления); n-число столбцов (пунктов назначения).
≤ 5+9-1
≤13
Условие вырождения выполняется, но план является «вырожденным». Для
устранения «вырождения» назначаются фиктивные перевозки х51=0,х23=0.
. Потенциалы столбцов определяются следующим образом:
Vi=Ui+cij
Где cij- критерий расстояния в заданной клетке.
Потенциалы строк определяются через занятые клетки, связанных со
столбцами, получившими потенциал по формуле:
i=Vj
- cij
Проверка на оптимальность. План считается оптимальным, если соблюдается
следующие условия:
i - Ui ≤ cij, при xij=0 (клетка
свободна)
Vi
- Ui = cij, при 
(клетка
базисная).i - Ui ≥cij, при xij=
(насыщенная клетка)
Формальное
правило улучшения плана:
а)
начиная с клетки с нарушением, двигаясь по горизонталям и вертикалям ходом
«шахматной ладьи», строят замкнутый контур с вершинами в базисных клетках;
б)
начиная с клетки с нарушением, нумеруют вершины контура (направление обхода
контура значения не имеет);
в)
в четный вершинах находится минимальная перевозка.
г)
для балансировки матрицы в нечетных вершинах контура найденное значение
прибавляется к значениям перевозок в этих клетках (с учетом возможных
ограничений в этих клетках), в четных вершинах - вычитается из значений
перевозок.
Формальное
правило улучшения плана при нарушении условия оптимальности для насыщенных
клеток:
а)
начиная с насыщенной клетки с нарушением, двигаясь по горизонталям и вертикалям
(ходом шахматной ладьи) строят замкнутый контур с вершинами в базисных клетках.
б)
начиная с клетки с нарушением, нумеруют вершины контура (направление обхода
контура значения не имеет);
в)
в нечетных вершинах находится минимальная перевозка;
г)
для балансировки матрицы в четных вершинах контура найденное значение
прибавляется к значениям перевозок в этих клетках (с учетом возможных
ограничений в этих клетках), в нечетных вершинах-вычитается из значений
перевозок.
|
Станция отправления
|
Ресурсы тыс.т
|
Станция назначения
(потребности)
|
Ui
|
|
|
В1
|
В2
|
В3
|
В4
|
В5
|
В6
|
В7
|
В8
|
В9
|
|
|
|
Недостаток порожних вагонов
|
|
|
|
|
|
18
|
20
|
12
|
15
|
10
|
15
|
20
|
25
|
15
|
|
|
А1
|
40
|
25 10 10
|
30 7 7
|
45Н23
|
60Н10
|
35 10
|
55Н25
|
60 6
|
90
|
75 7
|
20
|
|
А2
|
25
|
45 Н3
|
58
|
46 0
|
75
|
48
|
54Н4
|
65
|
58 25
|
95
|
|
А3
|
25
|
35 8 8
|
35 13
|
40
|
65
|
40
|
80
|
35 4
|
65
|
55
|
45
|
|
А4
|
15
|
48
|
50
|
30 6 6
|
55
|
45
|
45 7
|
55
|
50
|
40 2
|
55
|
|
А5
|
45
|
40 0
|
52
|
38 6
|
40 15
|
70
|
37 8 8
|
30 10 10
|
75
|
45 6
|
50
|
|
Vj
|
90
|
80
|
88
|
90
|
55
|
100
|
80
|
100
|
95
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Скорректированный план перевозок (первая итерация)
F=25*10+30*7+35*10+60*6+75*7+46*0+58*25+35*8+35*13+35*4+30*6+45*7+40*2+40*0+38*6+40*15+37*8+30*10+45*6=6289
(ваг-км)
Проверка на условие «вырождения»:
13≤5+9-1
=13
Скорректированный план перевозок (вторая итерация)
|
Станция отправления
|
Ресурсы тыс.т
|
Станция назначения
(потребности)
|
Ui
|
|
|
В1
|
В2
|
В3
|
В4
|
В5
|
В6
|
В7
|
В8
|
В9
|
|
|
|
Недостаток порожних вагонов
|
|
|
|
|
|
18
|
20
|
12
|
15
|
10
|
15
|
20
|
25
|
15
|
|
|
А1
|
40
|
25 10 10
|
30 7 7
|
45Н20
|
60Н7
|
35 10
|
55 7
|
60 6
|
90
|
75
|
50
|
|
А2
|
25
|
45 Н3
|
58
|
46 0
|
75
|
48
|
54
|
65
|
58 25
|
95
|
69
|
|
А3
|
25
|
35 8 8
|
35 13
|
40 0
|
65
|
40
|
80
|
35 4
|
65
|
55
|
75
|
|
А4
|
15
|
48
|
50
|
30 6 6
|
55
|
45
|
45
|
55
|
50
|
40 9
|
82
|
|
А5
|
45
|
40 0
|
52
|
38 6
|
40 15
|
70
|
37 8 8
|
30 10 10
|
75
|
45 6
|
77
|
|
Vj
|
117
|
110
|
115
|
117
|
85
|
105
|
110
|
127
|
122
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F=25*10+30*7+35*10+55*7+60*6+46*0+58*25+35*8+35*13+40*0+35*4+30*6+40*9+40*0+38*6+40*15+37*8+30*10+45*6=6114
(ваг-км)
Проверка на условие «вырождения»:
≤5+9-1
≤13
Условие вырождения выполняется, но план является «вырожденным». Для
устранения «вырождения» назначаются фиктивные перевозки х33=0.
Скорректированный план перевозок (третья итерация)
|
Станция отправления
|
Ресурсы тыс.т
|
Станция назначения
(потребности)
|
Ui
|
|
|
В1
|
В2
|
В3
|
В4
|
В5
|
В6
|
В7
|
В8
|
В9
|
|
|
|
Недостаток порожних вагонов
|
|
|
|
|
|
18
|
20
|
12
|
15
|
10
|
15
|
20
|
25
|
15
|
|
|
А1
|
40
|
25 10 10
|
30 7 7
|
45 0
|
60
|
35 10
|
55 7
|
60 6
|
90
|
75
|
50
|
|
А2
|
25
|
45 Н3
|
58 Н3
|
46 0
|
75
|
48
|
54
|
65
|
58 25
|
95
|
49
|
|
А3
|
25
|
35Н13 8
8
|
35 13
|
40
|
65
|
40
|
80
|
35 4
|
65
|
55
|
75
|
|
А4
|
15
|
48
|
50
|
30 6 6
|
55
|
45
|
45
|
55
|
50
|
40 9
|
62
|
|
А5
|
45
|
40 0
|
52 Н1
|
38 6
|
40 15
|
70
|
37 8 8
|
30 10 10
|
75
|
45 6
|
57
|
|
Vj
|
97
|
110
|
95
|
97
|
85
|
105
|
110
|
107
|
102
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F=25*10+30*7+35*10+55*7+60*6+46*0+58*25+35*8+35*13+40*0+35*4+30*6+40*9+40*0+38*6+40*15+37*8+30*10+45*6=6114
(ваг-км)
Проверка на условие «вырождения»:
≤5+9-1
=13
Скорректированный план перевозок (четвертая итерация)
|
Станция отправления
|
Ресурсы тыс.т
|
Станция назначения
(потребности)
|
Ui
|
|
|
В1
|
В2
|
В3
|
В4
|
В5
|
В6
|
В7
|
В8
|
В9
|
|
|
|
Недостаток порожних вагонов
|
|
|
|
|
|
18
|
20
|
12
|
15
|
10
|
15
|
20
|
25
|
15
|
|
|
А1
|
40
|
25 10 10
|
30 7 7
|
45 6
|
60
|
35 10
|
55 7
|
60
|
90
|
75
|
51
|
|
А2
|
25
|
45
|
58
|
46 0
|
75
|
48
|
54 Н2
|
65
|
58 25
|
95
|
50
|
|
А3
|
25
|
35 8 2
|
35 13
|
40 0
|
65
|
40
|
80
|
35 10
|
65
|
55
|
56
|
|
А4
|
15
|
48
|
50
|
30 6 6
|
55
|
45
|
45 Н5
|
55
|
50 Н2
|
40 9
|
56
|
|
А5
|
45
|
40 6
|
52
|
38 Н7
|
40 15
|
70
|
37 8 8
|
30 10 10
|
75
|
45 6
|
51
|
|
Vj
|
91
|
91
|
96
|
91
|
86
|
106
|
91
|
108
|
96
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F=25*10+30*7+45*6+35*10+55*7+46*0+58*25+35*2+35*13+40*0+35*10+30*6+40*9+40*6+40*15+37*8+30*10+45*6=6036
(ваг-км)
Проверка на условие «вырождения»:
≤5+9-1
=13
Скорректированный план перевозок (пятая итерация)
|
Станция отправления
|
Ресурсы тыс.т
|
Станция назначения
(потребности)
|
|
|
В1
|
В2
|
В3
|
В4
|
В5
|
В6
|
В7
|
В8
|
В9
|
|
|
|
Недостаток порожних вагонов
|
|
|
|
|
|
18
|
20
|
12
|
15
|
10
|
15
|
20
|
25
|
15
|
|
|
А1
|
40
|
25 10 10
|
30 7 7
|
45 6
|
60
|
35 10
|
55 7
|
60
|
90
|
75
|
51
|
|
А2
|
25
|
45 Н3
|
58
|
46 0
|
75
|
48
|
54 Н2
|
65
|
58 25
|
95
|
50
|
|
А3
|
25
|
35 8 2
|
35 13
|
40 0
|
65
|
40
|
80
|
35 10
|
65
|
55
|
63
|
|
А4
|
15
|
48
|
50
|
30 6 6
|
55
|
45
|
45
|
55
|
50
|
40 9
|
63
|
|
А5
|
45
|
40 6
|
52
|
38 0
|
40 15
|
70
|
37 8 8
|
30 10 10
|
75
|
45 6
|
58
|
|
Vj
|
98
|
98
|
96
|
98
|
86
|
106
|
98
|
108
|
103
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F=25*10+30*7+45*6+35*10+55*7+46*0+58*25+35*2+35*13+40*0+35*10+30*6+40*9+40*6+38*0+40*15+37*8+30*10+45*6=6036
(ваг-км)
Проверка на условие «вырождения»:
≤5+9-1
=13
Скорректированный план перевозок (шестая итерация)
|
Станция отправления
|
Ресурсы тыс.т
|
Станция назначения
(потребности)
|
Ui
|
|
|
В1
|
В2
|
В3
|
В4
|
В5
|
В6
|
В7
|
В8
|
В9
|
|
|
|
Недостаток порожних вагонов
|
|
|
|
|
|
18
|
20
|
12
|
15
|
10
|
15
|
20
|
25
|
15
|
|
|
А1
|
40
|
25 10 10
|
30 7 7
|
45 6
|
60
|
35 10
|
55 7
|
60
|
90
|
75
|
48
|
|
А2
|
25
|
45 0
|
58
|
46
|
75
|
48
|
54
|
65
|
58 25
|
95
|
50
|
|
А3
|
25
|
35 8 2
|
35 13
|
40
|
65
|
40
|
80
|
35 10
|
65
|
55
|
60
|
|
А4
|
15
|
48
|
50
|
30 6 6
|
55
|
45
|
45
|
55
|
50
|
40 9
|
60
|
|
А5
|
45
|
40 6
|
52
|
38 0
|
40 15
|
70
|
37 8 8
|
30 10 10
|
75
|
45 6
|
55
|
|
Vj
|
95
|
95
|
93
|
95
|
83
|
103
|
95
|
108
|
100
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F=25*10+30*7+45*6+35*10+55*7+45*0+58*25+35*2+35*13+35*10+30*6+40*9+40*6+38*0+40*15+37*8+30*10+45*6=6036
(ваг-км)
Скорректированный опорный план проверяется на условие «вырождения»:
Кзб≤m+n-1
≤5+9-1
=13
После присвоения потенциалов всем столбцам и строкам матрицы проверяются
условия оптимальности.
В полученном плане нет нарушений условий оптимальности. План оптимальный.
Значение целевой функции уменьшилось по сравнению с начальным планом на
313 ваг.-км(6349-6036=313) или на 313/6349*100%=4,9%
Условие.
На 4 станциях А1, А2, А3 и А4 имеется
избыток порожних вагонов в размере соответственно а1, а2,
а3 и а4 (табл.1) вагонов. Необходимо
распределить данные вагоны по 7 станциям В1, В2, В3,
В4, В5, В6 и В7 с недостатком
порожняка соответственно в количестве b1, b2, b3, b4, b5, b6 и b7
вагонов (табл. 2).
Расстояние между каждой станцией отправления (избытка вагонов) и каждой
станцией назначения (недостатка порожняка) представлено в виде матрицы
(табл.3).
Необходимо составить план распределения вагонов между указанными
станциями с минимальным суммарным пробегом порожних вагонов.
Ресурсы станций отправления
Таблица 1.
|
Станция отправления
|
А1
|
А2
|
А3
|
А4
|
|
Избыток порожних вагонов
|
100
|
100
|
60
|
40
|
Потребности станции назначения
Таблица 2.
|
Станция назначения
|
В1
|
В2
|
В3
|
В4
|
В5
|
В6
|
В7
|
|
Избыток порожних вагонов
|
55
|
50
|
45
|
35
|
45
|
25
|
45
|
Матрица расстояний между станциями, км
Таблица 3.
|
Станция отправления
|
Станция назначения
|
|
В1
|
В2
|
В3
|
В4
|
В5
|
В6
|
В7
|
|
А1
|
25
|
33
|
18
|
43
|
32
|
54
|
41
|
|
А2
|
24
|
37
|
29
|
42
|
34
|
25
|
29
|
|
А3
|
38
|
28
|
40
|
34
|
37
|
57
|
36
|
|
А4
|
22
|
48
|
38
|
26
|
21
|
30
|
42
|
Исходный план транспортной задачи.
|
Станция отправлен ия
|
Избыток порожних вагонов
|
Станция назначения
|
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
|
|
Недостаток порожних вагонов
|
|
|
55
|
50
|
45
|
35
|
45
|
25
|
45
|
|
1
|
100
|
25
|
33
|
18
|
43
|
32
|
54
|
41
|
|
2
|
100
|
24
|
37
|
29
|
42
|
34
|
25
|
29
|
|
3
|
60
|
38
|
28
|
40
|
34
|
37
|
57
|
36
|
|
4
|
40
|
22
|
48
|
38
|
26
|
21
|
30
|
42
|
Данная задача является, задачей транспортного вида ( так как суммарный
объем производства а аi
равен суммарному объему потребления а bi):
а1+а2+а3+а4=b1+b2+b3+b4
=300
Целевая функция (суммарный пробег порожних вагонов) определяется по
формуле:
где
сij- расстояние перевозки от i-ой станции
отправления до j-ой станции назначения; xij
- величина перевозки из пункта отправления i-ой станции
отправления до j-ой станции назначения.
Система
ограничений
где
ai - ресурсы i-ой станции
отправления; bj - потребность j-ой станции
назначения.
Условие
формирования закрытой транспортной задачи:
Для
решения задачи необходимо построить исходный опорный план перевозок, который в
дальнейшем будет подвергаться корректировке.
Исходный
опорный план перевозок может быть построен различными методами.
1.Метод
северо-западного угла.
|
Станция отправлен ия
|
Избыток порожних вагонов
|
Станция назначения
|
|
|
1
|
2
|
3
|
4
|
5
|
6
|
|
|
Недостаток порожних вагонов
|
|
|
55
|
50
|
45
|
35
|
45
|
25
|
45
|
|
1
|
100
|
25 55
|
33 45
|
18
|
43
|
32
|
54
|
41
|
|
2
|
100
|
24
|
37 5
|
29 45
|
42 35
|
34 15
|
25
|
29
|
|
3
|
60
|
38
|
28
|
40
|
34
|
37 30
|
57 25
|
36 5
|
|
4
|
40
|
22
|
48
|
38
|
26
|
21
|
30
|
42 40
|
Значение целевой функции составит:
F =
25*55+33*45+37*5+29*45+42*35+34*15+37*30+57*25+36*5+42*40= 10725(ваг-км)
2. Метод наименьшего критерия в строке.
|
Станция отправлен ия
|
Избыток порожних вагонов
|
Станция назначения
|
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
|
|
Недостаток порожних вагонов
|
|
|
55
|
50
|
45
|
35
|
45
|
25
|
45
|
|
1
|
100
|
25 55
|
33
|
18 45
|
43
|
32
|
54
|
41
|
|
2
|
100
|
24
|
37 0
|
29
|
42
|
34 30
|
25 25
|
29 45
|
|
3
|
60
|
38
|
28 50
|
40
|
34 10
|
37
|
57
|
36
|
|
4
|
40
|
22
|
48
|
38
|
26 25
|
21 15
|
30
|
42
|
Значение целевой функции составит:
F=25*55+28*50+18*45+34*10+26*25+34*30+21*15+25*25+29*45=7840 (ваг-км)
.Метод наименьшего критерия в столбце.
|
Станция отправлен ия
|
Избыток порожних вагонов
|
Станция назначения
|
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
|
|
Недостаток порожних вагонов
|
|
|
55
|
50
|
45
|
35
|
45
|
25
|
45
|
|
1
|
100
|
25
|
33
|
18 45
|
43
|
32 45
|
54
|
41 10
|
|
2
|
100
|
24 15
|
37
|
29
|
42 25
|
34
|
25 25
|
29 45
|
|
3
|
60
|
38
|
28 50
|
40
|
34 10
|
37
|
57
|
36
|
|
4
|
40
|
22 40
|
48
|
38
|
26
|
21
|
30
|
42
|
Значение целевой функции составит:
F=24*15+22*40+28*50+18*45+42*25+34*10+32*45+25*25+41*10+29*35=8330 (ваг-км)
4.Метод двойного предпочтения
|
Станция отправлен ия
|
Избыток порожних вагонов
|
Станция назначения
|
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
|
|
Недостаток порожних вагонов
|
|
|
55
|
50
|
45
|
35
|
45
|
25
|
45
|
|
1
|
100
|
25
|
33 15
|
18 45
|
43
|
32 40
|
54
|
41
|
|
2
|
100
|
24 30
|
37
|
29
|
42
|
34
|
25 25
|
29 45
|
|
3
|
60
|
38 25
|
28 35
|
40
|
34
|
37
|
57
|
36
|
|
4
|
40
|
22
|
48
|
38
|
26 35
|
21 5
|
30
|
42
|
Значение целевой функции составит:
F=24*30+38*25+33*15+28*35+18*45+26*35+32*40+21*5+25*25+29*45=8180 (ваг-км)
. Метод минимального элемента.
|
Станция отправлен ия
|
Избыток порожних вагонов
|
Станция назначения
|
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
|
|
Недостаток порожних вагонов
|
|
|
55
|
50
|
45
|
35
|
45
|
25
|
45
|
|
1
|
100
|
25
|
33
|
18 45
|
43 25
|
32 5
|
54
|
41 25
|
|
2
|
100
|
24 55
|
37
|
29
|
42
|
34
|
25 25
|
29 20
|
|
3
|
60
|
38
|
28 50
|
40
|
34 10
|
37
|
57
|
36
|
|
4
|
40
|
22
|
48
|
38
|
26
|
21 40
|
30
|
42
|
Значение целевой функции составит:
F=18*45+43*25+32*5+41*25+24*55+25*25+29*20+28*50+34*10+21*40=8175 (ваг-км)
Как видно из приведенных расчетов наименьшее значение целевой функции
(суммарный пробег порожних вагонов) получено при построении начального опорного
плана методом наименьшего критерия в строке (F=7840 ваг-км).
Так как целью данной задачи является получение минимального суммарного
пробега порожних вагонов, то для дальнейшего рассмотрения выбирается исходный
опорный план, построенный именно этим методом.
|
Станция отправления
|
Ресурсы, тыс.т
|
Станция
назначения(потребности)
|
|
|
В1
|
В2
|
В3
|
В4
|
В5
|
В6
|
В7
|
В8
|
В9
|
|
|
Объем потребления, тыс.т
|
|
|
18
|
20
|
12
|
15
|
10
|
15
|
20
|
25
|
15
|
|
А1
|
40
|
25 10
|
30 7
|
45
|
60
|
35
|
55
|
60
|
90
|
75
|
|
А2
|
25
|
45
|
58
|
46
|
75
|
48
|
54
|
65
|
58
|
95
|
|
А3
|
25
|
35 8
|
35
|
40
|
65
|
40
|
80
|
35
|
65
|
55
|
|
А4
|
15
|
48
|
50
|
30 6
|
55
|
45
|
45
|
55
|
50
|
40
|
|
А5
|
45
|
40
|
52
|
40
|
70
|
37 8
|
30 10
|
75
|
45
|
|
Станция отправления
|
Ресурсы, тыс.т
|
Станция
назначения(потребности)
|
|
|
В1
|
В2
|
В3
|
В4
|
В5
|
В6
|
В7
|
В8
|
В9
|
|
|
Объем потребления, тыс.т
|
|
|
18
|
20
|
12
|
15
|
10
|
15
|
20
|
25
|
15
|
|
А1
|
40
|
25 10
|
30 7
|
45
|
60
|
35
|
55
|
60
|
90
|
75
|
|
А2
|
25
|
45
|
58
|
46
|
75
|
48
|
54
|
65
|
58
|
95
|
|
А3
|
25
|
35 8
|
35
|
40
|
65
|
40
|
80
|
35
|
65
|
55
|
|
А4
|
15
|
48
|
50
|
30 6
|
55
|
45
|
45
|
55
|
50
|
40
|
|
А5
|
45
|
40
|
52
|
38
|
40
|
70
|
37 8
|
30 10
|
75
|
45
|
|
Станция отправления
|
Ресурсы, тыс.т
|
Станция
назначения(потребности)
|
|
|
В1
|
В2
|
В3
|
В4
|
В5
|
В6
|
В7
|
В8
|
В9
|
|
|
Объем потребления, тыс.т
|
|
|
18
|
20
|
12
|
15
|
10
|
15
|
20
|
25
|
15
|
|
А1
|
40
|
25 10
|
30 7
|
45
|
60
|
35
|
55
|
60
|
90
|
75
|
|
А2
|
25
|
45
|
58
|
46
|
75
|
48
|
54
|
65
|
58
|
95
|
|
А3
|
25
|
35 8
|
35
|
40
|
65
|
40
|
80
|
35
|
65
|
55
|
|
А4
|
15
|
48
|
50
|
30 6
|
55
|
45
|
45
|
55
|
50
|
40
|
|
А5
|
45
|
40
|
52
|
38
|
40
|
70
|
37 8
|
30 10
|
75
|
45
|
|
Станция отправления
|
Ресурсы, тыс.т
|
Станция
назначения(потребности)
|
|
|
В1
|
В2
|
В3
|
В4
|
В5
|
В6
|
В7
|
В8
|
В9
|
|
|
Объем потребления, тыс.т
|
|
|
18
|
20
|
12
|
15
|
10
|
15
|
20
|
25
|
15
|
|
А1
|
40
|
25 10
|
30 7
|
45
|
60
|
35
|
55
|
60
|
90
|
75
|
|
А2
|
25
|
45
|
58
|
46
|
75
|
48
|
54
|
65
|
58
|
95
|
|
А3
|
25
|
35 8
|
35
|
40
|
65
|
40
|
80
|
35
|
65
|
55
|
|
А4
|
15
|
48
|
50
|
30 6
|
55
|
45
|
45
|
55
|
50
|
40
|
|
А5
|
45
|
40
|
52
|
38
|
40
|
70
|
37 8
|
30 10
|
75
|
45
|
|
Станция отправления
|
Ресурсы, тыс.т
|
Станция
назначения(потребности)
|
|
|
В1
|
В2
|
В3
|
В4
|
В5
|
В6
|
В7
|
В8
|
В9
|
|
|
Объем потребления, тыс.т
|
|
|
18
|
20
|
12
|
15
|
10
|
15
|
20
|
25
|
15
|
|
А1
|
40
|
25 10
|
30 7
|
45
|
60
|
35
|
55
|
60
|
90
|
75
|
|
А2
|
25
|
45
|
58
|
46
|
75
|
48
|
54
|
65
|
58
|
95
|
|
А3
|
25
|
35 8
|
35
|
40
|
65
|
40
|
80
|
35
|
65
|
55
|
|
А4
|
15
|
48
|
50
|
30 6
|
55
|
45
|
45
|
55
|
50
|
40
|
|
А5
|
45
|
40
|
52
|
38
|
40
|
70
|
37 8
|
30 10
|
75
|
45
|
|
Станция отправления
|
Ресурсы, тыс.т
|
Станция
назначения(потребности)
|
|
|
В1
|
В2
|
В3
|
В4
|
В5
|
В6
|
В7
|
В8
|
В9
|
|
|
Объем потребления, тыс.т
|
|
|
18
|
20
|
12
|
15
|
10
|
15
|
20
|
25
|
15
|
|
А1
|
40
|
25 10
|
30 7
|
45
|
60
|
35
|
55
|
60
|
90
|
75
|
|
А2
|
25
|
45
|
46
|
75
|
48
|
54
|
65
|
58
|
95
|
|
А3
|
25
|
35 8
|
35
|
40
|
65
|
40
|
80
|
35
|
65
|
55
|
|
А4
|
15
|
48
|
50
|
30 6
|
55
|
45
|
45
|
55
|
50
|
40
|
|
А5
|
45
|
40
|
52
|
38
|
40
|
70
|
37 8
|
30 10
|
75
|
45
|
|
|
|
|
|
|
|
|
|
|
|
|