Метод цільового програмування

Дата: 2025-06-02; Просмотры: 8

Оценка:

0.00 из 5.00 — оценок

Скачиваний: 0

Скачать

Національний технічний університет України

Київський політехнічний інститут

Інститут телекомунікаційних систем

Домашня контрольна робота

дисципліни «Теорія прийняття рішень та системний аналіз»

на тему «Застосування методів векторної оптимізації для розв’язування задач підвищення ефективності ТКС»

Варіант 6

Виконала: ст..гр.ТЗ-41м

Москвитіна А.О.

Прийняв: Лисенко О.І.

Київ 2014

Методика розрахунків до питання 1

Постановка задачі

Розв’язати задачу багатокритеріальної(векторної) оптимізації:

де ОДР G задана нерівностями

l₁ x₁;

l₂ x₂;

l₃ x₃;

критерії упорядковані за рівнем важливості ( індекс “1” відповідає найважливішому критерію), МЕТОДОМ: ідеальної точки; цільового програмування (р=2; ₁=0.5, ₂=0.3, ₃=0.2); послідовних поступок; рівних та найменших відносних відхилень( ₁=1, ₂=0.5, ₃=0.5; обчислення додаткових обмежень – рівностей виконати із точністю D12=D13=0.1); мінімаксу ( ₁=0.5, ₂=0.25, ₃=0.25).

Таблиця 1. Вихідні данні

Таблиця 1(продовження). Вихідні данні

Метод ідеальної точки

Розв’язок

1.Задамо значення параметрів згідно 6 варіанту завдання:

a₁ = 2;

a₂ = 2;

a₃ = 3;

b₁ = 2;

b₂ = 2;

b₃ = 1;

d₁ = 8;

d₂ = 3;

d₃ = 1;

h₁₁ = 6;

h₁₂ = 11;

h₁₃ = 19;

h₂₁ = 12;

h₂₂ = 8;

h₂₃ = 11;

h₃₁ = 1;

h₃₂ = 1;

h₃₃ = 10;

H₁ = 860;

H₂ = 790;

H₃ = 820;

l₁ = 10;

l₂ = 10;

l₃ = 20;

Таким чином, маємо:

W₁= 2x₁ + 2x₂ + 3x₃ max;

W₂= 2x₁ + 2x₂ + x₃ max;

W₃= 8x₁ + 3x₂ + x₃ max;

де ОДР G задана нерівностями

6x₁ + 11x₂ + 19x₃ 860;

12x₁ + 8x₂ + 11x₃ 790;

x₁ + x₂ + x₃ 820;

l₁ x₁;

l₂ x₂;

l₃ x₃;

2. Використовуючи функцію “linprog” системи комп’ютерної математики MATLAB, обчислимо екстремум кожного окремого критерію на заданій ОДР G(! Пам’ятаємо, що функція “ linprog ” обчислює мінімум критерія):

>> A=[h₁₁ h₁₂ h₁₃;h₂₁ h₂₂ h₂₃;h₃₁ h₃₂ h₃₃]

>> b=[H₁;H₂;H3]

>> lb=[ l₁;l₂;l₃]

>> C1=[a₁ a₂ a₃]

>> C2=[b₁ b₂ b₃]

>> C3=[d₁ d₂ d₃]

Згідно варіанту маємо:

A =

6 11 19

12 8 11

1 1 10

b =

860

790

820

lb =

10

10

20

C1 =

2 2 3

C2 =

2 2 1

C3 =

8 3 1

>> [Xw1,minusW1,flag]=linprog((-1)*C1,A,b,[],[],lb,[])

W1max = -minusW1

[Xw2,minusW2,flag]=linprog( (-1)* C2,A,b,[],[],lb,[])

W2max = -minusW2

[Xw3,minusW3,flag]=linprog((-1)*C3,A,b,[],[],lb,[])

W3max=-minusW3

Optimization terminated.

Xw1 =

28.9286

27.8571

20.0000

minusW1 =

-173.5714

flag =

1

W1max =

173.5714

Optimization terminated.

Xw2 =

28.9286

27.8571

20.0000

minusW2 =

-133.5714

flag =

1

W2max =

133.5714

Optimization terminated.

Xw3 =

40.8333

10.0000

20.0000

minusW3 =

-376.6667

flag =

1

W3max =

376.6667

3. Методи розв’язання задач багатокритеріальної (векторної) оптимізації.

3.1. Метод ідеальної точки.

3.1.1. Знайдемо рівняння площини da*w₁+db*w₂+dc*w₃ = dd, яка задає положення множини Парето, в системі координат W₁W₂W₃O, де

“dd” – визначник матриці d, “da” - визначник матриці a,

“db” - визначник матриці b, “dc ”- визначник матриці c:

W11=W1max;

W12=C2*Xw1;

W13=C3*Xw1;

W21=C1*Xw2;

W22=W2max ;

W23=C3*Xw2;

W31=C1*Xw3;

W32=C2*Xw3;

W33=W3max;

d=[W11 W12 W13;

W21 W22 W23;

W31 W32 W33] ;

dd=det(d)

d =

173.5714 133.5714 335.0000

173.5714 133.5714 335.0000

161.6667 121.6667 376.6667

dd =

8.5292e-004

a=[W12 W13 1;

W22 W23 1;

W32 W33 1] ;

da=det(a)

a =

133.5714 335.0000 1.0000

133.5714 335.0000 1.0000

121.6667 376.6667 1.0000

da =

4.1721e-006

b=[W13 W11 1;

W23 W21 1;

W33 W31 1] ;

db=det(b)

b =

335.0000 173.5714 1.0000

335.0000 173.5714 1.0000

376.6667 161.6667 1.0000

db =

-1.1800e-006

c= [W11 W12 1;

W21 W22 1;

W31 W32 1] ;

dc=det(c)

c =

173.5714 133.5714 1.0000

173.5714 133.5714 1.0000

161.6667 121.6667 1.0000

dc =

8.5487e-007

3.1.2. Рівняння прямої, що проходить через “точку утопії” (W11;W12;W13) в системі координат W₁W₂W₃O перпендикулярно до площини da*w₁+db*w₂+dc*w₃ = dd має вигляд:

(w1-W11)/da = (w2-W22)/db = (w3-W33)/dc.

3.1.3. Знайдемо компромісне рішення

Xkompromis=[x_1kompromis x_2kompromis x_3kompromis]

в системі координат X1X2X3O, використовуючи точку компромісного рішення

Wkompromis=[Wkompromis1 Wkompromis2 Wkompromis3]

в площині Парето da∙w₁+db∙w₂+dc∙w₃ = dd , яка найменше віддалена від точки утопії, шляхом розв’язання системи рівнянь:

da*w₁+db*w₂+dc*w₃ = dd ,

(w1-W11)/da = (w2-W22)/db,

(w1-W11)/da = (w3-W33)/dc

або

[da db dc;

db (-1)*da 0;

dc 0 (-1)* da ] =[dd;db*W11-da*W22;dc*W11-da*W33].

Остаточно маємо

Wkompromis=inv([ da db dc;

db (-1)*da 0;

dc 0 (-1)* da ])*[dd;db*W11-da*W22;dc*W11-da*W33]

Xkompromis=inv([C1;C2;C3])*Wkompromis

Wkompromis =

165.9620

135.7237

375.1075

Xkompromis =

35.8163

24.4860

15.1192

Метод цільового програмування

Розв’язок

1.Задамо значення параметрів згідно варіанту завдання :

a₁ = 2;

a₂ = 2;

a₃ = 3;

b₁ = 2;

b₂ = 2;

b₃ = 1;

d₁ = 8;

d₂ = 3;

d₃ = 1;

h₁₁ = 6;

h₁₂ = 11;

h₁₃ = 19;

h₂₁ = 12;

h₂₂ = 8;

h₂₃ = 11;

h₃₁ = 1;

h₃₂ = 1;

h₃₃ = 10;

H₁ = 860;

H₂ = 790;

H₃ = 820;

L₁ = 10;

L₂ = 10;

L₃ = 20;

2. Використовуючи функцію “linprog” системи комп’ютерної математики MATLAB, обчислимо екстремум кожного окремого критерію на заданій ОДР G(! Пам’ятаємо, що функція “ linprog ” обчислює мінімум критерія):

>> A=[h₁₁ h₁₂ h₁₃;h₂₁ h₂₂ h₂₃;h₃₁ h₃₂ h₃₃]

>> b=[H₁;H₂;H3]

>> lb=[ L₁;L₂;L₃]

>> C1=[a₁ a₂ a₃]

>> C2=[b₁ b₂ b₃]

>> C3=[d₁ d₂ d₃]

A =

6 11 19

12 8 11

1 1 10

b =

860

790

820

lb =

10

10

20

C1 =

2 2 3

C2 =

2 2 1

C3 =

8 3 1

>> [Xw1,minusW1,flag]=linprog((-1)*C1,A,b,[],[],lb,[])

W1max = -minusW1

[Xw2,minusW2,flag]=linprog( (-1)* C2,A,b,[],[],lb,[])

W2max = -minusW2

[Xw3,minusW3,flag]=linprog((-1)*C3,A,b,[],[],lb,[])

W3max=-minusW3

Optimization terminated.

Xw1 =

28.9286

27.8571

20.0000

minusW1 =

-173.5714

flag =

1

W1max =

173.5714

Optimization terminated.

Xw2 =

28.9286

27.8571

20.0000

minusW2 =

-133.5714

flag =

1

W2max =

133.5714

Optimization terminated.

Xw3 =

40.8333

10.0000

20.0000

minusW3 =

-376.6667

flag =

1

W3max =

376.6667

3. Методи розв’язання задач багатокритеріальної (векторної) оптимізації.

3.1. Метод цільового компромісного програмування(MЦKП)

Згідно завданню: р=2; ₁=0.5, ₂=0.3, ₃=0.2.

3.1.1. Побудова файл-функції: File_New_M-file

function CKP=myfunCKPmin(x,C1,C2,C3,W1max,W2max,W3max)

CKP=sqrt(0.5*((C1*[x(1);x(2);x(3)]-W1max)/W1max)^2+0.3*((C2*[x(1);x(2);x(3)]-W2max)/W2max)^2+0.2*((C3*[x(1);x(2);x(3)]-W3max)/W3max)^2);

Save as… myfunCKPmin

3.1.2. Пошук оптимального значення змінних із використанням функції fmincon системи комп’ютерної математики MATLAB:

Формат функції fmincon

[x,W,flag]=fmincon(@myfun,[x₀],[A],[b],[A_eq],[b_eq],[l_b],[u_b],

@mynon,options,P1,P2,…)

[x,Dckp,flag]=fmincon(@myfunCKPmin,lb,A,b,[],[],lb,[],[],[],C1,C2,C3, W1max,W2max,W3max)

Warning: Trust-region-reflective algorithm does not solve this type of problem,

using active-set algorithm. You could also try the interior-point algorithm: set

the Algorithm option to 'interior-point' and rerun.

> In fmincon at 460

In CilProgram at 41

Local minimum possible. Constraints satisfied.

fmincon stopped because the predicted change in the objective function

is less than the default value of the function tolerance and constraints

were satisfied to within the default value of the constraint tolerance.

<stopping criteria details>

Active inequalities (to within options.TolCon = 1e-006):

lower upper ineqlin ineqnonlin

3 2

x =

33.3230

21.2655

20.0000

Dckp =

0.0402

flag =

5