Badania operacyjne
Wykład II
Analiza wrażliwości.
Dualizm w programowaniu
liniowym.
Badania operacyjne
Wykład II
Analiza wrażliwości.
Dualizm w programowaniu
liniowym.
Analiza wrażliwości zajmuje się badaniem
wrażliwości optymalnego rozwiązania
zagadnienia PL na zmianę parametrów. Na
podstawie analizy wrażliwości możemy
odpowiedzieć na następujące pytania:
• Jaką zmianę rozwiązania optymalnego wywoła
zmiana współczynników funkcji celu?
• W jakim zakresie możemy zwiększyć
(zmniejszyć) współczynniki funkcji celu, aby
rozwiązanie optymalne nie uległo zmianie?
• Jaką zmianę rozwiązania optymalnego wywoła
zmiana wielkości wyrazów wolnych, stojących
po prawej stronie ograniczeń?
Przykład – firma „Oko świata”
Zakład
Czasochłonność
Dziennie
limity
czasowe
Wyrób 1
Wyrób 2
1
2
3
1
0
3
0
2
2
4
12
18
Zysk
jednostkowy
(w zł)
30
50
max
Wielkość
produkcji
x
1
x
2
Odp.: Optymalnym rozwiązaniem była produkcja dwóch
wyrobów 1
i sześciu wyrobów 2. Przy takim planie maksymalny
dzienny zysk wynosi 360 zł
WYDRUK Z PROGRAMU QSB+
WYDRUK Z PROGRAMU QSB+
CZĘŚĆ PIERWSZA
CZĘŚĆ PIERWSZA
Summarized Report for......................
Number
Variable
Solution
Opportunity
Cost
Objective
Coefficient
Minimum
Obj. Coeff.
Maximum
Obj. Coeff.
1
2
X1
X2
+2,0
+6,0
0
0
+30,0
+50,0
0
+20,0
+75
+Infinity
Max (Min) Obj = .... Iteration = .... Elapsed CPU Second = ......
Nazwa projektu
Przy interpretacji wydruku
obowiązuje podwójny język:
• matematyczny
• ekonomiczny (menedżerski)
Numer zmiennej
decyzyjnej
numer wyrobu
numer składnika
mieszanki
Rozwiązanie (optymalne wartości
zmiennych decyzyjnych)
ilości produkowanych wyrobów
ilości użytych składników
Koszty alternatywne
(względne)
O ile trzeba zmienić
współczynnik funkcji
celu, aby wyrób (skład-
nik) wszedł do rozwią-
zania optymalnego (w
przykładzie = 0, gdyż
ilości są różne od zera)
Współczynniki
funkcji celu
(macierz C)
zyski jednost-
kowe z wyrobów
ceny składników
mieszanki
Optymalna wartość
funkcji celu
maksymalny zysk
producenta
minimalny koszt
mieszanki
Optymalne zakresy
współczynników
funkcji celu
przedziały zysku
jednostkowego nie
powodujące zmiany
planu produkcji
przedziały ceny
składników nie po-
wodujące zmiany
receptury miesza-
nki
Liczba iteracji wykonanych przez komputer
Czas szukania
optymalnego
rozwiązania
Podsumowując:
Jeśli zysk z jednostki wyrobu 2 pozostanie na poziomie 50
złotych (c
2
=50), to optymalny zakres dla współczynnika
c
1
(jednostkowego zysku z wyrobu 1) będzie
następujący:
Jeśli zysk z jednostki wyrobu 1 pozostanie na poziomie 30
złotych (c
1
=30), to optymalny zakres dla współczynnika
c
2
(jednostkowego zysku z wyrobu 2) będzie
następujący:
20
2
c
75
0
1
c
WPŁYW ZMIANY PRAWEJ STRONY
OGRANICZEŃ
Zmiana ograniczenia pociąga za sobą zmianę obszaru rozwiązań
dopuszczalnych oraz zmianę optymalnego rozwiązania
rozważanego problemu.
Wielkość zmiany optymalnej wartości funkcji celu
wywołana powiększeniem prawej strony ograniczenia
o jednostkę jest zwana cena dualną danego środka
produkcji.
Z każdym ograniczeniem związany jest pewien dopuszczalny zakres
wartości prawych stron ograniczeń.
Zmiana wartości prawej
strony ograniczenia o dowolną liczbę w granicach
tego zakresu wywołuje zmianę optymalnej wartości
funkcji celu o iloczyn ceny dualnej i tej liczby.
WYDRUK Z PROGRAMU QSB+
WYDRUK Z PROGRAMU QSB+
CZĘŚĆ DRUGA
CZĘŚĆ DRUGA
Przy interpretacji wydruku
obowiązuje podwójny język:
• matematyczny
• ekonomiczny (menedżerski)
S
u
m
m
a
r
i
z
e
d
R
e
p
o
r
t
f
o
r
.
.
.
.
.
.
.
C
o
n
s
t
r
a
i
n
t
S
t
a
t
u
s
R
H
S
S
h
a
d
o
w
P
r
i
c
e
S
l
a
c
k
o
r
S
u
r
p
l
u
s
M
i
n
R
H
S M
a
x
R
H
S
1
2
3
L
o
o
s
e
T
i
g
h
t
T
i
g
h
t
)
(
+
4
,
0
)
(
+
1
2
,
0
)
(
+
1
8
,
0
0
1
5
1
0
+
2
,
0
0
0
+
2
,
0
+
6
,
0
+
1
2
,
0
+
I
n
fi
n
i
t
y
+
1
8
+
2
4
M
a
x
(
M
i
n
)
O
b
j
=
.
.
.
.
.
.
I
t
e
r
a
t
i
o
n
=
.
.
.
.
.
.
E
l
a
p
s
e
d
C
P
U
S
e
c
o
n
d
=
.
.
.
.
.
.
Numer ograniczenia (warunku)
numer środka produkcji
numer komponentu
mieszanki
Sposób spełniania nierówności
z warunków ograniczających
(loose = nierówność silna,
tight = nierówność słaba)
loose = środek produkcji jest
w nadmiarze; tight = środek
produkcji wyczerpany
loose = komponent jest w
nadmiarze; tight = komponen-
tu jest dokładnie według wy-
magań normy
Ograniczenia (macierz B) z nierównością
ilości posiadanych środków produkcji
najmniejsze dopuszczalne ilości komponentów (normy)
Ceny dualne
dodatkowy
zysk z dodat-
kowej jedno-
stki środka
zmiana ko-
sztu miesza-
nki po zmnie-
jszeniu nor-
my o jednos-
tkę
Luz czyli nadmiar
ilość niewycze-
rpanego środka
produkcji
ilość kompone-
ntu ponad normę
Wartości zakresów
ograniczeń (macierzy
B), w których wartość
optymalna funkcji celu
zmienia się zgodnie z
cenami dualnymi
zakresy dla ilości
środka produkcji
zakresy dla ilości
komponentu mieszanki
Dualność zadań programowania liniowego
Z każdym zadaniem programowania liniowego sprzężone jest pewne inne
zadanie PL zwane zadaniem dualnym (dwoistym).
Tworzenie zadania dualnego
n
j
x
b
x
a
x
a
x
a
b
x
a
x
a
x
a
b
x
a
x
a
x
a
j
m
n
mn
m
m
n
n
n
n
,...
2
,
1
,
0
,
*
...
*
*
...
,
*
...
*
*
,
*
...
*
*
2
2
1
1
2
2
2
22
1
21
1
1
2
12
1
11
m
i
y
c
y
a
y
a
y
a
c
y
a
y
a
y
a
c
y
a
y
a
y
a
i
n
m
mn
n
n
m
m
m
m
,...
2
,
1
,
0
,
*
...
*
*
...
,
*
...
*
*
,
*
...
*
*
2
2
1
1
2
2
2
22
1
12
1
1
2
21
1
11
Wzajemnie dwoiste zadania PL mają
postać:
Pierwotne (prymalne)
zadanie PL
max Z = c
1
*x
1
+ c
2
*x
2
+ ... +
c
n
*x
n
Dualne zadanie PL
min f = b
1
*y
1
+ b
2
*y
2
+ ... +
b
m
*y
m
Właściwości zadań wzajemnie
dualnych
1. Jeśli pierwotne zadanie jest zadanie na maksimum, to wtedy
zadanie dwoiste będzie na minimum i odwrotnie, jeśli pierwotne
zadanie jest zadanie na minimum, to wtedy zadanie dwoiste
będzie na maksimum.
2. Współczynniki funkcji celu pierwotnego zadania będą
wolnymi wyrazami dla ograniczeń zadania dwoistego.
3. Wolne wyrazy ograniczeń pierwotnego zadania będą
współczynnikami funkcji celu zadania dwoistego.
4. Macierzy ograniczeń zadań pierwotnego i dwoistego to są
macierze transponowane.
5. Jeśli pierwotne zadanie jest zadanie maksymalizacji, wtedy
układ ograniczeń ma postać nierówności typu „”. Dwoiste
zadanie będzie rozwiązane na minimum, a ograniczenia
przedstawiony w postaci nierówności typu „”.
6. Ilość ograniczeń pierwotnego zadania równa się ilości
zmiennych zadania dwoistego, a ilość ograniczeń zadania
dwoistego równa się ilości zmiennych zadania pierwotnego.
7. Wszystkie zmienne w zadaniach pierwotnym i dwoistym są
nieujemne.
Właściwości dualnych zadań programowania liniowego
m
i
i
i
n
j
j
j
y
b
x
c
1
1
Twierdzenie 1. Dla dowolnych planów dopuszczalnych х= (x
1
;
x
2
; ... ; x
n
) i у = (y
1
; y
2
; ... ; у
m
) pierwotnego i dwoistego ZPL
będzie spełniona nierówność Z(x)
f(y), to znaczy
Treść ekonomiczna nierówności polega na tym, że dla
dowolnego dopuszczalnego planu produkcji х i dla
dowolnego wektora cen у surowców zsumowany zysk od
stworzonej produkcji nie przekracza zsumowanych kosztów
surowców.
Interpretacja
ekonomiczna
wartości
zmiennych dualnych:
Optymalna wartość zmiennej dualnej, tzw. cena
dualna to krańcowa produktywność jednostki
danego środka – informuje nas o tym, ile
wzrośnie (spadnie) wartość funkcji celu zadania
pierwotnego, jeśli wyraz wolny b
i
warunku
pierwotnego wzrośnie (spadnie) o jednostkę, dla
zmian b
i
w pewnych dopuszczalnych granicach.
Wartość
zmiennej
dualnej
jest,
zatem
maksymalną ceną, jaką warto zapłacić, za
dodatkową jednostką zasobu i.
Interpretacja
ekonomiczna
warunków
twierdzenia o równowadze:
Jeżeli zużycie i-tego środka produkcji jest mniejsze od
posiadanego
zasobu,
to
wycena
(krańcowa
produktywność) jednostki i-tego środka jest zerowa
Jeżeli wartość środków zużytych na wytworzenia jednostki
j-tego produktu jest większa od jego ceny, to produkcja
wyrobu jest zerowa
Jeżeli wycena i-tego środka jest dodatnia, to zużycie
środka musi być równe jego zasobowi,
Jeżeli produkcja j-tego wyrobu jest dodatnia, to wartość
środków zużytych na jednostkę j-tego produktu jest równa
jego cenie
Metoda Simplex
Metoda Simplex – algorytm sympleksowy lub metoda
sympleks(ów):
- stosowana w matematyce iteracyjna metoda
rozwiązywania zadań programowania liniowego za
pomocą optymalizacji rozwiązania
- twórcą metody Simplex jest George Bernard Dantzig
( 1947 r. )
- nazwa metody pochodzi od sympleksu
Symplex
• to najprostsza n-wymiarowa
figura wypukła określona przy
pomocy n+1 wierzchołków
• w przestrzeni jednowymiarowej
taką figurą jest prosta
• w przestrzeni dwuwymiarowej
jest to trójkąt
• w przestrzeni trójwymiarowej
jest to czworościan
Wielościan algorytmu sympleksowego w trzech
wymiarach
Metoda Simplex - polega na sekwencyjnym (krokowym) i
ściśle ukierunkowanym (efektywnym) przeglądzie tzw.
rozwiązań bazowych programu liniowego o postaci
kanonicznej (czyli takiej, w której wszystkie warunki
ograniczające mają postać równości) w następujący sposób:
1. Znajdujemy (dowolne) rozwiązanie bazowe programu
2. Sprawdzamy czy jest ono optymalne
3. Jeżeli dane rozwiązanie nie jest optymalne, znajdujemy
następne rozwiązanie
4.Postepowanie kończy się gdy aktualnego rozwiązania
bazowego nie można już poprawić, czyli jest optymalne
Rozważmy problem optymalizacji
przedstawiony w standardowej postaci :
Funkcja celu :
z(x
1
, x
2
,…, x
n
) = c
1
x
1
+ c
2
x
2
+ … + c
n
x
n
max
Ograniczenia :
a
11
x
1
+ a
12
x
2
+ … + a
1n
x
n
≤ b
1
a
21
x
1
+ a
22
x
2
+ … + a
2n
x
n
≤ b
2
. . . . . . . . . .
a
m1
x
1
+ a
m2
x
2
+ … + a
mn
x
n
≤ b
m
x
1
, x
2
,…, x
n
≥ 0
Postać macierzowa :
C X max
A X ≤ B
X ≥ 0
gdzie :
C= X =
A = B =
Algorytm Simplex polega na badaniu rozwiązań bazowych
programu o postaci kanonicznej, zatem przed przestąpieniem do
budowy pierwszej tablicy simpleks zamieniamy wszystkie
nierówności na równości przez wprowadzenie dodatkowych
zmiennych.
a
11
x
1
+ a
12
x
2
+ … + a
1n
x
n
+ x
n +1
=b
1
a
21
x
1
+ a
22
x
2
+ … + a
2n
x
n
+ + x
n +2
= b
2
. . . . . . . . . . . . . . .
a
m1
x
1
+ a
m2
x
2
+ … + a
mn
x
n
+ + x
n +m
= b
m
wiemy, że max(z)=min(-z) zatem nasza funkcja celu przyjmuje
postać
-c
1
x
1
- c
2
x
2
+ … - c
n
x
n
min
Przykład – problem doboru składu
mieszanki
Zakład przerabiający ropę uzyskuje 4 półfabrykaty: 400
tys. litrów półfabrykatu I, 250 tys. litrów półfabrykatu
II, 250 tys. litrów półfabrykatu III, 100 tys. litrów
półfabrykatu IV.
W rezultacie połączenia tych czterech składników w
różnych proporcjach powstają trzy asortymenty
benzyny: benzyna A – 2:3:5:2, benzyna B – 3:1:2:1,
benzyna C – 2:2:1:3.
Wartość jednego litra poszczególnych asortymentów
benzyny wynosi: A – 120 j.p., B – 100 j.p., C – 150 j.p.
Dokonać połączenia składników w taki sposób, aby
zapewnić maksymalną wartość produkcji.
Rozwiązanie
Jeśli przez x
1
, x
2
, x
3
oznaczymy wielkości produkcji
poszczególnych asortymentów benzyny, to zapis
modelu matematycznego jest następujący:
przy warunkach:
max,
150
100
120
3
2
1
x
x
x
z
0
,
,
,
100
8
3
7
1
12
2
,
250
8
1
7
2
12
5
,
250
8
2
7
1
12
3
,
400
8
2
7
3
12
2
3
2
1
3
2
1
3
2
1
3
2
1
3
2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x