Liniowe modele decyzyjne

Sytuacja decyzyjna - przykład

Mały zakład wytwarza dwa produkty A i B, których ceny zbytu

wynosz

ą

odpowiednio 3 $/szt. oraz 4 $/szt.

Nale

ż

y opracowa

ć

dzienny plan produkcji zakładu tak, aby

warto

ść

produkcji liczona w cenach zbytu była mo

ż

liwie najwi

ę

ksza.

Produkcja jest limitowana głównie przez dwa czynniki: dost

ę

pny

czas pracy maszyn i surowiec podstawowy.

Dzienny limit czasu pracy maszyn wynosi 500 minut. Sztuka

wyrobu A wymaga 1 minuty czasu pracy maszyn, natomiast sztuka
wyrobu B - 2 minut. Na wyprodukowanie sztuki wyrobu A zu

ż

ywa si

ę

1

kg surowca specjalnego. Równie

ż

sztuka wyrobu B wymaga 1 kg tego

surowca.

Umowy z producentem surowca podstawowego wskazuj

ą

,

ż

e

ka

ż

dego dnia zakład b

ę

dzie miał do dyspozycji 350 kg tego surowca

(bezpieczny poziom).

Zakład jest zainteresowany takim programem dziennej

produkcji, przy którym osi

ą

gał b

ę

dzie zysk minimum 600 $. Jednostkowy

zysk ze sztuki wyrobu A wynosi 2 $/szt., a ze sztuki wyrobu B – 1 $/szt.

Model decyzyjny

1. Lista zmiennych decyzyjnych:

x

1

- dzienna produkcja wyrobu A [szt.]

x

2

- dzienna produkcja wyrobu B [szt.]

2. Funkcja celu: (warto

ść

produkcji w cenach zbytu)

F(x) = F(x

1

,x

2

,) = 3x

1

+ 4x

2

→

max

[$]

3. Ograniczenia: (warunki okre

ś

laj

ą

ce zbiór planów dopuszczalnych)

(maszyny)

x

1

+ 2x

2

≤

500

[min]

(surowiec)

x

1

+ x

2

≤

350

[kg]

(min. poziom zysku) 2x

1

+ x

2

≥

600

[$]

4. Warunki brzegowe: (warunki dotycz

ą

ce zmiennych decyzyjnych)

x

1

≥

0

[szt.]

x

1

, x

2

∈

C

x

2

≥

0

[szt.]

Posta

ć

ogólna modelu decyzyjnego (1)

1. Lista n zmiennych decyzyjnych:

x

1

– zmienna decyzyjna nr 1

[j.m.]

x

2

– zmienna decyzyjna nr 2

[j.m.]

.

.

.
x

n

– zmienna decyzyjna nr n

[j.m.]

2. Funkcja celu:

F(x) = F(x

1

,x

2

,…, x

n

) = c

1

x

1

+ c

2

x

2

+ … + c

n

x

n

→

max (lub min)

[j.m.]

Posta

ć

ogólna modelu decyzyjnego (2)

3. Ograniczenia:

(ograniczenie nr 1)

a

11

x

1

+ a

12

x

2

+ … + a

1n

x

n

≤

b

1

[j.m.]

.

.

.

.

.

.

(ograniczenie nr k)

a

k1

x

1

+ a

k2

x

2

+ … + a

kn

x

n

= b

k

[j.m.]

.

.

.

.

.

.

(ograniczenie nr m)

a

m1

x

1

+ a

m2

x

2

+ … + a

mn

x

n

≥

b

m

[j.m.]

4. Warunki brzegowe:

x

1

≥

0 x

2

≥

0 … x

n

≥

0

Ilustracja graficzna zbioru decyzji dopuszczalnych

x

1

x

2

200

400

600

200

400

600

maszyny

surowiec

min. zysk

x

Rozwi

ą

zanie optymalne

1. Formalny zapis decyzji optymalnej:

x

1

opt

= 250

x

2

opt

= 100

F(x

1

opt

; x

2

opt

) = 1150

2. Najlepsza dzienna decyzja produkcyjna:

produkowa

ć

250 szt. wyrobu A

produkowa

ć

100 szt. wyrobu A

maksymalna warto

ść

produkcji wyniesie 1150 $

fundusz czasu pracy maszyn (max. 500 minut) nie zostanie w pełni
wykorzystany (codziennie wolne 50 minut)

zasób surowca (350 kg) b

ę

dzie wykorzystany w pełni

minimalny

żą

dany poziom zysku został osi

ą

gni

ę

ty dokładnie na

żą

danym poziomie

Poszukiwanie rozwi

ą

zania optymalnego

•

metoda graficzna (2 zmienne decyzyjne)

•

metoda simpleks (dowolna liczba zmiennych decyzyjnych)

Metoda graficzna

x

1

x

2

100

200

300

100

200

300

C

B

A

A = (300,0)
B = (350,0)
C = (250,100)

w: F = 1150

w: F = 1050

w: F = 900

G[150,200]

rozwi

ą

zanie

optymalne

F

→

max

Klasyczna metoda simpleks (informacje ogólne, idea) (1)

1. Posta

ć

modelu:

F(x) = F(x

1

,x

2

,) = 3x

1

+ 4x

2

→

max

x

1

+ 2x

2

≤

500

(maszyny)

x

1

+ x

2

≤

350

(surowiec)

2x

1

+ x

2

≥

600

(min. poziom zysku)

x

1

≥

0 x

2

≥

0

x

1

, x

2

∈

C

2. Posta

ć

kanoniczna modelu:

3x

1

+ 4x

2

+ 0s

1

+ 0s

2

+ 0s

3

– Mt

3

→

max

x

1

+ 2x

2

+ s

1

= 500

(maszyny)

x

1

+ x

2

+ s

2

= 350

(surowiec)

2x

1

+ x

2

- s

3

+ t

3

= 600

(min. poziom zysku)

x

1

≥

0

x

2

≥

0 s

1

≥

0 s

2

≥

0 s

3

≥

0 t

3

≥

0

Klasyczna metoda simpleks (informacje ogólne, idea) (2)

3. Interpretacja zmiennych swobodnych:

s

1

– niewykorzystany fundusz czasu pracy maszyn (limit 500 minut)

(ang. slack – luz)

s

2

– niewykorzystany zasób surowca (limit 350 kg)

(ang. slack – luz)

s

3

– przekroczenie minimalnej kwoty zysku (

żą

dane minimum 600 $)

(ang. surplus – nadwy

ż

ka)

t

3

– zmienna sztuczna – zmienna pomocnicza, nie ma interpretacji

ekonomicznej
(ang. artificial – sztuczny)

Metoda simpleks (program WinSTORM) (1)

PROBLEM DATA IN EQUATION STYLE

Maximize

3 X1 + 4 X2

Subject to

MASZYNY

1 X1 + 2 X2 <= 500

SUROWIEC

1 X1 + 1 X2 <= 350

MIN. ZYSK

2 X1 + 1 X2 >= 600

0 <= X1 <= Infinity
0 <= X2 <= Infinity

Metoda simpleks (program WinSTORM) (2)

OPTIMAL SOLUTION - DETAILED REPORT

Variable

Value Cost

Red. cost

Status

1 X1

250.0000 3.0000 0.0000

Basic

2 X2

100.0000 4.0000 0.0000

Basic

Objective Function Value = 1150

Slack Variables
3 MASZYNY

50.0000 0.0000 0.0000

Basic

4 SUROWIEC

0.0000 0.0000 -5.0000

Lower

5 MIN. ZYSK 0.0000 0.0000 -1.0000

Lower

Constraint Type

RHS

Slack

Shadow price

1 MASZYNY <=

500.0000

50.0000 0.0000

2 SUROWIEC <=

350.0000

0.0000 5.0000

3 MIN. ZYSK >= 600.0000

0.0000 -1.0000

Metoda simpleks (program WinSTORM) (3)

SENSITIVITY ANALYSIS OF COST COEFFICIENTS

Current

Allowable

Allowable

Variable

Coeff.

Minimum

Maximum

1 X1

3.0000

- Infinity

4.0000

2 X2

4.0000

3.0000

Infinity

SENSITIVITY ANALYSIS OF RIGHT-HAND SIDE VALUES

Current

Allowable Allowable

Constraint

Type

Value

Minimum Maximum

1 MASZYNY

<= 500.0000 450.0000 Infinity

2 SUROWIEC

<= 350.0000 300.0000 366.6667

3 MIN. ZYSK

>= 600.0000 550.0000 700.0000

Wycena dualna

Wyceny dualne pozwalaj

ą

okre

ś

li

ć

wielko

ść

oraz kierunek zmian

uzyskanej optymalnej warto

ś

ci funkcji celu na skutek zmiany warto

ś

ci

prawych stron ogranicze

ń

(wyrazów wolnych).

y

j

– wycena dualna

Je

ż

eli w j-tym ograniczeniu zadania programowania liniowego wyraz

wolny b

j

wzro

ś

nie (spadnie) o jednostk

ę

, to optymalna warto

ść

funkcji

celu f(x

opt

) wzro

ś

nie o y

j

jednostek, tj. do poziomu f(x

opt

) + y

j

.

Analiza wra

ż

liwo

ś

ci (1)

Czy, a je

ż

eli tak to na ile zmieni si

ę

uzyskane rozwi

ą

zanie optymalne,

je

ż

eli zmieni si

ę

warto

ść

jednego wybranego parametru

rozwi

ą

zywanego zadania programowania liniowego?”

parametr w funkcji celu c

j

prawa strona ograniczenia b

j

Analiza wra

ż

liwo

ś

ci (2)

Konsekwencje zmian jednego wybranego współczynnika c

j

w ramach

przedziału dopuszczalnych zmian:

rozwi

ą

zanie optymalne zadania nie ulegnie zmianie

zmieni si

ę

optymalna warto

ść

funkcji celu

zmieni si

ę

wycena dualna

Analiza wra

ż

liwo

ś

ci (3)

Konsekwencje zmian jednego wybranego wyrazu wolnego
ogranicze

ń

b

j

w ramach przedziału dopuszczalnych zmian:

rozwi

ą

zanie optymalne zadania ulegnie zmianie, lecz tylko w

zakresie zmiennych bazowych (status: basic)

zmieni si

ę

optymalna warto

ść

funkcji celu

wycena dualna pozostanie bez zmian

Warianty rozwi

ą

za

ń

zadania PL (1)

x

1

x

2

X =

∅

∅

∅

∅

zadanie sprzeczne

Warianty rozwi

ą

za

ń

zadania PL (2)

x

1

x

2

brak sko

ń

czonego

rozwi

ą

zanie zadania PL

G

X

Warianty rozwi

ą

za

ń

zadania PL (3)

x

1

x

2

jednoznaczne optymalne
rozwi

ą

zanie zadania PL

G

X

A

Warianty rozwi

ą

za

ń

zadania PL (4)

x

1

x

2

niejednoznaczne optymalne
rozwi

ą

zanie zadania PL

G

X