2010-02-27

1

Badania operacyjne

Arkadiusz Mazurkiewicz

Tomasz Owczarek

2

Plan przedmiotu

Wstęp.

Liniowe zadanie decyzyjne

model matematyczny, zadanie dualne, metody rozwiązywania.

Różne typy liniowego zadania decyzyjnego

zadanie produkcyjne, mieszanki i diety, zadanie transportowe.

Problem maksymalizacji przepływu

Optymalizacja dyskretna

zagadnienie przydziału, lokalizacji produkcji, wyboru projektu
inwestycyjnego.

Analiza sieciowa przedsięwzięć

sieci z funkcją czasu, analiza czasowo-kosztowa.

Gry i strategie

gry dwuosobowe o sumie zero, gry z naturą – podejmowanie decyzji w
warunkach niepewności i ryzyka.

2010-02-27

2

3

Bibliografia

Ignasiak E. (red.) [2001], Badania operacyjne, PWE,
Warszawa.

Czerwiński Z. [1984], Matematyka na usługach ekonomii,
PWN, Warszawa.

Wagner H.M. [1980], Badania operacyjne. Zastosowania w
zarządzaniu

, PWE, Warszawa.

Kukuła K. (red.) [1993], Badania operacyjne w przykładach i
zadaniach

, PWN, Warszawa.

Jóźwiak J. J. Podgórski [1997], Statystyka od podstaw, PWE,
Warszawa.

4

Laboratorium

Materiały do laboratorium i wszelkie materiały pomocnicze znajdują
się w systemie Ilias.

Ś

cieżka dojścia do materiałów: Wydział Przedsiębiorczości i

Towaroznawstwa / 2009/2010 - semestr letni / Zarządzanie II semestr,
studia II stopnia / Badania operacyjne

Hasło do kursu: bo

Dwa zagadnienia (zagadnienie produkcji i diety oraz zagadnienie
transportowe) będą realizowane na zajęciach, dwa pozostałe w
ramach e-learningu (przydziału i podejmowanie decyzji w warunkach
niepewności i ryzyka)

Kontakt do konsultacji w ramach e-learningu (i nie tylko):

dr A. Mazurkiewicz: [e-mail]

dr T. Owczarek: [e-mail]

lub pokój B-418 w godzinach konsultacji.

2010-02-27

3

5

Przedmiot zainteresowań

Badania operacyjne to dziedzina nauki zajmująca się
analizą procesów związanych z podejmowania decyzji w
celowej działalności, generowaniem różnych wariantów
decyzji oraz ich oceną ze względu na różne kryteria.

Decyzje oceniane są na podstawie kryteriów ilościowych
(matematycznych, szczególnie optymalizacyjnych).

Zajmują się analizą decyzji na podstawie posiadanej
informacji. Przetwarzanie informacji wskazuje na silny
związek badań operacyjnych z informatyką. Jednak
związek ten nie pozwala na utożsamianie obu tych dziedzin
wiedzy.

6

Przedmiot zainteresowań

Metody informatyczne są (mogą być) narzędziem
wykorzystywanym do podejmowania decyzji.

Badania operacyjne wykorzystywane były pierwotnie przez
wojsko w latach drugiej wojny światowej. Aktualnie mogą
służyć do modelowania większości procesów zachodzących w
przedsiębiorstwie (produkcja, gospodarka magazynowa,
logistyka) i gospodarce (przydział ograniczonej ilości zasobów).

Badania operacyjne pozwalają na budowę modeli analitycznych,
opisujących rzeczywistość (w uproszczony sposób) za pomocą
układów równań i nierówności, oraz symulacyjnych,
pozwalających odpowiedzieć na pytanie: Co stałoby się
gdyby..?

2010-02-27

4

7

Podejmowanie decyzji

Podejmując decyzje ekonomiczne mamy najczęściej do
czynienia z optymalizacją warunkową, tzn. podejmowania
decyzji uwzględniających zbiór ograniczeń związanych z
wielkością posiadanych zasobów, wzajemnych stosunków
pomiędzy podmiotami, relacjami pomiędzy podmiotami a
otoczeniem.

Wybierane są decyzje spełniające w sposób najlepszy kryterium
nazywane funkcją celu, najczęściej maksymalizujące lub
minimalizujące ją.

Możliwe jest wystąpienie wielu sprzecznych ze sobą kryteriów,
których jednoczesne spełnienie jest celem decydenta. Występuje
wówczas konflikt, rozwiązaniem którego może być np.
ustalenie hierarchii celów zadania.

8

Podejmowanie decyzji

Obecnie jako dopuszczalne rozwiązanie zadania
decyzyjnego przyjmuje się rozwiązanie niesprzeczne,
tzn. rozwiązanie spełniające wszystkie warunki
ograniczające, które można uzyskać w określonym
czasie i przy określonych kosztach.

Oznacza to zgodę na uproszczony charakter modelu
zjawiska oraz poszukiwanie rozwiązania „dostatecznie
dobrego”, tzn. na zaprzestanie poszukiwania
rozwiązania w chwili uzyskania założonej wcześniej
dokładności (np. w problemie komiwojażera).

2010-02-27

5

9

Podejmowanie decyzji

Etapy podejmowania decyzji:

1.

Sformułowanie problemu decyzyjnego.

2.

Budowa modelu matematycznego.

3.

Pozyskanie informacji wejściowych niezbędnych do ustalenia
parametrów zadania.

4.

Procedura obliczeniowa za pomocą wybranego algorytmu.

5.

Analiza jakości rozwiązań modelu z punktu widzenia realności
i stabilności.

6.

Weryfikacja modelu – sprawdzenie jego adekwatności i
poprawności.

7.

Podjęcie decyzji i wdrożenie rozwiązania.

10

Model matematyczny

Model matematyczny to uproszczony opis zjawiska

pozwalający na znalezienie przybliżonego rozwiązania
problemu decyzyjnego.

W badaniach operacyjnych występują trzy rodzaje

modeli:

modele deterministyczne

modele w warunkach ryzyka

modele w warunkach niepewności.

2010-02-27

6

11

Model matematyczny

W modelu deterministycznym wszystkie parametry są stałe i
znane. Rozwiązaniem problemu są wektory i/lub funkcje
mające określoną interpretację ekonomiczną.

W modelu w warunkach ryzyka (sytuacje ryzykowne) dany
jest rozkład prawdopodobieństwa zmiennej losowej opisującej
parametry zadania.

W modelu w warunkach niepewności nieznane są rozkłady
zmiennych losowych, informacje wejściowe dotyczą reguł
zachowania się przeciwnika znajdującego się w sytuacji
konfliktowej (np. w teorii gier), a rozwiązanie zależy od
awersji do ryzyka decydenta.

12

Model matematyczny

Można wyróżnić również modele liniowe i nieliniowe oraz modele

(rozwiązania) dyskretne:

W modelach liniowych wszystkie ograniczenia i funkcja celu
wyrażone są za pomocą funkcji liniowych wielu zmiennych.

W modelu nieliniowym przynajmniej jedno ograniczenie lub
funkcja celu wyrażona jest za pomocą funkcji nieliniowej.

W modelach dyskretnych rozwiązaniem jest zbiór złożony z
przeliczalnej ilości punktów (zmienne przyjmują przeliczalną
ilość wartości).

Wykład z Badań operacyjnych w znacznej części poświęcony

będzie wyłącznie liniowemu zadaniu decyzyjnemu (LZD).

2010-02-27

7

13

Model matematyczny

W modelu matematycznym zadania liniowego

występują:

zmienne decyzyjne – wielkości, które mają być
wyznaczone,

parametry zadania – wielkości dane,

warunki ograniczające – ograniczenia wynikające z
postawionego problemu (treści zadania lub wiedzy
ogólnej),

funkcja celu – funkcja-kryterium określająca
przydatność otrzymanych rozwiązań.

14

Model matematyczny

Istnieją dwa rodzaje rozwiązań LZD:

rozwiązanie dopuszczalne – każde rozwiązanie
spełniające wszystkie warunki ograniczające. Z
zasady istnieje wiele rozwiązań dopuszczalnych,

rozwiązanie optymalne – to rozwiązanie
dopuszczalne, które najlepiej spełnia funkcję celu
(żadne rozwiązanie nie spełnia lepiej funkcji celu).
Ilość rozwiązań optymalnych jest ściśle określona.
Może być ich nieskończenie wiele, jedno lub
ż

adnego.

2010-02-27

8

15

Rozwiązania dopuszczalne

W zadaniu programowania liniowego zbiór rozwiązań
dopuszczalnych jest zbiorem wypukłym.

Wnioski.

Niemożliwe jest istnienie dwóch, trzech, itd.. rozwiązań optymalnych.

Zadanie Programowania Liniowego ma 0, 1 lub nieskończenie wiele
rozwiązań.

16

Model matematyczny

Model matematyczny w postaci normalnej LZD o

n

niewiadomych i m ograniczeniach można zapisać następująco:

Zmienne:
x

= [x

1

, x

2

, ..., x

n

]

Funkcja celu:
F

(x) = c

1

x

1

+ c

2

x

2

+ ... + c

n

x

n

→ max (min)

Warunki ograniczające:
a

1,1

x

1

+ a

1,2

x

2

+ ... + a

1,n

x

n

≤ (≥, =) b

1

a

2,1

x

1

+ a

2,2

x

2

+ ... + a

2,n

x

n

≤ (≥, =) b

2

...

a

m

,1

x

1

+ a

m

,2

x

2

+ ... + a

m

,n

x

n

≤ (≥, =) b

m

Ograniczenia zmiennych:
x

i

≥ (≤, bez ograniczenia) d

i

, gdzie i=1, 2, ..., n

2010-02-27

9

17

Przykłady

Przykład 1. Zadanie produkcyjne (wybór asortymentu produkcji)

Zakład produkuje dwa wyroby, które są produkowane na dwóch obrabiarkach:
O

1

i O

2

oraz na frezarce F. Czas pracy tych maszyn jest ograniczony i wynosi:

O

1

– 33.000 h, O

2

– 13.000 h, F – 80.000 h. Zużycie czasu pracy maszyn na

wyprodukowanie wyrobów przedstawia tabelka:

Zysk ze sprzedaży wyrobu I wynosi 1 zł, wyrobu II – 3 zł. Z analizy sprzedaży
wynika, że wyrobu II nie można sprzedać więcej niż 7.000 szt.

Zaplanować produkcję tak, aby zysk był jak największy.

I

II

O

1

3

1

O

2

1

1

F

5

8

Maszyny

Zużycie czasu

18

Przykłady

Zmienne decyzyjne:

x

1

, x

2

– wielkość produkcji wyrobów I i II.

Funkcja celu:

Celem jest maksymalizacja zysku.
F

= 1x

1

+ 3x

2

→ max

Ograniczenia:

1.

3x

1

+ 1x

2

≤ 33.000

– ograniczenie dla obrabiarki O

1

2.

1x

1

+ 1x

2

≤ 13.000

– ograniczenie dla obrabiarki O

2

3.

5x

1

+ 8x

2

≤ 80.000

– ograniczenie dla frezarki F

4.

x

2

≤ 7.000

– ograniczenie dla wielkości sprzedaży

5.

x

1

≥ 0

– ograniczenia zmiennych

6.

x

2

≥ 0

2010-02-27

10

19

Przykłady

Zadanie ma nieskończenie wiele rozwiązań dopuszczalnych.

Są nimi między innymi pary liczb:

x

1

=0

x

2

=0

F

=0

x

1

=1

x

2

=1

F

=4

x

1

=1 000

x

2

=1 000

F

=4 000

x

1

=11 000

x

2

=0

F

=11 000

x

1

=4 000

x

2

=7 000

F

=25 000

Które z tych rozwiązań jest najlepsze, a które najgorsze?

Czy najlepsze rozwiązanie ze wskazanych rozwiązań jest

rozwiązaniem optymalnym?

Rozwiązanie optymalne (obliczone):

x

1

=4 800, x

2

=7 000,

F

=25 800

20

Metoda graficzna

Zbiór rozwiązań dopuszczalnych
ma brzeg.

Rozwiązanie optymalne jest
zawsze na brzegu zbioru
rozwiązań dopuszczalnych.

Rysujemy kierunek funkcji celu.

X

1

X

2

Przesuwamy równolegle prostą
reprezentującą funkcję celu aż
znajdziemy najodleglejszy punkt
zbioru rozwiązań dopuszczalnych.

Po znalezieniu wierzchołka
będącego rozwiązaniem
optymalnym znajdujemy jego
współrzędne.

W układzie współrzędnych należy zaznaczyć poszczególne
warunki ograniczające. Zbiór punktów należący do wszystkich
ograniczeń jest zbiorem rozwiązań dopuszczalnych

2010-02-27

11

21

Metoda graficzna

Wierzchołek będący rozwiązaniem optymalnym leży na przecięciu
prostych reprezentujących ograniczenia 3 i 4. Jego współrzędne są
rozwiązaniem układu równań:

5x

1

+ 8x

2

= 80.000

x

2

= 7.000

Rozwiązanie to jest następujące:

x

1

= 4.800

x

2

= 7.000

Wartość funkcji celu dla rozwiązania optymalnego:

F

= x

1

+ 3x

2

= 4.800 + 3*7.000 = 25.800

Odpowiedź.
Jeżeli zakład wyprodukuje 4.800 sztuk wyrobu I i 7.000 sztuk
wyrobu II to zysk będzie maksymalny i będzie wynosił 25.800.

22

Przykłady

Przykład 2. Zagadnienie diety

Dziecko potrzebuje tygodniowo co najmniej 120 j. witaminy A, 60 j. wit. D, 36
j. wit. C oraz 180 j. wit. E. Witaminy te są zawarte w dwóch produktach: P1 i
P2. Ze względu na szkodliwość witaminy A można jej spożyć najwyżej 240j.
Zawartość poszczególnych witamin w kilogramie produktów zawiera tabelka:

Ile należy zakupić produktów P1 i P2, aby dostarczyć dziecku odpowiednią ilość
witamin oraz aby koszt zakupu był minimalny?

Witaminy

P1

P2

A

6

3

D

1

3

C

9

1

E

6

6

Cena

1,20 zł 1,80 zł

2010-02-27

12

23

Przykłady

Model matematyczny
Zmienne decyzyjne:

x

1

, x

2

– ilość kupionych produktów P1 i P2 (w kg).

Funkcja celu:

Celem jest minimalizacja kosztów zakupu.
F

= 1,2x

1

+ 1,8x

2

→ min

Ograniczenia:

1.

6x

1

+3x

2

≥ 120

– ograniczenie dla witaminy A

2.

1x

1

+3x

2

≥ 60

– ograniczenie dla witaminy D

3.

9x

1

+x

2

≥ 36

– ograniczenie dla witaminy C

4.

6x

1

+6x

2

≥ 180

– ograniczenie dla witaminy E

5.

6x

1

+3x

2

≤ 240

– ograniczenie dla witaminy A

6.

x

1

≥ 0, x

2

≥ 0

– ograniczenia zmiennych

24

Przykłady

Rozwiązania

Rozwiązania dopuszczalne (przykładowe):

x

1

= 15

x

2

= 40

F

= 90

x

1

= 10

x

2

= 20

F

= 48

x

1

= 20

x

2

= 30

F

= 78

x

1

= 30

x

2

= 15

F

= 63

x

1

= 11

x

2

= 46

F

= 96

Które z podanych rozwiązań jest najlepsze?

Czy to jest rozwiązanie optymalne?

Rozwiązanie optymalne:

x

1

=15, x

2

=15, F=45

2010-02-27

13

25

Przykłady

Rozwiązanie metodą graficzną:

X

1

X

2

1

2

3

4

5

1,2

x +

1,8

x =

36

1

2

Jest dokładnie jedno rozwiązanie optymalne: x

1

=15 i x

2

=15.

26

Przykłady

Rozwiązanie optymalne leży na przecięciu prostych ograniczeń 2
i 4. Jest ono rozwiązaniem układu równań:

x

1

+ 3x

2

= 60

6x

1

+ 6x

2

= 180

Rozwiązanie to jest następujące:

x

1

= 15

x

2

= 15

Wartość funkcji celu dla rozwiązania optymalnego:

F

= 1,2x

1

+ 1,8x

2

= 1,2*15 + 1,8*15 = 45

Odpowiedz.
Koszt diety będzie minimalny oraz spełnione będą wszystkie
ograniczenia jeżeli dieta będzie się składała z 15 kg produktu P1 i
15 kg produktu P2. Minimalny koszt wyniesie 45 zł.

2010-02-27

14

27

Przykłady

Przykład 3. Zagadnienie diety

Dieta specjalna powinna dostarczyć do organizmu ponad 100 j.
cukru i nie więcej niż 100 j. tłuszczu. Koszt zakupu produktu P1
wynosi 2 zł/kg, produktu P2 – 5 zł/kg. Zawartość obu składników
w dwóch produktach przedstawia tabela (w j/kg):

Produkty

P1

P2

Cukier

10

10

Tłuszcz

20

25

Dobierz skład diety optymalnie pod względem kosztów.

28

Przykłady

Model matematyczny
Zmienne decyzyjne:

x

1

, x

2

– ilość kupionych produktów P1 i P2 (w kg).

Funkcja celu:

Celem jest minimalizacja kosztów zakupu.
F

= 2x

1

+ 5x

2

→ min

Ograniczenia:

1.

10x

1

+10x

2

≥ 100

– ograniczenie dla cukru

2.

20x

1

+25x

2

≤ 100

– ograniczenie dla tłuszczu

3.

x

1

≥ 0, x

2

≥ 0

– ograniczenia zmiennych

2010-02-27

15

29

Przykłady

Rozwiązanie metodą graficzną

X

1

X

2

1

2

Brak części wspólnej. Brak rozwiązań dopuszczalnych. Brak rozwiązania
optymalnego.

30

Przykłady

Przykład 4.
Przedsiębiorstwo produkuje dwa wyroby: A i B. Do produkcji tych
wyrobów zużywa się trzech surowców: S1, S2 i S3, których
dzienne zużycie jest limitowane. Ilość surowców niezbędnych do
produkcji poszczególnych wyrobów pokazano w tabelce:

Surowce

A

B

Limit

S1

2

2

30

S2

3

2

36

S3

5

1

60

Dobrać wielkość produkcji, aby zysk był największy, jeżeli zysk
jednostkowy ze sprzedaży wyrobu A wynosi 10 zł, a wyrobu B -
10 zł.

2010-02-27

16

31

Przykłady

Model matematyczny
Zmienne decyzyjne:

x

1

, x

2

– wielkość produkcji wyrobów A i B.

Funkcja celu:

Celem jest maksymalizacja zysku.
F

= 10x

1

+ 10x

2

→ max

Ograniczenia:

1.

2x

1

+2x

2

≤ 30 – ograniczenie dla surowca S1

2.

3x

1

+2x

2

≤ 36 – ograniczenie dla surowca S2

3.

5x

1

+x

2

≤ 60

– ograniczenie dla surowca S3

4.

x

1

≥ 0, x

2

≥ 0

– ograniczenia zmiennych

32

Przykłady

Rozwiązanie metoda graficzną

X

1

X

2

1

2

3

10

x

+1

0x

=1

00

1

2

2010-02-27

17

33

Przykłady

Rozwiązaniem optymalnym jest jeden z boków.
Oznacza to że jest nieskończenie wiele rozwiązań.

Konieczne jest zapisanie tego rozwiązania.

Z rozwiązania odpowiednich układów równań wynika, że
wierzchołki wielokąta należące do rozwiązania optymalnego
mają współrzędne (0;15) i (6;9), natomiast cały odcinek
zawiera się w prostej o równaniu x

1

+x

2

=15.

Rozwiązanie można zapisać:
„Rozwiązaniem optymalnym jest każdy punkt należący do
odcinka o wierzchołkach (0;15) i (6;9)”
„Rozwiązaniem optymalnym jest każda para liczb x

1

i x

2

,

spełniających zależność: x

2

=15-x

1

, gdzie x

1

∈

[0;6]”.

34

I jeszcze przykłady...

Przykład 5. Zagadnienie transportowe.

Trzy duże gospodarstwa rolne mogą odstawić do trzech punktów skupu pszenicę
w następujących ilościach: gospodarstwo 1 – 100 T, gospodarstwo 2 – 250 T,
gospodarstwo 3 – 50 T. Punkty skupu mogą przyjąć pszenicę w następujących
ilościach: A – 150 T, B – 100 T, C – 100 T. Jednostkowe koszty transportu (w
zł za tonę) pszenicy z gospodarstw do punktów skupu podano w tabeli:

A

B

C

1

50

100

100

2

150

200

50

3

20

100

20

Gospodarstwa

Punkty skupu

Wyznaczyć plan przewozów, tak aby całkowity koszt przewozów był jak
najmniejszy.

2010-02-27

18

35

I jeszcze przykłady...

Model matematyczny

Zmienne decyzyjne:

x

i,j

– ilość pszenicy przewożonej z i-tego gospodarstwa do j-tego punktu skupu.

Funkcja celu:

Celem jest minimalizacja całkowitych kosztów transportu.
F

=50x

1,1

+100x

1,2

+100x

1,3

+150x

2,1

+200x

2,2

+50x

2,3

+20x

3,1

+100x

2,3

+20x

3,3

→ min

Ograniczenia:

x

1,1

+x

1,2

+x

1,3

≤ 100

– ograniczenia dla dostawców

x

2,1

+x

2,2

+x

2,3

≤ 250

x

3,1

+x

3,2

+x

3,3

≤ 50

x

1,1

+x

2,1

+x

3,1

= 150

– ograniczenia dla odbiorców

x

1,2

+x

2,2

+x

3,2

= 100

x

1,3

+x

2,3

+x

3,3

= 100

x

i,j

≥ 0

– ograniczenia zmiennych

36

I jeszcze przykłady...

Rozwiązanie optymalne:

000

.

33

F

,

0

0

50

150

100

0

0

0

100

X

=





















=

Odpowiedz.

Gospodarstwo 1 dostarcza 100 t pszenicy do punktu skupu A,
0 t pszenicy do punktu skupu B i 0 t pszenicy do punktu skupu C,
gospodarstwo 2 dostarcza 0 t pszenicy do punktu skupu A,
100 t pszenicy do punktu skupu B, itd.
Całkowity koszt transportu będzie wtedy najmniejszy i będzie wynosił
33 tys. zł.

2010-02-27

19

37

I jeszcze przykłady...

Przykład 6.

W poszczególne dni tygodnia na poczcie potrzebna jest następująca
liczba pracowników pełnoetatowych do sprawnej obsługi klienta:

Dzień tygodnia

Wymagana liczba

pracowników

poniedziałek

17

wtorek

13

ś

roda

15

czwartek

19

piątek

14

sobota

16

niedziela

11

Wiedząc, że pracownicy muszą pracować przez 5 kolejnych dni, po czym
korzystają z dwudniowej przerwy w pracy, wyznacz optymalną liczbę
zatrudnionych w każdym dniu tygodnia w taki sposób, aby
zminimalizować ogólną liczbę zatrudnionych.

38

I jeszcze przykłady...

Model matematyczny

Zmienne decyzyjne:

x

i

– ilość pracowników zaczynających pracę i-tego dnia tygodnia..

Funkcja celu:

Celem jest minimalizacja całkowitej ilości zatrudnionych.
F

= x

1

+ x

2

+ x

3

+ x

4

+ x

5

+ x

6

+ x

7

→ min

Ograniczenia:

x

1

+ x

4

+ x

5

+ x

6

+ x

7

≥ 17

– ograniczenie dla poniedziałku

x

1

+ x

2

+ x

5

+ x

6

+ x

7

≥ 13

– ograniczenie dla wtorku

x

1

+ x

2

+ x

3

+ x

6

+ x

7

≥ 15

– ograniczenie dla środy

x

1

+ x

2

+ x

3

+ x

4

+ x

7

≥ 19

– ograniczenie dla czwartku

x

1

+ x

2

+ x

3

+ x

4

+ x

5

≥ 14

– ograniczenie dla piątku

x

2

+ x

3

+ x

4

+ x

5

+ x

6

≥ 16

– ograniczenie dla soboty

x

3

+ x

4

+ x

5

+ x

6

+ x

7

≥ 11

– ograniczenie dla niedzieli

x

i

≥ 0

– ograniczenia zmiennych

2010-02-27

20

39

I jeszcze przykłady...

Rozwiązanie:

(zyskane za pomocą Solvera w MS Excel)

x

1

=1, x

2

=3, x

3

=2, x

4

=8, x

5

=0, x

6

=3, x

7

=6

Wartość funkcji celu:

F

=21

40

Metoda Simpleks

Metoda Simpleks jest metodą rozwiązywania Zadań
Programowania Liniowego.

W praktyce jest to metoda rozwiązywania układu wielu równań
z wieloma niewiadomymi, przy założeniu niedostatecznej liczby
niezależnych równań i występowania kryterium oceny
rozwiązań (funkcji celu).

Występuje w wielu odmianach i mutacjach. Prezentowana
odmiana oparta jest na operacjach na układzie równań i
rozwiązuje wyłącznie zadania na maksimum.

Ideą metody jest wyszukiwanie kolejnych rozwiązań leżących
na wierzchołkach wielokąta rozwiązań dopuszczalnych i ocena
ich pod względem realizacji funkcji celu.

2010-02-27

21

41

Metoda Simpleks

Przed rozpoczęciem konstruowania tablicy Simpleks
konieczna jest zamiana modelu matematycznego z
postaci normalnej na postać kanoniczną.

F

(x) - c

1

x

1

- c

2

x

2

- ... - c

n

x

n

= 0

a

1,1

x

1

+ a

1,2

x

2

+ ... + a

1,n

x

n

+ s

1

= b

1

a

2,1

x

1

+ a

2,2

x

2

+ ... + a

2,n

x

n

+ s

2

= b

2

...

a

m

,1

x

1

+ a

m

,2

x

2

+ ... + a

m

,n

x

n

+ s

m

= b

m

x

i

≥ (≤, bez ograniczenia) d

i

,

s

i

≥ (≤, =) 0, gdzie i=1, 2, ..., n.

42

Metoda Simpleks

Przykład 7.

Wytwórnia Zabawek Pluszowych „KUBUŚ PUCHATEK”
produkuje dwa rodzaje zabawek Kłapouchego i Prosiaczka. Do
produkcji używa się m.in. dwóch rodzajów guzików: czerwonych i
niebieskich. Przy produkcji Kłapouchego zużywa się 2 guziki
czerwone i 1 niebieski, przy produkcji Prosiaczka : 2 czerwone i 4
niebieskie. W magazynie znajduje się 100 guzików czerwonych i
160 niebieskich. Zysk ze sprzedaży Kłapouchego wynosi 6 zł,
natomiast Prosiaczka – 4 zł. Proszę podać optymalną produkcję
wytwórni ze względu na zysk.

2010-02-27

22

43

Metoda Simpleks

Model matematyczny

Postać normalna:

F

=6x

1

+4x

2

→ max

2x

1

+2x

2

≤ 100

x

1

+4x

2

≤ 160

x

1

, x

2

≥ 0

Postać kanoniczna:

F

-6x

1

-4x

2

= 0

2x

1

+2x

2

+s

1

= 100

x

1

+4x

2

+s

2

= 160

x

1

, x

2

, s

1

, s

2

≥ 0

44

Metoda Simpleks

Budowa tablicy Simpleks:

Do tablicy przepisujemy w wierszach współczynniki stojące przy
wszystkich zmiennych z postaci kanonicznej modelu
matematycznego LZD:

W

F

x

1

x

2

s

1

s

2

stałe

uwagi

0

1

-6

-4

0

0

0

1

0

2

2

1

0

100

2

0

1

4

0

1

160

2010-02-27

23

45

Metoda Simpleks

Każda tablica Simpleks zawiera kolumny składające się z
samych zer i jednej jedynki (kolumny F, s

1

i s

2

) oraz kolumny

zawierające „coś innego” (x

1

i x

2

). Pierwsze należą do

rozwiązania bazowego (zmienne bazowe), pozostałe są poza
tym rozwiązaniem (zmienne niebazowe).

Z kolumn z zerami i jedynką zawsze można zbudować macierz
jednostkową (jedynki na przekątnej pozostałe to zera). Brak
takiej możliwości oznacza błąd obliczeniowy.

W każdym kroku można odczytać rozwiązanie dopuszczalne i
sprawdzić czy jest ono rozwiązaniem optymalnym.

46

Metoda Simpleks

Odczytywanie rozwiązania:

Zmienne niebazowe mają z definicji wartość 0. Czyli x

1

i x

2

równają się 0.

Zmienne z rozwiązania bazowego: w kolumnie odszukujemy jedynkę i w
wierszu w którym ona się znajduje, w stałych odczytujemy wynik. (np. w
kolumnie s

1

jedynka znajduje się w wierszu 1, w stałych w wierszu 1 jest liczba

100 tzn. s

1

=100). W tym kroku rozwiązaniem jest:

F

= 0, x

1

= 0, x

2

= 0, s

1

= 100, s

2

= 160

Rozwiązanie optymalne.

Odczytane rozwiązanie jest optymalne, jeżeli w wierszu 0 nie ma liczb
ujemnych. Jeżeli w wierszu 0 znajdują się liczby ujemne to rozwiązanie nie jest
optymalne i należy je poprawić.

Otrzymane rozwiązanie nie jest optymalne.

2010-02-27

24

47

Metoda Simpleks

Poprawianie rozwiązania dopuszczalnego:

Wyszukujemy kolumnę mającą w wierszu 0 liczbę ujemną i
najmniejszą.

Dzielimy stałą (kolumna stałe) przez liczbę z kolumny i
wybieramy najmniejszy iloraz. Nie dzielimy przez liczby ujemne.

W miejscu, gdzie jest najmniejszy iloraz po zmianach będzie 1, w
pozostałych komórkach kolumny będą 0.

W

F

x

1

x

2

s

1

s

2

stałe

Uwagi

0

1

-6 (0)

-4

0

0

0

1

0

2 (1)

2

1

0

100

2

0

1 (0)

4

0

1

160

48

Metoda Simpleks

Aby uzyskać taki układ kolumny można wykonywać
następujące działania:

1.

Wszystkie działania muszą dotyczyć całych wierszy. Nie wolno
wykonań jakiegoś działania dla jednego elementu macierzy.

2.

Wiersz w którym ma być 1 (tutaj: wiersz 1) należy pomnożyć lub
podzielić przez odpowiednią liczbę (tutaj: podzielić przez 2).

3.

Do wiersza w którym ma być 0 można dodać (odjąć) wiersz z pkt. 2
pomnożony lub podzielony przez odpowiednią liczbę. Ważne aby
zachować kolejność działań. (tu jest sporo błędów).

W

F

x

1

x

2

s

1

s

2

stałe

Uwagi

0

1

0

2

3

0

300

=w0+w1*3

1

0

1

1

½

0

50

=w1:2

2

0

0

3

- ½

1

110

=w2-w1:2

2010-02-27

25

49

Metoda Simpleks

Odczytywanie rozwiązania:

Rozwiązanie dopuszczalne w tym kroku:

F

= 300, x

1

= 50, x

2

= 0, s

1

= 0, s

2

= 110

Rozwiązanie optymalne?

Ponieważ w wierszu 0 są same liczby nieujemne, rozwiązanie jest również

rozwiązaniem optymalnym.

(Gdyby były liczby ujemne należałoby znowu poprawiać to rozwiązanie).

Odpowiedz. (dla zadania z treścią jest obowiązkowa)

Aby zmaksymalizować zysk należy produkować 50 Kłapouchów

(Kłapouchych??) i 0 Prosiaczków (niestety). Zysk wyniesie 300 zł.
W magazynie pozostanie 0 guzików czerwonych i 110 guzików
niebieskich.

50

Przykład

Przykład 8.

Przy produkcji 2 wyrobów: krzeseł i stołów zużywa się 2
rodzaje drewna: D1 i D2. Zużycie i zapas drewna oraz
zysk ze sprzedaży wyrobów podano w tabeli:

krzesło

stół

D1

0,4

0,4

120 m

3

D2

0,6

0,2

120 m

3

Zysk

120 zł

80 zł

Wyroby

Drewno

Zapas

Proszę podać wielkość produkcji optymalnej ze względu
na zysk.

2010-02-27

26

51

Przykład

Model matematyczny:

Postać normalna:

F

= 120x

1

+ 80x

2

→ max

0,4x

1

+ 0,4x

2

≤ 120

0,6x

1

+ 0,2x

2

≤ 120

x

1

, x

2

≥ 0

Postać kanoniczna:

F

- 120x

1

- 80x

2

= 0

0,4x

1

+ 0,4x

2

+ s

1

= 120

0,6x

1

+ 0,2x

2

+ s

2

= 120

x

1

, x

2

, s

1

, s

2

≥ 0

52

Przykład

Rozwiązanie metodą Simpleks

W

F

x1

x2

s1

s2

stałe

Uwagi

0

1

-120 (0)

-80

0

0

0

1

0

0,4 (0)

0,4

1

0

120

2

0

0,6 (1)

0,2

0

1

120

W

F

x1

x2

s1

s2

stałe

Uwagi

0

1

0

-40 (0)

0

200

24.000

=w0+w2*200

1

0

0

4/15 (1)

1

-2/3

40

=w1-w2*4/6

2

0

1

1/3 (0)

0

10/6

200

=w2*10/6

W

F

x1

x2

s1

s2

stałe

Uwagi

0

1

0

0

150

100

30.000

=w0+w1*150

1

0

0

1

15/4

-5/2

150

=w1*15/4

2

0

1

0

-5/4

5/2

150

=w2-w1*5/4

2010-02-27

27

53

Przykład

Rozwiązanie optymalne:

F

= 30.000, x

1

= 150, x

2

= 150, s

1

= 0, s

2

= 0

Odpowiedz.

Aby osiągnąć maksymalny zysk w wysokości 30.000

zł należy produkować 150 sztuk krzeseł i 150 sztuk
stołów.

54

Zadanie dualne

Na zadanie decyzyjne można spojrzeć z różnych punktów
widzenia. Np. zwiększenie zysków może być realizowane
zarówno poprzez zwiększenie przychodów ze sprzedaży jak i
poprzez zmniejszenie kosztów.

Inną możliwością jest konstrukcja tzw. zadania dualnego, tzn.
zadania sprzężonego z analizowanym problemem decyzyjnym,
czyli zadaniem pierwotnym.

Zadanie pierwotne i dualne nie są tożsame. Mają również różne
rozwiązania. Pojęcie zadania dualnego jest jednak wygodnym
narzędziem przy analizie rozwiązania problemu decyzyjnego,
np. w analizie wrażliwości.

2010-02-27

28

55

Zadanie dualne

Konstrukcja zadania dualnego

Pojęcia „zadanie pierwotne” i „zadanie dualne” można stosować
zamiennie, tzn. wszystkie własności zadania pierwotnego są
własnościami zadania dualnego i odwrotnie.

Jeżeli zadanie pierwotne jest zadaniem na maksimum to zadanie
dualne jest na minimum.

Ilość zmiennych w zadaniu pierwotnym jest równa ilości
ograniczeń w zadaniu dualnym.

Ilość ograniczeń w zadaniu pierwotnym jest równa ilości
zmiennych w zadaniu dualnym.

Współczynniki stojące przy zmiennych w funkcji celu w
zadaniu pierwotnym są wyrazami wolnymi w ograniczeniach
zadania dualnego i na odwrót.

56

Zadanie dualne

Macierz współczynników ograniczeń w zadaniu dualnym jest
równa transponowanej macierzy współczynników ograniczeń
zadania pierwotnego.
(należy czytać: współczynniki stojące w ograniczeniach zadania
pierwotnego czytamy w wierszach i wpisujemy do kolumn
ograniczeń zadania dualnego

).

(Ustalanie znaków nierówności/równania) Znak nierówności w
ograniczeniu zadania pierwotnego jest związany ze znakiem
odpowiedniej zmiennej w zadaniu dualnym. Znak zmiennej
zadania pierwotnego jest związany z odpowiednim znakiem
nierówności w ograniczeniu zadania dualnego.

2010-02-27

29

57

Zadanie dualne

Naturalne ograniczenia z zadania pierwotnego przechodzą na
naturalne ograniczenia zadania dualnego. Nienaturalne na
nienaturalne.
Naturalne ograniczenia (nienaturalne maja przeciwne znaki):

Znak ograniczenia

Znak zmiennej

Zad. na max

≤

≥

Zad. na min

≥

≥

Własność: Jeżeli istnieje rozwiązanie optymalne zadania
pierwotnego to istnieje również rozwiązanie zadania dualnego i
oba rozwiązania dają tę samą wartość funkcji celu.

58

Zadanie dualne

Przykład - ściąga

Poniższe zadanie zawiera wszystkie możliwości przy tworzeniu zadania dualnego.

Zbudować model zadania dualnego do zadania:

F

= x

1

+ 2x

2

+ 3x

3

+ 4x

4

→ max

5x

1

+ 6x

2

+ 7x

3

+ 8x

4

≤ 9

10x

1

+ 11x

2

+ 12x

3

+ 13x

4

≥ 14

15x

1

+ 16x

2

+ 17x

3

+ 18x

4

= 19

x

1

– dowolne, x

2

≤ 0, x

3

≥ 0, x

4

≤ 0

Model zadania dualnego:

F

= 9y

1

+ 14y

2

+ 19y

3

→ min

5y

1

+ 10y

2

+ 15y

3

= 1

6y

1

+ 11y

2

+ 16y

3

≤ 2

7y

1

+ 12y

2

+ 17y

3

≥ 3

8y

1

+ 13y

2

+ 18y

3

≤ 4

y

1

≥ 0, y

2

≤ 0, y

3

– dowolne

2010-02-27

30

59

Zadanie dualne

Przykład 9.
Zakład produkuje mieszankę paszową dla trzody chlewnej.
Produkowana jest ona z ziarna i uszlachetniacza. Koszt obu
składników wynosi 10 zł/kg i 25 zł/kg. Wartość energetyczna,
zawartość składników mineralnych oraz dzienne zapotrzebowanie
na te składniki dla 1 zwierzęcia znajduje się w tabelce:

Ziarno

Uszlachetniacz

Energia

1000 kcal/kg

500 kcal/kg

5000 kcal

Składniki min.

5 mg/kg

20 mg/kg

100 mg

Produkty

Minimalna ilość

składników

Jaki powinien być skład mieszanki dla jednego zwierzęcia aby
pasza miała odpowiedni skład i aby koszt był minimalny?

60

Zadanie dualne

Polecenia:

1.

Zbudować model matematyczny

2.

Zbudować model zadania dualnego

3.

Rozwiązać metodą SIMPLEX

4.

Podać rozwiązania zadania pierwotnego i dualnego z
uwzględnieniem zmiennych nadmiaru i niedoboru.

5.

W jakich jednostkach są wyrażone zmienne pierwotne i
dualne?

6.

Co się stanie z funkcją celu jeżeli minimalne zapotrzebowanie
na składniki mineralne zwiększy się o 1?

7.

Jaki jest sens ekonomiczny zmiennych dualnych?

8.

Czy to rozwiązanie jest jedynym rozwiązaniem optymalnym
(czy jest jednoznaczne)?

2010-02-27

31

61

Zadanie dualne

Model matematyczny zadania:

F

= 10x

1

+ 25x

2

→ min

1000x

1

+ 500x

2

≥ 5000

5x

1

+ 20x

2

≥ 100

x

1

, x

2

≥ 0

Model matematyczny zadania dualnego:
Postać ogólna

F

= 5000y

1

+100y

2

→ max

1000y

1

+ 5y

2

≤ 10

500y

1

+ 20y

2

≤ 25

y

1

, y

2

≥ 0

62

Zadanie dualne

Model matematyczny zadania dualnego:
Postać kanoniczna

F -

5000y

1

- 100y

2

= 0

1000y

1

+ 5y

2

+ t

1

= 10

500y

1

+ 20y

2

+ t

2

= 25

y

1

, y

2

, t

1

, t

2

≥ 0

2010-02-27

32

63

Zadanie dualne

Rozwiązanie metodą Simpleks:

W

F

y

1

y

2

t

1

t

2

stałe

Uwagi

0

1

-5000 (0)

-100

0

0

0

1

0

1000 (1)

5

1

0

10

2

0

500 (0)

20

0

1

25

W

F

y

1

y

2

t

1

t

2

st.

Uwagi

0

1

0

-75 (0)

5

0

50

=w0+w1*5

1

0

1

1/200 (0)

1/1000

0

1/100

=w1/1000

2

0

0

17 1/2 (1)

-1/2

1

20

=w2-w1/2

W

F

y

1

y

2

t

1

t

2

st.

Uwagi

0

1

0

0

100/35

150/35

950/7

=w0(2)+w2(3)*75

1

0

1

0

8/7000

-1/3500

3/700

=w1(2)-w2(3)/200

2

0

0

1

-1/35

2/35

8/7

=w2*2/35

gdzie w1(2) oznacza: wiersz pierwszy z kroku drugiego.

64

Zadanie dualne

Rozwiązanie:

Rozwiązanie zadania dualnego

(na max):

y

1

= 3/700

y

2

= 8/7

t

1

= 0

t

2

= 0

F

= 950/7

Rozwiązanie zadania

pierwotnego (na min):

x

1

= 100/35

x

2

= 150/35

s

1

= 0

s

2

= 0

F

= 950/7

Rozwiązanie zadania pierwotnego (na minimum) znajduje się w
wierszu 0 i można je odczytać po odpowiedniej zamianie
zmiennych (zamiast y

1

i y

2

– s

1

i s

2

, zamiast t

1

i t

2

– x

1

i x

2

).

2010-02-27

33

65

Zadanie dualne

Zadanie pierwotne (na min)

F

– zł

x

1

, x

2

– kg

s

1

– kcal, s

2

– mg

Zadanie dualne (na max):

F

– zł

y

1

– zł/kcal, y

2

– zł/mg

t

1

, t

2

– zł/kg

Jednostki zmiennych:

Zmiana ograniczenia:

Jeżeli drugie ograniczenie (100) w zadaniu pierwotnym zwiększy się o 1 (101)
to funkcja celu zwiększy się o wartość drugiej zmiennej dualnej (y

2

=8/7) i

będzie wynosiła F=958/7.

Sens ekonomiczny zmiennych dualnych:

Pierwsza zmienna dualna to maksymalna cena po jakiej opłaca się wymienić 1
jednostkę energii (w tym wypadku 3/700 zł), druga – cena po której opłaca się
wymienić jednostkę składników mineralnych (8/7 zł).

66

Zadanie dualne

Jednoznaczność rozwiązania:

Rozwiązanie jest optymalne i jedyne, jeżeli w kolumnach
rozwiązania niebazowego (zawierających coś innego niż zera i
jedynkę) w wierszu zerowym znajdują się liczby większe od
zera. Jeżeli w którejś z tych kolumn w wierszu 0 znajduje się
liczba 0, oznacza to że istnieje jeszcze jedno rozwiązanie
optymalne, a to znaczy, że jest ich nieskończenie wiele.

W tym wypadku kolumnami niebazowymi są t

1

i t

2

. Mają one w

wierszu 0 liczby: 100/35 i 150/35. Są one większe od zera w
związku z tym rozwiązanie jest jedyne (jest wyznaczone
jednoznacznie).

2010-02-27

34

67

Przykład

Przykład 10.
Karmimy małe zwierzę. Powinno ono w ciągu dnia dostać
przynajmniej 4 mg witamin i 10 mg białka. Do kamienia używamy
dwóch produktów: marchewki i ziarna pszenicy. Zawartość
poszczególnych składników (mg/kg) w obydwu produktach
pokazuje tablica:

Marchew Pszenica

Witaminy

1

2

Białko

2

5

Wiadomo również, że 1 kg marchwi kosztuje 20 gr., a 1 kg
pszenicy 10gr. Jaki powinien być skład mieszanki, aby zwierzę
dostawało odpowiednią ilość witamin i białka i aby rozwiązanie
było optymalne pod względem kosztów?

68

Przykład

Dodatkowe polecenia:

1.

Zbudować model matematyczny

2.

Zbudować model zadania dualnego

3.

Rozwiązać metodą SIMPLEX

4.

Podać rozwiązania zadania pierwotnego i dualnego z
uwzględnieniem zmiennych nadmiaru i niedoboru.

5.

W jakich jednostkach są wyrażone zmienne pierwotne i
dualne?

6.

Co się stanie z funkcją celu jeżeli minimalne zapotrzebowanie
na białko zwiększy się o 1?

7.

Jaki jest sens ekonomiczny zmiennych dualnych?

8.

Czy to rozwiązanie jest jedynym rozwiązaniem optymalnym
(czy jest jednoznaczne)?

2010-02-27

35

69

Przykład

Model matematyczny zadania:

F

= 20x

1

+ 10x

2

→ min

x

1

+ 2x

2

≥ 4

2x

1

+ 5x

2

≥ 10

x

1

, x

2

≥ 0

Model matematyczny zadania dualnego:
Postać ogólna

F

= 4y

1

+ 10y

2

→ max

y

1

+ 2y

2

≤ 20

2y

1

+ 5y

2

≤ 10

y

1

, y

2

≥ 0

70

Przykład

Model matematyczny zadania dualnego:
Postać kanoniczna

F -

4y

1

- 10y

2

= 0

y

1

+ 2y

2

+ t

1

= 20

2y

1

+ 5y

2

+ t

2

= 10

y

1

, y

2

, s

1

, s

2

≥ 0

2010-02-27

36

71

Przykład

Rozwiązanie metodą Simpleks:

W

F

y

1

y

2

t

1

t

2

st.

Uwagi

0

1

0

0

0

2

20

1

0

1/5

0

1

-2/5

16

2

0

2/5

1

0

1/5

2

Rozwiązanie: F=20, y

1

=0, y

2

=2, t

1

=16, t

2

=0.

Rozwiązanie jest optymalne.

W kolumnie niebazowej (y

1

) w wierszu 0 znajduje się liczba 0.

Rozwiązanie nie jest jedynym rozwiązaniem optymalnym.

W

F

y

1

y

2

t

1

t

2

stałe

Uwagi

0

1

-4

-10 (0)

0

0

0

=w0(1)+w2(1)*2

1

0

1

2 (0)

1

0

20

=w1(1)-w2(2)*2

2

0

2

5 (1)

0

1

10

=w2(1)/5

72

Przykład

Szukamy drugiego rozwiązania:

W

F

y

1

y

2

t

1

t

2

st.

Uwagi

0

1

0 (0)

0

0

2

20

=w0

1

0

1/5 (0)

0

1

-2/5

16

=w1-w2/2

2

0

2/5 (1)

1

0

1/5

2

=w2*5/2

Rozwiązanie: F=20, y

1

=5, y

2

=0, t

1

=15, t

2

=0.

Rozwiązanie jest optymalne.

Zadanie dualne (na maksimum) ma nieskończenie wiele
rozwiązań.

W

F

y

1

y

2

t

1

t

2

st.

Uwagi

0

1

0

0

0

2

20

1

0

0

-1/2

1

-1/2

15

2

0

1

5/2

0

1/2

5

2010-02-27

37

73

Przykład

Rozwiązanie:

Rozwiązanie zadania pierwotnego (na min):

x

1

= 0

x

2

= 2

s

1

= 0

s

2

= 0

F

= 20

Zadanie pierwotne ma jedno rozwiązanie.

Rozwiązanie zadania pierwotnego (na minimum) znajduje się w
wierszu 0 i można je odczytać po odpowiedniej zamianie
zmiennych (zamiast y

1

i y

2

– s

1

i s

2

, zamiast t

1

i t

2

– x

1

i x

2

).

74

Przykład

Zadanie pierwotne (na min)

F

– gr

x

1

, x

2

– kg

s

1

– mg, s

2

– mg

Zadanie dualne (na max):

F

– gr

y

1

– gr/mg, y

2

– gr/mg

t

1

, t

2

– gr/kg

Jednostki zmiennych:

Zmiana ograniczenia:

Jeżeli drugie ograniczenie (10) w zadaniu pierwotnym zwiększy się o 1 (11) to
wartość funkcji celu zwiększy się o wartość drugiej zmiennej dualnej (y

2

=2) i

będzie wynosiła F=22.

Sens ekonomiczny zmiennych dualnych:

Pierwsza zmienna dualna to maksymalna cena po jakiej opłaca się wymienić 1
mg witamin (w tym wypadku 0 gr.), druga – cena po której opłaca się wymienić
mg białka (2 zł).

2010-02-27

38

75

Zagadnienie transportowe

Zadanie transportowe dotyczy przewozu pewnego towaru.

Występują w nim dwie grupy podmiotów: dostawcy
posiadający określone ilości towarów, oraz odbiorcy
zgłaszający zapotrzebowanie na pewne ilości tego towaru.

Każdego dostawcę i każdego odbiorcę łączy ze sobą sieć dróg.
Przejazd różnymi drogami pociąga za sobą różne koszty (w
pieniądzach, czasie przejazdu, itp.).

Kryterium oceny rozwiązań jest łączny koszt transportu towaru
do wszystkich odbiorców. Koszt ten jest minimalizowany.

Zadaniem decydenta jest takie skonstruowanie przewozów, aby
od dostawców wywieziono co najwyżej tyle towaru ile
posiadają, do odbiorców dostarczono tyle towaru ile zamówili i
aby całkowity koszt transportu był minimalny.

76

Zagadnienie transportowe

Zadanie transportowe może występować w dwóch odmianach:

Zadania zamkniętego (zbilansowanego) – w którym
zapotrzebowanie zgłoszone przez odbiorców równe jest
możliwościom dostawców.

Zadania otwartego (niezbilansowanego) – w którym
zapotrzebowanie zgłoszone przez odbiorców jest mniejsze od
możliwości dostawców.

W gospodarce rynkowej niemożliwe jest trwałe występowanie

nadwyżki popytu nad podażą, dlatego zwykle nie analizuje się
takiej sytuacji (choć można dla niej zbudować model – tzw.
nieklasyczny model zadania transportowego).

2010-02-27

39

77

Zagadnienie transportowe

Większość metod służących do modelowania i
rozwiązywania zagadnienia transportowego opiera się
na założeniu, że zadanie jest zbilansowane
(zamknięte).

Możliwe jest łatwe przekształcenie zadania otwartego
w zadanie zamknięte tzw. zamykanie (domykanie)
zadania. Polega ono na wstawieniu dodatkowego,
fikcyjnego odbiorcy, którego zadaniem jest przyjęcie
nadwyżki podaży nad popytem. Inaczej mówiąc
reprezentuje on tę część towaru, która „nigdzie nie
pojedzie”.

78

Zagadnienie transportowe

Model matematyczny:

W zadaniu jest r dostawców i s odbiorców.

Zmienne:

x

i,j

gdzie i=1,..., r; j=1,..., s – reprezentujące ilość towaru przewożonego od

i

-tego dostawcy do j-tego odbiorcy.

Funkcja celu:

F

= c

1,1

x

1,1

+ c

1,2

x

1,2

+ c

1,3

x

1,3

+ ... + c

r,s

x

r,s

→ min

gdzie c

i,j

są jednostkowymi kosztami transportu od i-tego dostawcy do j-

tego odbiorcy.

Ograniczenia dla dostawców:

x

i

,1

+ x

i

,2

+ ... + x

i,s

≤ a

i

, gdzie i = 1, ..., r

Ograniczenia dla odbiorców:

x

1,j

+ x

2,j

+ ... + x

r,j

= b

j

, gdzie j = 1, ..., s

Warunki nieujemności:

x

i,j

≥ 0, gdzie i=1,..., r; j=1,..., s

2010-02-27

40

79

Zagadnienie transportowe

Przykład 11.

Cztery piekarnie są zaopatrywane w mąkę z trzech magazynów.
Zasoby mąki w magazynach wynoszą: mag.1 – 100 t, mag.2 –
150 t i mag.3 – 200 t., a zapotrzebowanie na mąkę zgłaszane przez
piekarnie wynoszą: piekarnia A – 50 t, B – 80 t, C – 180 t, D –
120 t. Jednostkowe koszty transportu (w zł/t) pokazano w tabelce:

A

B

C

D

mag.1

20

15

18

25

mag.2

10

18

13

20

mag.3

18

20

25

6

Magazyny

Piekarnie

Wyznaczyć plan przewozów, aby koszt transportu był minimalny.

80

Zagadnienie transportowe

Możliwości dostarczenia mąki przez magazyny (podaż)
wynoszą łącznie 450 t.

Zapotrzebowanie zgłoszone przez odbiorców (popyt) wynosi
łącznie 430 t.

Podaż jest większa od popytu w związku z tym zadanie jest
niezbilansowane.

Aby je zbilansować dodajemy fikcyjnego odbiorcę E o
zapotrzebowaniu 20 t.

A

B

C

D

E

mag.1

20

15

18

25

0

100

mag.2

10

18

13

20

0

150

mag.3

18

20

25

6

0

200

Popyt

50

80

180

120

20

450

Podaż

Piekarnie

Magazyny

2010-02-27

41

81

Zagadnienie transportowe

Model matematyczny (zadania zbilansowanego):

Jest 15 zmiennych: x

11

, x

12

, x

13

, ..., x

35

Każda zmienna x

i,j

wyraża ilość mąki przewożonej z i-tego magazynu do

j

-tej piekarni.

F

= 20x

11

+ 15x

12

+ 18x

13

+ 25x

14

+ 0x

15

+ 10x

21

+ 18x

22

+ 13x

23

+ 20x

24

+

+ 0x

25

+ 18x

31

+ 20x

32

+ 25x

33

+ 6x

34

+ 0x

35

→ min

x

11

+ x

12

+ x

13

+ x

14

+ x

15

≤ 100 – ograniczenia dla dostawców

x

21

+ x

22

+ x

23

+ x

24

+ x

25

≤ 150

x

31

+ x

32

+ x

33

+ x

34

+ x

35

≤ 200

x

11

+ x

21

+ x

31

= 50

– ograniczenia dla odbiorców

x

12

+ x

22

+ x

32

= 80

x

13

+ x

23

+ x

33

= 180

x

14

+ x

24

+ x

34

= 120

x

15

+ x

25

+ x

35

= 20

x

i,j

≥ 0

– warunki nieujemności

82

Zagadnienie transportowe

Rozwiązywanie zadania transportowego składa się z

dwóch etapów:

1.

Poszukiwania rozwiązania dopuszczalnego.

metoda kąta Północno-Zachodniego N-W,

metoda Najmniejszego Elementu Macierzy NEM,

inne.

2.

Poprawiania tego rozwiązania tak długo, aż do
osiągnięcia rozwiązania optymalnego.

2010-02-27

42

83

Zagadnienie transportowe

Metoda N-W.
Polega na wpisywaniu maksymalnie dużej, możliwej do wpisania,
wartości w polu znajdującym się najdalej z lewej i u góry (najdalej
na północny-zachód).

100
150
200

50

80

180

120

20

?

100
150
200

50

80

180

120

20

50

50

150
200

0

80

180

120

20

84

Zagadnienie transportowe

50

?

50

150
200

0

80

180

120

20

50

50

0

?

150
200

0

30

180

120

20

50

50

0

30

?

120
200

0

0

180

120

20

50

50

0

30

120

0

?

200

0

0

60

120

20

2010-02-27

43

85

Zagadnienie transportowe

Otrzymane rozwiązanie jest rozwiązaniem dopuszczalnym,
ponieważ spełnia wszystkie warunki ograniczające.

50

50

0

30

120

0

60

?

140

0

0

0

120

20

50

50

0

30

120

0

60

120

?

20

0

0

0

0

20

50

50

0

30

120

0

60

120

20

0

0

0

0

0

0

50

50

0

0

0

100

0

30

120

0

0

150

0

0

60

120

20

200

50

80

180

120

20

86

Zagadnienie transportowe

Koszt rozwiązania:

F

=20*50+15*50+18*30+13*120+25*60+6*120+0*20 = 6070.

Rozwiązanie nie jest rozwiązaniem optymalnym!

Konstruując to rozwiązanie w ogóle nie braliśmy pod

uwagę kosztów.

2010-02-27

44

87

Zagadnienie transportowe

Metoda Najmniejszego Elementu Macierzy.
Polega na wybieraniu dróg, dla których koszty transportu są
najmniejsze i wysyłanie nimi maksymalnie dużej, dopuszczalnej,
ilości towaru.

20

15

18

25

0

100

10

18

13

20

0

150

18

20

25

6

0

200

50

80

180

120

20

20

15

18

25

0

100

10

18

13

20

0

150

18

20

25

6

(?)

0

200

50

80

180

120

20

20

15

18

25

0

100

10

(?)

18

13

20

0

150

18

20

25

6

(120)

0

80

50

80

180

0

20

88

Zagadnienie transportowe

20

15

18

25

0

100

10

(50)

18

13

(?)

20

0

100

18

20

25

6

(120)

0

80

0

80

180

0

20

20

15

(?)

18

25

0

100

10

(50)

18

13

(100)

20

0

0

18

20

25

6

(120)

0

80

0

80

80

0

20

20

15

(80)

18

(?)

25

0

20

10

(50)

18

13

(100)

20

0

0

18

20

25

6

(120)

0

80

0

0

80

0

20

20

15

(80)

18

(20)

25

0

0

10

(50)

18

13

(100)

20

0

0

18

20

25

(?)

6

(120)

0

80

0

0

60

0

20

20

15

(80)

18

(20)

25

0

0

10

(50)

18

13

(100)

20

0

0

18

20

25

(60)

6

(120)

0

(?)

20

0

0

0

0

20

2010-02-27

45

89

Zagadnienie transportowe

Otrzymane rozwiązanie jest rozwiązaniem dopuszczalnym.

Koszt rozwiązania:

F

=10*50+15*80+18*20+13*100+25*60+6*120+0*20 = 5580.

Rozwiązanie nie jest rozwiązaniem optymalnym!

20

15

(80)

18

(20)

25

0

0

10

(50)

18

13

(100)

20

0

0

18

20

25

(60)

6

(120)

0

(20)

0

0

0

0

0

0

20

(0)

15

(80)

18

(20)

25

(0)

0

(0)

50

10

(50)

18

(0)

13

(100)

20

(0)

0

(0)

150

18

(0)

20

(0)

25

(60)

6

(120)

0

(20)

200

50

80

180

120

20

90

Zagadnienie transportowe

Poprawianie rozwiązania dopuszczalnego.

Metoda składa się z dwóch, powtarzanych wielokrotnie

etapów:

1.

sprawdzania, czy otrzymane rozwiązanie jest
optymalne,

1.

konstrukcja tabeli kosztów zastępczych,

2.

obliczenie różnicy pomiędzy rzeczywistymi kosztami a
kosztami zastępczymi,

2.

poprawiania rozwiązania nieoptymalnego.

2010-02-27

46

91

Zagadnienie transportowe

1.1. Konstrukcja tabeli kosztów zastępczych (KZ).

1.

Z tabeli zawierającej rzeczywiste koszty transportu
przepisujemy wartości odpowiadające niezerowym
wartościom rozwiązania.

2.

Pozostałe wartości uzupełniane są w taki sposób, aby wiersze i
kolumny były „liniowo zależne” tzn. różnica pomiędzy
wszystkimi wartościami w dwóch kolumnach (wierszach)
musi być taka sama, identyczna jak pomiędzy przeniesionymi
wartościami z tabeli kosztów.

92

Zagadnienie transportowe

1.2. Obliczenie różnicy pomiędzy rzeczywistymi kosztami a

kosztami zastępczymi (K-KZ).

1.

Obliczamy różnice pomiędzy odpowiednimi wartościami
pochodzącymi z tabeli zawierającej rzeczywiste koszty
transportu, a wartościami z tabeli kosztów zastępczych
(K-KZ),

2.

Jeżeli występują wyłącznie wartości nieujemne to rozwiązanie
jest rozwiązaniem optymalnym.

3.

Jeżeli w tabeli różnic występuje przynajmniej jedna wartość
ujemna – rozwiązanie nie jest optymalne. Należy je poprawić.

2010-02-27

47

93

Zagadnienie transportowe

2. Poprawianie rozwiązania.

1.

W miejscu w którym w K-KZ znajduje się najmniejsza ujemna
liczba będzie znajdowało się nowe niezerowe rozwiązanie.

2.

Aby sumy kolumn i wierszy zgadzały się należy jednocześnie
odjąć i dodać odpowiednią liczbę w innych zmiennych. W tym
celu wyznaczam graf zadania (linia łącząca wszystkie elementy
„zakręcająca” wyłącznie w miejscach niezerowych rozwiązań).

3.

Nowy element rozwiązania należy połączyć z najbliższymi
elementami grafu w taki sposób, aby powstała zamknięta
ścieżka

. Liczby znajdujące się na wierzchołkach tej ścieżki

kolejno oznaczam znakiem (+) i (-) rozpoczynając od (+) dla
nowego elementu rozwiązania.

4.

Z liczb z (-) wybieram najmniejszą. Liczbę tę w zależności od
znaku należy dodać lub odjąć od wierzchołków.

94

Przykład

Przykład 12.

Dystrybutor jest odpowiedzialny za rozwiezienie butelek z napojami
chłodzącymi od trzech dostawców do czterech odbiorców. Dystrybutor wie ile
jednostek towaru mają do dyspozycji dostawcy (odpowiednio 1000, 1500 i 2000
butelek) i ile jednostek towaru potrzebują odbiorcy (odpowiednio 1250, 650,
1850, 750). Aby zaspokoić popyt, dostawcy dysponować muszą ilością towaru
co najmniej równa popytowi. Zadaniem dystrybutora jest ustalić taki plan
przewozów, który spełniałby wymagania odbiorców i jednocześnie brał pod
uwagę możliwości dostawców. Kryterium oceny rozwiązań jest koszt całkowity
transportu. Koszty jednostkowe transportu przedstawiają się następująco:





















11

17

15

12

14

11

8

6

7

9

10

12

2010-02-27

48

95

Przykład

Rozwiązanie.

I. Szukanie dowolnego rozwiązania dopuszczalnego.

Rozwiązanie dopuszczalne otrzymane metodą N-W:

1000

0

0

0

1000

250

650

600

0

1500

0

0

1250

750

2000

1250

650

1850

750

Wartość funkcji celu F=54.800 zł.

96

Przykład

II. Sprawdzanie czy rozwiązanie jest optymalne

Buduję tabelę kosztów zastępczych (KZ).

Z tabeli zawierającej koszty wybieram pola odpowiadające
niezerowym rozwiązaniom. Następnie pozostałe pola uzupełniam
w taki sposób aby kolumny i wiersze były liniowo zależne.

12

14

17

11

6

8

11

5

12

14

17

11

Znajduję różnicę między kosztami i kosztami zastępczymi (K-KZ):

0

-4

-8

-4

0

0

0

9

0

1

0

0

Jeżeli w K-KZ znajdują się liczby ujemne – rozwiązanie nie jest
optymalne (analogicznie jak w metodzie Simpleks). To nie jest.

2010-02-27

49

97

Przykład

III. Poprawianie rozwiązania.

Najmniejsza i ujemna w tablicy różnicy kosztów jest liczba –6
(wiersz 1, kolumna 3). Po skonstruowaniu ścieżki przechodzącej

przez wszystkie elementy rozwiązania dodajemy nowy element:

1000

(-)

0

?

(+)

0

250

(+)

650

600

(-)

0

0

0

1250

750

400

0

600

0

850

650

0

0

0

0

1250

750

Wartość funkcji celu F=50.000 zł.

98

Przykład

II. Sprawdzanie czy rozwiązanie jest optymalne

KZ=

12

14

9

3

6

8

3

-3

20

22

17

11

0

-4

0

4

0

0

8

17

-8

-7

0

0

W tabeli są liczby ujemne – rozwiązanie nie jest optymalne.

2010-02-27

50

99

Przykład

III. Poprawianie rozwiązania.

400

(-)

0

600

(+)

0

850

650

0

0

?

(+)

0

1250

(-)

750

0

0

1000

0

850

650

0

0

400

0

850

750

Wartość funkcji celu F=46.800 zł.

100

Przykład

II. Sprawdzanie czy rozwiązanie jest optymalne

KZ=

Brak liczb ujemnych.

Rozwiązanie:

4

6

9

3

6

8

11

5

12

14

17

11

8

4

0

4

0

0

0

9

0

1

0

0

0

0

1000

0

850

650

0

0

400

0

850

750

jest rozwiązaniem optymalnym.

2010-02-27

51

101

Zadania sprowadzalne do
zagadnienia transportowego

Jest wiele rodzajów zadań, które pomimo tego, że nie są

zadaniami transportowymi, łatwo można sprowadzić
do zadania transportowego.

Wszystkie przykłady są rozwinięciem przykładu o

piekarniach i mące:

A

B

C

D

E

mag.1

20

15

18

25

0

100

mag.2

10

18

13

20

0

150

mag.3

18

20

25

6

0

200

Popyt

50

80

180

120

20

450

Podaż

Piekarnie

Magazyny

102

Zadania sprowadzalne do
zagadnienia transportowego

Zadanie transportowo – magazynowe

Pozostawienie mąki w magazynach kosztuje odpowiednio 10, 6
i 5 zł/t.

Po dodaniu tych wartości w kolumnie „fikcyjnego odbiorcy”
tablicy kosztów otrzymujemy zadanie transportowe z kosztami
wyglądającymi następująco:

A

B

C

D

fikcyjny

mag.1

20

15

18

25

10

100

mag.2

10

18

13

20

6

150

mag.3

18

20

25

6

5

200

Popyt

50

80

180

120

20

450

Magazyny

Podaż

Piekarnie

2010-02-27

52

103

Zadania sprowadzalne do
zagadnienia transportowego

Zadanie produkcyjno – transportowe

Dostawcy nie są magazynami mąki, ale z młynami i w każdym
z nich tona maki kosztuje odpowiednio: 100, 80 i 90 zł/t.

Po dodaniu ceny mąki w wierszach pierwotnej tablicy kosztów
otrzymujemy zadanie transportowe w którym koszty wyglądają
następująco:

A

B

C

D

fikcyjny

młyn 1

120

115

118

125

100

100

młyn 2

90

98

93

100

80

150

młyn 3

108

110

115

96

90

200

Popyt

50

80

180

120

20

450

Magazyny

Piekarnie

Podaż

104

Zadania sprowadzalne do
zagadnienia transportowego

Zadanie produkcyjno – transportowo – magazynowe

Łączymy oba poprzednie przykłady. Mąka jest produkowana w
młynach, gdzie występują różne koszty produkcji. Następnie
jest rozwożona do piekarni lub pozostaje w magazynach.

Po dodaniu fikcyjnego odbiorcy i przydzieleniu mu kosztów
magazynowania, a następnie nałożeniu kosztów produkcji na
wiersze, tabela kosztów będzie wyglądała następująco:

A

B

C

D

fikcyjny

młyn 1

120

115

118

125

110

100

młyn 2

90

98

93

100

86

150

młyn 3

108

110

115

96

95

200

Popyt

50

80

180

120

20

450

Magazyny

Piekarnie

Podaż

2010-02-27

53

105

Zadania sprowadzalne do
zagadnienia transportowego

Zadanie z blokowaniem tras

Piekarnia 3 nie zapłaciła trzeciemu magazynowi ostatnich 5
faktur i kierownik tego magazynu odmówił przewożenia mąki
do tej piekarni.

Należy odpowiednią trasę zablokować poprzez wpisanie dużej
liczby. Liczba powinna być większa od pozostałych, ale nie za
duża. Tablica z kosztami wygląda wtedy następująco:

1

2

3

4

fikcyjny

mag.1

20

15

18

25

0

100

mag.2

10

18

13

20

0

150

mag.3

18

20

100

6

0

200

Popyt

50

80

180

120

20

450

Magazyny

Piekarnie

Podaż

106

Zadania sprowadzalne do
zagadnienia transportowego

Zadanie wieloetapowe

Mąka jest produkowana przez 2 młyny i dostarczana do 3
magazynów, a następnie z magazynów do 4 piekarni.

Koszt transportu z młynów do magazynów pokazano w tabeli:

mag.1

mag.2

mag.3

Podaż

Młyn 1

20

25

15

250

Młyn 2

16

18

30

200

Popyt

100

150

200

450

Koszt transportu z mąki z magazynów do piekarni jest taki jak
w pierwotnym zadaniu.

Zadanie musi być w obydwu etapach zbilansowane.

Młynom nie wolno sprzedawać maki bezpośrednio do piekarni.

Należy skonstruować plan przewozów tak, aby łączny koszt
transportu był minimalny.

2010-02-27

54

107

Zadania sprowadzalne do
zagadnienia transportowego

W zadaniu dostawcami są młyny i magazyny, natomiast
odbiorcami magazyny i piekarnie.

Po połączeniu obydwu etapów i zablokowaniu odpowiednich
tras powstanie nowa tabela kosztów:

mag.1

mag.2

mag.3

piek.A

piek.B

piek.C

piek.D

Fikcyjny

młyn 1

20

25

15

50

50

50

50

50

250

młyn 2

16

18

30

50

50

50

50

50

200

mag.1

50

50

50

20

15

18

25

0

100

mag.2

50

50

50

10

18

13

20

0

150

mag.3

50

50

50

18

20

25

6

0

200

100

150

200

50

80

180

120

20

900

Popyt

Odbiorcy

Podaż

D

o

st

a

w

cy

108

Problem maksymalnego
przepływu

Dany jest jednorodny produkt, który należy
przetransportować z punktu początkowego s
(dostawca) do punktu końcowego t (odbiorca).

Dana jest również sieć służąca do transportu tego
produktu. W sieci tej określono połączenia pomiędzy
poszczególnymi punktami węzłowymi oraz
dopuszczalne przepływy w każdym z połączeń.

Zadanie takie jest zadaniem programowania liniowego,
w którym zmiennymi są przepływy w poszczególnych
połączeniach, a funkcją celu jest maksymalizacja
całkowitego przepływu sieci.

2010-02-27

55

109

Problem maksymalnego
przepływu

Model matematyczny:
W sieci jest n węzłów. Przez (i, j) oznaczmy połączenie
zaczynające się w punkcie i i kończące się w punkcie j, a przez f

i,j

dopuszczalny przepływ w tym połączeniu.

Zmienne: Zmienne x

i,j

oznaczają przepływ w połączeniu z węzła i

do węzła j.

Cel: maksymalizacja całkowitego przepływu

ν

.

Model:

υ

υ

−

=

−

≠

=

+

−

=

≤

≤

∑

∑

∑

∑

∈

∈

∈

∈

U

t

i

t

i

U

j

i

j

i

U

i

h

i

h

U

j

s

j

s

j

i

j

i

x

t

s

i

x

x

x

f

x

)

,

(

,

)

,

(

,

)

,

(

,

)

,

(

,

,

,

,

,

0

0

110

Problem maksymalnego
przepływu

Przykład 13.

Dana jest sieć transportowa. W nawiasach podano
przepustowość poszczególnych połączeń.

(10)

(15)

(9

)

(12

)

(1

2)

(1

6)

Skonstruować przepływy w połączeniach tak, aby
całkowity przepływ był jak największy.

2010-02-27

56

111

Problem maksymalnego
przepływu

Model matematyczny:

x

1,2

+ x

1,3

=

ν

− ograniczenia dla węzłów

-x

1,2

+ x

2,4

= 0

-x

1,3

+ x

3,5

= 0

-x

2,4

+ x

4,6

= 0

-x

3,5

+ x

5,6

= 0

-x

4,6

- x

5,6

= -

ν

0

≤ x

1,2

≤ 9

0

≤ x

1,3

≤ 12 − ograniczenia dla połączeń

0

≤ x

2,4

≤ 10 0 ≤ x

3,5

≤ 15

0

≤ x

4,6

≤ 12 0 ≤ x

5,6

≤ 16

F =

ν

→ max

112

Problem maksymalnego
przepływu

Zadanie maksymalizacji przepływu jest zadaniem
programowania liniowego i może być rozwiązywane
metodą simpleks.

Istnieją również specjalne metody rozwiązywania
problemu maksymalnego przepływu. Jedną z nich jest
algorytm Forda-Fulkersona.

Rozwiązaniem przykładu 13 jest 9 w górnej części
diagramu [połączenia (1,2), (2,4) i (4,6)] i 12 w dolnej
części [połączenia (1,3), (3,5) i (5,6)]. Maksymalny
przepływ sieci wynosi 21.

2010-02-27

57

113

Optymalizacja dyskretna

W przypadku niektórych problemów decyzyjnych
niedopuszczalne jest, aby zmienne przyjmowały wartości
rzeczywiste. Tak jest gdy reprezentują one ilości sztuk
produkowanych w fabryce pralek, ilość pracowników
niezbędnych do wykonania jakichś czynności, przydział firm do
wykonania projektów inwestycyjnych. W takich wypadkach
zmienne mogą przyjąć wartości dyskretne: przeliczalne lub
binarne.

Zagadnienie w którym przynajmniej jedna zmienna jest
dyskretna nazywa się dyskretnym zagadnieniem decyzyjnym
lub dyskretnym zadaniem decyzyjnym (DZD).

114

Optymalizacja dyskretna

Zbiór rozwiązań dyskretnego zadania decyzyjnego jest zbiorem
izolowanych punktów spełniających warunki ograniczające:

2010-02-27

58

115

Optymalizacja dyskretna

Dyskretne zadanie decyzyjne w którym wszystkie funkcje są

funkcjami liniowymi nazywane jest zadaniem programowania
dyskretnego, liniowego (PDL) lub dyskretnym, liniowym
zadaniem decyzyjnym.

Dyskretne, liniowe zadanie decyzyjne może być rozwiązywane na

dwa sposoby:

Najpierw formułowane i rozwiązywane jest zagadnienie
programowania liniowego, a następnie z jego rozwiązań
wybiera się rozwiązania całkowitoliczbowe.

Zagadnienie rozwiązywane jest bezpośrednio za pomocą
algorytmów stworzonych specjalnie do tego celu.

116

Optymalizacja dyskretna

Zadania dyskretne mogą przyjąć wiele różnych form. Są nimi

między innymi:

Zagadnienie (optymalnego) przydziału

Zagadnienie lokalizacji produkcji

Przedsiębiorstwo wielozakładowe musi podjąć decyzję o rozbudowie. Może

rozbudować istniejące zakłady lub budować nowe. Należy przy
ustalonym budżecie podjąć decyzję o lokalizacji inwestycji.

Zagadnienie wyboru projektu inwestycyjnego

Inwestor dysponujący określonymi funduszami w kolejnych okresach musi

podjąć decyzje o wyborze zadania inwestycyjnego, na które przeznaczy
fundusze. Każda inwestycja może być realizowana za pomocą jednego z
wielu projektów. Należy wybrać inwestycje i projekty tak aby przyniosły
największe zyski.

2010-02-27

59

117

Optymalizacja dyskretna

Zagadnienie ustalania harmonogramu realizacji prac

1.

Firma ma wykonać n zadań. Podana jest minimalna ilość pracowników
niezbędna do wykonania każdego zadania oraz czas jego realizacji.
Pracownicy mogą wykonywać każde zadanie. Ponadto niektóre
czynności nie mogą być wykonywane przed zakończeniem innych.
Należy tak dobrać kolejność wykonywanych zadań, aby całkowita ilość
zatrudnionych pracowników była jak najmniejsza.

2.

Firma zatrudniająca określoną ilość pracowników ma do wykonania n
zależnych od siebie zadań. Podany jest czas niezbędny na wykonanie
każdego zadania, minimalna ilość pracowników potrzebna do
wykonania zadania, termin w którym trzeba zakończyć poszczególne
zadania oraz kary za opóźnienia. Należy skonstruować harmonogram
zadań tak, aby zminimalizować nałożone kary.

Zagadnienie cięcia

Problem komiwojażera

118

Zagadnienie przydziału

W zagadnieniu przydziału należy przydzielić n osób do
n

zadań, w taki sposób żeby każda osoba wykonywała

dokładnie jedno zadanie i aby każde zadanie
wykonywane było przez dokładnie jedną osobę.

Celem zadania jest minimalizacja lub maksymalizacja
funkcji związanej z przydzielonymi zadaniami (koszt,
zysk, łączny czas wykonania operacji).

Rozwiązaniem zadania jest lista zawierająca
informacje, która osoba została przydzielona do
każdego zadania.

2010-02-27

60

119

Zagadnienie przydziału

Model matematyczny (PDZ):

W zadaniu jest r pracowników i r zadań.

Zmienne:

x

i,j

gdzie i,j = 1,..., r – reprezentujące informacje o tym czy i-ty pracownik

został przydzielony do j-tej czynności.

Funkcja celu:

F

= c

1,1

x

1,1

+ c

1,2

x

1,2

+ c

1,3

x

1,3

+ ... + c

s,r

x

r,r

→ min (max)

gdzie c

i,j

są wartościami jednostkowymi funkcji celu dla i-tego pracownika

wykonującego j-tą czynność.

Ograniczenia dla pracowników:

x

i

,1

+ x

i

,2

+ ... + x

i,r

= 1, gdzie i = 1, ..., r

Ograniczenia dla czynności:

x

1,j

+ x

2,j

+ ... + x

r,j

= 1, gdzie j = 1, ..., r







=

zadania

tego

-

j

wykonuje

nie

pracownik

ty

-

i

gdy

0

zadanie

te

-

j

wykonuje

pracownik

ty

-

i

gdy

1

ij

x

120

Zagadnienie przydziału

Równoważny model zagadnienia przydziału:

Na zadanie przydziału można spojrzeć jak na problem
ustawienia w kolejności pracowników, firm itp. Jeżeli i-ty
pracownik znajduje się na j-tej pozycji to znaczy że
przydzielono tego pracownika do wykonania j-tej czynności.
Każda permutacja pracowników jest rozwiązaniem
dopuszczalnym.

Oznaczmy przez v=(v

1

, ..., v

n

) dowolną permutację liczb 1,..., n,

przez f(v) – wartość funkcji celu dla tej permutacji, a przez D –
zbiór wszystkich permutacji. Rozwiązanie zagadnienia
przydziału v* sprowadza się do rozwiązania problemu:

f

(v*)= min {f(v) | v

∈D} lub f(v*)= max {f(v) | v∈D}

2010-02-27

61

121

Zagadnienie przydziału

Przykład 13.
Miasto chce zlecić modernizację 4 budynków. Każdy z nich jest
inny i wymaga od firmy budowlanej innych umiejętności, wiedzy i
doświadczenia. Ogłoszono przetarg do którego stanęły 4 firmy
budowlane. Proponowany koszt każdej modernizacji zgłoszony
przez poszczególne firmy pokazano w tabeli (w tys. zł):

Należy przydzielić firmom kontrakty tak, aby każda firma dostała
dokładnie jeden kontrakt i aby całkowity koszt modernizacji
budynków był minimalny.

Budynek 1 Budynek 2 Budynek 3 Budynek 4

Firma 1

150

180

130

220

Firma 2

160

200

150

190

Firma 3

140

220

180

200

Firma 4

140

210

140

200

Modernizowane budynki

F

ir

m

y

122

Zagadnienie przydziału

Model matematyczny:

W modelu będzie 16 zmiennych reprezentujących każdy
możliwy kontrakt. Każda zmienna odpowiada na pytanie: czy
dana firma dostanie kontrakt na wykonanie modernizacji
określonego budynku ? W związku z tym zmienne przyjmują
tylko dwie wartości: 0 i 1.
Zmienne:
x

11

, x

12

, x

13

, x

14

x

21

, x

22

, x

23

, x

24

x

31

, x

32

, x

33

, x

34

x

41

, x

42

, x

43

, x

44

Ważne. Ilość firm i ilość budynków musi być taka sama!

2010-02-27

62

123

Zagadnienie przydziału

Ograniczenia dla firm:

x

11

+x

12

+x

13

+x

14

= 1

x

21

+x

22

+x

23

+x

24

= 1

x

31

+x

32

+x

33

+x

34

= 1

x

41

+x

42

+x

43

+x

44

= 1

Ograniczenia dla budynków:

x

11

+x

21

+x

31

+x

41

= 1

x

12

+x

22

+x

32

+x

42

= 1

x

13

+x

23

+x

33

+x

43

= 1

x

14

+x

24

+x

34

+x

44

= 1

Funkcja celu:

F = 150x

11

+ 180x

12

+ 130x

13

+ 220x

14

+ 160x

21

+ 200x

22

+ 150x

23

+ 190x

24

+

+ 140x

31

+ 220x

32

+ 180x

33

+ 200x

34

+ 140x

41

+ 210x

42

+ 140x

43

+ 200x

44

→ min

124

Zagadnienie przydziału

Metoda węgierska

Metoda węgierska służy do rozwiązywania wyłącznie
zagadnienia przydziału.

Zagadnienie przydziału może być rozwiązywane metoda
Simpleks, jednak rozwiązanie metodą węgierską jest szybsze i
łatwiejsze.

Metoda węgierska rozwiązuje wyłącznie zadania „na
minimum”.

W przypadku zadania „na maksimum” niezbędne będzie
wykonanie zabiegu zmieniającego „kierunek zadania”.

2010-02-27

63

125

Zagadnienie przydziału

Rozwiązywanie metodą węgierską

1.

W każdej kolumnie znajdujemy wyraz najmniejszy i
odejmujemy go od wszystkich elementów w kolumnie.

2.

W każdym wierszu znajdujemy element najmniejszy i
odejmujemy go od wszystkich elementów w wierszu.
(Obie operacje można traktować zamiennie)

3.

Po wykonaniu obydwu czynności w każdym wierszu i każdej
kolumnie powinno znajdować się przynajmniej jedno zero.

4.

„Wycinamy” wszystkie zera jak najmniejszą ilością linii
pionowych i poziomych.

5.

Jeżeli minimalna ilość cięć jest równa rzędowi macierzy to z
pośród zer można wybrać rozwiązanie optymalne. Jeżeli jest
mniejsza to należy rozwiązanie poprawiać .

126

Zagadnienie przydziału

Rozwiązywanie metodą węgierską c.d.

6.

Jeżeli niema jeszcze rozwiązania optymalnego to spośród
elementów nieskreślonych wybieramy najmniejszy a następnie
element ten:

odejmujemy od nieskreślonych,

dodajemy do podwójnie skreślonych,

elementy raz skreślone przepisujemy.

7.

Powtarzamy punkt 4 i 5.

8.

Jeżeli minimalna ilość cięć jest równa rzędowi macierzy to
wybieramy r zer w taki sposób, aby z każdej kolumny i
każdego wiersza wybrać dokładnie jedno zero. Wybrane zera
reprezentują rozwiązanie optymalne.

2010-02-27

64

127

Zagadnienie przydziału

Pierwotna tablica z kosztami modernizacji budynków:

150

180

130

220

160

200

150

190

140

220

180

200

140

210

140

200

W każdej kolumnie znajdujemy najmniejsze elementy:

150

180

130

220

160

200

150

190

140

220

180

200

140

210

140

200

...i odejmujemy je:

10

0

0

30

20

20

20

0

0

40

50

10

0

30

10

10

128

Zagadnienie przydziału

W każdym wierszu znajdujemy najmniejsze elementy:

Po odjęciu ich w wierszach nic się nie zmieniło:

Wycinamy zera jak najmniejszą ilością cięć:

10

0

0

30

20

20

20

0

0

40

50

10

0

30

10

10

10

0

0

30

20

20

20

0

0

40

50

10

0

30

10

10

10

0

0

30

20

20

20

0

0

40

50

10

0

30

10

10

2010-02-27

65

129

Zagadnienie przydziału

Minimalna ilość cięć jest mniejsza od rzędu macierzy. Nie
można wybrać rozwiązania optymalnego. Należy poprawić
rozwiązanie. Spośród nieskreślonych liczb wybieramy
najmniejszą:

Liczbę 10 odejmiemy od nieskreślonych, dodamy do
skreślonych podwójnie. Raz skreślone przepiszemy:

10

0

0

30

20

20

20

0

0

40

50

10

0

30

10

10

20

0

0

30

30

20

20

0

0

30

40

0

0

20

0

0

130

Zagadnienie przydziału

Sprawdzamy czy w otrzymanej tablicy można odnaleźć
rozwiązanie optymalne. Wycinamy zera jak najmniejszą ilośćią
cięć.

Minimalna ilość cięć wynosi 4 i jest równa rzędowi macierzy.
Można wskazać wśród zer rozwiązanie optymalne

Wybieramy 4 zera w taki sposób aby w każdej kolumnie i
każdym wierszu wybrane było dokładnie jedno

20

0

0

30

30

20

20

0

0

30

40

0

0

20

0

0

20

0

0

30

30

20

20

0

0

30

40

0

0

20

0

0

2010-02-27

66

131

Zagadnienie przydziału

Wartość funkcji celu dla rozwiązania optymalnego:
F

= 140 + 180 + 140 + 190 = 650

Rozwiązanie zadania:
Najmniejszy koszt remontu budynków w wysokości
650 tys. zł uzyskamy, gdy:

Firma 1 dostanie kontrakt na modernizację Budynku 2,

Firma 2 dostanie kontrakt na modernizację Budynku 4,

Firma 3 dostanie kontrakt na modernizację Budynku 1,

Firma 4 dostanie kontrakt na modernizację Budynku 3.

132

Przykład

Przykład 14.

Pięciu pracowników chcemy przydzielić do pięciu czynności.
Dzienny zysk z pracy tych osób przy wykonywaniu
poszczególnych czynności pokazano w tabeli:

czynność 1 czynność 2 czynność 3 czynność 4 czynność 5

prac.1

100

120

90

80

100

prac.2

80

70

90

100

110

prac.3

140

150

130

110

120

prac.4

110

80

70

80

100

prac.5

90

100

80

70

110

Proszę dobrać pracowników do czynności, tak aby łączny zysk był
jak największy, i aby każdy pracownik wykonywał dokładnie jedna
czynność.

2010-02-27

67

133

Przykład

Model matematyczny

Ograniczenia dla pracowników:

x

11

+x

12

+x

13

+x

14

+x

15

= 1

x

21

+x

22

+x

23

+x

24

+x

25

= 1

x

31

+x

32

+x

33

+x

34

+x

35

= 1

x

41

+x

42

+x

43

+x

44

+x

45

= 1

x

51

+x

52

+x

53

+x

54

+x

55

= 1

Ograniczenia dla czynności:

x

11

+x

21

+x

31

+x

41

+x

51

= 1

x

12

+x

22

+x

32

+x

42

+x

52

= 1

x

13

+x

23

+x

33

+x

43

+x

53

= 1

x

14

+x

24

+x

34

+x

44

+x

54

= 1

x

15

+x

25

+x

35

+x

45

+x

55

= 1

Funkcja celu:

F

= 100x

11

+ 120x

12

+ 90x

13

+ 80x

14

+ 100x

15

+ 80x

21

+ 70x

22

+ 90x

23

+ 100x

24

+

+110x

25

+ 140x

31

+ 150x

32

+ 130x

33

+ 110x

34

+ 120x

35

+ 110x

41

+ 80x

42

+ 70x

43

+

+80x

44

+ 100x

45

+ 90x

51

+ 100x

52

+ 80x

53

+ 70x

54

+ 110x

55

→ max

134

Przykład

Rozwiązanie.

Metoda węgierska jest skuteczna wyłącznie dla zadań na
minimum. Niezbędna jest „zmiana kierunku” zadania.

W tym celu należy znaleźć największą liczbę w tabeli...

... i od niej odjęć po kolei wszystkie liczby:

100

120

90

80

100

80

70

90

100

110

140

150

130

110

120

110

80

70

80

100

90

100

80

70

110

50

30

60

70

50

70

80

60

50

40

10

0

20

40

30

40

70

80

70

50

60

50

70

80

40

2010-02-27

68

135

Przykład

Otrzymane zadanie jest zadaniem na minimum i może być
rozwiązywane metoda węgierską.

W kolumnach szukam wartości najmniejszych:

50

30

60

70

50

70

80

60

50

40

10

0

20

40

30

40

70

80

70

50

60

50

70

80

40

Liczby te odejmujemy wszystkich liczb w kolumnach:

40

30

40

30

20

60

80

40

10

10

0

0

0

0

0

30

70

60

30

20

50

50

50

40

10

136

Przykład

W wierszach szukamy wartości najmniejszych:

Liczby te odejmujemy wszystkich liczb w wierszach:

40

30

40

30

20

60

80

40

10

10

0

0

0

0

0

30

70

60

30

20

50

50

50

40

10

20

10

20

10

0

50

70

30

0

0

0

0

0

0

0

10

50

40

10

0

40

40

40

30

0

2010-02-27

69

137

Przykład

Jak najmniejszą ilością cięć wycinamy wszystkie zera.

Minimalna ilość cięć wynosi 3, np.:

Wśród zer niema rozwiązania optymalnego.

Wybieramy najmniejszą z nieskreślonych:

20

10

20

10

0

50

70

30

0

0

0

0

0

0

0

10

50

40

10

0

40

40

40

30

0

20

10

20

10

0

50

70

30

0

0

0

0

0

0

0

10

50

40

10

0

40

40

40

30

0

138

Przykład

Liczbę 10 dodajemy do podwójnie skreślonych, odejmujemy od
nieskreślonych, a raz skreślone przepisujemy:

Minimalna ilość cięć wynosi 5. Można wśród zer znaleźć
rozwiązanie optymalne.

10

0

10

0

0

50

70

30

0

10

0

0

0

0

10

0

40

30

0

0

30

30

30

20

0

10

0

10

0

0

50

70

30

0

10

0

0

0

0

10

0

40

30

0

0

30

30

30

20

0

2010-02-27

70

139

Zagadnienie przydziału

Wartość funkcji celu dla rozwiązania optymalnego:
F

= 110 + 120 + 130 + 100 + 110 = 570

Rozwiązanie zadania:
Największy zysk z pracy 5 pracowników w wysokości
570 zł dziennie uzyskamy, gdy:

Pracownik 1 będzie wykonywał Czynność 2,

Pracownik 2 będzie wykonywał Czynność 4,

Pracownik 3 będzie wykonywał Czynność 3,

Pracownik 4 będzie wykonywał Czynność 1,

Pracownik 5 będzie wykonywał Czynność 5.

140

Zadania sprowadzalne do
zagadnienia przydziału

Czasami zdarzają się zadania „podobne” do zadania
przydziału.

W niektórych wypadkach można łatwo sprowadzić je
do postaci umożliwiającej skorzystanie z metody
węgierskiej. Możliwe jest to w przypadku:

zadania, w którym macierz kosztów/zysków nie jest
kwadratowa,

zadania, w którym musimy uniemożliwić przydzielenie
pracownika do konkretnej czynności.

2010-02-27

71

141

Zadania sprowadzalne do
zagadnienia przydziału

Przykład 15.

Treść jak w poprzednim przykładzie, ale mamy 6 pracowników:

czynność 1 czynność 2 czynność 3 czynność 4 czynność 5

prac.1

100

120

90

80

100

prac.2

80

70

90

100

110

prac.3

140

150

130

110

120

prac.4

110

80

70

80

100

prac.5

90

100

80

70

110

prac.6

100

150

120

160

90

Należy dołożyć odpowiednią jedną kolumnę tak, aby macierz
współczynników była kwadratowa.

Współczynniki w tej kolumnie wpisujemy tak, aby były
najgorszymi w tabelce. W zadaniu na maksimum wpisujemy 0, w
zadaniu na minimum wpisujemy liczby większe od wszystkich
pozostałych.

142

Zadania sprowadzalne do
zagadnienia przydziału

Nowa tabela zysków będzie wyglądała następująco:

Powstałe zadanie jest zadaniem przydziału i może być
rozwiązywane metodą węgierską.

czynność 1 czynność 2 czynność 3 czynność 4 czynność 5

słodkie

nicnierobienie

prac.1

100

120

90

80

100

0

prac.2

80

70

90

100

110

0

prac.3

140

150

130

110

120

0

prac.4

110

80

70

80

100

0

prac.5

90

100

80

70

110

0

prac.6

100

150

120

160

90

0

2010-02-27

72

143

Zadania sprowadzalne do
zagadnienia przydziału

Przykład 16.

Treść jak w poprzednim przykładzie, ale Pracownik 3 niema
uprawnień do wykonywania Czynności 2:

Aby uniemożliwić metodzie przydzielenie Pracownika 3 do
Czynności 2 należy wpisać w odpowiednie pole „coś złego”.

W tym wypadku jeżeli wpiszemy 0, metoda węgierska nie
przydzieli tego pracownika do tej czynności.

czynność 1 czynność 2 czynność 3 czynność 4 czynność 5

prac.1

100

120

90

80

100

prac.2

80

70

90

100

110

prac.3

140

-

130

110

120

prac.4

110

80

70

80

100

prac.5

90

100

80

70

110

144

Zadania sprowadzalne do
zagadnienia przydziału

Nowa tabela zysków będzie wyglądała następująco:

Powstałe zadanie jest zadaniem przydziału i może być
rozwiązywane metodą węgierską.

czynność 1 czynność 2 czynność 3 czynność 4 czynność 5

prac.1

100

120

90

80

100

prac.2

80

70

90

100

110

prac.3

140

0

130

110

120

prac.4

110

80

70

80

100

prac.5

90

100

80

70

110

2010-02-27

73

145

Problem komiwojażera

Komiwojażer wyjeżdża z pewnego miasta i ma
odwiedzić pewną ilość miast na swojej drodze. Podane są
odległości pomiędzy miastami. Do każdego miasta może
przyjechać tylko raz, nie może również dwa razy
przejechać po tej samej trasie. Na koniec komiwojażer
musi wrócić do miasta, z którego wyjechał.

Należy skonstruować plan przyjazdu tak, aby długość
trasy była jak najmniejsza

146

Problem komiwojażera

Problem komiwojażera sprowadza się do ustalenia kolejności

odwiedzanych miast.

Może być rozwiązywany na wiele sposobów:

jako zadanie kombinatoryczne. Należy wskazać wszystkie
możliwe rozwiązania, obliczyć dla nich wartość funkcji celu i
wybrać spośród nich najlepsze,

jako zadanie liniowego programowania dyskretnego, przy
pomocy zwykłych metod (model matematyczny jest zbliżony
do modelu zagadnienia przydziału), np. metody Simpleks lub
algorytmu Little’a.

z wykorzystaniem metod przybliżonych. Nie szukamy
rozwiązania „najlepszego” ale „dostatecznie dobrego”.

2010-02-27

74

147

Gry i strategie

Słuszność podejmowanych decyzji często zależy do
stanu otoczenia, w którym znajduje się podejmujący
decyzje.

Podejmując decyzję często nie wiemy jaki będzie stan
natury (pogoda, koniunktura na produkowany wyrób,
klimat gospodarczym, itp.) lub jakie decyzje podejmie
partner w grze (druga osoba, od której zależy wynik
podjętej decyzji, konkurencja, itp.).

Rozpatrywaniem tego typu sytuacji zajmuje się teoria
gier. W szczególności problematyką tą zajmuje się
podejmowanie decyzji w warunkach niepewności.

148

Gry i strategie

Przykład 17. Gra „Turyści” J.D. Williamsa.

Mąż i żona wybrali się na wycieczkę. On lubi wyżyny, ona niziny.
Każde z nich ma do wyboru cztery trasy: on prowadzące ze
wschodu na zachód, ona z północy na południe. Umówili się, że
noc spędzą razem na przecięciu wybranych przez siebie tras. On
chciałby być wtedy jak najwyżej, ona – najniżej. Wysokości
punktów przecięcia przedstawia tablica:

1

2

3

4

1

7

2

5

1

2

2

2

3

4

3

5

3

4

4

4

3

2

1

6

T

ra

s

y

w

s

c

h

ó

d

-

z

a

c

h

ó

d

Trasy północ - południe

Jaką trasę powinno wybrać każde z nich, jeżeli wie że drugie
zachowuje się racjonalnie?

2010-02-27

75

149

Gry i strategie

Rozwiązaniem jest wybór trasy 3 przez męża i trasy 2 przez żonę:

1

2

3

4

1

7

2

5

1

2

2

2

3

4

3

5

3

4

4

4

3

2

1

6

T

ra

s

y

w

s

c

h

ó

d

-

z

a

c

h

ó

d

Trasy północ - południe

Jeżeli założymy racjonalność podejmowanych decyzji, tzn. że
każdy z graczy (małżonków) chce zminimalizować swoje straty, to
powyższe rozwiązanie jest jedynym możliwym do przyjęcia
rozwiązaniem.

Każde inne rozwiązanie (wybór innych tras) powoduje, że istnieje
niebezpieczeństwo pogorszenia sytuacji w jakiej znajdują się
małżonkowie.

150

Gry i strategie

Przykład 18. Duopol.

Na jakimś rynku panuje duopol, tzn. występują dwa konkurujące
ze sobą przedsiębiorstwa. Każde z nich poprzez swoje decyzje
może zwiększyć swój zysk.
Zakładamy jednak, że całkowita ilość klientów na rynku jest stała,
w związku z tym wzrost zysku jednej firmy wiąże się ze spadkiem
zysku drugiej.
Każde z przedsiębiorstw dąży do maksymalizacji swojego zysku.
Ich cele są jednak sprzeczne ze sobą.
Logiczne jest, że przedsiębiorstwa będą poszukiwały pewnego
punktu równowagi, tzn. punktu w którym żaden z konkurentów nie
będzie już szukał lepszego rozwiązania.

2010-02-27

76

151

Gry i strategie

Przykład 19. Papier – nożyczki – kamień.

W grze występują trzy przedmioty: papier, kamień i
nożyczki. Papier wygrywa z kamieniem, kamień
wygrywa z nożyczkami, a nożyczki wygrywają z
papierem. Jeżeli przyjmiemy 1 jako wygraną gracza
pierwszego, -1 jako jego przegraną, a 0 jako remis to
wyniki gry można przedstawić w postaci tablicy:

Papier

Kamień

Nożyczki

Papier

0

1

-1

Kamień

-1

0

1

Nożyczki

1

-1

0

Jaką strategię należy przyjąć aby zawsze wygrywać w tej
grze?

152

Gry i strategie

W przypadku tej gry nie istnieje najlepsza decyzja.

Niema również możliwości znalezienia punktu
równowagi pomiędzy obydwoma graczami.

Jedyna skuteczną metodą na zachowanie szans na
wygranie w tej grze jest losowe wybieranie każdej z
decyzji w taki sposób, aby były one tak samo
prawdopodobne.

2010-02-27

77

153

Gry i strategie

Przykład 20. Wakacje.

Koszt spędzenia wakacji w różnych miejscach w Polsce
zależy między innymi od pogody. Koszt pobytu w
zależności od pogody przedstawiono w tablicy:

W domu

Nad morzem

W górach

Upał

1200

1500

1400

Chłodne dni

1200

1200

1100

Deszcze

1200

1000

1300

Gdzie należy się wybrać, aby koszt wakacji był
najmniejszy?

154

Gry i strategie

W tym wypadku nie można wybrać decyzji najlepszej.
Nie można również wskazać stanu równowagi,
satysfakcjonującego obydwu graczy, gdyż drugim
graczem jest natura.

Można wskazać wiele metod postępowania
prowadzących do podjęcia różnych decyzji. Można
zabezpieczyć się przed wystąpieniem najgorszego
wariantu pogody, można zaryzykować zakładając
najlepszą pogodę, można policzyć średni koszt
każdego wyjazdu.

2010-02-27

78

155

Gry i strategie

Powyższe przykłady prowadzą do podziału sytuacji, w

których decyzje zależą od postępowania dwóch graczy
na:

gry dwuosobowe, w których obydwaj gracze są racjonalni,
czyli dążą do maksymalizacji swojego zadowolenia oraz
wiedzą, że przeciwnik również podejmuje decyzje
racjonalne.

gry z naturą, w których jeden z graczy (natura) nie jest
racjonalny, jego decyzje są przypadkowe.
Nieracjonalność natury nie może być rozumiana jako
podejmowanie decyzji głupich.

156

Gry dwuosobowe o sumie
zero

W grze bierze udział dwóch, racjonalnych graczy.

Każdy z graczy podejmuje samodzielne i niezależne
decyzje.

Wynik gry zależy od tego, które decyzje podjęli
obydwaj gracze.

Zysk jednego gracza jest jednocześnie stratą drugiego.
Jest to układ zamknięty, nic nie jest dostarczane „z
zewnątrz” i nic nie trafia „na zewnątrz”.

2010-02-27

79

157

Gry dwuosobowe o sumie
zero

W przypadku gier dwuosobowych o sumie zero istnieją

dwie strategie:

Jeżeli nie występuje punkt równowagi (punkt
siodłowy) najlepszym wyborem jest podejmowanie
decyzji przypadkowych, z równym
prawdopodobieństwem podjęcia każdej z nich. Takie
podejście nazywa się strategią mieszaną.

Jeżeli występuje punkt równowagi stosuje się tzw.
strategię czystą. Każdy z graczy wybiera decyzję
minimalizującą jego ryzyko (maxmin). Raz podjęta
decyzja nigdy nie ulega zmianie.

158

Gry z naturą

W grze bierze udział dwóch graczy.

Jeden gracz jest graczem racjonalnym, drugi
podejmuje decyzje nieracjonalne (natura).

Zysk gracza zależy od decyzji podjętej przez niego
oraz zaistniałego stanu natury i jest znany.

Gracz nie ma wpływu na zaistnienie stanu natury, nie
potrafi również oszacować prawdopodobieństwa jego
zajścia.

Sytuację taką nazywa się również podejmowaniem
decyzji w warunkach niepewności.

2010-02-27

80

159

Podejmowanie decyzji w
warunkach niepewności

Kryteria podejmowania decyzji w warunkach

niepewności:

Każde z poniższych kryteriów jest stosowane
oddzielnie i przy podejmowaniu decyzji nie łączy się
ich.

Wybór kryterium zależy od osobistych preferencji
decydenta. Musi więc samodzielnie wskazać
kryterium, którego rezultaty uzna za najlepsze. Wybór
kryterium zależy wyłącznie od awersji gracza do
ryzyka.

Decydent nie może wybierać stanów natury tylko
własne decyzje!!

160

Podejmowanie decyzji w
warunkach niepewności

Kryterium optymisty (maksimaksowe)

Optymista wybiera najlepszą możliwość dla każdej decyzji i z tych
najlepszych wybiera najlepszą:

max {max [wartości dla danej decyzji]}

najlepsze z najlepszych stanów dla decyzji

Kryterium pesymisty (maksiminowe)

Pesymista wybiera najgorszą możliwość dla każdej decyzji i z tych
najgorszych wybiera najlepszą:

max {mim [wartości dla danej decyzji]}

najlepsze z najgorszych stanów dla decyzji

Niema kryteriów najgorsze z najgorszych i najgorsze z
najlepszych. To świadczyłoby o nieracjonalności
podejmowanych decyzji.

2010-02-27

81

161

Podejmowanie decyzji w
warunkach niepewności

Kryterium Laplace’a (wartości średniej)

Dla każdej możliwości wyboru należy obliczyć średnią, a
następnie wybrać najlepszą z nich.

Kryterium Hurwicza

a

i

– najlepsza wartość dla i-tego wyboru

b

i

– najgorsza wartość dla i-tego wyboru

Dla każdej możliwości wyboru należy obliczyć wyrażenie:

φ

(A

i

) =

λ

a

i

+ (1-

λ

)b

i

Spośród wartości

φ

należy wybrać najlepszą.

Współczynnik

λ

∈[0,1] nazywany jest współczynnikiem

optymizmu.

162

Podejmowanie decyzji w
warunkach niepewności

Kryteria Niehansa – Savage’a (utraconych
szans, strat alternatywnych)

Dla każdego stanu natury wybieramy wartość najlepszą i
od niej po kolei odejmujemy wszystkie wartości dla tego
stanu natury.

Powstała tablica zawiera szanse utracone, czyli zyski których
nie uzyskamy jeżeli nastąpi wybrany stan natury, a my
podjęliśmy daną decyzję.

Dalej dla tabeli zawierającej utracone szanse stosowane jest
kryterium pesymisty.

2010-02-27

82

163

Podejmowanie decyzji w
warunkach niepewności

Przykład 21.

Masz nadmiar gotówki ☺ i chcesz go ulokować tak, aby mieć z
tego największe korzyści. Po sprawdzeniu wszystkich
ewentualności zbudowałeś tabelę zawierającą realne stopy zysku z
różnych inwestycji przy różnych stanach inflacji:

„skarpeta”

bank

akcje

obligacje

inflacja 2%

-2%

3%

4%

3%

inflacja 3%

-3%

2%

7%

3%

inflacja 5%

-5%

4%

0%

3%

Wybory

S

t.

n

a

tu

ry

Wybierz inwestycję, która najbardziej Ci odpowiada.

164

Podejmowanie decyzji w
warunkach niepewności

Wybory zdominowane

Jeżeli któraś z możliwości wyboru jest zawsze gorsza od innej
to znaczy, że jest przez nią zdominowana i powinna zostać
usunięta przed zastosowaniem któregokolwiek z kryteriów ceny
decyzji.

W tym zdaniu trzymanie pieniędzy w „skarpecie” jest dla
każdego stanu natury gorsze od wszystkich pozostałych
wyborów, w związku z tym powinno być usunięte z rozważań.

bank

akcje

obligacje

inflacja 2%

3%

4%

3%

inflacja 3%

2%

7%

3%

inflacja 5%

4%

0%

3%

S

ta

n

y

n

a

tu

ry

Wybory

2010-02-27

83

165

Podejmowanie decyzji w
warunkach niepewności

Kryterium optymisty

Optymista wybiera najlepszą możliwość dla każdego wyboru i z tych

najlepszych wybiera najlepszą:

bank – 4%

akcje – 7%

obligacje – 3%

Najlepsza wartość to 7%, więc należy wybrać inwestycję w akcje.

Kryterium pesymisty

Pesymista wybiera najgorszą możliwość dla każdego wybory i z tych

najgorszych wybiera najlepszą:

bank – 2%

akcje – 0%

obligacje – 3%

Najlepsza wartość to 3%, więc należy wybrać inwestycję w obligacje.

166

Podejmowanie decyzji w
warunkach niepewności

Kryterium Laplace’a (wartości średniej)

Dla każdej możliwości wyboru należy obliczyć średnią, a

następnie wybrać najlepszą z nich:

bank – 3%

akcje – 3,66%

obligacje – 3%

Najlepsza wartość to 3,66%, więc należy wybrać inwestycję

w akcje

2010-02-27

84

167

Podejmowanie decyzji w
warunkach niepewności

Kryterium Hurwicza

Dla każdej możliwości wyboru należy obliczyć wyrażenie:

φ

(A

i

) =

λ

a

+ (1-

λ

)b

(

λ

jest zwykle dobierane na drodze doświadczalnej)

następnie z pośród nich wybrać najlepsze (dla

λ

=0,2):

bank – 2,4%

akcje – 1,4%

obligacje – 3%

Najlepsza wartość to 3%, więc należy wybrać inwestycję w

obligacje.

168

Podejmowanie decyzji w
warunkach niepewności

Kryteria Niehansa – Savage’a (kryterium utraconych szans)

Dla każdego stanu natury wybieramy wartość najlepszą i od niej odejmujemy

wszystkie wartości dla tego stanu natury

bank

akcje

obligacje

inflacja 2%

1%

0%

1%

inflacja 3%

5%

0%

4%

inflacja 5%

0%

4%

1%

S

ta

n

y

n

a

tu

ry

Wybory

Tabela zawiera utracone, czyli zyski których nie uzyskamy jeżeli nastąpi
wybrany stan natury.

Do wyboru najmniejszej straty należy zastosować kryterium pesymisty:

bank – 5%

akcje – 4%

obligacje – 4%

Najlepsza wartość to 4%, należy więc wybrać inwestycję w akcje lub
obligacje.

2010-02-27

85

169

Podejmowanie decyzji w
warunkach ryzyka

Z podejmowaniem decyzji w warunkach ryzyka
decydent ma do czynienia, gdy parametry zadania
opisane są za pomocą zmiennej losowej.

W praktyce w grach z naturą podejmowanie decyzji w
warunkach ryzyka występuje wtedy, gdy znamy lub
potrafimy oszacować prawdopodobieństwo zajścia
poszczególnych stanów natury.

W podejmowaniu decyzji w tym przypadku pomagają
narzędzia i procedury rachunku prawdopodobieństwa.

170

Podejmowanie decyzji w
warunkach ryzyka

Kryteria podejmowania decyzji w warunkach

niepewności:

Kryterium wartości oczekiwanej

Dla każdej decyzji obliczana jest wartość oczekiwana, a

następnie spośród nich wybierana jest najlepsza (największa
lub najmniejsza.

Kryterium odchylenia standardowego

W przypadku, gdy kryterium wartości oczekiwanej zawodzi ze

względu na jednakową wartość kilku decyzji można
posłużyć się drugim kryterium wskazującym kolejność tych
decyzji. Należy dla nich obliczyć odchylenie standardowe.
Jest to miara ryzyka i jest mniejsze tym lepsza decyzja.

2010-02-27

86

171

Podejmowanie decyzji w
warunkach ryzyka

Kryterium największej wiarygodności

Spośród stanów natury wybiera się stan o największym

prawdopodobieństwie. Za najlepszą decyzję uznaje się tą o
najlepszej wartości przypisanej temu stanowi natury.

172

Podejmowanie decyzji w
warunkach ryzyka

Przykład 22.

Masz nadmiar gotówki i chcesz go ulokować tak, aby mieć z tego
największe korzyści. Po sprawdzeniu wszystkich ewentualności
zbudowałeś tabelę zawierającą realne stopy zysku z różnych
inwestycji przy różnych stanach inflacji:

Znamy jest również rozkład prawdopodobieństwa wystąpienia
poszczególnych wartości inflacji: P(2%) = 0,3; P(3%) = 0,5;
P

(5%) = 0,2.

Proszę podjąć decyzję o inwestycji.

„skarpeta”

bank

akcje

obligacje

inflacja 2%

-2%

3%

4%

3%

inflacja 3%

-3%

2%

7%

3%

inflacja 5%

-5%

4%

0%

3%

Wybory

S

t.

n

a

tu

ry

2010-02-27

87

173

Podejmowanie decyzji w
warunkach ryzyka

Zadanie można również sformułować w postaci tablicy:

bank

akcje

obligacje

Prawdopod.

inflacja 2%

3%

4%

3%

0,3

inflacja 3%

2%

7%

3%

0,5

inflacja 5%

4%

0%

3%

0,2

S

ta

n

y

n

a

tu

ry

Decyzje

174

Podejmowanie decyzji w
warunkach ryzyka

Kryteria podejmowania decyzji

Kryterium wartości oczekiwanej

Dla każdego wyboru (inwestycji) należy obliczyć wartość oczekiwaną stopy

zwrotu, a następnie wybrać najlepszą:

bank – 2,7%

akcje – 4,7%

obligacje – 3%

Najlepsza wartość to 4,7%, więc należy wybrać inwestycje w akcje.

Kryterium największej wiarygodności

Wybieramy stan natury o najwyższym prawdopodobieństwie. Jest nim

Inflacja 3%.

bank – 2%

akcje – 7%

obligacje – 3%

Najlepsza wartość to 7%, należy więc wybrać inwestycję w akcje.

2010-02-27

88

175

Podejmowanie decyzji w
warunkach ryzyka

Przykład 23.

Koszty pewnych inwestycji zależą od koniunktury
gospodarczej. Oczekiwane koszty inwestycji (w mln zł)
oraz prawdopodobieństwa poszczególnych stanów
koniunktury przedstawiono w tablicy:

Wzrost

Bez zmian

Spadek

Inwestycja A

10

20

50

Inwestycja B

15

5

15

Inwestycja C

12

10

14

Prawdopodobieństwo

0,4

0,3

0,3

Koniunktura gospodarcza

Decyzje

Wybierz najlepszą, Twoim zadaniem, inwestycję.

176

Podejmowanie decyzji w
warunkach ryzyka

Kryteria podejmowania decyzji

Kryterium wartości oczekiwanej

Dla każdego decyzji inwestycyjnej należy obliczyć wartość oczekiwaną

kosztu, a następnie wybrać najlepszą:

Inwestycja A – 25

Inwestycja B – 12

Inwestycja C – 12

Najlepsza wartość to 12 mln zł nie można rozstrzygnąć która z Inwestycji:

B czy C jest lepsza.

Kryterium odchylenia standardowego

Dla Inwestycji B i C należy obliczyć odchylenie standardowe:

Inwestycja B – 4,58

Inwestycja C – 1,55

Należy wybrać Inwestycję C ze względu na mniejsze ryzyko.

2010-02-27

89

177

Podejmowanie decyzji w
warunkach ryzyka

Kryterium największej wiarygodności

Wybieramy stan natury o najwyższym prawdopodobieństwie.

Jest nim „Wzrost koniunktury gospodarczej”.

Koszty inwestycji dla tego stanu natury są następujące:

Inwestycja A – 10 mln zł

Inwestycja B – 15 mln zł

Inwestycja C – 12 mln zł

Najlepsza wartość to 10 mln zł.

Na podstawie kryterium największej wiarygodności należy

wybrać Inwestycję A.