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

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
59
Пример 1. Решить
задачу линейного
программирования
графическим методом:
min52),(
®
+
-
=
yxyxI
,
1427
-
£
-
-
yx ,
3065
£
+
yx ,
3824
xy
--£-
,
0,0
³
³
yx .
Проведем необходимые построения.
Из чертежа (рис. 2) видно, что точка
(
)
**
yx , определяется как решение
следующей системы алгебраических уравнений:
2483,3065
-
=
-
-
=
+
yxyx .
Отсюда находим
()
11
21
,,
11
15
,
11
48
-====
*****
yxIIyx .
Графический способ решения применим и для задач линейного
программирования в канонической форме с матрицей ограничений
A
размера
)2(
+
´
mm , для которой
[
,1,2,
rangAmm
==
L
. Продемонстрируем это на
примере для случая 3
=
m .
Пример 2. Решить задачу линейного программирования в канонической форме:
(
)
5432154321
363740,,,, xxxxxxxxxxI ++-+-= ,
55324
54321
=++++ xxxxx ,
465241617
54321
=++-+- xxxxx ,
668472633
54321
=++-+- xxxxx , (1)
0,0,0,0,0
54321
³³³³³ xxxxx .
-2
4
6810
2
4
6
8
-2
-4-6
2
x
y
(
)
**
,
y
x
Рис. 2
3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


                   y                                                                  Пример              1.      Решить
                                                                              задачу                            линейного
                       8
                                                                                                    программирования
                       6                                                      графическим методом:
                       4
                                                                                         I ( x, y ) = -2 x + 5 y ® min ,
                       2
                                       ( x* , y * )
                                                                       x                        - 7 x - 2 y £ -14 ,
  -6     -4   -2            2       4          6      8        10                5 x + 6 y £ 30 , -3 x - 8 y £-24 ,
                       -2

                       Рис. 2                                                                        x ³ 0, y ³ 0 .

       Проведем необходимые построения.

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

                                        5 x + 6 y = 30, - 3x - 8 y = -24 .

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

                                        48        15                         21
                                x* =       , y * = , I * = I (x * , y * ) = - .
                                        11        11                         11

       Графический      способ             решения          применим             и      для         задач      линейного
программирования в канонической форме с матрицей ограничений A размера
m ´ (m + 2) , для которой              rang [ A] = m, m = 1, 2,L . Продемонстрируем это на

примере для случая m = 3 .

       Пример 2. Решить задачу линейного программирования в канонической форме:

                       I (x1 , x 2 , x 3 , x 4 , x 5 ) = -40 x1 + 7 x 2 - 3 x 3 + 6 x 4 + 3 x 5 ,

                                            4 x1 + x 2 + 2 x 3 + x 4 + 3 x 5 = 55 ,

                                       - 17 x1 + 16 x 2 - 4 x 3 + 2 x 4 + 5 x 5 = 46 ,

                                - 33x1 + 26 x 2 - 7 x 3 + 4 x 4 + 8 x 5 = 66 ,                                        (1)

                                         x1 ³ 0, x 2 ³ 0, x 3 ³ 0, x 4 ³ 0, x 5 ³ 0 .


                                                          59

Страницы