1

doc. dr Beata Pułaska-Turyna
Zakład Badań Operacyjnych
Zarządzania – B 506.

Tel.: [phone]

Mail:

[e-mail]

Literatura:
Wspomaganie procesów decyzyjnych,
Marianna Lipiec-Zajchowska (red.),
tom III, Badania operacyjne, C.H.Beck,
2003


Badania operacyjne w przykładach i
zadaniach , Karol Kukuła (red.),
Wydawnictwo Naukowe PWN, dowolne
wydanie

2

BADANIA OPERACYJNE

„Badanie operacji” - operations research 

II wojna światowa.

„Badania operacyjne”

- operational research

- naukowa metoda rozwiązywania problemów

z zakresu podejmowania decyzji.

Zastosowania:

 sporządzanie

matematycznych,

ekonomicznych

i

statystycznych opisów lub modeli decyzji oraz problemów

sterowania w celu analizy sytuacji charakteryzujących się

dużą złożonością i niepewnością,

 analiza

zależności

determinujących

prawdopodobne

konsekwencje

wyboru

decyzji

oraz

formułowanie

odpowiednich mierników efektywności w celu oszacowania

względnej wartości alternatywnych działań.

3

Cechy charakterystyczne:

 ukierunkowanie na podejmowanie decyzji,

 możliwość oceny działania na podstawie kryteriów

ekonomicznej efektywności,

 zaufanie do modelu matematycznego;

 konieczność stosowania oprogramowania komputerowego.

Sposoby osiągania celu:

 poprawa jakości podejmowanych decyzji,

 poprawa jakości koordynacji działań wewnątrz organizacji,

 polepszenie jakości kontroli,

 doskonalenie systemów.

4

Procedura badań operacyjnych

Sytuacja decyzyjna, problem zarządzania

-

wspomaganie decydentów

w poszukiwaniu najlepszej

odpowiedzi na pytanie „Co - jeżeli?”

Sytuacja decyzyjna

Problem

zarządzania

Model

problemu

Decyzje

Rozwiązanie

problemu

Rozpoznanie
Wartościowanie
Modelowanie

Analiza
i ocena

Im

p

le

m

en

ta

cj

a

A

lg

o

ry

tm

y

P

ro

g

ra

m

y

k

o

m

p

u

te

ro

w

e

5

Rozpoznanie, wartościowanie, modelowanie:



rozpoznanie

- zebranie danych liczbowych o

problemie decyzyjnym,



wartościowanie

(ewaluacja)

zebranych

materiałów liczbowych - stwierdzenie problemu

zarządzania i jego określenie merytoryczne i

formalne (matematyczne),



modelowanie.

Model problemu

Algorytmy, programy komputerowe

-

metody

programowania

matematycznego

(programowanie

liniowe,

algorytm

transportowy),

regresja liniowa i wieloraka, drzewo decyzyjne,

programowanie sieciowe, programowanie dynamiczne.

6

Rozwiązanie problemu

Analiza, ocena

- analiza poprawności:

 założeń,

 rozpoznania, wartościowania i modelowania,

wybranego modelu,

 zastosowanego algorytmu,

 zastosowanego programu komputerowego,

 uzyskanego rozwiązania matematycznego.

Decyzje

- zbiór rozwiązań o akceptowanym wstępnie

stopniu dobroci każdego rozwiązania oraz zbiór rozwiązań

suboptymalnych.

Implementacja

- rozwiązanie problemu wybrane przez

decydenta zostaje zastosowane.

7

PROGRAMOWANIE LINIOWE

Postać klasyczna (standardowa)

Funkcja celu (kryterium):

1) maksymalizacja
z = c

1

x

1

+ c

2

x

2

+ ... + c

n

x

n

 MAX

lub z =

j

n





1

c

j

x

j

 MAX

Ograniczenia:
a

11

x

1

+ a

12

x

1

+ ... + a

1n

x

1

< b

1

a

21

x

1

+ a

22

x

1

+ ... + a

2n

x

1

< b

2

...............................................
a

m1

x

1

+ a

m2

x

1

+ ... + a

mn

x

1

< b

m

Warunki brzegowe:
x

1

, x

2

, ... x

n

> 0

cx  MAX
Ax < b
x > 0

8

gdzie:
x

j

- zmienna decyzyjna dla j = 1,2, ..., n,

c

j

- współczynniki funkcji celu j = 1,2, ..., n,

a

ij

- współczynniki nakładów j = 1,2, ..., n oraz

i= 1,2, ..., m,
b

j

- zasoby czynników produkcji (zakłada się, że są

nieujemne).

2) minimalizacja
z = c

1

x

1

+ c

2

x

2

+ ... + c

n

x

n

 MIN

lub z =

j

n





1

c

j

x

j

 MIN

Ograniczenia:
a

11

x

1

+ a

12

x

1

+ ... + a

1n

x

1

> b

1

a

21

x

1

+ a

22

x

1

+ ... + a

2n

x

1

> b

2

...............................................
a

m1

x

1

+ a

m2

x

1

+ ... + a

mn

x

1

> b

m

Warunki brzegowe:
x

1

, x

2

, ... x

n

> 0

cx  MIN
Ax > b
x > 0

9

Wektor zmiennych decyzyjnych:

X = [x

1

, x

2

, ..., x

n

]

spełniający warunki ograniczające i brzegowe
nazywamy rozwiązaniem dopuszczalnym
zagadnienia programowania liniowego.

Takie rozwiązanie dopuszczalne, dla którego
funkcja celu osiąga wartość ekstremalną
(MAX,

MIN)

nazywamy

rozwiązaniem

optymalnym.

Graficzna interpretacja programowania

liniowego

Przykład:
Firma

specjalizująca

się

w

produkcji

mrożonych

półfabrykatów

spożywczych

produkuje frytki (1) oraz puree (2). Firma
może kupować ziemniaki u dwóch dostawców.
Z 1t zakupionych ziemniaków u dostawcy
pierwszego (I) można wyprodukować 0,2t
frytek i 0,6t puree (0,2t stanowią odpady), zaś
u dostawcy drugiego (II) odpowiednio - 0,3t i
0,6t. Przy zakupie ziemniaków od I dostawcy
zysk względny wynosi 5 j.p., natomiast od II –
6 j.p. Frytki mogą być produkowane w ilości

10

nie większej niż 18t/miesiąc, natomiast puree
w ilości nie większej niż 48t/miesiąc.

Problem: ile ziemniaków należy zakupić od
każdego dostawcy, aby zmaksymalizować
zysk całkowity?

Produkt

Dostawca I Dostawca II Wielkość

produkcji

Frytki

0,2

0,3

18

Puree

0,6

0,6

48

Zysk względny

5

6

x

1

- ilość ziemniaków kupowana u I dostawcy,

x

2

- ilość ziemniaków kupowana u II dostawcy,

Funkcja celu:

z = 5 x

1

+ 6 x

2

 MAX

Ograniczenia:

0,2 x

1

+ 0,3 x

2

< 18

0,6 x

1

+ 0,6 x

2

< 48

Warunki brzegowe:

x

1

> 0

x

2

> 0

11

1.Zamieniamy nierówności na równania:

I linia prosta:

0,2 x

1

+ 0,3 x

2

= 18

x

1

= 0



0,3 x

2

= 18



x

2

= 60

x

2

= 0



0,2 x

1

= 18



x

1

= 90

II linia prosta:

0,6 x

1

+ 0,6 x

2

= 48

x

1

= 0



0,6 x

2

= 48



x

2

= 80

x

2

= 0



0,6 x

1

= 48



x

1

= 80

12

0,2 x

1

+ 0,3 x

2

< 18

0,6 x

1

+ 0,6 x

2

< 48

A(0, 0): 0,20+0,30=0

0,60+0,60=0

B(80,0): 0,280+0,30=16

0,680+0,60=48

C(90,0): 0,290+0,30=18

0,690+0,60=

54

rozw. sprz.

D(?,?):

0,2 x

1

+ 0,3 x

2

= 18

0,6 x

1

+ 0,6 x

2

= 48



x

1

=60,

x

2

=20



D(60,20): 0,260 + 0,320 = 18

0,660 +0,620 = 48

E(0,80): 0,20 + 0,380 =

24

rozw. sprz.

0,60 + 0,680 = 48

F(0,60): 0,20 + 0,360 = 18

0,60 + 0,660 = 36

13

2. Wyznaczamy

zbiór rozwiązań

dopuszczalnych

14

3. Poszukujemy

rozwiązania

optymalnego

:

 Metoda

podstawiania

:

z = 5 x

1

+ 6 x

2



MAX

A(0,0):

50 + 60 = 0

B(80,0):

580 + 60 = 400

D(60,20):

560 + 620 =

420

MAX

F(0,60):

50 + 660 = 36

15

 Metoda

warstwicy funkcji celu

:

z = 5 x

1

+ 6 x

2



MAX

Zakładamy dowolną wartość funkcji celu:

5 x

1

+ 6 x

2

= 250

x

1

= 0



6 x

2

= 250



x

2

= 41 2/3

x

2

= 0



5 x

1

= 250



x

1

= 50

5 x

1

+ 6 x

2

= 300

x

1

= 0



6 x

2

= 300



x

2

= 50

x

2

= 0



5 x

1

= 300



x

1

= 60

16

Rozwiązanie:

Należy zakupić od I dostawcy 60t ziemniaków
(

x

1

= 60

) natomiast od II dostawcy 20t

ziemniaków (

x

2

=

20

), aby osiągnąć

maksymalny zysk związany z zakupem na
poziomie

z

MAX

= 420 j.p.

Możliwe zbiory rozwiązań dopuszczalnych

1. Zbiór ograniczony (wielokąt wypukły).






2. Zbiór rozwiązań dopuszczalnych jest
zbiorem nieograniczonym (od góry).

17

3. Zbiór rozwiązań dopuszczalnych jest
zbiorem pustym.






4. Zbiór rozwiązań dopuszczalnych jest
punktem.

Rozwiązanie optymalne

1. Zbiór rozwiązań dopuszczalnych jest
wielokątem wypukłym:

18

 funkcja celu osiąga ekstremum (MAX lub

MIN) w jednym punkcie wierzchołkowym

 funkcja celu osiąga ekstremum (MAX lub
MIN) w dwóch wierzchołkach wielokąta
wypukłego

2. Zbiór rozwiązań dopuszczalnych jest
zbiorem nieograniczonym:

 funkcja celu osiąga ekstremum (MIN) w

jednym wierzchołku tego obszaru

19

 funkcja celu osiąga ekstremum (MIN) w

dwóch wierzchołkach tego obszaru

 funkcja celu nie osiąga skończonej wartości

ekstremalnej (MAX)

20

Dualizm w programowaniu liniowym

1. Dla każdego zadania programowania
liniowego można zbudować inne zagadnienie
programowania

liniowego,

zwane

zagadnieniem

(zadaniem)

dualnym

do

zagadnienia wyjściowego - prymalnego.
Zadanie prymalne:
z = c

1

x

1

+ c

2

x

2

+ ... + c

n

x

n

 MAX

a

11

x

1

+ a

12

x

1

+ ... + a

1n

x

1

< b

1

a

21

x

1

+ a

22

x

1

+ ... + a

2n

x

1

< b

2

...............................................
a

m1

x

1

+ a

m2

x

1

+ ... + a

mn

x

1

< b

m

x

1

, x

2

, ... x

n

> 0

Zadanie dualne:
w = b

1

y

1

+ b

2

y

2

+ ... + b

n

y

m

 MIN

a

11

y

1

+ a

21

y

2

+ ... + a

m1

y

m

> c

1

a

12

y

1

+ a

22

y

2

+ ... + a

m2

y

m

> c

2

...............................................
a

1n

y

1

+ a

2n

y

2

+ ... + a

mn

y

m

> c

n

y

1

, y

2

, ... y

m

> 0

21

2. W zadaniu dualnym występuje tyle
zmiennych decyzyjnych (y

m

) ile warunków

ograniczających zawiera zadanie prymalne
(b

m

). Zmienne decyzyjne w zadaniu dualnym

są nazywane cenami dualnymi.

3.

W

zadaniu

dualnym

macierz

współczynników warunków ograniczających
jest

macierzą

transponowaną

względem

macierzy

współczynników

warunków

ograniczających zadania prymalnego.

a

11

a

12

..... a

1n

a

11

a

21

..... a

m1

a

21

a

22

..... a

2n

a

12

a

22

..... a

m2

A =

.....

.................

A

T

= ......................

a

m1

a

m2

..... a

mn

a

1n

a

2n

..... a

mn

4. Warunki ograniczające w zadaniu dualnym
mają nierówności o przeciwnym kierunku do
nierówności warunków ograniczających w
zadaniu prymalnym.

22

5. W zadaniu dualnym wyrazy wolne
warunków

ograniczających

są

równe

współczynnikom

funkcji

celu

zadania

prymalnego.

6. Współczynniki funkcji celu zadania
dualnego

są

równe

wyrazom

wolnym

warunków

ograniczających

zadania

prymalnego.

7.

Kryterium

optymalizacyjne

zadania

dualnego

jest

przeciwne

do

kryterium

optymalizacyjnego zadania prymalnego.

8. Jeśli jedno z zagadnień dualnych ma
rozwiązanie

optymalne,

to

rozwiązanie

optymalne ma również drugie z tych
zagadnień, przy czym zachodzi równość:

z

MIN

= w

MAX

9. Jeśli w jednym z zagadnień dualnych
optimum funkcji celu jest nieograniczone, to
jego zagadnienie dualne jest sprzeczne.

23

10. Jeżeli j-ty warunek zadania dualnego jest
(chociaż w jednym) optymalnym rozwiązaniu
tego programu spełniony z nierównością
(ostro), to odpowiadająca mu j-ta zmienna x

j

w

(dowolnym) optymalnym rozwiązaniu zadania
prymalnego przyjmuje wartość 0 i odwrotnie.
Jest to tzw. twierdzenie o równowadze
wykorzystywane

do

sprawdzania

optymalności

danego

rozwiązania

dopuszczalnego.

Przykład:
Zadanie prymalne:
x

1

- ilość ziemniaków kupowana u I dostawcy,

x

2

- ilość ziemniaków kupowana u II dostawcy,

Funkcja celu:

z =

5

x

1

+

6

x

2



MAX

Ograniczenia:

0,2

x

1

+

0,3

x

2

<

18

0,6

x

1

+

0,6

x

2

<

48

Warunki brzegowe:

x

1

> 0

x

2

> 0

Rozwiązanie: x

1

=60, x

2

=20, z

MAX

= 420

24

Zadanie dualne:
y

1

- cena dualna I ograniczenia (moce

produkcyjne przy produkcji frytek),

y

2

- cena dualna II ograniczenia (moce

produkcyjne przy produkcji puree),

Funkcja celu:

w =

18

y

1

+

48

y

2



MIN

Ograniczenia:

0,2

y

1

+

0,6

y

2

>

5

0,3

y

1

+

0,6

y

2

>

6

Warunki brzegowe:

y

1

> 0

y

2

> 0

25

Rozwiązanie: y

1

=10, y

2

=5, w

MIN

= 420

Interpretacja:

y

1

=10

zwiększenie

I

zasobu

(mocy

produkcyjnych przy produkcji frytek) o
jednostkę

(1t)

spowoduje

taką

zmianę

rozwiązania

optymalnego

w

zadaniu

prymalnym w efekcie, której wartość funkcji
celu wzrośnie o 10 j.p:

0,2 x

1

+ 0,3 x

2

<

19 (18+1)

0,6 x

1

+ 0,6 x

2

< 48



x

1

=50,

x

2

=30



z

MAX

= 550 + 630 = 430

z = 430 - 420 = 10  y

1

26

y

2

=5

zwiększenie

II

zasobu

(mocy

produkcyjnych przy produkcji puree) o
jednostkę

(1t)

spowoduje

taką

zmianę

rozwiązania

optymalnego

w

zadaniu

prymalnym w efekcie, której wartość funkcji
celu wzrośnie o 5 j.p:

0,2 x

1

+ 0,3 x

2

< 18

0,6 x

1

+ 0,6 x

2

<

49 (48+1)



x

1

=65,

x

2

=16 2/3



z

MAX

= 565 + 616 2/3 = 425

z = 425 - 420 = 5  y

2