wyklad_2_liniowe_modele_decyzyjne.pdf

Liniowe modele decyzyjne

Model decyzyjny (1)

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 specjalnego

surowca. 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 (2)

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 ,) = 3 x 1 + 4 x 2 → max

[$]

3. Ograniczenia: (warunki okre ś laj ą ce zbiór planów dopuszczalnych)

(maszyny)

x 1 + 2 x 2 ≤ 500

[min]

(surowiec)

x 1 + x 2 ≤ 350

[kg]

(min. poziom zysku) 2 x 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 2

600

min. zysk

400

surowiec

200

maszyny

200

400

600

x 1

Poszukiwanie rozwi ą zania optymalnego

• metoda graficzna (2 zmienne decyzyjne)

• metoda simpleks (dowolna liczba zmiennych decyzyjnych)

Metoda graficzna

x 2

300

G (150,200)

w: f = 1150

w: f = 1050

200

rozwi ą zanie

optymalne

w: f = 900

100

A = (300,0)

B = (350,0)

C = (250,100)

100

200

300

x 1

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

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

1. Postać modelu:

F ( x ) = F ( x 1 , x 2 ,) = 3 x 1 + 4 x 2 → max

x 1 + 2 x 2 ≤ 500

(maszyny)

2 x 1 + x 2 ≥ 600

(min. poziom zysku)

x 1 ≥ 0 x 2 ≥ 0

2. Postać kanoniczna modelu:

3 x 1 + 4 x 2 + 0 s 1 + 0 s 2 + 0 s 3 – M t 3 → max

x 1 + 2 x 2 + s 1 = 500 (maszyny)

x 1 + x 2 + s 2 = 350 (surowiec)

2 x 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)

Klasyczna metoda simpleks ( program WinSTORM ) (3)

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

x 1 + x 2 ≤ 350

(surowiec)

Klasyczna metoda simpleks ( program WinSTORM ) (4)

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

Klasyczna metoda simpleks ( program WinSTORM ) (5)

SENSITIVITY ANALYSIS OF COST COEFFICIENTS

Current

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

Rozwi ą zanie (1)

Zmienna

decyzyjna

Rozwi ą zanie

Min. c j

c j

Max. c j

Status

x 1

250

– ∞

x 2

100

∞

Warto ść funkcji celu

1150

Ograniczenie

Zmienna

swobodna

Min. RHS

RHS

Max. RHS

Wycena

dualna

Maszyny

450

500

∞

Surowiec

300

350

366,67

Min. zysk

550

600

700

-1

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: