Wykład 1

Badania operacyjne

dr Radosław Jadczak

Katedra Badań Operacyjnych

Bud. „E” pok. E136

WT, 11.30-15.00

rjadczak@pai.net.pl

Badania operacyjne – zakres zagadnień (1) 1.

Elementy teorii podejmowania decyzji

podejmowanie decyzji w warunkach niepewności

podejmowanie decyzji w warunkach ryzyka

Liniowe modele decyzyjne

budowa modeli decyzyjnych

poszukiwanie i analiza rozwiązań optymalnych

analiza postoptymalizacyjna

Optymalizacja w zagadnieniach przewozowych

klasyczne zadanie transportowe

modyfikacje zadania transportowego

pochodne zadania transportowego – zagadnienie przydziału Badania operacyjne – zakres zagadnień (2) 4.

Modelowanie złożonych przedsięwzięć wieloczynnościowych (zarządzanie projektami)

deterministyczna analiza przedsięwzięcia

kosztowo-czasowa analiza przedsięwzięcia

Modelowanie procesów o charakterze masowym

podstawowe pojęcia i definicje

klasyfikacja systemów masowej obsługi

Badania operacyjne – literatura i oprogramowanie

1. Krawczyk S., Badania operacyjne dla menedżerów, Wyd. AE we Wrocławiu, Wrocław, 1997

2. Kukuła K. (red.), Badania operacyjne w przykładach i zadaniach, PWN, Warszawa, 1999

3. Miszczyńska D., Miszczyński M., Wybrane metody badań operacyjnych, WSzEH, Skierniewice, 2002

4. Trzaskalik T. , Wprowadzenie do badań operacyjnych z komputerem, PWE, Warszawa, 2003

1. BAD_OP - pakiet programów załączony do podręcznika [6]

2. SOLVER (narzędzie Excel’a w MS Office)

3. WinQSB

4. WinSTORM

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 - dzienna produkcja wyrobu A [szt.]

x - dzienna produkcja wyrobu B [szt.]

2. Funkcja celu: (wartość produkcji w cenach zbytu) F( x) = F( x , x ,) = 3 x + 4 x 1

→

max

[$]

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

x + 2 x

2 ≤ 500

[min]

(surowiec)

x + x

2 ≤ 350

[kg]

(min. poziom zysku) 2 x + x

2 ≥ 600

[$]

4. Warunki brzegowe: (warunki dotyczące zmiennych decyzyjnych) x

, x ∈ C

1 ≥ 0

[szt.]

x1 2

x2 ≥ 0

[szt.]

Postać ogólna modelu decyzyjnego (1)

1. Lista n zmiennych decyzyjnych:

x – zmienna decyzyjna nr 1

[j.m.]

x – zmienna decyzyjna nr 2

[j.m.]

...

x – zmienna decyzyjna nr n

[j.m.]

2. Funkcja celu:

F( x) = F( x , x ,…, x ) = c x + c x + … + c x 1

1 1

2 2

n n

→

max (lub min) [j.m.]

Postać ogólna modelu decyzyjnego (2)

3. Ograniczenia:

(ograniczenie nr 1)

a x + a x + … + a x

[j.m.]

11 1

12 2

1n n

≤ b1

(ograniczenie nr k)

a x + a x + … + a x

= b

[j.m.]

k1 1

k2 2

kn n

(ograniczenie nr m)

a x + a x + … + a x

[j.m.]

m1 1

m2 2

mn n ≥ bm

4. Warunki brzegowe:

x1 ≥ 0 x2 ≥ 0 … xn ≥ 0

Ilustracja graficzna zbioru decyzji dopuszczalnych

600

min. zysk

400

surowiec

200

maszyny

200

400

600

Rozwiązanie optymalne

1. Formalny zapis decyzji optymalnej:

x opt = 250

opt

= 100

F( x

; x

) = 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) 4

Metoda graficzna

F → max

300

G[150,200]

w: F = 1150

w: F = 1050

200

rozwiązanie

w: F = 900

optymalne

A = (300,0)

100

B = (350,0)

C = (250,100)

100

200

300

Klasyczna metoda simpleks ( informacje ogólne, idea) (1) 1. Postać modelu:

F( x) = F( x , x ,) = 3 x + 4 x 1

→

max

x + 2 x

2 ≤ 500

(maszyny)

x + x

2 ≤ 350

(surowiec)

2 x + x

2 ≥ 600

(min. poziom zysku)

, x ∈ C

1 ≥ 0 x2 ≥ 0

x1 2

2. Postać kanoniczna modelu:

3 x + 4 x

2 + 0 s + 0 s + 0 s – M t 1

→

max

x + 2 x

= 500

(maszyny)

2 + s1

x + x

= 350

(surowiec)

+ s2

2 x + x

= 600

(min. poziom zysku)

- s + t

x1 ≥ 0 x2 ≥ 0 s1 ≥ 0 s2 ≥ 0 s3 ≥ 0 t3 ≥ 0

Klasyczna metoda simpleks ( informacje ogólne, idea) (2) 3. Interpretacja zmiennych swobodnych:

s – niewykorzystany fundusz czasu pracy maszyn (limit 500 minut) 1

( ang. slack – luz)

s – niewykorzystany zasób surowca (limit 350 kg) 2

( ang. slack – luz)

s – przekroczenie minimalnej kwoty zysku (

żądane minimum 600 $)

( ang. surplus – nadwyżka)

t – zmienna sztuczna – zmienna pomocnicza, nie ma interpretacji 3

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

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 – wycena dualna

Jeżeli w j-tym ograniczeniu zadania programowania liniowego wyraz wolny b wzro

śnie (spadnie) o jednostkę, to optymalna wartość funkcji celu f(xopt) wzrośnie o y jednostek, tj. do poziomu f(xopt) + y .

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 cj

prawa strona ograniczenia bj

Analiza wrażliwości (2)

Konsekwencje zmian jednego wybranego współczynnika c w ramach j

przedziału dopuszczalnych zmian:

rozwiązanie optymalne zadania nie ulegnie zmianie

zmieni się optymalna wartość funkcji celu

zmieni się wycena dualna