Теория принятия решений

 

1)–1.5p₁+9500 £ 4900;

2)–2.1p₂+7900 £ 5100;

3)–0.67p₃+13200 £ 11300;

4)–1.5p₁–2.1p₂–0.67p₃+29600 £ 15000;

5)p₁ ³ 0;

6)p₂ ³ 0;

7)p₃ ³ 0;

8)V₁ ³ 0;

9)V₂ ³ 0;

10)V₃ ³ 0.

                                    

Составим следующие  матрицы :

           -1.5     0         0                                                -3600                                           

A=      0      -2.1        0                                    B=       -2800                                           

           0          0      -0.67                                            -1900                                           

           -1.5  -2.1    -0.67                                           -14600                                          

          -8500                                                               1.5      0        0    

P=      -7900                                                     C=       0     2.1       0

           -13200                                                              0       0      0.67        

 

n = 3,    m = 4,    N = 7,   2N = 14.

Матрица С выполняет  требования , т.к. является симметричной и положительно  полуопределенной, что гарантирует выпуклость целевой  функции. Для нашей задачи из выражения (5) (см. выше) получим:

                                                                                                                    p1

                                                                                                                    p2    

                                                                                                                    p3         

                                                                                                                    Y1            -3600   

-1.5      0         0      1  0  0  0    0  0  0     0       0      0       0                      Y2            -2800                             

   0     -2.1       0      0  1  0  0    0  0  0     0       0      0       0                      Y3            -1900                    

   0        0     -0.67   0  0  1  0    0  0  0     0       0      0       0                      Y4           -14600                      

-1.5    -2.1  -0.67   0  0  0  1    0  0  0     0       0     0       0              *      V1      =     8500                                       

                                                                                                                    V2             7900                    

3.00    0          0     0  0  0  0   -1  0  0    -1.5   0       0  -1.5                   V3            13200                   

   0     4.2        0     0  0  0  0    0 –1  0     0    -2.1     0     -2.1                    λ1                                       

   0        0      1.34   0  0  0  0    0  0  -1     0      0   - 0.67 -0.67                 λ2                                   

                                                                                                                    λ3                        

                                                                                                                    λ4                                  

 

Откуда можно получить следующие уравнения:

 -1.5*p1 + Y1 = -3600;

-2.1*p2 + Y2 = -2800;

-0.67*p3 +Y3 = -1900;

-1.5*p1 –2.1*p2 – 0.67*p3 + Y4 = -14600;                        (8)

3*p1 – V1 –1.5* λ1 –1.5* λ4 = 8500;

4.2*p2 – V2 – 2.1*λ2 – 2.1*λ4 = 7900;

1.34*p3 – V3 – 0.67*λ3 – 0.67*λ4 = 13200.

Для получения допустимого базисного решения (опорного решения) можно использовать любой метод отыскания опорного решения задачи ЛП. Для системы (8) достаточно выбрать p1,p2,p3,Y1,Y2,Y3,Y4 базисными, тогда:

Значит P1 = 8500/3, P2 = 7900/4.2, P3 = 13200/1.34, Y1 = 650, Y2 = 1150, Y3 = 4800, Y4 = 200– опорное решение. Составим симплекс-таблицу, учтя, что знаки коэффициентов при свободных переменных (в отличии от симплекс-таблицы задачи ЛП) не меняются. Пустые клетки соответствуют нулевым коэффициентам.

 

	1	V1	V2	V3
P1	8500/3	0.33			0.5			0.5
P2	7900/4.2		0.238				0.5	0.5
P3	13200/1.34			0.75			0.5	0.5
Y1	650	0.5			0.75			0.75
Y2	1150		0.5			1.05		1.05
Y3	4800			0.5			0.335	0.335
Y4	200	0.5	0.5	0.5	0.75	0.05	0.335	2.135
V1		1
V2			1
V3				1
					1
						1
							1
								1
α j	0
β j
Θj
Κj

Таблица 2

 

Т.к. α₀=0, то сразу получаем оптимальное решение:

 

P1 = 2833.33;

P2 = 1880.95;

P3 = 9850.746;

Y1=650,Y2=1150,Y3=4800,Y4=200;

V1=0,V2=0,V3=0;

λ1=0,λ2=0,λ3=0,λ4=0.

 

Использование компьютерных средств для решения задачи.

 

Сравним полученное решение  с решением на пакете программ GINO.

Gino – система для  решения задач нелинейного, квадратичного  программирования, разработанная для  широкого круга пользователей.

     С другой  стороны, GINO используется для решения промышленных нелинейных, квадратичных программ значительного размера (более 10000 строк и несколько тысяч переменных).

      Чтобы  решить данную задачу нужно  составить программную модель. Эта модель имеет следующий вид:

 

MODEL:   

       1)max=-1.5*X1^2-2.1*X2^2-0.67*X3^2+8500*X1+7900*X2+13200*X3;

       2)-1.5*X1+7900 < 4900;     

       3) -2.1*X2+7900 < 5100 ;

       4) -0.67*X3+13200 < 11300;

       5) -1.5*X1-2.1*X2-0.67*X3+29600 < 15000;

       6) X1>0 ;

       7) X2 > 0 ;

       8) X3 > 0 ;

 

    END

Программу можно набрать  вручную, либо загрузить из файла c помощью  команды take<имя файла>. Командой Look all можно просмотреть весь этот файл. Чтобы получить решение задачи нужно выполнить команду go.

В результате работы на пакете программ GINO было получено оптимальное решение. Оно совпало с решением задачи “вручную”.

TOTAL FRACTIONAL CHANGE IN OBJECTIVE LESS THAN  1.00000E-04 FOR   4 CONSECUTIVE

ITERATIONS

     OBJECTIVE FUNCTION VALUE

 

         1)  84486352.615718

 

   VARIABLE        VALUE         REDUCED COST

         X1      2833.181956          .000000

         X2      1880.886440          .000000

         X3      9850.676452          .000000

 

        ROW   SLACK OR SURPLUS          PRICE

         2)      1249.772933          .000000

         3)      1149.861344          .000000

         4)      4699.953387          .000000

         5)       199.587665          .000000

         6)      2833.181956          .000000

         7)      1880.886440          .000000

         8)      9850.676452          .000000

 

Список использованной литературы

 

1. Есипов Б.А. Лекции по курсу “Теория принятия решений”, 2001
2. Решение задач по курсу “Исследование операций”: нелинейное программирование. / методические указания, составитель Есипов Б.А., Куйбышев, 1988, 42с.
3. Линейное и нелинейное программирование / под ред. Е.Е. Караваева. – М.: Наука, 1999, 190 с.
4. Кузнецов Ю.Н., Кузубов В.Н., Волощенко А.Б. Математическое программирование. М.: Высшая школа, 1980, 190 с.