E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna
1
WYKŁAD 2_1
PROGRAMOWANIE LINIOWE
optymalizacja metodą graficzną
1.
Funkcja celu:
f(x) = f(x
1
, x
2
) = c
1
x
1
+c
2
x
2
max
2.
Ograniczenia:
g
1
(x) = a
1
x
1
+ b
1
x
2
≤ A
g
2
(x) = g
2
(x
1
, x
2
)
g
3
(x) = g
3
(x
1
, x
2
)
g
4
(x) = x
1
≥ 0
g
5
(x) = x
2
≥ 0
Rozwiązanie graficzne w układzie współrzędnych
(x
1
, x
2
)
znaleźć: x
1
i x
2
f(x) max
Przykład:
Funkcja celu:
f(x) = f(x
1
, x
2
) = 2x
1
+3x
2
max
Ograniczenia:
g
1
(x) = 2x
1
+ 2x
2
≤ 14
(1)
g
2
(x) = 4x
1
≤ 16
(2)
g
3
(x) = x
1
+ 2x
2
≤ 8
(3)
g
4
(x) = x
1
≥ 0
(4)
g
5
(x) = x
2
≥ 0
(5)
Rozwiązanie: jednoznaczne (4, 2),
x
1
= 4;
x
2
= 2
wartość maksymalna funkcji celu:
z(x) = z(x
1
, x
2
) = 2*4 +3*2 = 14
E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna
2
ALGORYTM POSTĘPOWANIA
g
4
(x) = x
1
≥ 0
x
1
≥ 0
x
1
x
2
E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna
3
g
5
(x) = x
2
≥ 0
x
2
≥ 0
x
1
x
2
E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna
4
Część wspólna: g
4
(x) = x
1
≥ 0 i g
5
(x) = x
2
≥ 0
x
1
≥ 0
x
2
≥ 0
x
1
x
2
E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna
5
g
1
(x) = a
1
x
1
+ b
1
x
2
≤ A
ax
1
+ b x
2
≤ c
x
1
x
2
g
1
(x
1
, x
2
) ≤ 0
E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna
6
Część wspólna:
g
1
(x) = a
1
x
1
+ b
1
x
2
≤ A i
g
4
(x) = x
1
≥ 0 i g
5
(x) = x
2
≥ 0
ax
1
+ b x
2
≤ A
x
1
x
2
ax
1
+ b x
2
– A ≤ 0
^ x
1
≥ 0 ^ x
2
≥ 0
E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna
7
g
2
(x) = g
2
(x
1
, x
2
)
x
1
x
2
g
1
(x
1
, x
2
) ≤ 0
g
2
(x
1
, x
2
) ≤ 0
E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna
8
g
3
(x) = g
3
(x
1
, x
2
)
g
1
(x
1
, x
2
) ≤ 0
x
1
x
2
g
2
(x
1
, x
2
) ≤ 0
g
3
(x
1
, x
2
) ≤ 0
E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna
9
Obszar rozwiązań dopuszczalnych
g
1
(x
1
, x
2
) ≤ 0
x
1
x
2
g
2
(x
1
, x
2
) ≤ 0
g
3
(x
1
, x
2
) ≤ 0
OBSZAR
ROZWIĄZAŃ
DOPUSZCZALNYCH
E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna
10
Funkcja celu
g
1
(x
1
, x
2
) ≤ 0
x
1
x
2
g
2
(x
1
, x
2
) ≤ 0
g
3
(x
1
, x
2
) ≤ 0
OBSZAR
ROZWIĄZAŃ
DOPUSZCZALNYCH
z = f (x
1
, x
2
) = 0
E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna
11
Funkcja celu, izolinie
g
1
(x
1
, x
2
) ≤ 0
x
1
x
2
g
2
(x
1
, x
2
) ≤ 0
g
3
(x
1
, x
2
) ≤ 0
z = f (x
1
, x
2
) = 0
90
o
z = f (x
1
, x
2
) max
E. Michlowicz: BO - Programowanie liniowe (2). Metoda graficzna
12
Rozwiązanie optymalne – jedno, jednoznaczne
A (x
1opt
, x
2opt
)
g
1
(x
1
, x
2
) ≤ 0
x
1
x
2
g
2
(x
1
, x
2
) ≤ 0
g
3
(x
1
, x
2
) ≤ 0
A (x
1opt
, x
2opt
)
z = f (x
1
, x
2
) max
z = f (x
1
, x
2
) = 0
x
2opt
X
1opt