Standardowe zadanie
programowania liniowego
Gliwice
1
Standardowe zadanie programowania liniowego
Rozważamy proces, w którym zmiennymi są x1, x2, & , xn.
Proces poddany jest m ograniczeniom, zapisanymi w postaci
a11x1 + a12x2 + ...+ a1nxn = b1
a21x1 + a22x2 + ...+ a2nxn = b2
(1)
...
am1x1 + am2x2 + ...+ amnxn = bm
aij, bi  znane współczynniki
Gliwice
2
Standardowe zadanie programowania liniowego
Dopuszczamy jedynie nieujemne wartości xj, czyli:
xj e" 0, j =1,2, ...,n
(2)
Zakładamy również, że:
bi e" 0, i =1,2, ...,m
(3)
Z procesem jest związana funkcja celu Z:
Z = c1x1 + c2x2 + ...+ cnxn
(4)
cj, j = 1,2, & ,n  znane współczynniki
Gliwice
3
Standardowe zadanie programowania liniowego
Zagadnienie polega na maksymalizacji (minimalizacji) funkcji
celu Z (4), spełniającej ograniczenia (1), (2), (3).
Model matematyczny:
n
FC : Z =
"c xj MAX
j
j=1
m
ż#
"a xj = bi
ij
�#
j=1 (5)
�#
�#x e" 0,
O : j =1,2, ...,n
�#
j
�#b e" 0,
i =1,2, ...,m
i
�#
�#
�#
Gliwice
4
Standardowe zadanie programowania liniowego
Zapis w postaci macierzowej
FC : Z = cTx MAX
Ax = b
ż#
(6)
�#
O: x e" 0
�#
�#
b e" 0
�#
a11 a12 ... a1n c1 x1 b1
Ą# ń#Ą# ń#Ą# ń# Ą# ń#
ó#aa22 ... a2n Ą#ó#c Ą#ó#x Ą# ó#b Ą#
21 2 2
ó# Ą#ó# Ą#ó# Ą# ó# Ą#
A = c =2
x = b =
ó# ... ... ... ... Ą#ó#...Ą#ó#...Ą# ó#...Ą#
ó#aam2 ... amn Ą#ó#c Ą#ó#x Ą# ó#b Ą#
Ł# m1 Ś#Ł# n Ś#Ł# n Ś# Ł# n Ś#
Gliwice
5
Standardowe zadanie programowania liniowego
Bardzo powszechną w zagadnieniach praktycznych odmianą

ograniczeń są ograniczenia w postaci nierówności.
To również, są zagadnienia programowania liniowego, ale
nie w postaci standardowej.
Gliwice
6
Standardowe zadanie programowania liniowego
Przykład 1
Zakład zamierza rozpocząć produkcję dwóch wyrobów: F1 i F2.
Wśród środków produkcyjnych, które zostaną użyte w procesie
produkcji dwa są limitowane. Limity te wynoszą: dla środka
pierwszego S1 63 kilogramów, dla środka drugiego S2 64
kilogramy. Aby wyprodukować jeden produkt F1 potrzeba 9 kg
środka S1 oraz 8 kg środka S2. Aby wyprodukować jeden produkt
F2 potrzeba 7 kg środka S1 oraz 8 kg środka S2. Produkt F1 będzie
wytwarzany jednocześnie na 3 maszynach, a produkt F2 na
2 maszynach. Koszty przestrojenia maszyn zwrócą się po
wyprodukowaniu łącznie 6 sztuk wyrobów.
Wiedząc, że cena F1 będzie wynosić 6 zł, a cena F2 5 zł określić
wielkość produkcji, która zoptymalizuje zysk ze sprzedaży.
Gliwice
7
Standardowe zadanie programowania liniowego
F1 F2
S1
9763
1
S2
8864
2
ilość
3 32 6
maszyn
cena 65
Gliwice
8
Standardowe zadanie programowania liniowego
Zmienne decyzyjne:
x1  wielkość produkcji F1
x2  wielkość produkcji F2
Gliwice
9
Standardowe zadanie programowania liniowego
Funkcja celu (FC):
Z x1, x2 = 6x1 + 5x2 MAX
( )
Ograniczenia (O):
9x1 + 7x2 d" 63
1
8x1 + 8x2 d" 64
2
3x1 + 2x2 e" 6
3
Warunki brzegowe (WB):
x1 e" 0, x2 e" 0
Gliwice
10
Standardowe zadanie programowania liniowego
Zadanie programowania liniowego
Z x1, x2 = 6x1 + 5x2 MAX
FC: ( )
O:
9x1 + 7x2 d" 63
1
x1 + x2 d" 8
2
3x1 + 2x2 e" 6
3
x1 e" 0, x2 e" 0
WB:
Ograniczenia w postaci nierówności.

To nie jest standardowe zadanie programowania liniowego.
Gliwice
11
Metoda geometryczna
Gliwice
12
Sprowadzenie modelu
do postaci bazowej
Gliwice
13
Sprowadzenie modelu do postaci bazowej
Przykład 2
Model matematyczny z Przykładu 1 sprowadzić do
postaci bazowej.
Gliwice
14
Sprowadzenie modelu do postaci bazowej
9x1 + 7x2 d" 63
Ograniczenie
1
Aby otrzymać ograniczenie w postaci równania wprowadzamy
dodatkową zmienną do ograniczenia:
9x1 + 7x2 + x3 = 63
x3  zmienna bilansująca
Zmienna bilansująca x3 określa ilość środka S1 jaki nie zostanie
wykorzystany w procesie produkcji.
Gliwice
15
Sprowadzenie modelu do postaci bazowej
x1 + x2 d" 8
Ograniczenie
2
Aby otrzymać ograniczenie w postaci równania wprowadzamy
dodatkową zmienną do ograniczenia (analogicznie jak dla
pierwszego ograniczenia):
x1 + x2 + x4 = 8
x4  zmienna bilansująca
Zmienna bilansująca x4 określa ilość środka S2 jaki nie zostanie
wykorzystany w procesie produkcji.
Gliwice
16
Sprowadzenie modelu do postaci bazowej
3x1 + 2x2 e" 6
Ograniczenie
3
Aby otrzymać ograniczenie w postaci równania wprowadzamy
dodatkową zmienną do ograniczenia:
3x1 + 2x2 - x5 = 6
x5  zmienna bilansująca
Gliwice
17
Sprowadzenie modelu do postaci bazowej
W postaci bazowej, w każdym ograniczeniu musi znajdować

się jedna zmienna, która po wyzerowaniu wszystkich
pozostałych zmiennych w ograniczeniu jest nieujemna.
Wprowadzamy kolejną zmienną:
3x1 + 2x2 - x5 + x6 = 6
x6  zmienna sztuczna
Gliwice
18
Sprowadzenie modelu do postaci bazowej
Rozwiązanie zadania po wprowadzeniu zmiennej sztucznej

nie jest równoważne z rozwiązaniem zadania
początkowego.
Byłoby równoważne tylko wtedy, gdyby w rozwiązaniu

optymalnym zmienna sztuczna miała wartość zero.
Gliwice
19
Sprowadzenie modelu do postaci bazowej
Aby zapewnić x6 = 0 w rozwiązaniu optymalnym, każdą

zmienną sztuczną wprowadza się do funkcji celu.
Współczynnik przy zmiennej sztucznej w funkcji celu

dobiera się tak, aby niezerowa wartość tej zmiennej mocno
pogarszała wartość funkcji celu.
Z x1, x2, x6 = 6x1 + 5x2 + Mx6 MAX
FC: ( )
M = -1000
Gliwice
20
Sprowadzenie modelu do postaci bazowej
Czy zmienne bilansujące należy uwzględnić w funkcji celu?
Tak.
Z jakimi współczynnikami?
Wszystkie współczynniki przy zmiennych bilansujących
w funkcji celu mają wartość równą zero.
Z x1, x2, x3, x4, x5, x6 = 6x1 + 5x2 + 0x3 + 0x4 + 0x5 -1000x6 MAX
()
Gliwice
21
Sprowadzenie modelu do postaci bazowej
Postać bazowa zadania z Przykładu 1:
FC:
Z x1, x2, x3, x4, x5, x6 = 6x1 + 5x2 + 0x3 + 0x4 + 0x5 -1000x6 MAX
( )
O:
9x1 + 7x2 + x3 = 63
1
x1 + x2 + x4 = 8
2
3x1 + 2x2 - x5 + x6 = 6
3
WB:
x1 e" 0, x2 e" 0, x3 e" 0, x4 e" 0, x5 e" 0, x6 e" 0
Gliwice
22
Sprowadzenie modelu do postaci bazowej
Sprowadzenie do postaci bazowej ograniczenia typu:
x1 + 2x2 = 4
Wprowadzamy zmienną sztuczną:
x1 + 2x2 + x3 = 4
Zmienną sztuczną x3 należy uwzględnić w funkcji celu w podany
poprzednio sposób, czyli tak, aby jej niezerowa wartość mocno
pogarszała wartość funkcji celu.
Gliwice
23
Sprowadzenie modelu do postaci bazowej
Postać bazowa:
Wszystkie ograniczenia w postaci równań
W każdym ograniczeniu znajduje się zmienna, która po
wyzerowaniu pozostałych zmiennych ma wartość nieujemną
Współczynnik przy zmiennej sztucznej ma wartość 1
Wprowadzone zmienne bilansujące wprowadza się do
funkcji celu z zerowymi współczynnikami
Wprowadzone zmienne sztuczne uwzględnia się w funkcji
celu ze współczynnikami mocno pogarszającymi jej wartość
Gliwice
24
Metoda simpleks
Gliwice
25
Metoda simpleks
Przykład 3
Rozwiązać zadanie z Przykładu 1 metodą simpleks.
Gliwice
26
Metoda simpleks
Tablica simpleks:
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
Gliwice
27
Metoda simpleks
Tablica simpleks:
cTxMAX 6 5 0 0 0 -1000
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
97100063
1101008
3200-116
Gliwice
28
Metoda simpleks
Tablica simpleks:
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
97100063
1101008
3200-116
Gliwice
29
Metoda simpleks
Tablica simpleks:
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
97100063
x3 0
x4 0 1101008
x5 -1000 3200-116
Gliwice
30
Metoda simpleks
Tablica simpleks:
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 097100063
x4 01101008
x6 -1000 3 2 0 0 -1 1 6
zj -3000
z1 = 0�"9 + 0�"1+ -1000 �"3 = -3000
( )
Gliwice
31
Metoda simpleks
Tablica simpleks:
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 097100063
x4 01101008
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000
z2 = 0�"7 + 0�"1+ -1000 �" 2 = -2000
( )
Gliwice
32
Metoda simpleks
Tablica simpleks:
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 097100063
x4 01101008
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0
z3 = 0�"1+ 0�"0 + -1000 �"0 = 0
( )
Gliwice
33
Metoda simpleks
Tablica simpleks:
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 097100063
x4 01101008
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0 0
z4 = 0�"0 + 0�"1+ -1000 �"0 = 0
( )
Gliwice
34
Metoda simpleks
Tablica simpleks:
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 097100063
x4 01101008
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0 0 1000
z5 = 0�"0 + 0�"0 + -1000 �" -1 = 1000
( ) ( )
Gliwice
35
Metoda simpleks
Tablica simpleks:
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 097100063
x4 01101008
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0 0 1000 -1000
z6 = 0�"0 + 0�"0 + -1000 �"1 = -1000
( )
Gliwice
36
Metoda simpleks
Tablica simpleks:
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 097100063
x4 01101008
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0 0 1000 -1000
cj  zj -3006
c1 - z1 = 6 - -3000 = 3006
()
Gliwice
37
Metoda simpleks
Tablica simpleks:
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 097100063
x4 01101008
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0 0 1000 -1000
cj  zj 3006 2005
c2 - z2 = 5 - -2000 = 2005
()
Gliwice
38
Metoda simpleks
Tablica simpleks:
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 097100063
x4 01101008
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0 0 1000 -1000
cj  zj 3006 2005 0
c3 - z3 = 0 - 0 = 0
Gliwice
39
Metoda simpleks
Tablica simpleks:
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 097100063
x4 01101008
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0 0 1000 -1000
cj  zj 3006 2005 0 0
c4 - z4 = 0 - 0 = 0
Gliwice
40
Metoda simpleks
Tablica simpleks:
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 097100063
x4 01101008
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0 0 1000 -1000
cj  zj 3006 2005 0 0 -1000
c5 - z5 = 0 -1000 = -1000
Gliwice
41
Metoda simpleks
Tablica simpleks:
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 097100063
x4 01101008
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0 0 1000 -1000
cj  zj 3006 2005 0 0 -1000 0
c6 - z6 =-1000 - -1000 = 0
( )
Gliwice
42
Metoda simpleks
cj  zj wskaz
niki optymalności
Dla zmiennych bazowych wskaz
niki optymalności zawsze

są równe 0.
Gliwice
43
Metoda simpleks
Kryterium optymalności
Rozwiązanie jest optymalne, jeżeli wartości wszystkich
wskaz
ników optymalności są niedodatnie.
Rozwiązanie w bazie [x3, x4, x6] nie jest rozwiązaniem optymalnym.
Należy przejść do następnej bazy
Gliwice
44
Metoda simpleks
Kryterium wejścia do bazy
Do bazy wchodzi zmienna, która ma największą wartość
wskaz
nika optymalności.
Jeżeli największa wartość wskaz
nika optymalności

odpowiada więcej niż jednej zmiennej, wybieramy zmienną
o niższym indeksie.
W przykładzie kryterium wejścia spełnia zmienna x1.
Gliwice
45
Metoda simpleks
Kryterium wyjścia z bazy
Obliczamy ilorazy wyrazów wolnych (kolumna bi) przez elementy
(tylko dodatnie) kolumny zmiennej wchodzącej do bazy.
Bazę opuszcza ta zmienna, dla której obliczony iloraz jest
najmniejszy.
Jeżeli najmniejsza wartość ilorazu występuje dla więcej niż

jednej zmiennej, to jako zmienną opuszczającą bazę można
wybrać dowolną z nich.
Gliwice
46
Metoda simpleks
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 097100063
x4 01101008
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0 0 1000 -1000
cj  zj 3006 2005 0 0 -1000 0
x3 : 63/9 = 7 x4 : 8/1 = 8 x6 : 6/3 = 2
W przykładzie kryterium wyjścia spełnia zmienna x6.
Gliwice
47
Metoda simpleks
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 097100063
x4 01101008
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0 0 1000 -1000
cj  zj 3006 2005 0 0 -1000 0
Gliwice
48
Metoda simpleks
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 097100063
x4 01101008
x1 6 1 2/3 0 0 -1/3 1/3 2
zj
cj  zj
3 2 0 0 -1 16 / 3
Gliwice
49
Metoda simpleks
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 097100063
x4 0 0 1/3 0 1 1/3 -1/3 6
x1 6 1 2/3 0 0 -1/3 1/3 2
* (-1)
zj
cj  zj
+
1 1 0 1 0 08
Gliwice
50
Metoda simpleks
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 001103-3 45
x4 0 0 1/3 0 1 1/3 -1/3 6
x1 6 1 2/3 0 0 -1/3 1/3 2
* (-9)
zj
cj  zj
+
9 7 1 0 0 063
Gliwice
51
Metoda simpleks
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 001103-3 45
x4 0 0 1/3 0 1 1/3 -1/3 6
x1 6 1 2/3 0 0 -1/3 1/3 2
zj 6400-22
cj  zj 0 1 0 0 2 -1002
Rozwiązanie w bazie [x3, x4, x1] nie jest rozwiązaniem optymalnym.
Gliwice
52
Metoda simpleks
Do bazy wchodzi zmienna: x5
Ilorazy:
x3 : 45/ 3 = 7
x4 : 6 / 1/ 3 =18
( )
x1 : -
ujemny współczynnik  nie liczymy ilorazu
Z bazy wychodzi zmienna: x3
Gliwice
53
Metoda simpleks
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x5 0 0 1/3 1/3 0 1 -1 15
x4 0 0 2/9 -1/9 1 0 0 1
x1 61 7/9 1/9 0007
zj 6 14/3 2/3 0 0 0
cj  zj 0 1/3 -2/3 0 0 -1000
Rozwiązanie w bazie [x5, x4, x1] nie jest rozwiązaniem optymalnym.
Gliwice
54
Metoda simpleks
Do bazy wchodzi zmienna: x2
Ilorazy:
x5 : 15 / 1/ 3 = 45
( )
x4 : 1/ 2 / 9 = 4.5
()
x1 : 7 / 7 / 9 = 9
()
Z bazy wychodzi zmienna: x4
Gliwice
55
Metoda simpleks
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x5 0 0 0 1/2 -3/2 1 -1 27/2
x2 501 -1/2 9/2 00 9/2
x1 6 1 0 1/2 -7/2 0 0 7/2
zj 65 1/2 3/2 00
cj  zj 0 0 -1/2 -3/2 0 -1000
Rozwiązanie w bazie [x5, x2, x1] jest rozwiązaniem optymalnym.
Gliwice
56
Metoda simpleks
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x5 0 0 0 1/2 -3/2 1 -1 27/2
x2 501 -1/2 9/2 00 9/2
x1 6 1 0 1/2 -7/2 0 0 7/2
zj 65 1/2 3/2 00
cj  zj 0 0 -1/2 -3/2 0 -1000
Zmienne bazowe: x5 = 27/2 x2 = 9/2 x1 = 7/2
Zmienne niebazowe: x3 = 0 x4 = 0 x6 = 0
Gliwice
57
Metoda simpleks
Rozwiązanie:
x1 = 3.5 x2 = 4.5 x3 = 0 x4 = 0 x5 = 13.5 x6 = 0
Funkcja celu:
Z x1, x2, x3, x4, x5, x6 = 43.5
( )
Gliwice
58
Różnice w algorytmie
metody simpleks na
MAX i MIN
Gliwice
59
Różnice w algorytmie metody simpleks na MAX i MIN
Kryterium wejścia do bazy
MAX:
Zmienna z największą wartością wskaz
nika optymalności.
MIN:
Zmienna z najmniejszą wartością wskaz
nika optymalności.
Gliwice
60
Różnice w algorytmie metody simpleks na MAX i MIN
Kryterium wyjścia z bazy
MAX:
Zmienna, dla której iloraz elementu z wektora wyrazów
wolnych przez współczynnik z kolumny zmiennej
wchodzącej do bazy ma najmniejszą wartość.
MIN:
Identycznie jak w zadaniu na MAX.
Gliwice
61
Różnice w algorytmie metody simpleks na MAX i MIN
Rozwiązanie optymalne
MAX:
Wszystkie wskaz
niki optymalności muszą być niedodatnie.
MIN:
Wszystkie wskaz
niki optymalności muszą być nieujemne.
Gliwice
62
Szczególne przypadki rozwiązań
Gliwice
63
Szczególne przypadki rozwiązań
Zadanie sprzeczne
Z x1, x2 = 6x1 + 5x2 MAX
( )
x1 + x2 e" 8
1
3x1 + 2x2 d" 6
2
x1, x2 e" 0
W postaci bazowej:
Z x1, x2, x3, x4, x5 = 6x1 + 5x2 + 0x3 -1000x4 + 0x5 MAX
( )
x1 + x2 - x3 + x4 = 8
1
3x1 + 2x2 + x5 = 6
2
x1, x2, x3, x4, x5 e" 0
Gliwice
64
Szczególne przypadki rozwiązań
x2
10
9
8
7
6
5
4
3
2 2
1
1
x1
1 2 3 4 5 6 7 8 9 10
Gliwice
65
Szczególne przypadki rozwiązań
Zadanie sprzeczne:
Nie ma rozwiązań dopuszczalnych
Objawy w metodzie simpleks:
W rozwiązaniu optymalnym, zmienna sztuczna (w tym
przykładzie zmienna x4) będzie miała wartość niezerową (czyli
będzie w bazie).
Gliwice
66
Szczególne przypadki rozwiązań
Alternatywne rozwiązania optymalne
Z x1, x2 = 2x1 + 2x2 MAX
( )
x1 + x2 d" 8
1
3x1 + 2x2 e" 6
2
x1, x2 e" 0
W postaci bazowej:
Z x1, x2, x3, x4, x5 = 2x1 + 2x2 + 0x3 + 0x4 -1000x5 MAX
( )
x1 + x2 + x3 = 8
1
3x1 + 2x2 - x4 + x5 = 6
2
x1, x2, x3, x4, x5 e" 0
Gliwice
67
Szczególne przypadki rozwiązań
x2
10
9
C (0, 8): Z(0, 8) = 16
C
8
D (8, 0): Z(8, 0) = 16
7
6
5
4
B
1
3
2
1
2
A D
x1
1 2 3 4 5 6 7 8 9 10
Gliwice
68
Szczególne przypadki rozwiązań
Alternatywne rozwiązania optymalne:
Każdy punkt odcinka CD jest rozwiązaniem optymalnym
- odpowiada alternatywnemu, optymalnemu rozwiązaniu
Może się zdarzyć, że zadanie ma nieskończenie wiele
rozwiązań optymalnych
Objawy w metodzie simpleks:
W rozwiązaniu optymalnym, zerowe wartości wskaz
ników
optymalności dla zmiennych niebazowych.
Rozwiązania optymalne można zidentyfikować przechodząc do
kolejnych baz.
Gliwice
69
Szczególne przypadki rozwiązań
Nieograniczony zbiór rozwiązań dopuszczalnych
Z x1, x2 = 2x1 + 3x2 MAX
( )
3x1 + 2x2 e" 6
1
x1 d" 7
2
x1, x2 e" 0
W postaci bazowej:
Z x1, x2, x3, x4, x5 = 2x1 + 3x2 + 0x3 -1000x4 + 0x5 MAX
( )
3x1 + 3x2 - x3 + x4 = 6
1
x1 + x5 = 7
2
x1, x2, x3, x4, x5 e" 0
Gliwice
70
Szczególne przypadki rozwiązań
x2
10
9
8
7
6
5
4
2
B
3
2
1
1
C
A
x1
1 2 3 4 5 6 7 8 9 10
Gliwice
71
Szczególne przypadki rozwiązań
W tym zadaniu:
Zbiór rozwiązań jest nieograniczony
Funkcja celu jest nieograniczona z góry
Objawy w metodzie simpleks:
W tablicy simpleks kolumna zmiennej wchodzącej do bazy ma
wszystkie elementy niedodatnie.
Gliwice
72
Szczególne przypadki rozwiązań
Czy funkcja celu może być nieograniczona od dołu?
Nie, ponieważ wymagana jest nieujemność zmiennych.
Czy pomimo tego, że zbiór rozwiązań dopuszczalnych jest
nieograniczony może istnieć  dokładne rozwiązanie optymalne?
Może, gdy zadanie jest zadaniem na MIN.
Gliwice
73
Szczególne przypadki rozwiązań
Z x1, x2 = 2x1 + 3x2 MIN
( )
3x1 + 2x2 e" 6
1
x1 d" 7
2
x1, x2 e" 0
3
Z poprzedniego rysunku:
A (2, 0): Z(2, 0) = 4 MIN
B (0, 3): Z(0, 3) = 9
C (7, 0): Z(7, 0) = 14
Gliwice
74