Badania Operacyjne www.pure6.neostrada.pl

Wykład 04 2004-11-08

PROGRAM DUALNY - ZADANIE

Program Pierwotny:

x₁,…,x₄ ≥ 0

warunki ograniczające:

x₁+2x₂+1,5x₃+6x₄ ≤ 90000

2x₁+2x₂+1,5x₃+4x₄ ≤ 120000

funkcja:

f(x₁,…,x₄) = 4x₁+6x₂+3x₃+12x₄ » max

Program Dualny:

a) y₁+2y₂ ≥ 4 (4;0) (0;2)

b) 2y₁+2y₂ ≥ 6 (3;0) (0;3)

c) 1,5y₁+1,5y₂ ≥ 3 (2;0) (0;2)

d) 6y₂+4y₂ ≥ 12 (2;0) (0;3)

y₁,y₂ ≥ 0

f(y₁,y₂) = 90000y₁ + 120000y₂ » min

ZRD - Zbiór rozwiązań dopuszczalnych

90000y₂ + 120000y₂ = 360000 (4;0) (0;3)

Q - rozwiązanie optymalne PD

y₁+2y₂ = 4

2y₁ + 2y₂ =6

-y₁-2y₂ = -4

2y₁ +2y₂ =6

y₁ = 2

y₂ = 1 Q = (2;1)

Wartość funkcji celu wynosi:

f (2;1) = 90000 ∙ 2 + 120000 ∙ 1 = 180000 + 120000 = 300000

	Y1	Y2	F (y1,y2)
P	0	3	360 000
Q	2	1	300 000
S	4	0	360 000

Punkt Q stanowi rozwiązanie optymalne PROGRAMU DUALNEGO, a wartość funkcji celu jest wtedy minimalna i wynosi 300000

Po podstawieniu rozwiązania optymalnego Programu dualnego do warunków ograniczających programu dualnego otrzymujemy:

x₃* = x₄* = 0

x₁+2x₂ = 90000

2x₁ +2x₂ = 120000

x₂* = 30000

x₁* = 30000

Rozwiązaniem optymalnym PROGRAMU PIERWOTNEGO jest wektor, którego elementami są :

x₁* = 30000, x₂* = 30000, x₃* = 0, x₄* = 0. Wartość funkcji celu jest wtedy max i wynosi:

f (30000;30000) = 4 ∙ 30000 + 6 ∙ 30000 + 3 ∙ 0 + 12 ∙ 0 = 120000 +180000 + 0 + 0 = 300000

---