Matematyczne techniki zarządzania - 211

Jak to wszystko zrealizować matematycznie? — patrz

skrypt, s. 18

skrypt, s. 186-191

6-191

Kłopoty matematyczne biorą się z tego, że mamy więcej zmiennych (nie-
wiadomych) niż równań

0

0

0

8

5

1

26

1

3

3

14

1

4

2

4

3

2

1

0

4

2

1

3

2

1

























x

x

x

x

x

x

x

x

x

x

x

warunki ograniczające ze zmiennymi swobodnymi

dołączona funkcja celu z jej wartością x

0

Jedynym sposobem rozwiązania tego układu jest rachunek iteracyjny,
polegający na wielokrotnym zakładaniu, że zmienne występujące we
wszystkich równaniach są równe zero, przez co otrzymamy niezerowe
wartości pozostałych zmiennych.

x

1

=0x

2

=0

x

3

=14

x

4

=26

x

0

= 0

ZMIENNE

ZMIENNE

NIEBAZOWE

NIEBAZOWE

ZMIENNE

ZMIENNE

BAZOWE

BAZOWE

BAZA 0

BAZA 0

Mysz w tym momencie znajduje
się na początku układu
współrzęd-nych: Z(X) = x

0

= 0

Przejście do następnego wierz-
chołka to

zmiana bazy

zmiana bazy, co wyma-

ga podjęcia dwu decyzji:

• którą zmienną wprowadzić do bazy, a którą z niej wycofać (dla myszy to
decyzja — którą krawędzią się poruszać)

• jaką wartość przyjąć dla zmiennej wprowadzanej do bazy, aby maksyma-
lnie poprawić Z(X), a równocześnie nie wyjść poza obszar rozwiązań do-
puszczalnych (dla myszy to decyzja — jak iść aby nie minąć wierzchołka)

Tablica simpleksowa

Skrypt, s.188

Matematyczne techniki zarządzania - 212

Zmiana bazy polega na wymianie tylko jednej zmiennej, czyli na zmianie na
wierzchołku kierunku marszu ku rozwiązaniu optymalnemu.

BAZA 0

BAZA 0

BAZA 1

BAZA 1

BAZA 2

BAZA 2

BAZA 3

BAZA 3

Po wyznaczeniu tych
decyzji, układ równań
przekształca się (przez
ich mnożenie i doda-
wanie) tak, aby zmien-
ne bazowe występowa-
ły tylko w jednym rów-
naniu.

Rachunek iteracyjny kończy się w momencie, gdy z
dołączonej funkcji celu wynika, że nie ma już moż-
liwości poprawy wartości funkcji celu.

Baza zdegenerowana:

Baza zdegenerowana: baza, w której pojawiło się przypadkowe zero

ZAGADNIENIE DUALNE SYMETRYCZNE

Zagadnienie pierwotne

Zagadnienie dualne

0

max

)

(













j

i

j

ij

j

j

x

b

x

a

x

c

X

Z



0

min

)

(













i

j

i

ji

i

i

y

c

y

a

y

b

Y

Z

• nowa zmienna

dualna y

dualna y

i

i

• odwrócenie kierunku optymali-
zacji

• zamiana c

j

oraz b

i

miejscami

• transponowanie macierzy A
• zmiana kierunku nierówności

Zagadnienie dualne (zagadnienia dualnego) = zagadnienie pierwotne

Rozwiązując jedno z nich rozwiązujemy równocześnie drugie, czasem

wygodniej jest rozwiązywać dualne zamiast pierwotnego

)

(

min

)

(

max

Y

Z

X

Z



Matematyczne techniki zarządzania - 213

Ekonomiczna interpretacja zmiennych dualnych y

i

Są to

ceny dualne środków produkcji

ceny dualne środków produkcji określające jaki dodatkowy zysk mo-

że przynieść firmie dodatkowa jednostka i-tego środka.

W każdym warunku ograniczającym występuje nierówność , co oznacza,

że dany środek (surowiec, robocizna, czas pracy maszyn) może być przy
rozwiązaniu optymalnym albo wykorzystany całkowicie (=), albo tylko
częściowo (<).

Stopień wykorzystania i-tego środka produkcji poznajemy po wartości
zmiennej swobodnej (plansza 207).

1. Środek produkcji wyczerpany w rozwiązaniu optymalnym



25

6

3

3

2

1







x

x

x

=0

Zmienna dualna związana z tym środkiem
ma wartość , gdyż sprowadzenie nowej

jednostki tego środka pozwoli zwiększyć
produkcję, co da dodatkowy zysk równy y

i

2. Środek produkcji niewyczerpany w rozwiązaniu optymalnym

42

2

6

4

2

1







x

x

x

=8

Zmienna dualna związana z tym środkiem
ma wartość 0, gdyż tego środka jest już te-
raz w nadmiarze i sprowadzenie nowej je-
go jednostki nic w firmie nie zmieni — ani
wielkości produkcji, ani zysku

A jaka będzie interpretacja zmiennej dualnej dla mieszanki?



Matematyczne techniki zarządzania - 214

ANALIZA WRAŻLIWOŚCI W PROGRAMOWANIU LINIOWYM

Co będzie,
jeśli...

PROGRAMOWA
NIE
PARAMETRYCZ
NE

Bada się reakcję

X

X

(rozwiązania optymalnego) na

zmianę

A, B, C

A, B, C (założeń)

1. Skutki zmiany funkcji celu (macierzy C)

Funkcja celu

]

5

,

3

[

max

5

3

2

1







C

x

x

• x

j

nie ma w ostatniej bazie w rozwiązaniu optymalnym, czyli x

j

= 0

WYRÓB j-TY NIE JEST PRODUKOWANY W ROZWIĄZANIU OPTYMALNYM —

WYRÓB j-TY NIE JEST PRODUKOWANY W ROZWIĄZANIU OPTYMALNYM —

DLACZEGO?

DLACZEGO?

PONIEWAŻ JEGO RENTOWNOŚĆ JEST ZA NISKA W PORÓWNANIU Z INNYMI

PONIEWAŻ JEGO RENTOWNOŚĆ JEST ZA NISKA W PORÓWNANIU Z INNYMI

Wnioski:

— obniżenie zysku jednostkowego c

— obniżenie zysku jednostkowego c

j

j

nie zmieni rozwiązania optymalnego,

nie zmieni rozwiązania optymalnego,

gdyż j-ty wyrób w dalszym ciągu będzie nierentowny

gdyż j-ty wyrób w dalszym ciągu będzie nierentowny

—

—

zwiększenie zysku jednostkowego może zmienić rozwiązanie optymalne,

zwiększenie zysku jednostkowego może zmienić rozwiązanie optymalne,

gdyż j-ty wyrób może (jeśli przekroczymy pewną wartość c

gdyż j-ty wyrób może (jeśli przekroczymy pewną wartość c

j

j

) stać się bar-

) stać się bar-

dziej opłacalny niż inne wyroby

dziej opłacalny niż inne wyroby

Pytanie: o ile najwięcej (p

Pytanie: o ile najwięcej (p

j

j

) może wzrosnąć c

) może wzrosnąć c

j

j

, aby rozwiązanie optymalne nie

, aby rozwiązanie optymalne nie

uległo zmianie?

uległo zmianie?

Przykład odpowiedzi:

Przykład odpowiedzi:

p

p

2

2

<0,4286

<0,4286

Interpretacja:

Interpretacja:

dopóki c

dopóki c

2

2

<5,4286, wyrób 2 nie powinien wchodzić do produkcji

<5,4286, wyrób 2 nie powinien wchodzić do produkcji



Matematyczne techniki zarządzania - 215

• zmienna x

j

znajduje się w ostatniej bazie, czyli x

j

>0

WYRÓB j-TY JEST PRODUKOWANY W ROZWIĄZANIU OPTYMALNYM — DLACZEGO?

WYRÓB j-TY JEST PRODUKOWANY W ROZWIĄZANIU OPTYMALNYM — DLACZEGO?

PONIEWAŻ JEGO RENTOWNOŚĆ JEST WYŻSZA W PORÓWNANIU Z INNYMI

PONIEWAŻ JEGO RENTOWNOŚĆ JEST WYŻSZA W PORÓWNANIU Z INNYMI

Wnioski:

— obniżenie zysku jednostkowego c

— obniżenie zysku jednostkowego c

j

j

może zmienić rozwiązanie optymalne,

może zmienić rozwiązanie optymalne,

gdyż j-ty wyrób może stać się nierentowny (po zejściu poniżej pewnej

gdyż j-ty wyrób może stać się nierentowny (po zejściu poniżej pewnej

granicy)

granicy)

—

—

zwiększenie zysku jednostkowego może zmienić rozwiązanie optymalne,

zwiększenie zysku jednostkowego może zmienić rozwiązanie optymalne,

gdyż j-ty wyrób może (jeśli przekroczymy pewną wartość c

gdyż j-ty wyrób może (jeśli przekroczymy pewną wartość c

j

j

) stać się

) stać się

jeszcze bardziej opłacalny niż dotychczas

jeszcze bardziej opłacalny niż dotychczas

Pytanie: o ile (p

Pytanie: o ile (p

j

j

) może zmaleć lub wzrosnąć c

) może zmaleć lub wzrosnąć c

j

j

, aby rozwiązanie optymalne

, aby rozwiązanie optymalne

nie uległo zmianie?

nie uległo zmianie?

Przykład odpowiedzi:

Przykład odpowiedzi:

—0,6<

p

p

1

1

<2,2

<2,2

Interpretacja:

Interpretacja:

dopóki 2,4<c

dopóki 2,4<c

1

1

<5,2, wyrób 1 powinien być produkowany w

<5,2, wyrób 1 powinien być produkowany w

ilości x

ilości x

1

1

wyznaczonej przez rozwiązanie optymalne

wyznaczonej przez rozwiązanie optymalne

2. Skutki zmiany wektora ograniczeń (macierzy B)

48

6

3

2

1



 x

x



Każda zmiana (w pewnych granicach) ilości środków produkcji

Każda zmiana (w pewnych granicach) ilości środków produkcji

zmienia wartość funkcji celu

zmienia wartość funkcji celu

Analizę wrażliwości na B przeprowadza się z uwzględnieniem:

— zmiany struktury asortymentowej wyrobów (które wyroby się produkuje)
oraz osobno szczegółów produkcji (ile się produkuje)

— ceny dualnej środków: czy dany środek jest wyczerpany w rozwiązaniu
optymalnym, czy nie wyczerpany

Matematyczne techniki zarządzania - 216

3. Skutki zmiany współczynników technologicznych (macierzy A)

• wprowadzenie nowego wyrobu

25

1

4

48

6

3

2

1

2

1









x

x

x

x

3

x

25

5

1

4

48

3

6

3

3

2

1

3

2

1













x

x

x

x

x

x

Pytanie: ile musi wynosić c

Pytanie: ile musi wynosić c

3

3

, aby rozwiązanie optymalne uległo zmianie, czyli

, aby rozwiązanie optymalne uległo zmianie, czyli

aby wyrób trzeci wszedł do produkcji?

aby wyrób trzeci wszedł do produkcji?

Przykład odpowiedzi:

Przykład odpowiedzi:

jeśli c

3

>14, wyrób trzeci wejdzie do produkcji

• zmiana technologii produkcji

4

6

12

12







a

a



Zagadnienie skomplikowane

POMIJAMY

DUŻE PROFESJONALNE PROGRAMY KOMPUTEROWE UMOŻLIWIAJĄ

ANALIZOWANIE WRAŻLIWOŚCI ROZWIĄZANIA OPTYMALNEGO NA

RÓWNOCZESNĄ ZMIANĘ KILKU CZYNNIKÓW

WIĘCEJ INFORMACJI O

ANALIZIE WRAŻLIWOŚCI W

SKRYPCIE (ROZDZIAŁ 7)

WYDRUK Z PROGRAMU QSB+

ZAWIERA DUŻO

ELEMENTÓW ANALIZY

WRAŻLIWOŚCI




Matematyczne techniki zarządzania - 217

WYDRUK Z PROGRAMU QSB+

WYDRUK Z PROGRAMU QSB+

CZĘŚĆ PIERWSZA

CZĘŚĆ PIERWSZA

Summarized Report for......................

Number

Variable

Solution

Opportunity

Cost

Objective

Coefficient

Minimum

Obj. Coeff.

Maximum

Obj. Coeff.

1

2

X1

X2

+2,0

+6,0

0

0

+30,0

+50,0

0

+20,0

+75

+Infinity

Max (Min) Obj = .... Iteration = .... Elapsed CPU Second = ......

Nazwa projektu

Przy interpretacji wydruku

obowiązuje podwójny język:

• matematyczny

• ekonomiczny (menedżerski)

Numer zmiennej

decyzyjnej

 numer wyrobu
 numer składnika

mieszanki

Rozwiązanie (optymalne wartości

zmiennych decyzyjnych)

 ilości produkowanych wyrobów
 ilości użytych składników

Koszty alternatywne

(względne)

O ile trzeba zmienić
współczynnik funkcji
celu, aby wyrób (skład-
nik) wszedł do rozwią-
zania optymalnego (w
przykładzie = 0, gdyż
ilości są różne od zera)

Współczynniki

funkcji celu

(macierz C)

 zyski jednost-

kowe z wyrobów

 ceny składników

mieszanki

Optymalna wartość

funkcji celu

 maksymalny zysk

producenta

 minimalny koszt

mieszanki

Optymalne zakresy

współczynników

funkcji celu

 przedziały zysku

jednostkowego nie
powodujące zmiany
planu produkcji

 przedziały ceny

składników nie po-
wodujące zmiany
receptury miesza-
nki

Liczba iteracji wykonanych przez komputer

Czas szukania

optymalnego

rozwiązania





Matematyczne techniki zarządzania - 218

WYDRUK Z PROGRAMU QSB+

WYDRUK Z PROGRAMU QSB+

CZĘŚĆ DRUGA

CZĘŚĆ DRUGA

Przy interpretacji wydruku

obowiązuje podwójny język:

• matematyczny

• ekonomiczny (menedżerski)

S

u

m

m

a

r

i

z

e

d

R

e

p

o

r

t

f

o

r

.

.

.

.

.

.

.

C

o

n

s

t

r

a

i

n

t

S

t

a

t

u

s

R

H

S

S

h

a

d

o

w

P

r

i

c

e

S

l

a

c

k

o

r

S

u

r

p

l

u

s

M

i

n

R

H

S M

a

x

R

H

S

1

2

3

L

o

o

s

e

T

i

g

h

t

T

i

g

h

t

)

(





+

4

,

0

)

(





+

1

2

,

0

)

(





+

1

8

,

0

0

1

5

1

0

+

2

,

0

0

0

+

2

,

0

+

6

,

0

+

1

2

,

0

+

I

n

fi

n

i

t

y

+

1

8

+

2

4

M

a

x

(

M

i

n

)

O

b

j

=

.

.

.

.

.

.

I

t

e

r

a

t

i

o

n

=

.

.

.

.

.

.

E

l

a

p

s

e

d

C

P

U

S

e

c

o

n

d

=

.

.

.

.

.

.

Numer ograniczenia (warunku)

 numer środka produkcji
 numer komponentu

mieszanki

Sposób spełniania nierówności

z warunków ograniczających

(loose = nierówność silna,

tight = nierówność słaba)

 loose = środek produkcji jest

w nadmiarze; tight = środek
produkcji wyczerpany

 loose = komponent jest w

nadmiarze; tight = komponen-
tu jest dokładnie według wy-
magań normy

Ograniczenia (macierz B) z nierównością

 ilości posiadanych środków produkcji
 najmniejsze dopuszczalne ilości komponentów (normy)

Ceny dualne

 dodatkowy

zysk z dodat-
kowej jedno-
stki środka

 zmiana ko-

sztu miesza-
nki po zmnie-
jszeniu nor-
my o jednos-
tkę

Luz czyli nadmiar

 ilość niewycze-

rpanego środka
produkcji

 ilość kompone-

ntu ponad normę

Wartości zakresów

ograniczeń (macierzy

B), w których wartość

optymalna funkcji celu

zmienia się zgodnie z

cenami dualnymi

 zakresy dla ilości

środka produkcji

 zakresy dla ilości

komponentu mieszanki

Matematyczne techniki zarządzania - 219

ZAST0SOWANIA PROGRAMOWANIA LINIOWEGO

ZAST0SOWANIA PROGRAMOWANIA LINIOWEGO

JEST TO METODA

UNIWERSALNA

PRAWIE WSZYSTKO

MOŻNA ZAPISAĆ

JAKO MODEL

PROGRAMOWANIA

LINIOWEGO

• planowanie produkcji

 ile i czego

 ile i jaką metodą

 ile i z czego

 ile i kiedy

• optymalizacja strategii rozwoju koncernu
• optymalizacja rozwoju branż gospodarki narodowej
• optymalizacja strategii reklamowej
• optymalizacja przepływów w sieciach
• optymalizacja kontraktacji w rolnictwie
• zagadnienia dowozu i przewozu (autobusy, lotnictwo)
• zagadnienia techniczne: projektowanie, cięcie, rozkrój
• harmonogramy dyżurów, plany zajęć
• teoria gier

SETKI ZADAŃ

W KSIĄŻCE

WAGNERA

BADANIA

OPERACYJNE

UMIEJĘTNOŚĆ INTERPRETACJI WYDRUKU Z PROGRAMOWANIA

LINIOWEGO TO MINIMUM WIEDZY STUDENTA

Matematyczne techniki zarządzania - 220

KLASYCZNE ZAGADNIENIE TRANSPORTOWE

KLASYCZNE ZAGADNIENIE TRANSPORTOWE



ODBIORCY

DOSTAWCY

O

1

O

2

O

3

PODAŻ

D

1

c

11

x

11

c

12

x

12

c

13

x

13

a

1

D

2

c

21

x

21

c

22

x

22

c

23

x

23

a

2

POPYT

b

1

b

2

b

3

MODEL

0

,...,

,

min

...

)

(

23

12

11

3

23

13

2

22

12

1

21

11

2

23

22

21

1

13

12

11

23

23

12

12

11

11





































x

x

x

b

x

x

b

x

x

b

x

x

a

x

x

x

a

x

x

x

x

c

x

c

x

c

X

Z

Twierdzenia związane z KZT

1.

ZAGADNIENIE MOŻE BYĆ

OTWARTE

OTWARTE LUB

ZAMKNIĘTE

ZAMKNIĘTE













j

i

j

i

b

a

b

a

Zagadnienie otwarte sprowadza się do
zamkniętego przez wprowadzenie fik-
cyjnego dostawcy lub odbiorcy

2.

JEŚLI DANE SĄ LICZBAMI CAŁKOWITYMI, TO KZT MA CO

NAJMNIEJ JEDNO ROZWIĄZANIE

CAŁKOWITOLICZBOWE

CAŁKOWITOLICZBOWE

CAŁKO-

WITOLI-

CZBOWOŚĆ

3.

JEŚLI ISTNIEJĄ DWA ROZWIĄZANIA OPTYMALNE,

MOŻNA TWORZYĆ

NOWE

NOWE JAK PRZY PROGRAMOWANIU

LINIOWYM

Matematyczne techniki zarządzania - 221

4.

ROZWIĄZANIE OPTYMALNE NIE ULEGNIE ZMIANIE, JEŚLI NA MACIERZY

ODLEGŁOŚCI

C

C WYKONAMY:

• mnożenie (dzielenie) całej macierzy przez stałą (zmiana skali liczb)
• dodawanie (odejmowanie) stałej do pojedynczych wierszy i kolumn
(tworzenie klatek zerowych)

UZYSKANE W TEN SPOSÓB NOWE ODLEGŁOŚCI NAZYWAMY

PSEUDOODLEGŁOŚCIAMI

PSEUDOODLEGŁOŚCIAMI

METODA KLATEK ZEROWYCH

METODA KLATEK ZEROWYCH

Przykład 47. Znajdź metodą klatek zerowych optymalny plan rozwozu
konserw rybnych z czterech portów do pięciu miast w głębi kraju. Odle-
głości podano w km, a podaż i popyt w postaci liczby kontenerów.

Częstochowa

Kraków

Wrocław

Toruń

Kielce

Gdynia

482

621

499

210

651

36

Ustka

631

747

504

311

780

7

Kołobrzeg

559

631

432

347

691

12

Szczecin

482

641

353

340

678

27

15

30

15

14

8

 





i j

ij

ij

x

c

X

Z

min

)

(

Funkcja celu

(w kontenero-kilometrach)

Zmienna decyzyjna x

ij

określa ile kontenerów trzeba przewieźć od i-

tego dostawcy do j-tego odbiorcy, tak aby jak najmniejszym kosz-
tem wywieźć konserwy z portów do odbiorców zgodnie z ich zapo-
trzebowaniem.

TO ZAGADNIENIE JEST ZAMKNIĘTE!

Matematyczne techniki zarządzania - 222

ETAP 1.

ETAP 1. Wprowadzenie zer do kolumn przez odjęcie najmniejszych
odległości

•

od elementów kolumny 1 odejmujemy 482

• od elementów kolumny 2 odejmujemy 621
• od elementów kolumny 3 odejmujemy 353
• od elementów kolumny 4 odejmujemy 210
• od elementów kolumny 5 odejmujemy 651

Dążymy do tego,

aby klatka zerowa

była w każdej

kolumnie i w

każdym wierszu

Przewozy

ulokujemy

w klatkach

zerowych

ETAP 2.

ETAP 2. Wprowadzenie zer do wierszy przez odjęcie najmniejszych
odległości

(wiersz 2: 101, wiersz 3: 10)

Matematyczne techniki zarządzania - 223

ETAP 3.

ETAP 3. Ulokowanie przewozów w klatkach zerowych

Czynność tę można rozpocząć od dowolnej decyzji, byle ona mogła być jednoznaczna;
gdzie wywieźć kontenery z Gdyni lub ze Szczecina — nie można teraz ustalić, ale moż-
na to ustalić dla Ustki i Kołobrzegu

Dec. 1:

7 kontenerów z Ustki do Torunia

7

Dec. 2:

12 kontenerów z Kołobrzegu do Krakowa

12

Dec. 3:

18 kontenerów z Gdyni do Krakowa

18

Dec. 4:

15 kontenerów ze Szczecina do Wrocławia

15

Dec. 5:

7 kontenerów z Gdyni do Torunia

7

Dec. 6:

8 kontenerów z Gdyni do Kielc

8

Dec. 7:

3 kontenery z Gdyni do Częstochowy

3

Dec. 8:

12 kontenerów ze Szczecina do Częstochowy

12

0

0

15

0

12

0

0

0

12

0

0

7

0

0

0

8

7

0

18

3



X

ROZWIĄZANIE OPTYMALNE

ROZWIĄZANIE OPTYMALNE

MINIMALNA WARTOŚĆ FUNKCJI CELU

MINIMALNA WARTOŚĆ FUNKCJI CELU

kkm

X

Z

130

.

40

678

0

340

0

353

15

...

499

0

621

18

482

3

)

(





























DECYZJE PODEJMOWA-

NE W SPOSÓB PRZYPA-

DKOWY DAWAŁY WYNI-

KI WYŻSZE 0 5-10%

Matematyczne techniki zarządzania - 224

INNE METODY „RĘCZNE”

INNE METODY „RĘCZNE”

• metoda Forda-Fulkersona (tworzenie dalszych klatek zerowych)
• metoda kąta północno-zachodniego (metoda węgierska)

SIMPLEKS TRANSPORTOWY (PROGRAMOWANIE LINIOWE)

SIMPLEKS TRANSPORTOWY (PROGRAMOWANIE LINIOWE)

JAK TO PRZE-
KSZTAŁCIĆ W

PROGRAMOWA-

NIE LINIOWE?

x

1

x

2

x

3

x

4

x

5

x

6

x

7

x

8

x

9

x

10

x

11

x

12

x

11

x

12

x

13

x

14

x

21

x

22

x

23

x

24

x

31

x

32

x

33

x

34

=

1

1

1

1

1

1

1

1

1

1

1

1

= 6

= 1

= 10

1

1

1

1

1

1

1

1

1

1

1

1

= 7

= 5

= 3

= 2

2

3

11

7

1

0

6

1

5

8

15

9

MIN

TYPOWA TABELKA PROGRAMOWANIA LINIOWEGO

Gdzie są i jak

powstały ma-

cierze A, B i C?

Jak się mają do siebie macierze zagadnienia transportowego i
macierze programowania liniowego?

To zadanie łatwiej rozwią-zać
wykorzystując zagad-nienie
dualne asymetryczne

.

2

4

1

itd

y

y





Matematyczne techniki zarządzania - 225

Klasyczne zagadnienie transportowe ma wiele wersji i zastosowań,
często do zadań nie mających nic wspólnego z przewozami

Możliwe jest wprowadzenie ograniczeń na przepustowość
poszczególnych tras

ij

ij

u

x 

ZAGADNIENIE PRZYDZIAŁU

ZAGADNIENIE PRZYDZIAŁU

MATEMATYCZ-

MATEMATYCZ-

NIE JEST TO

NIE JEST TO

SZCZEGÓLNY

SZCZEGÓLNY

PRZYPADEK

PRZYPADEK

KZT

KZT

ZWYKLE

ZWYKLE

DOTYCZY

DOTYCZY

PRODUKCJI

PRODUKCJI

Polega na takim rozdzieleniu n
zadań pomiędzy n wykonawców,
aby łączny efekt był jak najko-
rzystniejszy (znamy nakład c

ij

potrzebny i-temu wykonawcy do
wykonania j-tego zadania)

Jeden wykonawca może otrzy-
mać tylko jedno zadanie

1

,

0

1

1

max

min



















 

ij

n

j

ij

n

i

ij

n

i

n

j

ij

ij

x

x

x

x

c

Przykłady zagadnienia przydziału

• asystent ma 15 tematów dla 15 studentów i wie jaką
notę otrzyma każdy student z każdego tematu; celem
będzie taki przydział, aby w sumie grupa uzyskała jak
najwyższą ocenę

• kierownik ma 6 obrabiarek i 6 zadań obróbczych do
wykonania; jeśli wie ile trwa każde zadanie na każdej
obrabiarce, może tak je przydzielić, aby wszystkie za-
dania zostały wykonane w jak najkrótszym czasie

• jeśli istnieje kolejność obróbki — problem

szeregowania

szeregowania

Matematyczne techniki zarządzania - 226

ANALIZA SIECIOWA

ANALIZA SIECIOWA

JAK RYSOWAĆ SIEĆ?

• długości i kąty łuków nie mają

żadnego znaczenia



• sieć to uniwersalne narzędzie (można przy jej
użyciu rozwiązywać wiele problemów nie mają-
cych żadnej „siatki”)

• rozróżniamy sieci cykliczne i

acykliczne

acykliczne

• rozwiązanie sieci polega na znalezieniu:



najkrótszej drogi



najdłuższej drogi

• metody rozwiązywania sieci



ręc

znie

 programowanie liniowe

 programowanie dynamiczne

 profesjonalne programy komputerowe

Szukanie najkrótszej drogi

(zagadnienie dyliżansu)

(zagadnienie dyliżansu)

1

2

3

4

5

6

7

8



C

ij

km (mile)

godziny

złotówki

87

c

85

c

86

c

72

c

73

c

76

c

64

c

65

c

51

c

54

c

41

c

43

c

45

c

31

c

32

c

34

c

21

c

23

c

27

c

ji

ij

ij

c

c

c







)

(

0

Przykład 48

Matematyczne techniki zarządzania - 227

Programowanie liniowe —

Programowanie liniowe — sieć jest szczególnym przypadkiem za-
gadnienia przydziału:

• zmiennych decyzyjnych jest tyle, ile jest łuków: 1 — iść łukiem,
0 — nie iść łukiem
• warunków ograniczających jest tyle, ile jest węzłów; mamy ich
trzy rodzaje:

 w

ę

zeł pocz

ątk

owy: prawa strona = 1

 w

ę

zeł pośredni: prawa strona = 0

 w

ę

zeł końcowy: prawa strona = —1

•

współczynniki technologiczne:

 wyj

ś

cie z w

ę

zła: +1

 przyj

ś

cie do w

ę

zła: —1

Przykład 48 cd.

C

B

A

X

D O W Ę Z Ł A

7

6

5

4

3

2

1

8

c

87

x

87

c

86

x

86

c

85

x

85

1

7

c

76

x

76

c

73

x

73

c

72

x

72

1

6

c

65

x

65

c

64

x

64

1

5

c

54

x

54

c

51

x

51

1

4

c

45

x

45

c

43

x

43

c

41

x

41

1

3

c

34

x

34

c

32

x

32

c

31

x

31

1

2

c

27

x

27

c

23

x

23

c

21

x

21

1

Z

W

Ę

Z

Ł

A

1

1

1

1

1

1

1

Matematyczne techniki zarządzania - 228

Model decyzyjny

1

1

1

1

1

:

1

.

........

..........

..........

..........

0

1

1

1

1

1

:

7

.

1

1

1

1

:

8

.

min

...

21

31

41

51

72

87

72

73

76

85

86

87

21

21

23

23

27

27

85

85

86

86

87

87











































x

x

x

x

w

x

x

x

x

x

w

x

x

x

w

x

c

x

c

x

c

x

c

x

c

x

c

Z tych danych możne

ułożyć klasyczną tabelkę

progra-mowania liniowego

Model ten można łatwiej

rozwiązać przez wykorzys-

tanie asymetrycznego za-

gadnienia

dualnego

dualnego

Ogólna postać modelu najkrótszej drogi w sieci

Ogólna postać modelu najkrótszej drogi w sieci

)

(

1

lub

0

min

1

0

1

(

)

)

(

)

(

sieci

w

x

x

c

x

x

ij

si

w

ij

eci

ij

sieci

w

sieci

w

ik

kj



















 







Matematyczne techniki zarządzania - 229

Szukanie najdłuższej drogi

(metoda ścieżki krytycznej — CPM)

(metoda ścieżki krytycznej — CPM)

Przykład 49. Zorganizować budowę domu w jak najkrótszym czasie



1

2

3

4

5

5

A

12

B

7

C

0

10

D

7

0

4

E

6

0

7

F

10

G

12

I

8

6

H

9

2

N

10

11

5

J

2

K

2

M

6

L

KTÓRĘDY PROWADZI NAJDŁUŻSZA DROGA W TEJ SIECI I JAKA

KTÓRĘDY PROWADZI NAJDŁUŻSZA DROGA W TEJ SIECI I JAKA

JEST JEJ DŁUGOŚĆ?

JEST JEJ DŁUGOŚĆ?

Ścieżka krytyczna prowadzi przez węzły

1 - 2 - 3 - 4 - 6 -7 - 8 - 10 - 11

1 - 2 - 3 - 4 - 6 -7 - 8 - 10 - 11 i

ma długość wynoszącą

43 dni.

43 dni.

Czynności krytyczne

Czynności krytyczne (bez zapasu czasu):

C, D, I, H, M, L

C, D, I, H, M, L

Czynności niekrytyczne

Czynności niekrytyczne (z zapasem czasu):

A, B, E, F, G, J, N, K

A, B, E, F, G, J, N, K

Matematyczne techniki zarządzania - 230



1

2

3

4

5

5

A

12

B

7

C

0

10

D

7

0

4

E

6

0

7

F

10

G

12

I

8

6

H

9

2

N

10

11

5

J

2

K

2

M

6

L

Istnieje wiele rodzajów zapasu czasu i wiele metod jego obliczania

Wszystkie one bazują na danych: x

i

, x

j

, y

i

, y

j

i

i

i

y

x

X

i

— najwcześniejszy mo-

żliwy moment wystąpienia
danego zdarzenia

y

i

— najpóźniejszy dopusz-

czalny moment wystąpie-
nia danego zdarzenia

0

0

7

7

7

7

17

17

17

17

29

29

25

17

35

35

37

37

43

43

41

19

Zapasy czasu

Zapasy czasu

• dla czynności

G

G: 2 dni

• dla czynności

J

J: 3 dni

• dla czynności

B

B: 13 dni

• dla czynności

E

E: 8 dni

• dla czynności

N

N: 24 dni

• dla czynności

K

K: 24 dni

Wnioski dla kierownictwa

• jak negocjować termin i cenę

• których prac pilnować szczególnie
• jak reagować na zakłócenia

• analiza wrażliwości

Matematyczne techniki zarządzania - 231

Metoda PERT

Metoda PERT

Czasy wszystkich lub niektó-
rych czynności są zmiennymi
losowymi, danymi np. przez

t

1

(1%), t

2

, t

3

(1%)

Jak liczymy?

Dla każdej czynności

)

(

6

1

)

(

)

4

(

6

1

)

(

1

3

3

2

1

t

t

t

t

t

t

t

E













Znajdujemy ścieżkę krytycz-
ną i dla niej liczymy parame-
try czasu realizacji całego
przedsięwzięcia

)

(

)

(

)

(

)

(

.

.

2

2

.

.

t

T

t

E

T

E

kr

sc

kr

sc













PODSUMOWANIE



• całe przedsięwzięcie dzieli się na po-
jedyncze czynności

• ustala się techniczną kolejność czyn-
ności

• ustala się czas realizacji poszczegól-
nych czynności

• buduje się sieć, w której czynności to
łuki, a węzły to momenty czasu (zda-
rzenia, sytuacje)

• sieć musi mieć jeden początek i jeden
koniec

• dwa zdarzenia mogą być połączone
tylko jednym łukiem, trzeba więc
wprowadzać czynności puste

• szuka się najdłuższej drogi w sieci, co
daje optymalne rozwiązanie problemu

• problem najdłuższej drogi można
także sprowadzić do programowania
liniowego (prawe strony: = —1, 0, +1)

Matematyczne techniki zarządzania - 232

Inny przykład problemu sieciowego

Planowanie zatrudnienia w dużym przedsiębiorstwie o zmiennym (sezono-
wym zapotrzeowaniu na siłę roboczą

DANE

okresy: 1, 2, ..., i, j, ..., n

R

i

— zapotrzebowanie na siłę roboczą w i-tym okresie

c

ij

— koszt rekrutacji jednego pracownika w i-tym okresie i utrzymania go w

pracy do okresu j-tego

ZMIENNA DECYZYJNA x

ij

— liczba pracowników przyjęta do pracy w i-tym okresie i

zwolniona z niej w okresie j-tym

FUNKCJA CELU

min



 

ij

ij

x

c

WARUNKI OGRANICZAJĄCE

— bilanse pracowników zatrudnionych w i-tym okresie

PROGRAMOWANIE DYNAMICZNE

PROGRAMOWANIE DYNAMICZNE

Polega ona na podziale dużego problemu optymalizacyjnego na szereg
mniejszych problemów rozwiązywanych po kolei (etapami) oddzielnie

Zasada Bellmana

Zasada Bellmana

.........

..

..........

.

1

2

.

1

.

0

2

1

i

x

dec

i

x

dec

x

dec

S

S

S

S

S

i



 





 





 





ETAP 1

ETAP 2

ETAP i

S

i-1

— stan układu

na początku etapu

S

i

— stan układu

na końcu etapu

Matematyczne techniki zarządzania - 233

Zasada Bellmana głosi, że decyzja podejmowana w i-tym etapie
jest wyłącznie funkcją stanu układu (systemu) na początku tego
etapu i nie jest zależna od sposobu dojścia do tego stanu

)

,

(

)

(

1

1

i

i

i

i

i

i

x

S

f

S

S

f

x









Funkcja celu

NIE ROZPATRUJEMY NIGDY

ETAPÓW WCZEŚNIEJSZYCH

Zastosowania programowania dynamicznego

Zastosowania programowania dynamicznego



rozwiązywanie

sieci

 sterowanie zapasami

 zagadnienia wieloetapowe

 alokacja

kapitału

 problemy techniczne

 zagadnienie plecaka

 programowanie nieliniowe

 wymiana

urządzeń



W trakcie rozwiązywania zadań stosuje się indukcję odwrotną







1

n

ETAP PIERWSZY

ETAP OSTATNI

ROZWIĄZANIE

OGÓLNE

ROZWIĄZANIES

ZCZEGÓŁOWE

Matematyczne techniki zarządzania - 234

Szukanie najkrótszej drogi

(zagadnienie dyliżansu)

(zagadnienie dyliżansu)

1

2

3

4

5

6

7

8



C

ij

km (mile)

godziny

złotówki

Przykład 50. Znajdź metodą programowania dynamicznego najkrótszą
drogę z węzła 8 do węzła 1.

1

4

4

6

1

1

2

2

8

6

3

6

1

4

1

start

meta

Funkcja celu (stan systemu)

f

i

= min



0

1



f

1

)

0

1

min(

)

min(

1

21

2











f

c

f

2

)

1

1

;

0

4

min(

)

;

min(

2

32

1

31

3















f

c

f

c

f

3

)

2

1

;

0

4

min(

)

;

min(

3

43

1

41

4















f

c

f

c

f

5

)

3

2

;

0

6

min(

)

;

min(

4

54

1

51

5















f

c

f

c

f

6

)

5

2

;

3

3

min(

)

;

min(

5

65

4

64

6















f

c

f

c

f

7

)

6

1

;

2

6

;

1

8

min(

)

;

;

min(

6

76

3

73

2

72

7





















f

c

f

c

f

c

f

8

)

7

1

;

6

4

;

5

6

min(

)

;

;

min(

7

87

6

86

5

85

8





















f

c

f

c

f

c

f

Wracamy „żółtymi śladami”

najkrótsza droga: 8 - 7 - 6 - 4 - 3 - 2 - 1

najkrótsza droga: 8 - 7 - 6 - 4 - 3 - 2 - 1

jej długość wynosi 8 mil

jej długość wynosi 8 mil

Matematyczne techniki zarządzania - 235

Rozwiązanie matematyczne:

8

)

(

min

1

8

21

32

43

64

76

87

















f

X

Z

x

x

x

x

x

x

INTERPRETACJA

INTERPRETACJA

f

i

1.

1. Minimalna wartość funkcji celu po i-tym etapie (badania operacyjne)

2.

2. Stan systemu po i-tym etapie (programowanie dynamiczne)

3.

3. Najkrótsza droga z i-tego węzła do węzła końcowego „1”

Zadanie zostało rozwiązane przy użyciu modelu

j

i

f

c

f

j

ij

i







)

min(

RÓWNANIE

RÓWNANIE

REKURENCYJNE

REKURENCYJNE

Wada programowania dynamicznego: nie ma uniwersalnego modelu i do
każdego problemu trzeba budować oddzielny model

Sterowanie zapasami wyrobów gotowych





Przykład 51.

Zoptymalizować wielkość zapasów wyrobów gotowych w

fabryce Niezawodny dostawca (wg książki Wagnera)

Dane:

wielkość produkcji x

x

t

t

: od 0 do 5 sztuk

pojemność magazynu i

i

t

t

: 4 sztuki

popyt miesięczny stały d

d

t

t

: 3 sztuki

Matematyczne techniki zarządzania - 236

Kryterium decyzyjne:

Kryterium decyzyjne: f

i

= min(koszty produkcji + koszty magazynowania)

Koszty produkcji:

Koszty produkcji:

0

)

(

0

2

13

)

(



 













t

t

t

t

t

x

c

x

x

ax

b

x

c

Koszty magazynowania:

Koszty magazynowania:

t

t

t

i

ai

i

c

1

)

(





Czas analizy:

Czas analizy:

6 miesięcy — od I do VI

numerujemy miesiące wstecz: lipiec = 0, czerwiec =1 itd.

LIPIEC

LIPIEC

n = 0

t = 0

i

0

= 0

0

0



f

na koniec czerwca magazyn ma być pusty

CZERWIEC

CZERWIEC

n = 1 nie ma kosztów magazynowania, ale są 4 możliwości, jeśli chodzi
t = 1

o sposób pokrycia czerwcowego zapotrzebowania (różny udział

produkcji czerwcowej i zapasów z maja); stan zapasów na
początku czerwca: 0, 1, 2, 3

x

1

to decyzja wyznaczająca wielkość produkcji w

czerwcu (x

1

+i

1

=3), natomiast f

1

to skutek

finansowy decyzji x

1

, zależny także od decyzji

podjętych we wcześniejszych miesiącach, czyli od
stanu na początku etapu 1-szego

Matematyczne techniki zarządzania - 237

MAJ

MAJ

n = 2

t = 2

Teraz mogą wystąpić koszty magazynowania, posłużymy się
więc równaniem rekurencyjnym

)

.

.

.

.

(

min

1









t

x

t

f

mag

k

prod

k

f

skutki decyzji bieżącej stan na początku etapu t

i

2

x

2

0

1

2

3

4

5

x

2

(i

2

)

f

2

(i

2

)

0







19+0+19

21+1+17

23+2+15

3

38

1





17+0+19

19+1+17

21+2+15

23+3+0

5

26

2



15+0+19

17+1+17

19+2+15

21+3+0



4

24

3

0+0+19

15+1+17

17+2+15

19+3+0





0

19

4

0+1+17

15+2+15

17+3+0







0

18

stan zapasów na
początku maja

19=koszty produkcji; 0=koszty magazynowania; 19 z tabelki dla czerwca

Szukamy dla każdego wiersza takiej decyzji

x

2

,

która da najmniejszą war-

tość

f

2

kosztów działalności przedsiębiorstwa w maju i czerwcu łącznie

KWIECIEŃ

KWIECIEŃ

n = 3

MARZEC

MARZEC

n = 4

LUTY

LUTY

n = 5

STYCZEŃ

STYCZEŃ

n = 6

Po zakończeniu wszystkich obliczeń otrzy-

mamy następujące rozwiązanie ogólne

(model) minimalizacji kosztów działalności

przedsiębiorstwa przez wybór optymalnej

wielkości produkcji

Matematyczne techniki zarządzania - 238

TEN MODEL

TEŻ JEST

SIECIĄ

n=6

n=5

n=4

0

6



i

1

6



i

2

6



i

3

6



x

0

5



i

4

6



x

1

5



i

2

6



i

5

6



x

2

6



x

3

6



x

4

6



x

itd...

3

5



x

0

4



i

1

4



i

1

5



x

2

5



x

itd...

ROZWIĄZANIE

OGÓLNE

ROZWIĄZANIES

ZCZEGÓŁOWE

Znajdziemy je dla i

6

= 3, tj.

dla założenia, że stan zapa-
sów na początku stycznia
wynosi 3 sztuki

3

6



i

Szukamy najkrótszej drogi w tej
sieci od zaznaczonego węzła do
węzła końcowego, tj. takiej
strategii produkcji wyrobów,
która odpowiada minimalnym
kosztom działalności przedsię-
biorstwa

Matematyczne techniki zarządzania - 239

3

6



i

79

n=6

STYCZEŃ

DECYZJA Z MODELU

0

0

6





k

x

0

5



i

79

n=5

LUTY

25

2

23

5

5









k

x

54

n=4

MARZEC

2

4



i

27

4

23

5

4









k

x

4

3



i

27

n=3

KWIECIEŃ

1

0

3





k

x

26

n=2

MAJ

1

2



i

26

3

23

5

2









k

x

3

1



i

0

n=1

CZERWIEC

0

0

1





k

x

0

n=0

LIPIEC

0

0



i

OPTYMALNA DECYZJA

OPTYMALNA DECYZJA

(optymalny plan produkcji)

(optymalny plan produkcji)

dla założenia i

dla założenia i

6

6

= 3

= 3

X = [0 5 5 0 5 0]

X = [0 5 5 0 5 0]

Podobnie można znaleźć optymalne rozwiązanie dla innych założeń
odnośnie do zapasu wyrobów na początek stycznia

Wzór rekurencyjny

Wzór rekurencyjny stosowany do tego zadania





6

,....,

3

,

2

7

,

5

min

3

)]

3

(

)

3

(

1

)

(

[

min

)

(

1



























t

dla

i

x

i

x

i

f

x

i

x

C

i

f

t

x

t

skutki decyzji bieżącej stan na początku etapu t

Koncentracja
produkcji!

Dlaczego?

Wynika to z
efektu skali!

Matematyczne techniki zarządzania - 240

ANALIZA WRAŻLIWOŚCI

• horyzont planowania

• zapas początkowy

• zdolność produkcyjna



• pojemność magazynu

• popyt

Optymalny rozdział nakładów inwestycyjnych



Przypomnienie: należy rozdzielić kwotę K pomiędzy n obiektów o efek-
tywności q

i

(x

i

), gdzie x

i

— kwota przydzielona i-temu obiektowi, tak aby

łączny efekt z kwoty K był możliwie jak największy

K

1

)

(

1

1

x

q

2

3

1

x

3

2

1

x

x

x

K







2

x

]

[

2

1

x

x

K





3

x

)

(

3

3

x

q

3

f

)

(

2

2

x

q

2

f

1

f

Rozwiązanie
ogólne

Funkcje
efektywności
poszczególnych
obiektów

Równanie
rekurencyjne
(funkcje celu)