Линейные задачи оптимизации. Ч.1. Линейное программирование. Лутманов С.В. - 57 стр.

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
57
содержащая эту точку, в противном случае – ее дополнение. На рис.1 линия,
помеченная символом
(
)
i , задается уравнением
,
21
i
ii
byaxa =+
1,,
ik
=
L
,
а положение выбранной полуплоскости относительно границы определяется
направлением стрелки.
O
OO
x
x
x
y
y
y
(i)
(i)
(i)
Рис. 1
Область допустимых значений вектора
),( yx
строится по формуле
0
k
i
i
UU
=
=
.
Множество
U
является либо ограниченным выпуклым многоугольником
(см. левую фигуру на рис. 1), либо неограниченным выпуклым
многоугольником (см. центральную фигуру на рис. 1), либо пустым
множеством (см. правую фигуру на рис. 1).
Пусть
1
RÎ
a
– какое-либо число. Уравнение
a
=+ ycxc
21
определяет линию уровня целевой функции, соответствующую значению
a
.
Эта линия ортогональна вектору
÷
÷
ø
ö
ç
ç
è
æ
=
2
1
с
с
c . При изменении
a
от
¥
-
до
¥
+
она,
смещаясь параллельно самой себе, зачертит всю плоскость. Направление
перемещения линии уровня при возрастании
a
на рис. 1 отмечено стрелкой.
Последняя точка
÷
÷
ø
ö
ç
ç
è
æ
*
*
y
x
множества
U
, через которую линия уровня будет 
3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


содержащая эту точку, в противном случае – ее дополнение. На рис.1 линия,
помеченная символом (i ) , задается уравнением

                                   a i1 x + a i 2 y = b i , i = 1,L, k ,

а положение выбранной полуплоскости относительно границы определяется
направлением стрелки.

       y                               y                      (i)              y


                                                                               (i)
                                 (i)

                             x                                             x                x
       O                               O                                       O

                                                   Рис. 1
             Область допустимых значений вектора ( x, y ) строится по формуле
                                                       k
                                              U = IUi .
                                                    i= 0



       Множество U является либо ограниченным выпуклым многоугольником
(см.       левую   фигуру    на        рис.      1),       либо      неограниченным   выпуклым
многоугольником (см. центральную фигуру на рис. 1), либо пустым
множеством (см. правую фигуру на рис. 1).

       Пусть a Î R 1 – какое-либо число. Уравнение

                                            c1 x + c2 y = a

определяет линию уровня целевой функции, соответствующую значению a .
                                                æс ö
Эта линия ортогональна вектору c = çç 1 ÷÷ . При изменении a от - ¥ до + ¥ она,
                                    è с2 ø

смещаясь параллельно самой себе, зачертит всю плоскость. Направление
перемещения линии уровня при возрастании a на рис. 1 отмечено стрелкой.
                      æx ö
Последняя точка çç * ÷÷ множества U , через которую линия уровня будет
                 è y* ø


                                                   57

Страницы