Задачи ЛП и методы их решения
.pdf210 Длина критического пути равна 28. Дуги критического пути выбираются из условия
vj(u) −v i(u) = t[u]
(выделены на рисунке жирными линиями).
1. Вышеописанный алгоритм применяется и для поиска кратчайшего пути в сетевой модели задачи об аренде. Там "правильная"нумерация уже заложена в постановке задачи.
2. С задачей о дереве кратчайших путей тесно связана задача о кратчайшем дереве
– связывающем дереве с минимальной суммой длин дуг. Она решается при помощи
алгоритма Прима-Краскала, который основан на выделении связывающего дерева с "правильной" нумерацией [9]
3. Максимальный поток в сети
Эта задача является частным случаем СТЗ с ограничением пропускных способностей дуг. Пусть задан связный ориентированный граф M, N , положительный вектор пропускных
способностей его дуг d [N] и две выделенные вершины: i− – "источник" и i+ |
– "сток". |
Требуется найти поток x[N], удовлетворяющий во всех вершинах кроме i− и i+ |
условию |
баланса |
|
a[i, N] x[N]= 0, i M \{i− ,i+}, |
|
и при этом поток, выходящий из "источника" i− (равный потоку, входящему в "сток" i+ )
|
|
|
|
V = 1 |
N |
− x |
N |
− . |
|
|
|
|
|
|
|
|
|
|
|
|
i− |
|
i− |
|
|
|
|
Эта сумма называется величиной потока. |
|
|
|
|
|
|
|
|
|||||
Пример. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Числа около дуг – их пропускные способности, |
|||||||
|
|
3(1) |
|
|
|
в |
круглых скобках – дуговые потоки. На |
||||||
|
|
2 |
1 |
6(1) |
|
остальных дугах потоки равны нулю. |
|||||||
|
|
|
Величина потока v = 3 |
|
|
||||||||
6(1) |
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
3 |
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i- |
7(1) |
5 |
4 |
|
i+ |
|
|
|
|
|
|
|
|
6(1) |
|
|
6(1) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
7 |
1 |
4(1) |
|
|
|
|
|
|
3(3) |
|
|
|
|
5(1) |
|
|
|
|
|
|
|
|
2(2) |
1(1) |
6(4) |
|
|
|
|
|
|
|
|
|
|
6(5) |
|
|
|
Сведем задачу к СТЗ. Добавим к графу дугу u |
|
|
|
3 |
|
3(3) |
|||||||
|
i- |
|
|
i+ |
|||||||||
из i− в i+ . |
|
|
|
|
|
|
|
7(6) |
5(2) |
4 |
|||
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
||
c[u]=1, |
c[N]= 0[N], |
|
|
|
|
|
|
|
6(6) |
|
6(6) |
||
|
|
|
|
|
|
|
|
|
|
||||
b[i+ ]= −b[i− ]= d [u]=1+V, |
|
|
|
|
|
|
|
7(1) |
1(1) |
4(4) |
|||
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
b[M0 ]= 0[M0 ], |
M0 = M \{i+ ,i−}. |
|
|
|
|
|
|
5(3) |
|
|
|||
Минимизация стоимости |
потоков в |
этой сети |
|
|
u |
|
|
|
|||||
означает |
минимизацию |
|
перевозки |
по |
дуге |
|
|
[u]=1 x[u]=1 |
|
||||
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
c |
|
211
u (x[u]=1), т.е. максимизацию потока V через исходную сеть.
Запись полученной СТЗ в виде задачи линейного программирования выглядит следующим образом:
f = 0[N] x[N]+1 x[u]→ min
a[i− , N] x[N]− x[ |
|
|
|
]= −1−V |
||||||
u |
||||||||||
a[M0 , N] x[N]− 0[M0 ]= 0[M0 ] |
||||||||||
a[i |
, N] x[N]+ x[ |
|
]=1+V |
|||||||
u |
||||||||||
|
+ |
|
|
|
|
|
|
|
|
|
|
|
− x[N] |
|
|
|
≥ -d [N] |
||||
|
|
|
|
|
||||||
|
|
− x[ |
|
] |
|
|
|
≥ -1−V |
||
|
u |
|
|
|
||||||
|
|
x[N]≥ 0[N], x[u]≥ 0 |
||||||||
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
[ − ] |
|
[ |
|
0 |
] |
|
[ + ] |
|
[ |
|
] |
|
[ |
|
|
] |
||
Выпишем двойственную |
задачу ( g = v |
i |
,v |
|
M |
|
|
,v |
i |
, ρ |
|
N |
|
, ρ |
|
|
u |
– вектор |
|||||
двойственных переменных) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(1+V ) (v[i+ ]− v[i− ]− ρ [ |
|
])− ρ [N] d [N]→ max |
|
|
|
|
|
||||||||||||||||
u |
|
|
|
|
|
||||||||||||||||||
v[ j(u) |
]− v[i(u)]− ρ [u]≤ 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v[i ]− v[i ]− ρ [ |
|
]≤1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
u |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
+ |
− |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ρ [N]≥ 0[N], ρ [u]≥ 0
Пусть теперь V – максимальная величина потока, идущего через сеть. Тогда x[u]=1 и
дуга u является дугой оптимального базисного дерева (на рисунке эти дуги выделены). Базисное дерево имеет такую структуру, что при удалении дуги u оно распадается на две компоненты связности (два поддерева, одно из которых содержит источник i− , а другое –
сток i+ ). Обозначим множества вершин этих поддеревьев через M− и M+ соответственно. Тогда дуги, идущие из M− в M+ и обратно из M+ в M− называются дугами разреза (прямыми (N+ ) и обратными (N− )), разделяющего источник и сток (при их удалении
"разрезаются " все пути из источника в сток). Пропускной способностью разреза называется сумма пропускных способностей прямых дуг разреза
C (M− ,M+ ) = 1 |
|
+ |
|
+ |
N |
|
d N |
. |
Ясно, что величина потока, складывающаяся из величин потоков на путях, идущих из источника в сток, должна быть не больше пропускной способности разреза (иначе поток "не пройдет" через разрез). Отметим, что потенциалы всех вершин из M− равны нулю
(т.к. v[i− ]= 0 и C[N]= 0[N]), а потенциалы всех вершин из M+ равны единице (т.к.
v[i+ ]= v[i− ]+ c[ |
|
]= 0+1=1 и |
|
C[N]= 0[N]). Отсюда следует, что для всех дуг u N с |
||||||||||||||
u |
||||||||||||||||||
ненулевым потоком (кроме дуг разреза |
|
N+ |
и N− ) |
|
|
ρ [u]= 0 . Далее, из соотношений |
||||||||||||
дополняющей нежесткости получаем |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
x[ |
|
] (v[i+ ]− v[i− ]− ρ [ |
|
]−1)= 0 |
||||||||||||
|
|
u |
u |
|||||||||||||||
|
|
|
( |
|
[ |
|
|
] |
) |
|
|
|
[ |
|
|
] |
|
|
|
|
1 |
|
1/ − 0 − ρ |
|
|
u |
|
−1 |
= 0 ρ |
|
|
u |
|
= 0 |
212
По теореме двойственности для оптимальных решений прямой и двойственной задач находим
|
|
|
g = (1+V ) (v[i+ ]− v[i− ]− ρ [ |
|
])− ρ [N] d [N] = f = x[ |
|
] =1 |
|||||||||||||
|
|
|
u |
u |
||||||||||||||||
|
|
|
1+V − ρ [N] d [N]=1 V = ρ [N] d [N] |
|
|
|
|
. |
||||||||||||
|
|
|
|
|
|
|
|
|
||||||||||||
Далее имеем |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
+ |
|
+ |
|
− |
|
− |
≥ |
|||
|
|
|
|
V = ρ [N] d [N]≥ ρ N |
d N |
+ ρ N |
|
d N |
|
|||||||||||
|
|
|
|
≥ |
|
+ |
|
|
+ |
|
+ |
|
+ |
|
|
|
|
. |
||
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
ρ N |
|
|
d N |
≥ 1 |
N |
d |
N |
= C (M− ,M+ ) |
|
|
||||||
Отсюда |
следует, |
что |
при |
|
V == C (M− ,M+ ) |
прямые дуги разреза должны быть |
||||||||||||||
насыщенными ( x N+ |
= d N+ ), а на обратных дуговые потоки должны быть нулевыми |
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
( x N |
− |
= 0 N |
− ). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Алгоритм для нахождения максимального потока является вариантом метода потенциалов, однако, реально вводить b[M ],c[N] и дугу u нет необходимости. Основу алгоритма составляет систематический поиск путей из i− в i+ , поток по которым можно
увеличить. Найденный путь вместе с дугой u образует единственный цикл в базисном дереве и после увеличения потока на нем, он разрывается по насыщенной дуге (или по обратной дуге с нулевым потоком). При отсутствии путей, увеличивающих поток будет получено оптимальное решение.
Задача о выборе минимального разреза является также основой алгоритма при
распределении ограниченных ресурсов в сетевом графике [9, стр.185]
К сетевым транспортным моделям сводятся многие задачи о покрытиях и паросочетаниях на графах. В частности, доказательство теоремы Дилворта (минимальное число путей, содержащих все вершины графа равно максимальному числу попарно несравнимых вершин) сводится к решению специальным образом построенной СТЗ. Задачи о паросочетаниях в простых (двудольных) графах могут быть сформулированы в виде потоковых задач на сетях. Методы решения задач линейного программирования применимы ко многим задачам с матрицами из нулей и единиц (задача о различных представителях, задача о наилучшем покрытии или разбиении, задача о порядке исключения переменных) [9].
|
|
|
|
|
|
214 |
|
|
|
|
|
|
10. f = 7x1 |
+ 5x2 → min |
11. f = −x1 + 2x2 |
|
→ min |
||||||||
|
x + x |
|
≥ 3 |
|
2x |
− 3x |
|
|
≥ 0 |
|||
|
1 |
|
2 |
|
|
|
1 |
|
|
2 |
|
|
x1 + 5x2 ≥ 5 |
x1 − x2 ≤ 3 |
|||||||||||
|
2x |
+ x |
2 |
≥ 4 |
|
2x |
− x |
2 |
|
= 4 |
||
|
1 |
|
|
|
|
1 |
|
|
|
|
12-15. Используя метод исключения неизвестных и графический способ, найти решения следующих ЗЛП:
12. f = 8x1 − 2x2 |
− 3x3 |
→ max |
|
13. |
|
f |
|
= x1 |
|
|
|
|
+ x3 − 7x4 |
+ x5 → max |
|||||||||||||||||||
|
− x |
+ 3x |
|
+ x |
|
≤ 4 |
|
|
|
|
|
|
|
|
|
|
x |
− x |
|
|
|
+ |
6x |
|
− 2x |
|
= −7 |
||||||
|
1 |
|
|
2 |
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
2 |
|
|
|
|
4 |
|
5 |
|
7x1 |
|
|
− 2x3 ≤ 16 |
|
|
|
|
|
|
|
|
|
|
|
|
|
x2 − x3 − 4x4 + 6x5 = 24 |
||||||||||||||||
|
2x |
− x |
2 |
− x |
3 |
= 2 |
|
|
|
|
|
|
|
|
|
|
|
x |
+ x |
2 |
− x |
3 |
− |
3x |
4 |
+ 7x |
5 |
= 32 |
|||||
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
||||||
|
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 |
|
|
|
|
|
|
|
|
|
xj ≥ 0, j 1: 5 |
|
|
|
|
||||||||||||||||||
|
|
|
14. |
|
|
|
f |
= −x1 + x2 |
|
|
|
+ x4 |
+ 3x5 |
→ min |
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
x |
+ 2x |
|
− x |
|
− 5x |
|
+ |
2x |
|
|
= −5 |
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
1 |
|
|
2 |
|
|
3 |
|
|
|
4 |
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 + x |
2 + x3 − 2x4 + 5x5 = −2 |
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
− 2x2 + x3 + 3x4 − 3x5 = 6 |
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
15. |
|
f = x1 + x2 + 2x3 |
− 9x4 |
→ max |
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
2x1 − x2 + x3 − 4x4 ≤ 6 |
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
+ 2x2 |
− x3 + 7x4 = 5 |
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
x1 |
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
5x1 + x2 |
|
|
|
− 3x4 = 11 |
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
3x |
+ |
2x |
2 |
+ x |
3 |
− 3x |
4 |
= 7 |
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
xj |
≥ 0, |
|
|
j 1: 4 |
|
|
|
|
|
|
|
|
|
|
|
|
2.Базисные решения. Метод полного перебора вершин.
16-23. Найти базисы решений систем, приведенных в условиях (в случае вырожденности решения найти все его базисы).
x − x |
|
=1 |
3x + 2x |
|
=1 |
|
16. 1 |
2 |
|
17. |
1 |
2 |
|
x1 ≥ 0, x2 ≥ 0 |
x1 |
≥ 0, x2 ≥ 0 |
||||
X0 = (1, 0) |
X0 |
= (0 ,1/ 2) |
215
x1 |
− x2 = 0 |
|
|
x |
+ x |
|
|
= 2 |
|
|
|
|
||||
|
|
1 |
|
2 |
|
= 0 |
|
|
|
|
||||||
18. |
≥ 0, x2 ≥ 0 |
|
19. x1 − x2 |
|
|
|
|
|
||||||||
x1 |
|
x |
≥ 0, x |
2 |
≥ 0 |
|
|
|
||||||||
X0 |
= (0 , 0) |
|
|
1 |
|
|
|
|
|
|
|
|
|
|||
|
|
X0 = (1,1) |
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||
x + x |
|
+ x |
|
=1 |
x + x |
|
|
+ x |
|
= 0 |
|
|
||||
1 |
|
2 |
|
3 |
|
1 |
|
|
2 |
|
|
|
3 |
|
|
|
20. x1 |
|
|
− x3 |
= 0 |
21. x1 |
− x2 |
|
+ x3 |
= 0 |
|
|
|||||
|
≥ 0, i 1:3 |
|
≥ 0, i 1:3 |
|
|
|||||||||||
xi |
xi |
|
|
|||||||||||||
X 0 |
= (1/ 2, 0 ,1/ 2) |
X 0 |
= (0 , 0 , 0) |
|
|
|||||||||||
|
+ x2 + x3 + x4 =1 |
x |
+ x |
|
|
+ x |
|
+ x |
|
= 0 |
||||||
x1 |
1 |
|
|
2 |
|
|
|
3 |
|
4 |
|
|||||
|
− x2 |
+ x3 |
− x4 =1 |
x1 − x2 + x3 − x4 = 0 |
||||||||||||
22. x1 |
23. |
+ x2 − x3 + x4 = 0 |
||||||||||||||
|
≥ 0, i 1: 4 |
x1 |
||||||||||||||
xi |
|
≥ 0, i 1: 4 |
|
|
||||||||||||
X 0 |
= (1, 0 , 0 , 0) |
xi |
|
|
||||||||||||
X 0 |
= (0 , 0 , 0 , 0) |
|
|
|||||||||||||
|
|
|
|
|
|
|
|
24-27. Найти решения следующих ЗЛП методом полного перебора вершин.
24. |
f = x1 + x2 |
+ x3 |
→ max |
25. |
f = x1 + x2 |
+ 2x3 |
+ 3x4 |
→ min |
|||||||||||||||||||||||
|
|
x |
− x |
|
|
+ x |
|
≤ 4 |
|
2x − x |
|
+ x |
|
− |
|
4x |
|
≤ 6 |
|||||||||||||
|
|
1 |
|
2 |
|
3 |
|
|
|
|
|
|
1 |
|
2 |
|
|
|
|
|
3 |
|
|
|
|
|
4 |
|
|
|
|
|
2x1 + x2 + x3 ≤ 3 |
|
x1 |
+ x2 + 3x3 + 4x4 =12 |
|||||||||||||||||||||||||||
|
|
3x |
+ x |
2 |
+ 2x |
3 |
≤ 6 |
|
|
x |
− x |
2 |
+ x |
3 |
− x |
4 |
= 2 |
|
|||||||||||||
|
|
1 |
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
+ 2x2 − x3 ≤ −3 |
|
|
x j ≥ 0, j 1:4 |
|
|
|
|
|
||||||||||||||||||||
|
− x1 |
|
|
|
|
|
|
|
|||||||||||||||||||||||
26. |
f = x1 |
+ 2x2 − 3x3 |
→ max |
27. |
f |
= x1 + x2 |
|
|
− 4x3 + 2x4 |
→ max |
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
− x + |
2x |
|
|
− |
3x |
|
|
+ x |
|
= −4 |
||||||||
|
− x1 + 2x2 + 2x3 ≤1 |
|
|
|
1 |
|
|
|
|
2 |
|
|
|
|
|
3 |
|
|
|
4 |
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
3 x1 − x2 − x3 + 2x4 ≤ −3 |
||||||||||||||||||
|
x1 + x2 − x3 = 0 |
|
|
|
x + 5x |
2 |
+ x |
3 |
+ 3x |
4 |
≤ 4 |
||||||||||||||||||||
|
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 |
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
x2 |
≥ 0, |
|
x3 |
|
≥ 0 |
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
216
3. Прямой алгоритм симплекс-метода.
28-45. Решить ЗЛП, рассматривая в качестве начального базисного решения приведенное в условии.
28. |
f = x1 − 2x2 |
+ x3 → max |
|
|
|
|
|
29. |
|
f = x1 + x2 + x3 → max |
||||||||||||||||||||||||||||||||
|
|
x + 4x |
|
|
+ x |
|
|
= 5 |
|
|
|
|
|
|
|
|
|
|
|
− x + x |
|
|
+ x |
|
|
|
= 2 |
|||||||||||||||
|
|
1 |
|
|
|
2 |
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
2 |
|
|
|
3 |
|
|
|
|
|||
|
x1 − 2x2 − x3 = −1 |
|
|
|
|
|
|
|
|
|
|
3x1 − x2 + x3 = 0 |
||||||||||||||||||||||||||||||
|
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 |
|
|
|
|
|
|
|
|
|
|
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 |
||||||||||||||||||||||||||||||
|
|
X 0 |
= (1,1, 0) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X 0 |
= (0 ,1,1) |
|
||||||||||||||||||||||
30. |
f = 2x1 + x2 |
+ 3x3 + x4 |
→ max 31. |
|
f = 6x1 + x2 |
+ 4x3 |
− 5x4 → max |
|||||||||||||||||||||||||||||||||||
|
x + 2x |
|
|
|
+ 5x |
|
− x |
|
= 4 |
|
|
|
|
|
3x + x |
|
|
− x |
|
|
+ x |
|
|
= |
4 |
|||||||||||||||||
|
|
1 |
|
|
2 |
|
|
|
|
|
3 |
|
|
4 |
|
|
|
|
|
|
|
|
1 |
|
|
2 |
|
|
3 |
|
|
|
4 |
|
|
|
|
|||||
|
x1 − x2 − x3 + 2x4 =1 |
|
|
|
|
|
5x1 + x2 + x3 − x4 = 4 |
|||||||||||||||||||||||||||||||||||
|
|
x j ≥ 0, j 1:4 |
|
|
|
|
|
|
|
|
|
|
|
x j ≥ 0, j 1:4 |
|
|
|
|
|
|
||||||||||||||||||||||
|
|
X 0 |
= (0 , 0 ,1,1) |
|
|
|
|
|
|
|
|
|
|
|
X 0 = (1, 0 , 0 ,1) |
|
|
|
|
|
|
|||||||||||||||||||||
32. |
f = x1 + 2x2 |
|
+ 3x3 − x4 |
→ max |
33. |
|
f = x1 − 3x2 |
− 5x3 |
− x4 |
→ max |
||||||||||||||||||||||||||||||||
|
x − 3x |
|
|
|
− x |
|
|
− 2x |
|
|
= −4 |
|
|
|
|
|
x + 4x |
|
|
+ 4x |
|
+ x |
|
|
= 5 |
|||||||||||||||||
|
|
1 |
|
2 |
|
|
|
3 |
|
|
|
4 |
|
|
|
|
|
|
|
|
1 |
|
|
|
2 |
|
|
|
|
|
3 |
|
|
|
|
4 |
|
|||||
|
x1 − x2 + x3 |
|
|
|
|
|
|
|
= 0 |
|
|
|
|
|
x1 + 7x2 + 8x3 + 2x4 = 9 |
|||||||||||||||||||||||||||
|
|
x j ≥ 0, j 1:4 |
|
|
|
|
|
|
|
|
|
|
|
x j ≥ 0, j 1:4 |
|
|
|
|
|
|||||||||||||||||||||||
|
|
X 0 |
= (0 ,1,1, 0) |
|
|
|
|
|
|
|
|
|
|
|
X 0 = (1, 0 ,1, 0) |
|
|
|
|
|
||||||||||||||||||||||
34. |
f = x1 + x2 + x3 |
+ x4 → max |
|
|
35. |
f = x1 + 2x2 − x3 |
+ x4 → max |
|||||||||||||||||||||||||||||||||||
|
x + 3x |
|
|
|
+ x |
|
|
+ 2x |
|
= 5 |
|
|
|
|
|
|
x + x |
|
|
− 2x |
|
+ 3x |
|
=1 |
||||||||||||||||||
|
|
1 |
|
|
2 |
|
|
|
|
3 |
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
1 |
|
|
2 |
|
|
|
|
|
3 |
|
|
|
|
|
|
4 |
|
|
|
2x1 |
|
|
|
|
|
− x3 + x4 =1 |
|
|
|
|
|
|
|
2x1 − x2 − x3 + 3x4 = 2 |
||||||||||||||||||||||||||
|
|
x j ≥ 0, j 1:4 |
|
|
|
|
|
|
|
|
|
|
|
x j ≥ 0, j 1:4 |
|
|
|
|
||||||||||||||||||||||||
|
|
X 0 |
= (0 ,1, 0 ,1) |
|
|
|
|
|
|
|
|
|
|
|
X 0 |
= (0 , 0 ,1,1) |
|
|
|
|
||||||||||||||||||||||
|
|
|
|
|
36. |
|
|
|
f = x1 + x2 + x3 |
+ x4 |
+ x5 → max |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
2x + 3x |
|
+ 5x |
|
+ 7x |
|
+ 9x |
|
=19 |
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
2 |
|
|
3 |
|
|
4 |
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
− x2 |
|
|
|
|
+ x4 + 2x5 = 2 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x j |
≥ 0, |
|
j 1:5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X0 |
= (0 , 0 ,1, 2 , 0) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
217 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
37. |
|
f = −2x1 + x2 + x3 − x4 |
|
+ 4x5 |
+ x6 → max |
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
3x + x |
|
|
|
+ 2x |
|
+ 6x |
|
|
+ 9x |
|
+ 3x |
|
=15 |
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
1 |
|
2 |
|
|
|
|
3 |
|
|
|
4 |
|
|
|
5 |
|
|
|
|
6 |
|
|
|
|
|
||
|
|
|
|
|
|
x1 + 2x2 − x3 |
|
+ 2x4 + 3x5 + x6 = 5 |
|
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
x j ≥ 0, |
|
|
|
j 1:6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
X 0 |
= (1, 0 , 0 , 0 , 0 ,4) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
38. |
f = x1 + x2 + 2x3 |
− x4 + x5 − x6 → max |
|
|
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
x + 3x |
|
|
|
+ x |
|
|
− 3x |
|
|
|
+ 4x |
|
|
|
+ x |
|
= 6 |
|
|
|
|
|||||||
|
|
|
|
|
|
|
1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
|
|
5 |
|
|
|
6 |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
x1 − x2 − x3 |
|
|
+ x4 |
|
|
|
|
|
|
|
− x6 = 2 |
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
x j ≥ 0, |
|
|
j 1:6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
X 0 |
= (0 , 0 , 0 , 0 ,1,2) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
39. |
f = x1 − x2 |
|
+ x3 |
|
+ x4 − x5 − x6 → max |
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
2x |
+ x |
|
|
+ x |
|
+ 3x |
|
|
|
+ 3x |
|
|
+ |
2x |
|
= 7 |
|
|
|
|
|||||||
|
|
|
|
|
|
|
1 |
|
|
|
2 |
|
|
3 |
|
|
4 |
|
|
|
5 |
|
|
|
|
6 |
|
|
|
|
|
|||
|
|
|
|
|
|
x1 |
|
|
|
|
|
− x3 |
|
|
|
|
|
+ x5 − x6 = −2 |
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
x2 |
+ x3 |
+ x4 + x5 + 2x6 = 5 |
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
x j |
≥ 0, |
|
|
j 1:6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
X 0 = (0 , 0 , 2 , 0 ,1,1) |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
40. f = 5x1 + x2 + 2x3 + x4 → max |
|
|
|
|
|
41. |
|
|
|
f = x1 + 3x2 + x3 |
− x4 |
→ max |
||||||||||||||||||||||
x |
− x |
|
+ x |
|
|
= 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
+ 2x |
|
+ x |
|
= 3 |
||
|
1 |
|
2 |
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
2 |
|
4 |
|
|
2x1 + x2 |
|
+ x4 = 5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
− x1 + x2 + x3 |
|
|
=1 |
||||||||||
|
xj ≥ 0, j 1: 4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x j ≥ 0, j 1:4 |
|
|
||||||||||
|
X0 = (0 , 0 ,1, 5) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
X 0 |
= (0 , 0 ,1, 3) |
|
|
||||||||||
|
|
|
|
42. |
|
f = 3x1 |
+ 7x2 + 4x3 − 3x4 + 2x5 |
+ 2x6 → max |
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
− x1 + 3x |
2 + 2x3 + x4 + x5 + 3x6 = 3 |
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
4x1 |
− 2x2 − 3x3 − 4x4 + x5 − 7x6 = −2 |
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||
|
|
|
|
|
|
|
x j ≥ 0, |
|
|
|
j 1:6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
X 0 |
= (0 , 0 ,1, 0 ,1, 0) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
218 |
|
|
|
|
|
|
|
|
|
|
|
43. |
f = x1 + 3x2 |
+ 2x3 + 4x4 |
− 2x5 → min |
|||||||||||||||||
|
− x1 |
|
|
|
+ x3 − 2x4 |
|
|
|
|
= −2 |
||||||||||
|
|
|
|
|
x2 − x3 + x4 − 2x5 = 0 |
|||||||||||||||
|
|
|
|
|
||||||||||||||||
|
2x |
+ |
|
x |
2 |
|
|
+ 5x |
4 |
+ x |
5 |
= 7 |
||||||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
x j ≥ 0, |
|
j 1:5 |
|
|
|
|
|
|
|
|
|
|
||||||
|
|
X 0 |
= (3,1,1, 0 , 0) |
|
|
|
|
|
|
|
||||||||||
44. |
f = 3x1 |
− 2x2 + x3 + 3x4 + 3x5 |
→ max |
|||||||||||||||||
|
2x1 − x2 + x3 + x4 + x5 = 2 |
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
− 4x1 + 3 x2 − x3 − x4 − 3x5 = −4 |
|||||||||||||||||||
|
|
3x |
|
+ 2 x |
2 |
+ 3x |
3 |
+ 5x |
4 |
|
|
|
= 3 |
|||||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
x j |
≥ 0, |
|
j 1:5 |
|
|
|
|
|
|
|
|
|||||||
|
|
X 0 |
= (1, 0 , 0 , 0 , 0) |
|
|
|
|
|
|
|||||||||||
45. |
f = x1 + 3x2 − 2x3 − x4 |
+ x5 + 3x6 → max |
||||||||||||||||||
|
|
|
|
x2 + x3 + x4 − x5 + x6 =1 |
||||||||||||||||
|
|
|
− x2 |
− x3 + x4 + 4x5 − 3x6 = −1 |
||||||||||||||||
|
x1 |
|||||||||||||||||||
|
|
|
+ x2 |
|
|
|
|
+ x4 + x5 |
|
|
|
=1 |
||||||||
|
x1 |
|
|
|
|
|
|
|
||||||||||||
|
x |
+ x |
2 |
+ x |
3 |
+ x |
4 |
|
|
|
|
+ x |
6 |
=1 |
||||||
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
x j |
≥ 0, |
|
j 1:6 |
|
|
|
|
|
|
|
|
|||||||
|
|
X 0 |
= (0 ,1, 0 , 0 , 0 , 0) |
|
|
|
|
46-48. Решить следующие ЗЛП, предварительно преобразовав их к канонической форме.
46. f = −x1 + x2 |
− 2x3 + 3x4 + x5 → max |
|||||||||||
x |
+ 2x |
|
− x |
|
− 2x |
|
+ x |
|
≤ 3 |
|||
|
1 |
|
|
2 |
|
3 |
|
|
4 |
|
5 |
|
− x1 |
− x2 + x3 + 2x4 + x5 |
≤1 |
||||||||||
|
2x |
|
+ x |
2 |
+ x |
3 |
− x |
4 |
|
|
|
≤1 |
|
1 |
|
|
|
|
|
|
|
||||
|
x j |
|
≥ 0, |
j 1:5 |
|
|
|
|
|