PRZYKŁAD AP-1
Dana jest tablica rozwiązania optymalnego
C
B
BAZA
Niewia-
dome
bazowe
4
x
1
1
p
3
x
2
2
p
0
1
S
3
p
0
S
2
p
4
0
3
S
5
p
Wartości
niewiadomych
bazowych
3
2
p
x
2
0
1
2
0
-1
200
0
p
4
S
2
0
0
-1
1
0
500
4
1
p
x
1
1
0
-1
0
1
300
∆∆∆∆
j
j
j
z
c
=
−
0
0
2
0
1
1800
następującego
zadania
optymalizacyjnego:
Znaleźć
wartość
największą
funkcji
2
1
2
1
3
4
)
,
(
x
x
x
x
f
+
=
na zbiorze rozwiązań układu nierówności:
≥
≤
+
≤
+
≤
+
0
,
800
2
1000
500
2
1
2
1
2
1
2
1
x
x
x
x
x
x
x
x
.
Wiadomo, że bazę w startowej tablicy simpleks tworzyły wektory (
3
p
, p
4
,
5
p
).
a) Jakie wartości może przyjmować współczynnik
2
c
przy niewiadomej
2
x
, aby rozwiązanie
optymalne nie uległo zmianie (aby wartości zmiennych w rozwiązaniu optymalnym nie uległy
zmianie)?
b) Jakie wartości może przyjmować wartość ograniczenia
1
b
aby rozwiązanie optymalne było
w dalszym ciągu wyznaczane przez wektory (
2
p ,
p
4
,
1
p
)?
Rozwiązanie
:
Ad a) Załóżmy, że nowa wartość współczynnika przy niewiadomej
2
x
będzie równa
2
2
3
c
c
∆
+
=
. Wyznaczamy nowe wartości wskaźników optymalności dla zmiennych
niebazowych:
2
2
0
))
1
(
4
)
1
(
0
)
3
(
2
(
~
2
2
3
+
∆
=
−
−
⋅
+
−
⋅
+
∆
+
⋅
=
∆
c
c
,
1
0
)
1
4
0
0
)
3
(
1
(
~
2
2
5
+
∆
−
=
−
⋅
+
⋅
+
∆
+
⋅
−
=
∆
c
c
Ponieważ w zadaniu na maksymalizację żądamy, aby wskaźniki optymalności były
nieujemne, to rozwiązujemy następujący układ nierówności:
≥
+
∆
−
≥
+
∆
0
1
0
2
2
2
2
c
c
Po rozwiązaniu tego układu otrzymujemy, że
>
−
<
∈
∆
1
,
1
2
c
. Stąd wynika, że współczynnik
2
c
przy niewiadomej
2
x
może przyjmować wartości z przedziału
>
<
4
,
2
i rozwiązanie
optymalne
300
1
=
op
x
,
200
2
=
op
x
nie ulegnie zmianie, natomiast zmienić się może wartość
funkcji celu, która będzie równa
200
1800
)
200
,
300
(
)
,
(
2
2
1
⋅
∆
+
=
=
c
f
x
x
f
op
op
.
Ad b) Załóżmy, że nowa wartość ograniczenia
1
b będzie równa
1
1
500
b
b
∆
+
=
. Dopuszczalne
zmiany wartości ograniczenia
1
b , przy których nie zmienia się baza wyznaczająca
rozwiązanie optymalne otrzymujemy rozwiązując układ nierówności
0
b
B
≥
⋅
.
Z tablicy rozwiązania optymalnego odczytujemy elementy macierzy jako współrzędne
wektorów (
3
p
, p
4
,
5
p
)
, które tworzyły bazę w startowej tablicy simpleks, zatem
−
−
−
=
1
0
1
0
1
1
1
0
2
B
oraz
∆
+
=
800
1000
500
1
b
b
.
Rozwiązując układ nierówności
≥
⋅
+
⋅
+
∆
+
⋅
−
≥
⋅
+
⋅
+
∆
+
⋅
−
≥
⋅
−
+
⋅
+
∆
+
⋅
0
800
1
1000
0
)
500
(
)
1
(
0
800
0
1000
1
)
500
(
)
1
(
0
800
)
1
(
1000
0
)
500
(
2
1
1
1
b
b
b
Otrzymujemy, że
>
−
<
∈
∆
300
,
100
1
b
, a stąd
>
<
∈
800
,
400
1
b
. Rozwiązanie optymalne
będzie wówczas wyznaczone przez te same wektory (
2
p
,
p
4
,
1
p
) i będzie ono następujące
0
,
500
,
0
,
2
200
,
300
3
1
2
1
1
2
1
1
=
∆
−
=
=
∆
⋅
+
=
∆
−
=
op
op
op
op
op
S
b
S
S
b
x
b
x
. Funkcja celu dla tego
rozwiązania optymalnego ma wartość
1
2
1800
b
∆
⋅
+
.