Файл: Тихомиров В.И. Линейное программирование в организации и планировании путевого хозяйства конспект лекций для студентов специальности Стр-во ж. д., путь и путевое хоз-во учеб. пособие.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.07.2024
Просмотров: 246
Скачиваний: 0
|
Составим табл. |
13. |
|
|
|
|
|
|
|
|
Таблица 13 |
|||||||
|
|
|
|
СЧ |
со |
ч |
г |
|
|
гч |
со |
С4 |
ГО |
сч |
с о |
со |
1 |
|
|
|
|
1 |
н |
ч |
ч |
ч |
1 |
1 |
ч |
1 |
|
ч |
|||||
|
|
|
1 |
1 |
1 |
1 |
|
1 |
1 |
|
1 |
|
||||||
У\ = |
|
- 7 5 |
0 |
0 |
0 - 6 0 |
|
0 0 0 -5 0 |
0 0 |
0 -3 0 0 |
|||||||||
у 2 = |
|
0 |
—90 |
0 |
0 |
|
0 |
—60 |
0 |
0 |
0 |
- 4 5 |
0 |
0 |
— 180 |
|||
У з |
= |
|
0 |
0 |
- 5 0 |
0 |
|
0 |
|
0 |
—70 |
0 |
0 |
0 |
—35 |
0 -3 5 0 |
||
У4 |
= |
|
0 |
0 |
|
0 |
-10 0 |
0 |
|
0 |
0 |
- 5 0 |
0 |
0 |
0 |
—40 |
—400 |
|
0= |
|
ш |
1 |
|
1 |
1 |
|
0 0 0 0 0 0 0 0 |
8 |
|||||||||
0= |
|
0 |
0 |
|
0 |
0 |
|
1 |
|
t |
1 |
1 |
0 |
0 |
0 0 10 |
|||
0= |
|
0 |
0 0 |
0 |
|
0 0 0 0 1 |
1 |
1 |
1 |
6 |
||||||||
Z = |
|
- 6 |
- 1 0 - 8 |
|
- 1 5 |
- 8 |
|
- 7 - 4 |
— 6 |
- 6 |
—7 —4 - 7 |
0 |
||||||
|
Путем симплексных преобразований освобождаемся от ну |
|||||||||||||||||
левых уравнений. |
|
от первого |
нулевого |
уравнения, |
получим |
|||||||||||||
|
Освободившись |
|||||||||||||||||
табл. |
14. |
|
со |
|
|
|
|
с» |
|
|
|
|
|
-Р? |
Таблица 14 |
|||
|
|
|
|
|
|
|
С1 |
|
|
со |
|
|
го |
ГО |
|
|||
|
|
|
|
|
|
|
|
|
|
|
сч |
|
|
|
|
|||
|
|
|
|
! f |
|
|
ч |
ч |
|
ч |
|
|
|
ч |
ч |
ч |
ч |
1 |
|
|
|
|
1 |
|
|
1 |
|
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
|
|
|
i/i= |
75 |
7 5 |
|
75 |
-6 0 |
|
0 |
|
0 |
0 |
-5 0 |
0 |
0 |
0 |
300 |
||
|
Vo = |
- 9 0 |
0 |
|
0 |
0 - 6 0 |
0 |
0 |
0 -4 5 |
0 |
0 -1 8 0 |
|||||||
|
У3 = |
0 -5 0 |
|
0 |
0 |
|
0 |
- 7 0 |
0 |
0 |
0 |
-3 5 |
0 |
— 350 |
||||
|
У4= |
0 |
0 |
— 100 |
0 |
|
0 |
|
0 |
- 5 0 |
0 |
0 |
0 |
- 4 0 |
-4 0 0 |
|||
|
A'j |= |
1 |
1 |
|
1 |
0 |
|
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
8 |
||
|
|
0 = |
0 |
0 |
|
0 |
1 |
|
1 |
R |
1 |
0 |
0 |
0 |
0 |
10 |
||
|
|
0= |
0 |
0 |
|
0 |
0 |
|
0 |
|
0 |
0 |
1 |
1 |
1 |
1 |
6 |
|
|
z = |
- 4 — 2 - 9 |
— 8 |
— 7 |
- 4 |
— 6 |
- 6 |
- 7 |
- 4 |
- 7 |
< s |
|||||||
|
Освободившись от второго нулевого уравнения, получим |
|||||||||||||||||
таол. |
15. |
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 15 |
|||
|
|
|
|
СЧ |
со |
|
|
|
|
|
|
|
|
еч |
со |
СО |
|
|
|
|
|
|
н |
ч |
|
ч |
4 " |
|
н |
Ч |
|
- з |
со |
|
|
||
|
|
|
|
|
|
|
ч |
ч |
ч |
|
1 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
sS* |
|
|
|
|
||
|
|
|
|
1 |
1 |
|
1 |
1 |
|
1 |
|
1 |
1 |
|
1 |
1 |
|
|
|
У |
, |
= |
75 |
75 |
|
7 5 |
—60 |
|
0 |
|
0 -5 0 |
0 |
0 |
0 |
|
300 |
|
|
1 |
/ , = |
-9 0 |
0 |
|
0 |
0 |
-6 0 |
0 |
0 —45 |
0 |
0 |
— |
180 |
||||
|
У3 |
= |
0 -5 0 |
|
0 |
0 |
|
70 |
70 |
0 |
0 |
- 3 5 |
0 |
|
350 |
|||
|
У4 — |
0 |
0 |
-10 0 |
0 |
|
0 |
—50 |
0 |
0 |
0 |
- 4 0 |
—400 |
|||||
|
Х \ \ — |
1 |
1 |
|
1 |
0 0 0 |
0 0 |
0 |
0 |
|
8 |
|||||||
|
х 2 3 — |
0 |
0 |
|
0 |
1 |
|
1 |
|
1 |
0 |
0 |
0 |
0 |
|
10 |
||
|
|
0 = |
0 |
0 |
|
0 |
0 0 |
|
0 |
1 |
1 |
ly jl |
1 |
|
6 |
|||
|
Z = |
- 4 - 2 |
|
- 9 |
—4 - 3 - 2 |
- 6 —7 - 4 |
— 7 |
|
8 8 |
|||||||||
. 5 — 931 |
65 |
Освободившись от последнего нулевого |
уравнения, |
полу |
||||||||
чим новую табл. |
16. |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
Таблица 16 |
|
|
сч |
СО |
* |
«ч |
сч |
сч |
СО |
СЧ |
Н |
1 |
|
Ч |
Н |
|
|
ч |
ч |
ч |
|||
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
Уг= |
7 5 |
7 5 |
7 5 |
- 6 0 |
0 |
0 |
— 5 0 |
0 |
0 |
3 0 0 |
Уз= |
1— 9 0 Ц |
0 |
0 |
0 |
- 6 0 |
0 |
0 |
— 4 5 |
0 |
— 1 8 0 |
Уз= |
0 |
- 5 0 |
0 |
0 |
7 0 |
7 0 |
3 5 |
3 5 |
3 5 |
5 6 0 |
|
0 |
0 |
—1 0 0 |
0 |
0 |
- 5 0 |
0 |
0 |
- 4 0 - 4 0 0 |
|
*11 = |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
8 |
*.з= |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 0 |
*33= |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
6 |
Z = |
- 4 |
—2 |
- 9 |
—4 |
— 3 |
- 2 |
—2 |
—3 |
- 3 |
112 |
В этой таблице есть еще отрицательные свободные члены. Это говорит о том, что опорный план еще не получен.
Делаем один шаг модифицированного Жорданова исклю чения с разрешающим элементом, находящимся в первом столб це и второй строке (—90). В результате получим новую таблицу (табл. 17).
Таблица 17
|
—Уз |
* 1 3 |
— * 1 4 |
— * 2 1 |
— * 2 2 |
— * 2 1 |
'— * 3 1 |
— |
* 3 2 |
-----Л'3 4 |
1 |
< / i = |
-75/90 |
75 |
75 |
- 6 0 |
- 5 0 |
0 |
- 5 0 |
— |
75/2 |
0 |
150 |
* 1 2 = |
-1 /9 0 |
0 |
0 |
0 |
2/3 |
0 |
0 |
1/2 |
0 |
2 |
|
Уз— |
0 |
- 5 0 |
0 |
0 |
70 |
70 |
35 |
|
35 |
35 |
560 |
|
0 |
0 |
-10 0 |
0 |
0 |
1-50| |
0 |
|
0 |
- 4 0 |
-400 |
* и = |
1/90 |
1 |
1 |
0 |
—2/3 |
0 |
0 |
- |
1/2 |
0 |
6 |
* 2 3 = |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
|
0 |
0 |
10 |
* 3 3 = |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
1 |
1 |
6 |
Z — |
— 4/90 |
- 2 |
- 9 |
—4 |
- 1 /3 |
- 2 |
- 2 |
- 1 |
- 3 |
120 |
|
Вновь полученный план также не является опорным. Де лаем еще один шаг модифицированного Жорданова исключе ния с разрешающим элементом, находящимся в шестом столбце и четвертой строке. В результате придем к табл. 18.
66
I
Таблица 18
|
—Уз |
- - * 1 3 |
х н |
—* 3 1 |
—-^32 |
— У1 |
— * 3 1 |
* 3 2 |
—* 3 1 |
1 |
//,= |
— 75/90 |
75 |
75 |
- 6 0 |
-5 0 |
0 |
- 5 0 |
-7 5 /2 |
0 |
150 |
|
— 1/90 |
0 |
0 |
п |
2/3 |
0 |
0 |
1/2 |
0 |
2 |
Уъ = |
0 |
—50 |
-1 4 0 |
0 |
7и |
70/50 |
35 |
35 |
—21 |
0 |
*24= |
0 |
0 |
2 |
0 |
0 |
- 1 /5 0 |
0 |
0 |
4/5 |
8 |
A 'l t = |
1/90 |
1 |
1■ |
0 |
- 2 /3 |
0 |
0 |
- 1 /2 |
0 |
6 |
|
0 |
0 |
—2 |
1 |
1 |
1/50 |
0 |
0 |
- 4 /5 |
2 |
* 3 3 — |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
6 |
Z = |
— 4/90 |
- 2 |
—5 |
—4 |
- 1 /3 |
— 1/25! |
- 2 |
— 1 |
- 7 / 5 |
136 |
|
|
|
|
|
|
1 |
|
|
|
|
В данной таблице в последнем столбце нет отрицательных элементов, следовательно, получен опорный план.
Взаключительной строке все коэффициенты отрицатель ны, значит получен и оптимальный план.
Вданном плане две путевые '.машинные станции из первой группы закрепляются за вторым участком, шесть — за первым
участком (х12= 2 ; Л'ц= 6) .
Из второй группы 8 ПМС закрепляются за четвертым участком п 2—за третьим (л'24= 8; х23= 2). Остальные 6 ПМС
третьей группы закрепляются за третьим участком |
(*зз = 6). |
Суммарные годовые затраты при этом составят |
136 тыс. |
руб. |
|
З а д а ч а 4 |
|
Эта задача о назначениях. Будем рассматривать задачу о распределении п машин (работников) ПМС на п работ, так чтобы каждая машина (работник), каждая ПМС выполняли одну и только одну работу и чтобы при заданной производи тельности каждого механизма (работника) ПМС на каждой из работ суммарный эффект был максимальным. Рассмотрим задачу о распределении п ПМС по п работам.
Обозначим через Сп (i, / = 1 ,.. ., п) производительность /-той ПМС на /-той работе.
Тогда рассматриваемая задача будет заключаться в та ком выборе п элементов из матрицы ||Ci;-|| по одному из каждой строки и каждого столбца, чтобы их сумма cljl + ctjt+
+ cnjn (/*=/= je при k = l) была максимальной.
Обозначив через х,- переменную, равную единице, если бтая ПМС назначена на /-тую работу, и равную нулю, если она на эту работу не назначена, мы сведем задачу к следую щей задаче линейного программирования:
67
Среди неотрицательных |
целочисленных |
решений системы |
|||||
2 «-уравнении |
|
|
|
|
|
|
|
+1 + |
*» + |
•• • + |
Xi„ = |
^ |
0 ' = С •• •, |
п) |
|
x ,j + |
*2/ + |
• • • + |
xnj = |
* 1 |
( / = 1 , |
•• ■, |
п), |
означающих, что каждая ПМС выполняет одну работу и что каждая работа обеспечивается одной ПМС, найти такое решение, которое максимизирует линейную форму
7 — |
V |
V |
с ■V • |
^ |
Zl |
2j |
L4 XiJ- |
|
Ы1 |
/=1 |
|
Пусть на дороге имеется четыре путевые машинные стан ции: ПМС-1. ПМС-2, ПМС-3, ПМС-4.
Каждая ПМС может быть использована на каждом из че тырех видов работ:
К\ — капитальный ремонт пути на старом щебне и дере
вянных шпалах; |
|
|
|
|
Ко — то же на железобетонных шпалах; |
|
на щебень |
||
Кз — капитальный |
ремонт пути |
(с постановкой |
||
и деревянных шпалах); |
|
с производитель |
||
Кц — то же на железобетонных шпалах, |
||||
ностью в километрах пути, заданной в виде матрицы |
||||
(табл. 19). |
|
|
|
|
|
|
|
|
Т а б л и ц а 19 |
|
Кх |
к 2 |
К3 |
М |
П М С -1 |
60 |
55 |
50 |
45 |
П М С -2 |
65 |
to |
75 |
70 |
П М С -3 |
70 |
65 |
62 |
57 |
П М С -4 |
50 |
45 |
55 |
52 |
Требуется так распределить ПМС по одной на каждую из работ, чтобы суммарная производительность всех ПМС была максимальной.
На основании исходных данных суммарную производитель ность ПМС запишем в виде линейной формы
Z = 60* i 1-{-55л:j2+ 50л13Т 45*14+ 65*21 + 60*22Т
+ 75л'2з + 70л.'24+ 70*31 + 65*32 + 62*33 + 57* 3.i +
+ 50*41+ 45*42+ 55*43 + 52*44—>-гпах
68
Таблица 20
|
|
— x n |
—*12 |
— *13 |
0 = |
1 |
1 |
1 |
|
0 = |
0 |
0 |
0 |
|
0 = |
0 |
0 |
0 |
|
0 = |
0 |
0 |
0 |
|
0 = |
1 |
0 |
0 |
|
0 |
= |
0 |
1 |
0 |
0 |
= |
0 |
0 |
1 |
0 |
= |
0 |
0 |
0 |
z = |
|
- 6 0 |
- 5 5 |
- 5 0 |
~ * I4
1
0
0
0
0
0
0
1
1 «u СЛ
- * a i |
---x %2 |
—*23 |
— *24 |
- * j i |
— XZ2 |
* 3> |
— *:u |
— *41 |
- * 4 2 |
- *43 |
|
Л44 1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 . |
0 |
1 |
1 . |
1 |
|m | |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
—65 |
- 6 0 |
— 75 |
- 7 0 |
- 7 0 |
- 6 5 |
- 6 2 |
- 5 7 |
- 5 0 |
- 4 5 |
- 5 5 |
- 5 2 |
0 |
Т а б л и ц а 21
|
|
— V, 1 |
-^12 |
x 3 |
- Л |.4 |
*23 |
— -*22 |
- |
*24 |
— *31 |
*32 |
—*33 |
|
*41 |
*42 |
- * 4 3 |
— *44 |
1 |
■ |
0 = |
j m j |
1 |
1 |
1 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
0 |
|
||||||||||||||||
|
|
0 |
0 |
0 |
0 |
1 |
1 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
|
0 = |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
|
0 = |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
|
0 = |
1 |
0 |
0 |
0 |
1 |
0 |
|
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
|
0 = |
0 |
1 |
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
|
0 = |
0 |
0 |
1 |
0 |
- 1 |
- 1 |
— 1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
|
0 = |
0 |
0 |
0 |
1 |
0 |
0 |
|
1 |
0 |
0 |
0 |
l |
0 |
0 |
0 |
1 |
|
|
z = |
- 6 0 |
- 5 5 I - 5 0 |
- ' 5 |
- 1 0 |
15 |
1 |
5 |
- 7 0 |
— 65 |
- 6 2 1 - 5 7 |
- 5 0 |
—45 |
- 5 5 |
- 5 2 1 |
?5 |
||
|
|
|
||||||||||||||||