Составители:
Рубрика:
73
при условиях
:
=++
=++++
=+++
9
2524
225
531
54321
5421
xxx
xxxxx
xxxx
(2.2.29)
Преобразовав известным нам способом систему (2.2.29) в систему с единичным
базисом, соответствующим базисным переменным x
3
, х
4
, х
5
, получим:
=++−
=++
=+−
3
1623
62
321
421
521
xxx
xxx
xxx
(2.2.30)
Отбрасывая в этих уравнениях неотрицательные переменные x
3
, х
4
, х
5
, получим
систему трех неравенств с переменными x
1
и х
2
:
≤+−
≤+
≤−
.3
;1623
;62
21
21
21
xx
xx
xx
(2.2.31)
Из уравнений (2.2.30) имеем:
+−=
−−=
−+=
.26
;2316
;3
215
214
213
xxx
xxx
xxx
(2.2.32)
Подставляя эти значения x
3
, х
4
, х
5
в линейную форму (2.2.28), выразим ее только
через переменные х
1
и х
2
.
В результате придем к эквивалентной стандартной задаче. Найти неотрицательные
числа х
1
и х
2
, обращающие в максимум линейную форму
z=2x
1
+4x
2
+28 (2.2.33)
при условиях (2.2.31).
Эта задача решается элементарно графическим способом; x
1
=2, x
2
=5 —
оптимальное решение этой задачи и z
макс
= 52. Подставляя это решение в равенства
(2.2.32), найдем оптимальное решение исходной канонической задачи (2.2.28) — (2.2.29):
x
1
=2, x
2
=5, x
3
=0, x
4
=0, x
5
=7.
2.2.2. Двойственные или взаимосопряженные пары задач линейного
программирования
Задачи, двойственные стандартным задачам линейного программирования
Обратимся к стандартной задаче нахождения n-мерного неотрицательного вектора
X=[x
1
,x
2
,…,x
n
], (2.2.34)
который максимизирует скалярное произведение
z = CX (2.2.35)
при условии
АХ
≤
В, (2.2.36)
где А = ||а
ij
||
mxn
—матрица условий;
В = [b
1
, b
2
,..., b
m
] — вектор ограничений;
С=(с
1
, с
2
, . . ., с
п
)—вектор коэффициентов целевой функции.
Приведенной задаче максимизации соответствует следующая стандартная задача минимизации.
Страницы
- « первая
- ‹ предыдущая
- …
- 71
- 72
- 73
- 74
- 75
- …
- следующая ›
- последняя »
