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

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
61
162,623
2121
=+=- xxxx .
Отсюда находим
()
4
67
,,
4
21
,
2
11
2121
-====
*****
xxIIxx .
Таким образом, решением исходной задачи будет
()
4
67
,,,,,0,
4
111
,0,
4
21
,
2
11
5432154321
-=======
*****
******
xxxxxIIxxxxx .
Заметим, что в полученном решении число содержащихся в нем нулей в
точности совпадает с разностью между числом переменных в канонической
задаче линейного программирования и рангом матрицы ограничений. Ниже
будет установлена закономерность такого результата.
3.2. Угловые точки допустимого множества канонической задачи.
Дадим формальное определение интуитивно легко представляемому понятию
угловой точки множества в пространстве
n
R
.
Определение 1. Точка
n
RUv ÌÎ называется угловой точкой множества
U
, если ее представление в виде
21
)1( vvv
aa
-+= , Uvv Î
21
, ,
(
)
1,0Î
a
возможно лишь при vvv ==
21
.
Геометрический смысл данного определения состоит в том, что угловая
точка не может быть внутренней точкой ни одного отрезка, принадлежащего
множеству
U
.
Пример 3.
Для обеих множеств,
изображенных рис. 4, точка А –
угловая, а точка В – нет.
Изучим структуру угловых точек допустимого множества канонической
задачи линейного программирования
A
B
A
B
Рис. 4
3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


                                          3 x1 - 2 x 2 = 6, x1 + 2 x 2 = 16 .

    Отсюда находим

                                          11         21                                    67
                                  x1* =      , x 2* = ,       I * = I ( x1* , x 2* ) = -      .
                                           2         4                                     4

    Таким образом, решением исходной задачи будет

               11         21                  111                                                                67
       x1* =      , x 2* = , x 3* = 0, x 4* =     , x 5* = 0, I * = I (x1 * , x 2 * , x 3 * , x 4 * , x 5 * ) = - .
                2         4                    4                                                                  4

    Заметим, что в полученном решении число содержащихся в нем нулей в
точности совпадает с разностью между числом переменных в канонической
задаче линейного программирования и рангом матрицы ограничений. Ниже
будет установлена закономерность такого результата.

      3.2. Угловые точки допустимого множества канонической задачи.
Дадим формальное определение интуитивно легко представляемому понятию
угловой точки множества в пространстве R n .

    Определение 1. Точка v Î U Ì R n называется угловой точкой множества
U , если ее представление в виде

                                   v = av1 + (1 - a )v2 , v1 , v 2 Î U , a Î (0,1)

возможно лишь при v1 = v2 = v .

    Геометрический смысл данного определения состоит в том, что угловая
точка не может быть внутренней точкой ни одного отрезка, принадлежащего
множеству U .

                                                                              Пример 3.

       B                                      B           A                Для                обеих        множеств,
                     A                                             изображенных                   рис. 4, точка А –

                      Рис. 4                                       угловая, а точка В – нет.

    Изучим структуру угловых точек допустимого множества канонической
задачи линейного программирования

                                                              61

Страницы