skanuj0003

1

Ćwiczenia 3 (Postać standardowa, kanoniczna, Zadanie dualne).

1. Sprowadź do postaci kanonicznej zadania

' Xi+SX2+^X9^t—^ymaX X\ + 3^2    ^ 1

o-

2. Zbuduj zadanie dualne do zadania

jf"*-

2xi — 3x2 + *3^2 Xi — 2X2 ^ 4

xi ^ 0

X2 ^ 0,X3 € R-

’ 2xi-x₂ + 3®3 Hmin

4xi + 2x2 + 5*3 ^ 10 •

2xi + 3xs ^ 0 Xi — 2x2 ^ 4 *1,*2,*3 ^ 0

5xi + 6x₂ + 10x₃ + 12x4 + 8*5 + 4*6 +10*₇ + 7x₈ *—> min

*i + *5 = 50

*2 + *6 = 80

x₃ + x₇ = 40

*4 + *8 = 60

*1 + *2 + *3 + *4 ^ 220

X5 + x® + x₇ + xg ^ 140

*1» ••■>*8 ^ 0

(Odp. 50yi + S0y₂ + 40ys + 6O2/4 + 2202/5 + 1402/6 ¹—* max, yi+ys ^ 5,3/2 H-1/5 ^ 6,2/3 +2/5 ^ 10,2/4 + 2/5 ^ 12,2/1 + 2/0 ^ 8,y2 + 2/0 < 4,2/3 +y₆ ^ 10,2/4 + 2/0 ^ 7,|/₅,y₅ < 0,yi,2/2,2/3>y4 e K)

* Dla zagadnień

f    20xi + 12x2 + 12x₃ 1—> min (    3xi - 2x₂ + x₄ »—* max    (    x_x + 2x₂ + 5x₃ + 4z₄ >—► max

I    3xi+2x₂ +2xs^ 3    I    2xi-x₂ + 3x₃-x₄ ^ 6    I    xi +x₂ + x_s + x₄ ^10

I    4xi + 4x2 + 8x₃ ^ 9    |    *1 + 2x2 + x₃ + 2x₄ ^4    j    xi + 2x2 + x₃ + 2x₄ ^ 4

l    Xi,X2,X₃^0.    (    Xi,X2,X₃,X₄ ^ 0.    I    *1,*2,*3,*4 ^ 0.

zbuduj zadanie dualne, rozwiąż je metodą geometryczną, oraz korzystając z twierdzeń o dualności wyznacz rozwiązanie zadania prymalnego. (Odp. 1. x_x = x₃ = 0,X2 = 9/4, yi = 0,y2 = 3,(F(x) = 27), 2. xi = 16/5, X2 = x₃ = 0,x₄ = 2/5, yi = y₂ = 1, F(x) = 10, 3) x_x — xa = Zą = 0,x₃ = 4, F(x) = 20)

4. Organizm sportowca wymaga dostarczenia dziennie 400 j. witaminy A i 600 j. witaminy D. W tabeli podano zawartość witamin w 100 g. czterech odżywek dla sportowców 0i,02,0₃,0₄. Zminimalizuj koszty diety sportowca.

Witaminy	Oi	02	O3	04
A	2	6	0	8
D	4	4	1	8
Cena w zł. za 100 g.	30	40	6	64

a)    Sformułuj i rozwiąż graficznie zadanie dualne,

b)    Wyznacz optymalną dietę sportowca,

c)    Jak zmieni się koszt diety, jeśli witaminy A należy dostarczać o 20 j. mniej?

(Odp. a) yi = 2,y2 — 6,Fz?(y) = 4400, b)xi = x₂ = 0,x₃ = 200, £4 = 50, jF(x) = 4400, c) koszt diety spadnie o 40 zł.)

5. Wykaż, że jeśli w zadaniu liniowym

{c^Tx 1—V min

Ax ^ b x > 0.

wektory c, 6 są nieujemne (c, b ^ 0) to wektor x* — 0 jest rozwiązaniem optymalnym.

Wykaż, że jeśli x*,y* są rozwiązaniami dopuszczalnymi programów liniowych symetrycznych

{c^Tx 1—y max ( b^Ty 1—y min Ax ^ b    < A^Ty ^ c

x^0.    I 2/^0.

spełniają warunki komplementamości: x^T(c — A^Ty) = 0, y^T(Ax — b) = 0, to są rozwiązaniami optymalnymi.