Математические методы принятия решений. Бодров В.И - 46 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Различные методы задач линейного программирования предъявляют определенные требования к
типам ограничений. Так, некоторые из них требуют, чтобы ограничения были только типа равенств, т.е.
()
max,...
2211
→+++=
nn
uCuCuCuQ при условии
.0,0,0
;...,
...
;...,
;...,
21
2211
22222221
11212111
≥≥≥
=+++
=+++
=+++
n
mnmnmm
nn
nn
uuu
buauaua
buauaua
buauaua
Задача линейного программирования в такой постановке получила название канонической формы
задачи линейного программирования.
Общую задачу линейного программирования (4.1) – (4.4) можно свести к канонической форме вве-
дением дополнительных переменных u
n+ι
, mli −= ,1 . Для этого в каждом неравенстве прибавляется до-
полнительная переменная, которая превращает неравенство в равенство
lmlnnlll
mnnmmm
buuauaua
buuaaua
n
n
=++++
=
+
+
+
+
−+
+++++
...,
...
,..,
21
111111
21
21
,
тогда система ограничений может быть записана в единой форме
lbua
j
mln
j
j
,1,
1
=ι=
ι
−+
=
ι
∑
.
Дополнительные переменные формально могут быть включены в критерий оптимальности исходной
задачи, т.е.
()
ι
−+
=ι
ι
∑
= uCuQ
mln
1
, где С
ι
= 0 для ι > n.
Таким образом, общую задачу линейного программирования
(4.1) – (4.4) свели к канонической форме
()
max
1
→=
ι
−+
=ι
ι
∑
uCuQ
mjn
(4.5)
при ограничениях
mlnjulbua
jj
mln
j
j
−+=≥=ι=
ι
−+
=
ι
∑
,1,0,,1,
1
. (4.6)
Геометрическое представление можно осуществить только в случае двух переменных. Пусть требу-
ется найти максимум функции
()
2211
uCuCuQ += при ограничениях .0,0,
212211
≥≥
<
+
uubuaua
В рассмотрение вводится дополнительная переменная u
3
, которая неравенство 0
3
≥u превращает в
равенство
buuaua =++
32211
или
32211
ubuaua
−
=+ .
Геометрическое представление получаемой области допустимых решений после введения дополни-
тельной переменной u
3
изображено на рис. 4.5.

Страницы