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: arkad@am.gdynia.pl

dr T. Owczarek: nazgul@am.gdynia.pl

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”.