Линейное программирование. Элементы теории, алгоритмы и примеры. Азарнова Т.В - 4 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Линейное программирование
6
Пример 1. Решить графически следующую задачу линейного програм -
мирования
42
12
xx
+
→
max
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
+=
−=
.
Рис.1
X2
X1
X1
2
3
d=0
d=28
1
X
*
max
. 
Линейное программирование


     Пример 1. Решить графически следующую задачу линейного програм-
мирования
                           4 x 1 +2x 2 → max
                         2x 1 +3x 2 ≤18        (1)
                         −x 1 +3x 2 ≤9         (2)
                          2x 1 −x 2 ≤10        (3)
                              x 1 ≥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 и фиксируем направление увеличения значения целе-
вой функции при переходе от одной линии уровня к другой. Перемещая пря-
мую 4x 1 +2x 2 =d параллельно самой себе в найденном направлении, пока
она будет сохранять общие точки с допустимой областью, найдем, что в
крайнем возможном положении линия уровня пройдет через точку x max   *
                                                                       .
Этому положению линии уровня и соответствует d =dmax . Для нахождения
координат точки x max
                  *
                      необходимо решить систему уравнений:
                              � 2x 1 +3x 2 =18
                               �                 .
                                 � 2x 1 −x 2 =10


                                    6

Страницы