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

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
56
3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ
3.1. Графический метод. Рассмотрим задачу линейного
программирования в стандартной форме для .2
=
n Обозначим
(
)
yxuuyux ,,,
21
=== .
Задача 1.
12
min(max)
cxcy
+®
,
1
1112
12
1
1112
12
,
,
,
,
0,0.
m
mm
m
mm
k
kk
axayb
axayb
axayb
axayb
xy
+
++
+£
+£
+³
+³
³³
LLLLLL
LLLLLL
Опишем графический метод решения этой задачи. Полагаем
2
0
x
UuRxy
y
ìü
æö
ïï
ïï
÷
ç
==÷γ³
íý
ç
÷
ç
÷
ç
ïï
èø
ïï
îþ
212
1111212
,,
m
mmm
xx
UuRaxaybUuRaxayb
yy
ìüìü
æöæö
ïïïï
ïïïï
÷÷
çç
==÷Î+£==÷Î+£
íýíý
çç
÷÷
çç
÷÷
çç
ïïïï
èøèø
ïïïï
îþîþ
LL
212
1111212
,
k
mmmkkk
xx
UuRaxaybUuRaxayb
yy
+++
ìüìü
æöæö
ïïïï
ïïïï
÷÷
çç
==÷Î+³==÷Î+³
íýíý
çç
÷÷
çç
÷÷
çç
ïïïï
èøèø
ïïïï
îþîþ
LL .
Множество
0
U представляет собой положительный квадрант плоскости
XOY , а множества
i
U – полуплоскости с границами
12
i
ii
axayb
+=
,
1,,
ik
=
L
. Для
определения той половины плоскости, с которой отождествляется множество
i
U , достаточно проверить, удовлетворяет ли соответствующему неравенству
какая-нибудь точка, например точка 0. Если да, то берется полуплоскость, 
3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


                3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО
                                         ПРОГРАММИРОВАНИЯ


       3.1.          Графический                 метод.             Рассмотрим          задачу         линейного
программирования                     в     стандартной                форме       для    n = 2.       Обозначим
x = u 1 , y = u 2 , u = ( x, y ) .

       Задача 1.

                                                c1 x + c2 y ® min(max) ,

                                                 a11 x + a12 y £ b1 ,
                                                LLLLLL
                                                 am1 x + am 2 y £ b m ,
                                                 am +11 x + am+12 y ³ b m+1 ,
                                                LLLLLL
                                                 ak 1 x + ak 2 y ³ b k ,
                                                 x ³ 0, y ³ 0.

       Опишем графический метод решения этой задачи. Полагаем

                                                ïì     æ xö                     ïü
                                         U 0 = ïí u = çç ÷÷÷ Î R 2 x ³ 0, y ³ 0ïý ,
                                                 ïîï   çè y ÷ø                   ïþï

              ìï     æ xö                            üï          ìï     æ xö                              üï
        U1 = ïí u = çç ÷÷÷ Î R 2 a11 x + a12 y £ b1 ïý ,LLU m = ïí u = çç ÷÷÷ Î R 2 am1 x + am 2 y £ b m ïý ,
               ïîï   çè y÷ø                           ïþï         ïîï   çè y÷ø                             ïþï

             ìï     æ xö                                üï          ìï     æ xö                               üï
    U m+1 = ïí u = çç ÷÷÷ Î R 2 am+11 x + am+12 y ³ b1 ïý ,LLU k = ïí u = çç ÷÷÷ Î R 2 ak 1 x + ak 2 y ³ b k ïý .
              ïîï   çè y÷ø                               ïþï         ïïî   çè y ÷ø                             ïþï

       Множество U 0 представляет собой положительный квадрант плоскости
XOY , а множества U i – полуплоскости с границами ai1 x + ai 2 y = bi , i = 1,L, k . Для

определения той половины плоскости, с которой отождествляется множество
U i , достаточно проверить, удовлетворяет ли соответствующему неравенству

какая-нибудь точка, например точка 0 . Если да, то берется полуплоскость,



                                                               56

Страницы