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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

ляют только область допустимых решений.
Неравенства
+
121
ua ,
2222
bua
≤
+
3232131
buaua ≤
+
разделяют всю плос-
кость
(u
1
, u
2
) на две области: запрещенную и разрешенную
(рис. 4.3). Как правило, при геометрическом представлении ограниче-
ний типа неравенств на плоскости наносят штриховку в сторону запре-
щенной области. На рис. 4.3 разрешенной областью является область
АВС0, эта область всегда представляет собой выпуклый многогранник.
В задачах линейного программирования принято максимизиро-
вать функцию цели Q, поэтому оптимальное решение всегда лежит в
вершине допустимого многогранника, образованного ограничения-
ми.
П р и м е р 4.1.
Пусть Q(u) = u
1
+ u
2
→ max, при наличии ограничений на пере-
менные состояния 2u
1
+ u
2
≤ 1, u
1
+ 2u
2
≤ 1, u
1
≥ 0, u
2
≥ 0.
На фазовой плоскости U определяется область допустимых
решений АВС0, которая ограничивается прямыми линиями 2u
1
+ u
2
= 1, u
1
+ 2u
2
= 1, u
1
= 0, u
2
= 0 (рис.
4.4).
u
2
1
A
0
C
u
1
u
1
+ 2u
2
= 1
u
1
+ u
2
= Q
0
2u
1
+ u
2
= 1
B
1
l
Рис. 4.4 Геометрическая интерпретация
задачи линейного программирования
Необходимое условие экстремума функции дает, что
,1
1
=
∂
∂
u
Q
,1
2
=
∂
∂
u
Q
эти производные непрерывны и
не обращаются в нуль, следовательно, экстремальное значение Q достигается лишь на границе области U.
Критерий оптимальности имеет постоянное значение Q
0
вдоль линии l, определяемой уравнением u
1
+ u
2
= Q
0
. Если эту линию перемещать параллельно самой себе, то величина Q
0
, а, следовательно, и значение
критерия Q(u) будет изменяться. Увеличению критерия оптимальности соответствует перемещение линии
в направлении, указанном стрелкой, ее предельное положение, когда она проходит через точку В,
являющуюся вершиной многоугольника АВС0 допустимых решений, отвечает максимальному значению
Q(u). Это максимальное значение определяется координатами вершины В, т.е. координатами точки пере-
сечения уравнений 2u
1
+ u
2
= 1, u
1
+ 2u
2
= 1; ;
3
1
опт1
=u
.
3
2
3
1
maxопт2
== Qu
Если одна из границ допустимой области будет параллельна линии l, то в этом случае задача ли-
нейного программирования имеет в качестве решения бесконечный набор независимых переменных u
1
и u
2
. Критерий оптимальности достигает своего максимального значения вдоль всей линии соответст-
вующего ограничения.
Если допустимая область решений является незамкнутой областью, то максимальное значение кри-
терия оптимальности обеспечивается при бесконечно больших значениях переменных u
1
и u
2
.
4.4 КАНОНИЧЕСКАЯ ФОРМА ЗАДАЧИ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
u
2
22
2
a
b
A
32
3
a
b
0
B
C
21
2
a
b
31
3
a
b
u
1
Рис. 4.3 Геометрическое представле-

Страницы