Из пункта А в пункт Б ежедневно отправляются пассажирские и скорые поезда

Введем обозначения:
x1 - количество скорых поездов,
x2 - количество пассажирских поездов.
Целевая функция - количество пассажиров, перевезенных двумя поездами (количество поездов*количество вагонов*количество пассажиров):
F=1+1+5∙58+6∙40+3∙32x1+1+8∙58+4∙40+1∙32x2→max
или
F=628x1+657x2→maxОграничения по количеству вагонов:
x1+x2≤12
x1≤8
5x1+8x2≤81
6x1+4x2≤70
3x1+x2≤26
Дополнительные ограничения:
x1,x2≥0, целые
Перейдем к основной ЗЛП:
F=628x1+657x2→maxx1+x2+x3=12
x1+x4=8
5x1+8x2+x5=81
6x1+4x2+x6=70
3x1+x2+x7=26
xi≥0,i=1,7
Составим симплекс-таблицу:
Базис сб
F
628 657 0 0 0 0 0
x1
x2
x3
x4
x5
x6
x7
x3
0 12 1 1 1 0 0 0 0
x4
0 8 1 0 0 1 0 0 0
x5
0 81 5 8 0 0 1 0 0
x6
0 70 6 4 0 0 0 1 0
x7
0 26 3 1 0 0 0 0 1
∆
0 -628 -657 0 0 0 0 0
План не оптимален, т .к. есть ∆<0. В базис вводим x2 (минимальное ∆). Ввыводим из базиса x5, т. к.
min121,818,704,261=818
Пересчитаем таблицу:
Базис сб
F
628 657 0 0 0 0 0
x1
x2
x3
x4
x5
x6
x7
x3
0 1,875 0,375 0 1 0 -0,125 0 0
x4
0 8 1 0 0 1 0 0 0
x2
657 10,125 0,625 1 0 0 0,125 0 0
x6
0 29,5 3,5 0 0 0 -0,5 1 0
x7
0 15,875 2,375 0 0 0 -0,125 0 1
∆
6652,125 -217,375 0 0 0 82,125 0 0
План не оптимален, т .к. есть ∆<0. В базис вводим x1 (единственное отрицательное ∆). Ввыводим из базиса x3, т. к.
min1,8750,375,81,10,1250,625,29,53,5,15,8752,375=1,8750,375=5
Пересчитаем таблицу:
Базис сб
F
628 657 0 0 0 0 0
x1
x2
x3
x4
x5
x6
x7
x1
628 5 1 0 2 2/3 0 - 1/3 0 0
x4
0 3 0 0 -2 2/3 1 1/3 0 0
x2
657 7 0 1 -1 2/3 0 1/3 0 0
x6
0 12 0 0 -9 1/3 0 2/3 1 0
x7
0 4 0 0 -6 1/3 0 2/3 0 1
∆
7739 0 0 579 2/3 0 9 2/3 0 0
Так как все ∆≥0, план оптимален.
Таким образом, максимальное количество перевозимых пассажиров будет равно 7739 человек, если укомплектовать 5 скорых поездов и 7 пассажирских поездов.
2 . Решить транспортную задачу:
ai\bj
10 10 25 25 30
10 1 5 7 9 3
20 4 6 4 7 13
10 1 5 3 4 9
30 2 4 2 10 3
10 3 2 5 6 4
Проверим, является ли задача закрытой:
ai=10+20+10+30+10=80
bj=10+10+25+25+30=100
Задача открыта, закроем ее:
ai\bj
10 10 25 25 30
10 1 5 7 9 3
20 4 6 4 7 13
10 1 5 3 4 9
30 2 4 2 10 3
10 3 2 5 6 4
20 0 0 0 0 0
Найдем опорный план методом минимального элемента:
ai\bj
10 10 25 25 30
10 1 5 7 9 3
10
20 4 6 4 7
15 13
5
10 1 5 3 4
10 9
30 2 4 2
25 10 3
5
10 3 2 5 6 4
10
20 0
10 0
10 0 0 0
Имеем опорный план:
X=0000010 0000010 0002500 01510000 10505100, S=3∙10+13∙5+7∙15+4∙10+2∙25+3∙5+4∙10=345
Количество заполненных ячеек равно 9, а должно быть 6+5-1=10, поэтому ячейку (5,2) будем считать заполненной.
Проверим полученный план методом потенциалов:
1 2 3 4 5 αi
1 1
0 5
4 7
5 9
12 3+
10 0
2 4
-7 6
-5 54203613937004+
-8 7
15 13-
5 10
3 1
-7 5
-3 3
-6 4
10 9
-1 7
4 2
1 4
3 2-
25 10
13 3+
5 0
5 3
1 2
0 5
2 6
8 4
10 1
6 0
10 0
10 0
-1 0
4 0
-2 -1
βj
1 1 2 -3 3
Так как есть ∆ij<0, план не оптимален.
Для ячейки (2,3) – наименьшее отрицательное ∆ij – строим цикл и делаем сдвиг по циклу:
1 2 3 4 5
1 1 5 7 9 3
10
2 4 6 4
5 7
15 13
3 1 5 3 4
10 9
4 2 4 2
20 10 3
10
5 3 2
0 5 6 4
10
6 0
10 0
10 0 0 0
X=0000010 0000010 0502000 01510000 100010100, S=3∙10+4∙5+7∙15+4∙10+2∙20+3∙10+4∙10=305
Количество заполненных ячеек равно 10, и должно быть 6+5-1=10.
Проверим полученный план методом потенциалов:
1 2 3 4 5 αi
1 1
0 5
4 7
5 9
4 3
10 0
2 4
1 6
3 4+
5601463759005600703175005 7-
14691437590015 13
8 2
3 1
1 5
5 3
2 4
10 9
7 -1
4 2
1 4
3 2-
5594356350020 10
5 3+
20891576200010 0
5 3
1 55641214782800556260147320002+
0 5
2 6
0 4-
10 1
6 0
10 556412130759000-
10 0
-1 0+
-4 0
-2 -1
βj
1 1 2 5 3
Так как есть ∆ij<0, план не оптимален.
Для ячейки (6,4) – наименьшее отрицательное ∆ij – строим цикл и делаем сдвиг по циклу:
1 2 3 4 5
1 1 5 7 9 3
10
2 4 6 4
15 7
5 13
3 1 5 3 4
10 9
4 2 4 2
10 10 3
20
5 3 2
10 5 6 4
0
6 0
10 0
0 0
10 0
X=0000010 0000100 01501000 05100010 10002000, S=3∙10+4∙15+7∙5+4∙10+2∙20+3∙20+2∙10=265
Количество заполненных ячеек равно 9, а должно быть 6+5-1=10, поэтому ячейку (5,5) будем считать заполненной.
Проверим полученный план методом потенциалов:
1 2 3 4 5 αi
1 62547513271500625831133223001+
-4 5
4 7
5 9
4 120980132715003-
10 0
2 4
-3 6
3 4+
567461-261600567055-31750015 7-
59055-3175005 13
8 2
3 1
-3 5
5 3
2 4
10 9
7 -1
4 2
-3 4
3 567055157480002-
10 10
5 3+
20 0
5 3
-3 2
10 5
2 6
0 4
0 1
6 0-
62583149780010 0
4 0
3 0+
10 0
2 -5
βj
5 1 2 5 3
Так как есть ∆ij<0, план не оптимален.
Для ячейки (1,1) – наименьшее отрицательное ∆ij – строим цикл и делаем сдвиг по циклу:
1 2 3 4 5
1 1
5 5 7 9 3
5
2 4 6 4
20 7
13
3 1 5 3 4
10 9
4 2 4 2
5 10 3
25
5 3 2
10 5 6 4
0
6 0
5 0
0 0
15 0
X=500005 0000100 0200500 00100015 5002500, S=1∙5+3∙5+4∙20+4∙10+2∙5+3∙25+2∙10=245
Проверим полученный план методом потенциалов:
1 2 3 4 5 αi
1 1
5 5
4 7
5 9
8 3
5 0
2 4
1 6
3 4
20 7
4 13
8 2
3 1+
5673083086100-2 5
1 3
-2 4-
10 9
3 3
4 2
1 4
3 2
5 10
9 3
25 0
5 3
1 2
10 5
2 6
4 4
0 1
6 0-
5 0
0 0
-1 0+
15 0
-2 -1
βj
1 1 2 1 3
Так как есть ∆ij<0, план не оптимален.
Для ячейки (3,1) – наименьшее отрицательное ∆ij – строим цикл и делаем сдвиг по циклу:
1 2 3 4 5
1 1
5 5 7 9 3
5
2 4 6 4
20 7
13
3 1
5 5 3 4
5 9
4 2 4 2
5 10 3
25
5 3 2
10 5 6 4
0
6 0
0
0 0
20 0
X=505000 0000100 0200500 0050020 5002500, S=1∙5+3∙5+4∙20+1∙5+4∙5+2∙5+3∙25+2∙10=230
Проверим полученный план методом потенциалов:
1 2 3 4 5 αi
1 1
5 5
4 7
5 9
5 3
5 0
2 4
1 6
3 4
20 7
2 13
8 2
3 1
5 5
4 3
1 4
5 9
6 0
4 2
1 4
3 2
5 10
6 3
25 0
5 3
1 2
10 5
2 6
1 4
0 1
6 0
3 0
3 0
2 0
20 0
1 -4
βj
1 1 2 4 3
Так как все ∆ij≥0, план оптимален.
X*=505000 0000100 0200500 0050020 5002500, S=230