Линейное программирование. Азарнова Т.В - 3 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Линейное программирование
5
2318
12
xx
+
≤
(1)
−
+
≤
xx
12
39 (2)
210
12
xx
−
≤
(3)
xx
12
00
≥
≥
, .
Решение. Строим область допустимых решений в соответствии с ша-
гом 1 описанного выше алгоритма. В результате получим выпуклый много-
угольник (рис 1.)
Следуя пункту 2 рассмотренного алгоритма, строим линии уровня целевой
функции 42
12
xxd
+
=
и фиксируем направление увеличения значения целе-
вой функции при переходе от одной линии уровня к другой. Перемещая пря-
мую 42
12
xxd
+
=
параллельно самой себе в найденном направлении, пока
она будет сохранять общие точки с допустимой областью , найдем , что в
крайнем возможном положении линия уровня пройдет через точку
*
max
x .
Этому положению линии уровня и соответствует
dd
=
max
. Для нахождения
координат точки
*
max
x необходимо решить систему уравнений:
2318
210
12
12
xx
xx
+=
−=
.
В результате получим искомое оптимальное решение
(
)
X
max
*
,= 62
с
значением целевой функции 28
*
max
=L .
Пример 2. Решить графически следующую задачу:
Рис.1
X2
X1
X1
2
3
d=0
d=28
1
X
*
max
.
                                                     Линейное программирование


                         2x 1 +3x 2 ≤18       (1)
                         −x 1 +3x 2 ≤9        (2)
                          2x 1 −x 2 ≤10       (3)
                              x1 ≥0, x 2 ≥0 .
     Решение. Строим область допустимых решений в соответствии с ша-
гом 1 описанного выше алгоритма. В результате получим выпуклый много-
угольник (рис 1.)




                             2
                    1
                                      d=28


    X2
                                              3
                                         .   X*max




                          X1
                           X1

           d=0
                         Рис.1
Следуя пункту 2 рассмотренного алгоритма, строим линии уровня целевой
функции 4 x 1 +2x 2 =d и фиксируем направление увеличения значения целе-
вой функции при переходе от одной линии уровня к другой. Перемещая пря-
мую 4 x 1 +2x 2 =d параллельно самой себе в найденном направлении, пока
она будет сохранять общие точки с допустимой областью, найдем, что в
                                                                     *
крайнем возможном положении линия уровня пройдет через точку x max     .
Этому положению линии уровня и соответствует d =dmax . Для нахождения
                  *
координат точки x max необходимо решить систему уравнений:
                             � 2x1 +3x 2 =18
                              �                .
                                � 2x1 −x 2 =10
                                                        *
     В результате получим искомое оптимальное решение X max =(6,2) с
значением целевой функции L*max =28 .
     Пример 2. Решить графически следующую задачу:


                                  5

Страницы