PRZYKŁAD AP-2
Dana jest tablica rozwiązania optymalnego
C
B
BAZA
Niewiadome
bazowe
50
1
x
1
p
100
2
x
2
p
80
3
x
3
p
0
1
S
p
4
0
S
2
5
p
M
1
t
6
p
M
2
t
7
p
Wartości
niewiadomych
bazowych
80
3
p
3
x
0
0
1
-1
1
1
-1
10
50
1
p
1
x
1
1
0
1
-2
-1
2
20
∆∆∆∆
j
j
j
z
c
=
−
0
-50
0
-30
-20
30
-M
20
-M
1800
następującego zadania optymalizacyjnego:
Znaleźć wartość najmniejszą funkcji
3
2
1
3
2
1
80
100
50
)
,
,
(
x
x
x
x
x
x
f
+
+
=
na zbiorze
rozwiązań układu nierówności:
≥
≥
+
+
≥
+
+
0
,
,
30
40
2
3
2
1
3
2
1
3
2
1
x
x
x
x
x
x
x
x
x
.
Wiadomo, że bazę w startowej tablicy simpleks tworzyły wektory (
6
p ,
7
p
).
a) Jakie wartości może przyjmować współczynnik
2
c
przy niewiadomej
2
x
, aby rozwiązanie
optymalne nie uległo 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 (
3
p
,
1
p
)?
Rozwiązanie
:
Ad a) Załóżmy, że nowa wartość współczynnika przy niewiadomej
2
x
będzie równa
2
2
100
c
c
∆
+
=
. Ponieważ w rozwiązaniu optymalnym niewiadoma
2
x nie jest niewiadomą
bazową, to wystarczy aby
50
2
2
2
−
≥
∆
⇒
∆
≥
∆
c
c
. Stąd wynika, że
)
,
50
2
∞
+
−
<
∈
∆
c
,
czyli współczynnik
2
c
przy niewiadomej
2
x
może przyjmować wartości z przedziału
)
,
50
∞
+
<
i rozwiązanie optymalne
20
1
=
op
x
,
0
2
=
op
x
10
3
=
op
x
nie ulegnie zmianie, nie
zmieni się także wartość funkcji celu.
Ad b) Załóżmy, że nowa wartość ograniczenia
1
b
będzie równa
1
1
40
b
b
∆
+
=
. Dopuszczalne
zmiany wartości
1
b , przy których nie zmienia się baza wyznaczająca rozwiązanie optymalne
