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

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
60
(
)
*2*1
, xx
2
4
68
101214
16
2
6
4
8
-2
-2
1
x
2
x
O
Рис. 3
Здесь матрица ограничений имеет вид
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
--
--=
8472633
5241617
31214
A .
Ее ранг равен трем, так как определитель, составленный из элементов
трех последних столбцов матрицы, отличен от нуля. Действительно
017
847
524
312
¹-=
-
- .
Последнее обстоятельство позволяет представить ограничения (1) в виде
0,0,0216,055,0236
21215214213
³³³--=³++-=³+-= xxxxxxxxxxx
и свести исходную каноническую задачу линейного программирования к
стандартной задаче с матрицей ограничений размера
23
´
. Сформулируем эту
задачу
(
)
min4,
2121
®+-= xxxxI ,
0,0,162,55,623
21212121
³³£+-£--£- xxxxxxxx .
Проведем необходимые построения для реализации графического решения
сформулированной задачи. Из чертежа (рис. 3) видно, что точка
(
)
** 21
, xx
определяется как решение следующей системы алгебраических уравнений: 
3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


    Здесь матрица ограничений имеет вид

                                               æ 4     1  2 1 3ö
                                               ç                 ÷
                                           A = ç - 17 16 - 4 2 5 ÷ .
                                               ç - 33 26 - 7 4 8 ÷
                                               è                 ø

    Ее ранг равен трем, так как определитель, составленный из элементов
трех последних столбцов матрицы, отличен от нуля. Действительно

                                                2 1 3
                                               - 4 2 5 = -17 ¹ 0 .
                                               -7 4 8

    Последнее обстоятельство позволяет представить ограничения (1) в виде

    x 3 = 6 - 3 x1 + 2 x 2 ³ 0,   x 4 = -5 + 5 x1 + x 2 ³ 0,             x 5 = 16 - x1 - 2 x 2 ³ 0,   x1 ³ 0, x 2 ³ 0

    и свести исходную каноническую задачу линейного программирования к
стандартной задаче с матрицей ограничений размера 3 ´ 2 . Сформулируем эту
задачу

                                           I ( x1 , x 2 ) = -4 x1 + x 2 ® min ,

                 3 x1 - 2 x 2 £ 6, - 5 x1 - x 2 £ -5,           x1 + 2 x 2 £ 16, x1 ³ 0, x 2 ³ 0 .

    Проведем необходимые построения для реализации графического решения

                            x2

                                  8

                                  6
                                                        ( x1* , x 2* )
                                  4

                                  2
                                                                                                       x1

                       -2   O          2        4      6        8          10     12     14     16
                                  -2


                                                           Рис. 3
сформулированной задачи. Из чертежа (рис. 3) видно, что точка (x1* , x 2* )
определяется как решение следующей системы алгебраических уравнений:


                                                           60

Страницы