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

∆

⋅

+

.