Przypomnijmy, Ŝe rozwaŜamy problem
optymalizacji liniowej w postaci
FC:
1
2
1 1
2 2
( ,
,....,
)
.....
MAX(MIN)
n
n n
Z x x
x
c x
c x
c x
=
=
+
+
+
→
Przypomnijmy, Ŝe rozwaŜamy problem
optymalizacji liniowej w postaci
FC:
1
2
1 1
2 2
( ,
,....,
)
.....
MAX(MIN)
n
n n
Z x x
x
c x
c x
c x
=
=
+
+
+
→
O:
WB:
11 1
12 2
1
1
21 1
22 2
2
2
1 1
2 2
.....
.....
.............................
.....
n n
n n
m
m
mn n
m
a x
a x
a x
b
a x
a x
a x
b
a x
a
x
a
x
b
+
+
+
=
+
+
+
≤
+
+
+
≥
0,
1, 2,.....,
j
x
j
n
≥
=
0,
1, 2,.....,
i
b
i
m
≥
=
JeŜeli ograniczenia są równościami to
mówimy o postaci standardowej ZPL i
moŜemy je zapisać następująco:
1
FC:
MAX(MIN)
n
j j
j
Z
c x
=
=
→
∑
1
O:
n
ij j
i
j
a x
b
=
=
∑
0,
1, 2,.....,
i
b
i
m
≥
=
WB:
0,
1, 2,.....,
j
x
j
n
≥
=
wykorzystując zapis macierzowy ZPL w
postaci standardowej moŜemy zapisać
następująco:
(
)
Z
=
→
T
FC:
c x
MAX MIN
=
O: Ax b
0,
≥
b
0
≥
WB: x
gdzie:
11
12
1
21
22
2
1
2
n
n
m
m
mn
a
a
a
a
a
a
a
a
a
=
⋯
⋯
⋮
⋮
⋱
⋮
⋯
A
1
2
n
c
c
c
=
⋮
c
1
2
n
x
x
x
=
⋮
x
1
2
n
b
b
b
=
⋮
b
Metoda geometryczna
ZPL moŜe mieć rozwiązania dopuszczalne
lub być zadaniem sprzecznym nie mającym
rozwiązania dopuszczalnego.
JeŜeli ZPL ma rozwiązania dopuszczalne, to
zachodzi jedna z trzech moŜliwości:
• istnieje jedno rozwiązanie optymalne
• istnieje wiele rozwiązań optymalnych
• brak rozwiązania optymalnego
Problem znajdowania rozwiązania ZPL
metodą geometryczną sprowadza się do:
• wyznaczania półpłaszczyzn
odpowiadających poszczególnym
nierównościom
• znalezienia części wspólnej dla wszystkich
półpłaszczyzn, czyli zbioru rozwiązań
dopuszczalnych (ZRD)
• wyszukania w ZRD rozwiązania
najlepszego dla przyjętej funkcji celu
(rozwiązania optymalnego)
JeŜeli ZRD jest zbiorem pustym lub zbiorem
nieograniczonym w kierunku wzrostu
wartości funkcji celu dla zadania na
maksimum bądź spadku dla zadania na
minimum, to zadanie nie ma rozwiązania
optymalnego.