2013-10-15

1

Badania operacyjne

Badania operacyjne

w logistyce

w logistyce

[e-mail]

„Badania operacyjne s

ą

sztuk

ą

dawania złych odpowiedzi na te praktyczne

pytania, na które inne metody daj

ą

odpowiedzi jeszcze gorsze”.

T. Sayty

WYKŁAD ORGANIZACYJNO

WYKŁAD ORGANIZACYJNO--

WPROWADZAJĄCY

WPROWADZAJĄCY

Zakres tematyczny wykładów

Bibliografia

Warunki zaliczenia

ID,2013/2014

2013-10-15

2

Cel zajęć

Cel zajęć

1.

Nabycie umiej

ę

tno

ś

ci formułowania zada

ń

decyzyjnych i ich zapisów w postaci modeli
matematycznych.

2.

Zrozumienie znaczenia rozwi

ą

za

ń

optymalnych

w zarz

ą

dzaniu logistycznym.

ID,2013/2014

Główne bloki tematyczne

Główne bloki tematyczne

Wykład 1:

Wprowadzenie

Liniowe modele decyzyjne i ich zastosowania

Metoda graficzna rozwi

ą

zywania ZPL

Wykład 2:

Zadanie dualne i jego własno

ś

ci

Algorytm simpleks

Wykład 3:

Zagadnienia transportowe

Problemy przydziału

ID,2013/2014

2013-10-15

3

Główne bloki tematyczne (

Główne bloki tematyczne (cd

cd.)

.)

Wykład 4:

Metody sieciowego planowania przedsi

ę

wzi

ęć

(metoda CPM, metoda CPM-COST)

Wykład 5:

Programowanie sieciowe (minimalne drzewo
rozpinaj

ą

ce, najkrótsza droga w sieci,

maksymalny przepływ w sieci)

ID,2013/2014

Źródła wiedzy

Źródła wiedzy

1.

Sikora W. (red.), Badania operacyjne. PWE, Warszawa 2008
(rozdziały 1 i 2 bez 2.5).

2.

Guzik B. (red.), Ekonometria i badania operacyjne. Zagadnienia
podstawowe. Skrypt nr 115 (ew. 81 lub 50), AE, Pozna

ń

2002

(rozdziały 1-6, 9-13).

3.

Abtowa J., Piasecki K., Ró

ż

a

ń

ski T.,

Ś

witalski Z.: Matematyka

wspomagaj

ą

ca zarz

ą

dzanie. AE, Pozna

ń

2002 (rozdział 7.4).

4.

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

5.

J

ę

drzejczyk Z., Kukuła K., Skrzypek J., Walkosz A.: Badania

operacyjne w przykładach i zadaniach. Wydawnictwo Naukowe
PWN, Warszawa.

6.

Szapiro T. (red.): Decyzje mened

ż

erskie z Excelem. PWE, Warszawa

2000.

7.

Krawczyk S.: Badania operacyjne dla mened

ż

erów. Wydawnictwo AE

im. Oskara Lanego we Wrocławiu 1996.

ID,2013/2014

2013-10-15

4

Źródła wiedzy (

Źródła wiedzy (cd

cd.)

.)

8.

Siwak T.: Badania operacyjne dla in

ż

ynierów zarz

ą

dzania.

Wydawnictwa AGH, Kraków 1998.

9.

Trzaskalik T.: Badania operacyjne z komputerem. Łód

ź

1997.

10. Ostatni A.: Programowanie i modelowanie matematyczne w EXCELU .

Wy

ż

sza Szkoła Finansów i Zarz

ą

dzania, Białystok 2004.

11. Zajchowska- Lipiec M. (red.): Wspomaganie procesów decyzyjnych.

T.III – Wydawnictwo C.H. Beck Warszawa 2003.

12. Siudak M.: Badania operacyjne. Oficyna Wydawnicza Politechniki

Warszawskiej, Warszawa 1998

13. Glinka M.: Elementy bada

ń

operacyjnych w transporcie. Wydawnictwo

Politechniki Radomskiej, Radom 2009.

14. Witkowska D.: Metody wspomagaj

ą

ce podejmowanie decyzji w

zarz

ą

dzaniu. Podstawy bada

ń

operacyjnych. Seria Wydawnictw

Dydaktycznych Wydziału Organizacji i Zarz

ą

dzania Politechniki

Łódzkiej. Łód

ź

2000.

15. …

ID,2013/2014

Zasady współpracy:

Zasady współpracy:

1.

Zaj

ę

cia podzielone s

ą

na 2 bloki:

wykłady (15h) - obecno

ść

nie jest obowi

ą

zkowa

ć

wiczenia (15h) - obecno

ść

jest obowi

ą

zkowa

2.

Podstaw

ą

zaliczenia jest:

uzyskanie pozytywnej oceny z kolokwium, które b

ę

dzie

obejmowało materiał z

ć

wicze

ń

i wykładów do dnia

kolokwium (1 termin egzaminu – 25.01.2014r.)

ID,2013/2014

Istnieje mo

ż

liwo

ść

podwy

ż

szenia oceny (maksymalnie o 1 stopie

ń

w gór

ę

) za

Istnieje mo

ż

liwo

ść

podwy

ż

szenia oceny (maksymalnie o 1 stopie

ń

w gór

ę

) za

dodatkowe punkty za aktywno

ść

na zaj

ę

ciach

dodatkowe punkty za aktywno

ść

na zaj

ę

ciach

2013-10-15

5

Wykład 1

Wykład 1::

Badania operacyjne w rozwi

ą

zywaniu

Badania operacyjne w rozwi

ą

zywaniu

problemów decyzyjnych

problemów decyzyjnych

Zagadnienia programowania liniowego (PL)

Zagadnienia programowania liniowego (PL)

(modele, metoda graficzna)

(modele, metoda graficzna)

ID,2013/2014

Badania operacyjne – zbiór modeli i metod
wspomagania decyzji kierowniczych na wszystkich
poziomach zarz

ą

dzania.

Obszar wiedzy:

EM – ekonomia matematyczna

SE – statystyka ekonomiczna

SM – statystyka matematyczna

Badania operacyjne

Badania operacyjne –

– istota zagadnienia

istota zagadnienia

ID,2013/2014

2013-10-15

6

Ukierunkowanie na podejmowanie decyzji.

Mo

ż

liwo

ść

oceny działania (decyzji) na

podstawie okre

ś

lonych kryteriów.

Konieczno

ść

budowy modelu (na ogół

matematycznego) sytuacji decyzyjnej.

Mo

ż

liwo

ść

realizacji oblicze

ń

na

komputerze, np. SOLVER (narz

ę

dzie

Excel’a w MS Office).

Badania operacyjne

Badania operacyjne –

– cechy

cechy

ID,2013/2014

„Logistyka to proces planowania, realizowania i kontrolowania
sprawnego i efektywnego ekonomicznie przepływu surowców,
materiałów do produkcji, wyrobów gotowych i usług oraz
odpowiedniej informacji z punktu pochodzenia do punktu
konsumpcji w celu zaspokojenia wymaga

ń

klienta”.

[Council of Logistics Management (CLM)]

„Logistyka jest poj

ę

ciem obejmuj

ą

cym organizacj

ę

, planowanie,

kontrol

ę

i realizacj

ę

przepływów towarowych od ich wytworzenia i

nabycia poprzez produkcj

ę

i dystrybucj

ę

, a

ż

do finalnego odbiorcy,

której celem jest zaspokojenie wymaga

ń

rynku, przy minimalnych

kosztach i przy minimalnym zaanga

ż

owaniu kapitału”.

[European Logistics Association]

„Logistyka to zarz

ą

dzanie strategiczne całym ła

ń

cuchem dostaw”.

[Instytut Logistyki]

…

Przegl

ą

d definicji logistyki

ID,2013/2014

2013-10-15

7

Logistyka

Logistyka –

– jako dziedzina

jako dziedzina

zastosowa

ń

bada

ń

operacyjnych

zastosowa

ń

bada

ń

operacyjnych

Na gruncie bada

ń

operacyjnych opracowano wiele

skutecznych algorytmów rozwi

ą

zywania takich

problemów jak np.:

• zaprojektowanie harmonogramu przedsi

ę

wzi

ę

cia,

• optymalny wybór asortymentu produkcji,

• optymalny przydział zada

ń

produkcyjnych,

• optymalny dobór tras przewozu towarów.

ID,2013/2014

Badania operacyjne

Badania operacyjne –

– metodyka

metodyka

START

Sformułowanie problemu, który b

ę

dzie rozwi

ą

zywany

Zebranie i opracowanie danych potrzebnych do modelowania

Przyj

ę

cie zało

ż

e

ń

upraszczaj

ą

cych

Tworzenie modelu matematycznego

Poszukiwanie metod rozwi

ą

zywania modelu

Uzyskanie rozwi

ą

zania modelu

Weryfikacja i ocena modelu oraz rozwi

ą

zania

a

b

c

ID,2013/2014

2013-10-15

8

Badania operacyjne

Badania operacyjne –

– metodyka (

metodyka (cd

cd.)

.)

a

Czy model i rozwi

ą

zanie

s

ą

poprawne i przydatne?

c

N

Wdro

ż

enie rozwi

ą

zania

Obserwacja zmian zachodz

ą

cych pod wpływem

wprowadzonego rozwi

ą

zania

Czy problem został

rozwi

ą

zany?

b

T

N

T

KONIEC

Ź

ródło: Glinka M.: Elementy bada

ń

operacyjnych w

transporcie. Wydawnictwo Politechniki Radomskiej ,

Radom 2009.

ID,2013/2014

Etapy rozwi

ą

zywania problemów

Etapy rozwi

ą

zywania problemów

metodami bada

ń

operacyjnych

metodami bada

ń

operacyjnych

I.

Rozpoznanie sytuacji decyzyjnej i
wynikaj

ą

cego z niej problemu decyzyjnego.

II.

Budowa modelu matematycznego problemu.

III.

Rozwi

ą

zanie modelu.

IV.

Ocena poprawno

ś

ci i realno

ś

ci uzyskanych

rozwi

ą

za

ń

oraz ewentualna weryfikacja

modelu decyzyjnego.

V.

Przedstawienie rozwi

ą

za

ń

decydentowi i

ostateczne przygotowanie decyzji.

ID,2013/2014

2013-10-15

9

Model

Model –

– narz

ę

dzie bada

ń

operacyjnych

narz

ę

dzie bada

ń

operacyjnych

Model decyzyjny – konstrukcja formalna,
odwzorowuj

ą

ca istotne cechy rzeczywistej

sytuacji decyzyjnej.

Model matematyczny (symboliczny) – wzór
matematyczny (np. równanie) za pomoc

ą

którego odzwierciedlamy procesy decyzyjne i
społeczno-gospodarcze zachodz

ą

ce w

ż

yciu

gospodarczym.

ID,2013/2014

Elementy modelu matematycznego

Elementy modelu matematycznego

PARAMETRY (WSPÓŁCZYNNIKI) ZADANIA – to
wielko

ś

ci znane, ustalone tzn. niezmienne podczas

oblicze

ń

liczby np.: parametry techniczne maszyn,

koszty jednostkowe itp.

ZMIENNE DECYZYJNE - s

ą

to niewiadome, których

warto

ś

ci s

ą

wyznaczane w trakcie rozwi

ą

zywania

modelu.

WARUNKI OGRANICZAJ

Ą

CE - układy równa

ń

i/lub

nierówno

ś

ci, zawieraj

ą

ce zmienne decyzyjne i parametry

zadania, wyra

ż

aj

ą

ce ograniczenia zasobów, jakimi

dysponujemy, b

ą

d

ź

te

ż

wymagania, które musz

ą

by

ć

spełnione.

ID,2013/2014

2013-10-15

10

Elementy modelu matematycznego

Elementy modelu matematycznego

WARUNKI BRZEGOWE – to warunki nakładane na
zmienne decyzyjne, które s

ą

oczywiste. Wyró

ż

niamy:

Warunki nieujemno

ś

ci zmiennych decyzyjnych

powoduj

ą

,

ż

e zmienne decyzyjne przyjmuj

ą

w

rozwi

ą

zaniu warto

ś

ci ze zbioru liczb R

+

ᴗ

{0},

Warunki całkowitoliczbowo

ś

ci zmiennych decyzyjnych

powoduj

ą

,

ż

e zmienne decyzyjne nale

żą

ce do tej grupy

musz

ą

przyjmowa

ć

tylko warto

ś

ci ze zbioru liczb C

+

ᴗ

{0},

Warunki binarno

ś

ci (zero-jedynowo

ś

ci) zmiennych

decyzyjnych powoduj

ą

,

ż

e zmienne decyzyjne musz

ą

przyjmowa

ć

tylko jedn

ą

z dwóch warto

ś

ci 0 lub 1.

ID,2013/2014

FUNKCJA CELU (FUNKCJA KRYTERIUM) –
zapisane za pomoc

ą

zale

ż

no

ś

ci matematycznych, z

wykorzystaniem zmiennych decyzyjnych i parametrów
zadania, kryterium optymalizacji.

Warto

ść

funkcji celu jest miernikiem efektywno

ś

ci

proponowanego rozwi

ą

zania

.

Funkcja celu mo

ż

e by

ć

maksymalizowana lub

minimalizowana.

Funkcja celu mo

ż

e by

ć

liniowa lub nieliniowa, jedno-

lub wielokryterialna.

Elementy modelu matematycznego

Elementy modelu matematycznego

Rozwi

ą

zanie modelu polega na ustaleniu warto

ś

ci

Rozwi

ą

zanie modelu polega na ustaleniu warto

ś

ci

optymalnej funkcji celu w zbiorze decyzji dopuszczalnych.

optymalnej funkcji celu w zbiorze decyzji dopuszczalnych.

ID,2013/2014

2013-10-15

11

Ogólny zapis problemu programowania

Ogólny zapis problemu programowania

matematycznego (PM)

matematycznego (PM)

ID,2013/2014

Ogólny zapis problemu PM (

Ogólny zapis problemu PM (cd

cd.)

.)

ID,2013/2014

2013-10-15

12

Ogólny zapis problemu PM (

Ogólny zapis problemu PM (cd

cd.)

.)

ID,2013/2014

Klasyfikacja modeli decyzyjnych

Klasyfikacja modeli decyzyjnych

–

–

ze wzgl

ę

du na charakter parametrów wyst

ę

puj

ą

cych w

ze wzgl

ę

du na charakter parametrów wyst

ę

puj

ą

cych w

modelu

modelu

Model deterministyczny

Model deterministyczny – wszystkie parametry wyst

ę

puj

ą

ce

w modelu maj

ą

warto

ś

ci stałe i znane.

Model statyczny jedno- lub wieloetapowy, wykorzystuj

ą

cy ide

ę

programowania dynamicznego.

Model jedno- lub wielokryterialny.

Model w warunkach ryzyka

Model w warunkach ryzyka – przynajmniej jeden parametr
w modelu jest zmienn

ą

losow

ą

o znanym rozkładzie

prawdopodobie

ń

stwa.

Kryterium optymalizacji - warto

ść

oczekiwana zmiennej losowej

Modele te opisuj

ą

zagadnienia zapasów, magazynowania, a tak

ż

e

problemy masowej obsługi.

Model w warunkach niepewno

ś

ci

Model w warunkach niepewno

ś

ci – przynajmniej jeden

parametr w modelu jest zmienn

ą

losow

ą

o nieznanym

rozkładzie prawdopodobie

ń

stwa.

ID,2013/2014

2013-10-15

13

Klasyfikacja modeli decyzyjnych

Klasyfikacja modeli decyzyjnych

–

–

ze wzgl

ę

du na typ relacji zachodz

ą

cych mi

ę

dzy wielko

ś

ciami,

ze wzgl

ę

du na typ relacji zachodz

ą

cych mi

ę

dzy wielko

ś

ciami,

na które decydent ma wpływ (zmiennymi)

na które decydent ma wpływ (zmiennymi)

Programowanie liniowe,

Programowanie liniowe w liczbach całkowitych,

Programowanie liniowe binarne,

Programowanie nieliniowe,

Programowanie nieliniowe w liczbach całkowitych,

Programowanie nieliniowe binarne,

Programowanie stochastyczne,

Programowanie dynamiczne,

Programowanie mieszane,

Programowanie sieciowe.

ID,2013/2014

Liniowe modele decyzyjne

Liniowe modele decyzyjne

(zadania programowania liniowego

(zadania programowania liniowego

--ZPL)

ZPL)

ID,2013/2014

2013-10-15

14

Model programowania liniowego

Model programowania liniowego

1.

Funkcja celu (1) jest to funkcja liniowa,

2.

Równania i nierówno

ś

ci generuj

ą

ce zbiór

decyzji dopuszczalnych X s

ą

formami

liniowymi

ID,2013/2014

Standardowa postać ZPL

Standardowa postać ZPL

a

11

x

1

+ a

12

x

2

+ ... + a

1n

x

n

≤≤

(≥) b

1

a

21

x

1

+ a

22

x

2

+ ... + a

2n

x

n

≤≤

(≥) b

2

…………………………………………
a

m1

x

1

+ a

m2

x

2

+ ... + a

mn

x

n

≤≤

(≥) b

m

x

k

≥

0 dla k = 1,2,..., n

F(x

1

,…,x

n

) = c

1

x

1

+ c

2

x

2

+ ... + c

n

x

n

→

max (min)

Funkcja

c

1

x

1

+ c

2

x

2

+ ... + c

n

x

n

- funkcja celu

Liczby

a

ij

, i = 1, ... , m, j = 1, ... , n

współczynniki techniczno-ekonomiczne

Liczby b

i

, i = 1, ... , m

elementy wektora ograniczeń

Liczby c

i

, i = 1, ... , n to

współczynniki funkcji celu

Zmienne

X

k

, k = 1, ... , n

zmienne decyzyjne

ID,2013/2014

b

i

≥0 dla i=1,2,...,m

2013-10-15

15

Ogólna postać ZPL

Ogólna postać ZPL

∑

=

→

=

n

j

j

j

n

x

c

x

x

F

1

1

max(min)

)

,...

(

∑

≥

≤

i

j

ij

b

x

a

)

(

n

j

m

i

,...,

2

,

1

,...

2

,

1

=

=

0

≥

j

x

Kanoniczna postać ZPL

Kanoniczna postać ZPL

a

11

x

1

+ a

12

x

2

+ ... + a

1n

x

n

+x

n+1

=b

1

a

21

x

1

+ a

22

x

2

+ ... + a

2n

x

n

+x

n+2

= b

2

…………………………………………
a

m1

x

1

+ a

k2

x

2

+ ... + a

mn

x

n

+x

n+m

= b

m

x

k

≥

0 dla k = 1,2,..., n

F(x

1

,…,x

n

) = c

1

x

1

+ c

2

x

2

+ ... + c

n+m

x

n+m

→

max

ID,2013/2014

b

i

≥0 dla i=1,2,...,m

X

n+1

,…,x

n+m

≥0

2013-10-15

16

Macierzowa postać ZPL

Macierzowa postać ZPL

























=

mn

m

m

n

n

a

a

a

a

a

a

a

a

a

A

...

...

...

2

1

2

22

21

1

12

11

























=

n

x

x

x

x

...

2

1

























=

m

b

b

b

b

...

2

1

[

]

n

c

c

c

c

...

,

,

2

1

=

0

)

(

max(min)

≥

≥

≤

→

x

b

Ax

cx

- wektor wierszowy współczynników funkcji celu

- macierz o rozmiarze mn składaj

ą

ca si

ę

z

parametrów wyst

ę

puj

ą

cych przy odpowiednich

zmiennych po lewej stronie warunków ograniczaj

ą

cych

- wektor kolumnowy
zmiennych decyzyjnych

- wektor kolumnowy wyrazów
wolnych (prawych stron
warunków ograniczaj

ą

cych)

ID,2013/2014

Sformułowanie problemu

Sformułowanie problemu

Przedsi

ę

biorstwo posiada m ró

ż

nych

ś

rodków produkcji S

1

,S

2

,…,S

m

odpowiednio w ilo

ś

ciach: b

1

,b

2

,…,b

m

. W ramach posiadanych zasobów firma

jest w stanie produkowa

ć

n ró

ż

nych wyrobów. Na wytworzenie jednostki wyrobu

j-tego rodzaju (j=1,2,…,n) potrzeba u

ż

y

ć

a

ij

jednostek i-tego czynnika produkcji

(i=1,2,…,m), np. wyra

ż

onych za pomoc

ą

przepracowanych roboczogodzin,

czasu maszyn potrzebnego do wytworzenia jednostki produktu lub ilo

ś

ci

zu

ż

ytych surowców, stanowi

ą

cych normatywy zu

ż

ycia

ś

rodków produkcji.

Wiadomo te

ż

,

ż

e zyski jednostkowe osi

ą

gane przez firm

ę

na ka

ż

dym produkcie

wynosz

ą

odpowiednio c

1

,c

2

,…,c

n

. Nale

ż

y zbudowa

ć

taki plan produkcji, który

pozwoli na maksymalizacj

ę

zysków.

Przykłady modeli PL

Przykłady modeli PL
--

wybór asortymentu produkcji (1)

wybór asortymentu produkcji (1)

ID,2013/2014

2013-10-15

17

Budowa modelu

Budowa modelu

Zmiennymi decyzyjnymi w tym zadaniu s

ą

ilo

ś

ci produkowanych

wyrobów z ka

ż

dego rodzaju asortymentu – x

j

. Je

ż

eli wyprodukujemy x

j

(j=1,2,…,n) produktu j-tego, to zu

ż

yjemy do produkcji a

ij

x

j

ś

rodka S

i

. Rozpatruj

ą

c

pełen asortyment wyrobów wykorzystamy czynnika produkcji S

i

(i=1,2,…,m). Wiadomo jest,

ż

e zasoby ka

ż

dego

ś

rodka s

ą

ograniczone, dlatego

wielko

ść

i struktura produkcji nie mo

ż

e przekracza

ć

posiadanych zasobów, czyli

musi spełnia

ć

zbiór warunków ograniczaj

ą

cych danych w postaci:

(i=1,2,…,m).

Wiadomo przy tym,

ż

e wielko

ść

produkcji nie mo

ż

e by

ć

ujemna, czyli

musz

ą

by

ć

spełnione warunki brzegowe dane w postaci:

Przykłady modeli PL

Przykłady modeli PL
--

wybór asortymentu produkcji (2)

wybór asortymentu produkcji (2)

∑

=

n

j

j

ij

x

a

1

∑

=

≤

n

j

i

j

ij

b

x

a

1

0

≥

j

x

ID,2013/2014

Budowa modelu

Budowa modelu

W przypadku, kiedy produkowany przez firm

ę

asortyment mierzony jest w

jednostkach całkowitych np. sztukach, liczbie zestawów czy kompletów, nale

ż

y

doł

ą

czy

ć

dodatkowe warunki zapewniaj

ą

ce uzyskanie rozwi

ą

zania w liczbach

całkowitych, a mianowicie:

Zysk, jaki osi

ą

gnie firma przy strukturze produkcji zapisanej w wektorze

wynosi:

Przykłady modeli PL

Przykłady modeli PL
--

wybór asortymentu produkcji (3)

wybór asortymentu produkcji (3)

C

x

j

∈

]

[

j

x

x

=

∑

=

n

j

j

j

x

c

1

Zadanie polega na wyznaczeniu takich warto

ś

ci zmiennych decyzyjnych x

Zadanie polega na wyznaczeniu takich warto

ś

ci zmiennych decyzyjnych x

jj

spełniaj

ą

cych warunki ograniczaj

ą

ce i brzegowe, które zapewniaj

ą

spełniaj

ą

cych warunki ograniczaj

ą

ce i brzegowe, które zapewniaj

ą

maksimum funkcji celu, b

ę

d

ą

cej kryterium wyboru decyzji.

maksimum funkcji celu, b

ę

d

ą

cej kryterium wyboru decyzji.

ID,2013/2014

2013-10-15

18

Przykłady modeli PL

Przykłady modeli PL
--

wyznaczanie optymalnej diety (1)

wyznaczanie optymalnej diety (1)

Sformułowanie problemu

Sformułowanie problemu

Danych jest n produktów, które zawieraj

ą

m składników S

1

,S

2

,…,S

m

odpowiednio w ilo

ś

ciach: b

1

,b

2

,…,b

m

. Z analiz wynika,

ż

e w jednostce produktu

j-tego (j=1,2,…,n) znajduje si

ę

a

ij

składnika i-tego (i=1,2,…,m). Przyjmijmy,

ż

e

składniki od

ż

ywcze zostały tak uporz

ą

dkowane,

ż

e podanie pierwszych p<m

składników (tzn. S

1

,S

2

,…,S

p

) w nadmiernych ilo

ś

ciach jest szkodliwe i ich

zawarto

ść

w diecie nie powinna przekracza

ć

odpowiednio d

1

,d

2

,…,d

p

jednostek.

Pozostałe składniki (których jest (m-p) i zostały oznaczone jako:

S

p+1

,S

p+2

,…,S

m

) musz

ą

zosta

ć

dostarczone przynajmniej w dawkach

d

p+1

,d

p+2

,…,d

m

. Oznaczaj

ą

c przez c

1

,c

2

,…,c

n

ceny poszczególnych produktów

nale

ż

y wyznaczy

ć

optymaln

ą

diet

ę

, która spełni wymogi racjonalnego

ż

ywienia i

jednocze

ś

nie jej koszt b

ę

dzie najmniejszy.

ID,2013/2014

Budowa modelu

Budowa modelu

Zmiennymi decyzyjnymi x

j

w tym zadaniu s

ą

ilo

ś

ci produktu j-tego

rodzaju (np. w kilogramach). Dla wszystkich składników musi by

ć

spełniony

warunek: (i=1,2,…,m) oznaczaj

ą

cy,

ż

e nie mo

ż

emy przekroczy

ć

zadanej wielko

ś

ci poszczególnych składników od

ż

ywczych. Ponadto dla p

pierwszych składników nie mo

ż

e zosta

ć

przekroczona ich dawka, czyli:

(i=1,2,…,p) a dla pozostałych wymagane s

ą

minimalne ich ilo

ś

ci, co

mo

ż

na zapisa

ć

jako: (i=p+1,p+2,…,m).

Zmienne decyzyjne nie mog

ą

przyjmowa

ć

warto

ś

ci ujemnych:

Nale

ż

y wyznaczy

ć

takie warto

ś

ci zmiennych decyzyjnych x

j

, aby

spełnione zostały warunki ograniczaj

ą

ce i jednocze

ś

nie koszty zakupu:

były najmniejsze.

Przykłady modeli PL

Przykłady modeli PL
--

wyznaczanie optymalnej diety (2)

wyznaczanie optymalnej diety (2)

∑

=

≤

n

j

i

j

ij

b

x

a

1

∑

=

≤

n

j

i

j

ij

d

x

a

1

∑

=

≥

n

j

i

j

ij

d

x

a

1

0

≥

j

x

∑

=

n

j

j

j

x

c

1

ID,2013/2014

2013-10-15

19

Przykłady modeli PL

Przykłady modeli PL
--

zagadnienie optymalnego wykroju (1)

zagadnienie optymalnego wykroju (1)

Sformułowanie problemu

Sformułowanie problemu

Załó

ż

my,

ż

e do produkcji potrzebnych jest m ró

ż

nych detali wykrawanych z

jednolitego surowca, który dostarczany jest w postaci np. arkuszy blachy.

Zgodnie z otrzymanymi przez firm

ę

zamówieniami ustalono,

ż

e nale

ż

y wyci

ąć

b

i

detali i-tego typu (i=1,2,…,m). Przy ci

ę

ciu arkusza blachy j-tym sposobem

otrzymuje si

ę

a

ij

detali i-tego rodzaju i powstaje przy tym odpad, którego

wielko

ść

oszacowano na c

j

jednostek.

Zadanie polega na wyznaczeniu optymalnego programu ci

ę

cia minimalizuj

ą

cy

ł

ą

czny odpad i pozwalaj

ą

cy wykona

ć

przyj

ę

te zamówienia.

ID,2013/2014

Przykłady modeli PL

Przykłady modeli PL
--

zagadnienie optymalnego wykroju (2)

zagadnienie optymalnego wykroju (2)

Budowa modelu

Budowa modelu

Oznaczmy przez x

j

liczb

ę

arkuszy, z których wycina

ć

si

ę

b

ę

dzie detale j-tym

sposobem. Liczb

ę

detali i-tego rodzaju wyci

ę

tych z jednego arkusza blachy

ci

ę

tego j-tym sposobem czyli a

ij

oraz pozostałe dane do zadania tj. b

i

i c

j

wygodnie jest zapisa

ć

w tabeli nast

ę

puj

ą

cej postaci:

Detale i-

tego typu

Sposoby ci

ę

cia

Minimalna

liczba

detali

j=1

j=2

…

j=s

1

a

11

a

12

…

a

1s

b

1

2

a

21

a

22

…

a

2s

b

2

…

…

…

…

…

….

m

a

m1

a

m2

…

a

ms

b

m

Odpady

c

1

c

2

…

c

s

ID,2013/2014

2013-10-15

20

Przykłady modeli PL

Przykłady modeli PL
--

zagadnienie optymalnego wykroju (3)

zagadnienie optymalnego wykroju (3)

Budowa modelu

Budowa modelu

W celu zrealizowania zamówienia musz

ą

zosta

ć

spełnione

warunki ograniczaj

ą

ce postaci: dla i=1,2,…,m oraz warunki

brzegowe postaci:

Kryterium wyboru decyzji zostało zdefiniowane jako

minimalizacja ł

ą

cznych odpadów, czyli:

∑

=

≤

s

j

i

j

ij

b

x

a

1

C

x

x

j

j

∈

≥

,

0

∑

=

→

s

j

j

j

x

c

1

min

Model został sformułowany

Model został sformułowany przy zało

ż

eniu,

ż

e w procesie produkcyjnym

przy zało

ż

eniu,

ż

e w procesie produkcyjnym

wykorzystywany jest jeden surowiec.

wykorzystywany jest jeden surowiec.

ID,2013/2014

Przykłady modeli PL

Przykłady modeli PL
--

problem załadunku (plecaka) (1)

problem załadunku (plecaka) (1)

Sformułowanie problemu

Sformułowanie problemu

Wybieraj

ą

c si

ę

na wycieczk

ę

chcemy zabra

ć

m rzeczy, o obj

ę

to

ś

ci a

j

ka

ż

da

(j=1,2,…,m), czyli ł

ą

czna obj

ę

to

ść

pakowanych przedmiotów wynosi

Wszystko to nale

ż

y spakowa

ć

do plecaka, którego pojemno

ść

wynosi b, czy

czym Pojawia si

ę

wi

ę

c konieczno

ść

rezygnacji z jednego lub kilku

przedmiotów. Wiedz

ą

c,

ż

e nale

ż

y spakowa

ć

przynajmniej d przedmiotów,

dokonaj wyboru rzeczy, które nale

ż

y spakowa

ć

przyjmuj

ą

c jedno kryterium

wyboru:

1.

Jak najlepsze wykorzystanie miejsca w plecaku,

2.

Spakowanie przedmiotów najbardziej niezb

ę

dnych,

3.

Spakowanie jak najwi

ę

kszej liczy przedmiotów.

∑

=

m

j

j

a

1

.

∑

=

<

m

j

j

a

b

1

.

ID,2013/2014

2013-10-15

21

Przykłady modeli PL

Przykłady modeli PL
--

problem załadunku (plecaka) (2)

problem załadunku (plecaka) (2)

Budowa modelu

Budowa modelu

Zmienne decyzyjne x

j

przyjmowa

ć

b

ę

d

ą

warto

ś

ci jeden lub zero, co

oznacza

ć

b

ę

dzie,

ż

e j-ty przedmiot zostanie spakowany (kiedy x

j

=1) lub nie

zostanie spakowany (x

j

=0). Obj

ę

to

ść

wszystkich spakowanych rzeczy nie mo

ż

e

przekroczy

ć

pojemno

ś

ci plecaka, czyli:

Zało

ż

enie dotycz

ą

ce minimalnej liczby przedmiotów, które nale

ż

y

spakowa

ć

na wycieczk

ę

, mo

ż

na sformułowa

ć

nast

ę

puj

ą

co:

warunki brzegowe s

ą

postaci:

Funkcja celu zale

ż

y od sformułowanego kryterium wyboru i mo

ż

e by

ć

postaci:

1.

co oznacza,

ż

e minimalizowana jest pojemno

ść

plecaka, która nie zostanie wykorzystana.

∑

=

≤

m

j

j

ij

b

x

a

1

∑

=

≥

m

j

j

d

x

1

}

1

,

0

{

∈

j

x

∑

=

→

−

m

j

j

j

x

a

b

1

min

ID,2013/2014

Przykłady modeli PL

Przykłady modeli PL
--

problem załadunku (plecaka) (3)

problem załadunku (plecaka) (3)

Budowa modelu

Budowa modelu

2.

, gdzie c

j

jest wyra

ż

onym w punktach poziomem u

ż

yteczno

ś

ci

poszczególnych przedmiotów. W praktyce ustala si

ę

pewn

ą

hierarchi

ę

„wa

ż

no

ś

ci” poszczególnych przedmiotów, którym nadaje si

ę

tzw. wag

ę

zgodnie z przyj

ę

t

ą

przez konstruktora modelu skal

ą

. Mo

ż

e przy tym okaza

ć

si

ę

,

ż

e niektóre przedmioty b

ę

d

ą

równie wa

ż

ne, wówczas maj

ą

one takie

same wagi, przyjmuje si

ę

,

ż

e czym wy

ż

szy poziom u

ż

yteczno

ś

ci tym c

j

wi

ę

ksze.

3.

,co oznacza,

ż

e nale

ż

y spakowa

ć

jak najwi

ę

cej przedmiotów.

∑

=

→

m

j

j

j

x

c

1

max

∑

=

→

m

j

j

x

1

max

ID,2013/2014

2013-10-15

22

Przykłady modeli PL

Przykłady modeli PL
--

zadanie transportowe (1)

zadanie transportowe (1)

Sformułowanie problemu

Sformułowanie problemu

Danych jest m dostawców, u których znajduje si

ę

odpowiednio: a

1

,a

2

,…,a

m

jednostek towaru. Ładunek ten powinien zosta

ć

dostarczony do n odbiorców,

którzy zgłosili zapotrzebowanie w ilo

ś

ciach: b

1

,b

2

,…,b

n

jednostek. Wiadomo

jest,

ż

e koszty jednostkowe transportu od i-tego dostawcy do j-tego odbiorcy

wynosz

ą

c

ij

(i=1,2,…,m, j=1,2,…,n).

Nale

ż

y wyznaczy

ć

taki plan przewozów, aby ł

ą

czne koszty transportu były

minimalne.

ID,2013/2014

Przykłady modeli PL

Przykłady modeli PL
--

zadanie transportowe (2)

zadanie transportowe (2)

Budowa modelu

Budowa modelu

Zmienne decyzyjne x

ij

w tym modelu oznaczaj

ą

wielko

ść

przewozu

jednorodnego ładunku na trasie od i-tego dostawcy do j-tego odbiorcy. Istnieje

mn mo

ż

liwych tras przewozu, które mo

ż

na zapisa

ć

w macierzy:

Warunki ograniczaj

ą

ce dla nieujemnych zmiennych decyzyjnych

przyjmuj

ą

jedn

ą

z postaci:

























mn

m

m

n

n

x

x

x

x

x

x

x

x

x

...

...

...

...

...

...

...

2

1

2

22

21

1

12

11

ID,2013/2014

2013-10-15

23

Przykłady modeli PL

Przykłady modeli PL
--

zadanie transportowe (3)

zadanie transportowe (3)

∑

=

≤

n

j

i

ij

a

x

1

∑

=

=

m

i

j

ij

b

x

1

je

ś

li:

∑

∑

=

=

≥

m

i

n

j

j

i

b

a

1

1

∑

=

=

n

j

i

ij

a

x

1

∑

=

≤

m

i

j

ij

b

x

1

∑

∑

=

=

≤

m

i

n

j

j

i

b

a

1

1

je

ś

li:

∑

=

=

n

j

i

ij

a

x

1

∑

=

=

m

i

j

ij

b

x

1

je

ś

li:

∑

∑

=

=

=

m

i

n

j

j

i

b

a

1

1

)

,...,

2

,

1

(

)

,...,

2

,

1

(

n

j

m

i

=

=

Funkcja kryterium postaci:

zapewnia minimalizacj

ę

ł

ą

cznych kosztów transportu.

∑∑

=

=

→

m

i

n

j

ij

ij

x

c

1

1

min

ID,2013/2014

PL

PL –

– rozwiązywanie zadań

rozwiązywanie zadań

Uniwersaln

ą

metod

ą

rozwi

ą

zywania zada

ń

programowania liniowego jest algorytm simpleks.

W sytuacji gdy w zadaniu wyst

ę

puj

ą

dwie zmienne

decyzyjne, mo

ż

na je rozwi

ą

za

ć

metod

ą

geometryczn

ą

(graficzn

ą

). Na podstawie tej

metody otrzymujemy zbiór punktów, a nast

ę

pnie

sprawdzamy, w którym z nich warto

ść

funkcji celu

jest najwi

ę

ksza (lub najmniejsza).

ID,2013/2014

2013-10-15

24

Rozwiązywanie zadań PL –
metoda graficzna

1.

1.

Wyznaczenie zbioru rozwi

ą

za

ń

dopuszczalnych,

Wyznaczenie zbioru rozwi

ą

za

ń

dopuszczalnych,

okre

ś

lonych zbiorem nierówno

ś

ci:

okre

ś

lonych zbiorem nierówno

ś

ci:

Układ nierówno

ś

ci zast

ę

puje si

ę

równaniami prostych poprzez

przyrównanie ka

ż

dej ze zmiennych do 0.

Znajdujemy punkty przeci

ę

cia układu współrz

ę

dnych przez te proste i

wykre

ś

lamy proste odpowiadaj

ą

ce poszczególnym równaniom.

Po wyznaczeniu półpłaszczyzn spełniaj

ą

cych warunki pierwotnej

nierówno

ś

ci uzyskujemy obszar okre

ś

laj

ą

cy zbiór rozwi

ą

za

ń

dopuszczalnych w postaci nieregularnej figury geometrycznej.

2.

2.

Wyznaczenie punktu daj

ą

cego rozwi

ą

zanie optymalne

Wyznaczenie punktu daj

ą

cego rozwi

ą

zanie optymalne –

–

wykre

ś

lenie funkcji celu

wykre

ś

lenie funkcji celu

Bierzemy dowoln

ą

wspóln

ą

wielokrotno

ść

parametrów funkcji celu i

wyznaczamy punktu przeci

ę

cia układu współrz

ę

dnych przez prost

ą

odpowiadaj

ą

c

ą

funkcji celu.

ID,2013/2014

Kierunek przesuwania izolinii
wynika z kryterium optymalizacji !!!

Gdy funkcja celu jest MAX

MAX to prowadzimy linie

równoległe do niej a

ż

do znalezienia punktu(ów)

stycznych le

żą

cych jak najdalej od pocz

ą

tku

układu współrz

ę

dnych

Gdy funkcja celu jest MIN

MIN to prowadzimy linie

równoległe do niej a

ż

do znalezienia punktu(ów)

stycznych le

żą

cych jak najbli

ż

ej od pocz

ą

tku

układu współrz

ę

dnych

ID,2013/2014

2013-10-15

25

Przykład 1

Przykład 1 -- wybór optymalnego

wybór optymalnego

planu produkcji

planu produkcji

Przedsi

ę

biorstwo produkuje dwa wyroby: W1 i W2. W procesie produkcji tych wyrobów

zu

ż

ywa si

ę

wiele

ś

rodków, spo

ś

ród których dwa s

ą

limitowane. Limity te wynosz

ą

:

ś

rodek I - 96 000 jedn., natomiast

ś

rodek II - 80 000 jedn. Nakłady limitowanych

ś

rodków na jednostk

ę

wyrobów W1 i W2 podano w poni

ż

szej tabeli.

Środki

produkcji

Jednostkowe nakłady

W1

W2

I

16

24

II

16

10

Wiadomo tak

ż

e,

ż

e zdolno

ś

ci produkcyjne jednego z wydziałów, stanowi

ą

cego w

ą

skie

gardło procesu produkcyjnego, nie pozwalaj

ą

produkowa

ć

wi

ę

cej ni

ż

3000 szt.

wyrobów W1 oraz 4000 szt. wyrobów W2. Ponadto, działaj

ą

ca w ramach

przedsi

ę

biorstwa komórka analizy rynku ustaliła optymalne proporcje produkcji, które

kształtuj

ą

si

ę

odpowiednio jak 3:2. Cena sprzeda

ż

y (w zł) jednostki wyrobu W1

wynosi - 30, a wyrobu W2 – 40.
Ustali

ć

rozmiary produkcji przy zało

ż

eniu,

ż

e uzyskany przychód ze sprzeda

ż

y b

ę

dzie

maksymalny. W rozwi

ą

zaniu zastosowa

ć

metod

ę

geometryczn

ą

.

ID,2013/2014

Przykład 1

Przykład 1 -- rozwiązanie

rozwiązanie

Na pocz

ą

tku musimy zbudowa

ć

model matematyczny opisuj

ą

cy

przedstawion

ą

sytuacj

ę

.

Oznaczmy x

1

oznacza wielko

ść

produkcji wyrobu W1, a x

2

- wielko

ść

produkcji wyrobu W2.

Pierwsze dwa warunki ograniczaj

ą

ce dotycz

ą

limitów na

ś

rodki

produkcji I i II:

(1) 16x

1

+ 24x

2

≤

96000

(2) 16x

1

+ 10x

2

≤

80000

Nale

ż

y uwzgl

ę

dni

ć

informacj

ę

pochodz

ą

c

ą

z komórki analizy rynku:

(3) x

2

= 2/3 x

1

Po uwzgl

ę

dnieniu ograniczonych zdolno

ś

ci jednego z wydziałów

produkcyjnych: warunki brzegowe przybior

ą

posta

ć

:

(4) 0

≤

x

1

≤

3000

(5) 0

≤

x

2

≤

4000

ID,2013/2014

2013-10-15

26

Przykład 1

Przykład 1 –

– rozwiązanie (

rozwiązanie (cd

cd.)

.)

Na podstawie znajomo

ś

ci celu, jaki sobie postawiło przedsi

ę

biorstwo

(uzyskanie maksymalnego przychodu ze sprzeda

ż

y), formułujemy

funkcj

ę

celu:

6)

F(x

1

,x

2

) = 30x

1

+ 40x

2

→

max

Mo

ż

emy zatem zapisa

ć

nasz model w nast

ę

puj

ą

cej postaci:

(1) 16x

1

+ 24x

2

≤

96000

(2) 16x

1

+ 10x

2

≤

80000

(3)

x

2

= 2/3 x

1

(4) 0

≤

x

1

≤

3000

(5) 0

≤

x

2

≤

4000

(6) F(x

1

,x

2

) = 30x

1

+ 40x

2

→

max.

Ze wzgl

ę

du na warunki (4) i (5)

rozwi

ą

zanie modelu musi si

ę

znajdowa

ć

w pierwszej

ć

wiartce

układu współrz

ę

dnych

ID,2013/2014

x

2

x

1

2000

4000

6000

8000

2000

4000

6000

8000

(1) 16x

1

+ 24x

2

≤

96000

(2) 16x

1

+ 10x

2

≤

80000

(3)

x

2

= 2/3 x

1

(4) 0

≤

x

1

≤

3000

(5) 0

≤

x

2

≤

4000

Przykład 1

Przykład 1 –

– rozwiązanie (

rozwiązanie (cd

cd.)

.)

Odcinek OA jest odcinkiem rozwi

ą

za

ń

dopuszczalnych, st

ą

d rozwi

ą

zania optymalnego

nale

ż

y poszukiwa

ć

w tym wła

ś

nie odcinku.

0

A

A

Bior

ą

c dowoln

ą

wspóln

ą

wielokrotno

ść

parametrów

funkcji celu, tj. 30 i 40 np. 60000 wyznaczamy lini

ę

jednakowego przychodu.

Nast

ę

pnie lini

ę

t

ę

przesuwamy równolegle wzdłu

ż

odcinka OA jak najdalej od pocz

ą

tku układu

współrz

ę

dnych

(6) F(x

1

,x

2

) = 30x

1

+40x

2

→

max

ID,2013/2014

2013-10-15

27

x

2

x

1

2000

4000

6000

8000

2000

4000

6000

Przykład 1

Przykład 1 –

– rozwiązanie (

rozwiązanie (cd

cd.)

.)

0

A

A

F(x

1

,x

2

) = 30x

1

+40x

2

→

max

Kierunek przesuwania izolinii wynika z kryterium
optymalizacji (funkcji celu).

Oznacza to,

ż

e w tym wła

ś

nie punkcie mamy

poszukiwane rozwi

ą

zanie.

W rozwa

ż

anym przykładzie funkcja F jest

maksymalizowana, co oznacza,

ż

e przyjmujemy

kolejno coraz to wi

ę

ksze warto

ś

ci wyrazu wolnego

przesuwanej prostej.

Dopiero izolinia (3) trafia na koniec odcinka OA.

Punkt A ma współrz

ę

dne:

x

1

=3000 i x

2

=2000, a F(x

1

,x

2

)=170000

ID,2013/2014

Przykład 2

Przykład 2 –

– problem mieszanek

problem mieszanek

Dziecko w pewnym wieku potrzebuje tygodniowo co najmniej 120
jednostek witaminy A, 60 jednostek witaminy D, 36 jednostek witaminy
C oraz 180 jednostek witaminy E. Witaminy te zawarte s

ą

w dwóch

produktach P1 i P2. Ze wzgl

ę

du na uboczne szkodliwe działanie

witaminy A nale

ż

y jej dostarcza

ć

co najwy

ż

ej 240 jednostek. Zawarto

ść

poszczególnych witamin w jednostce produktu oraz ceny jednostkowe
produktów podano w tabeli.

Jak skomponowa

ć

po

ż

ywienie dziecka z produktów P1 i P2, aby

zapewni

ć

dziecku wymagane witaminy po jak najni

ż

szym koszcie?

Witaminy

P1

P2

A

6

3

D

1

3

C

9

1

E

6

6

Cena (w zł)

1,2

1,8

ID,2013/2014

2013-10-15

28

Przykład 2

Przykład 2 –

– rozwiązanie

rozwiązanie

Budujemy model matematyczny

Zmienne decyzyjne:

Warunki ograniczaj

ą

ce dotycz

ą

…

Warunki brzegowe

Funkcja celu

x

1

, x

2

– ilo

ść

produktu P1, P2, któr

ą

nale

ż

y

zakupi

ć

i poda

ć

dziecku,

A) 6x

1

+3x

2

≥

120 6x

1

+3x

2

≤

240

D) 1x

1

+3x

2

≥

60

C) 9x

1

+1x

2

≥

36

E) 6x

1

+6x

2

≥

180

x

1

,x

2

≥

0

F(x

1

,x

2

) = 1,2x

1

+1,8x

2

→MIN

Witaminy

P1

P2

A

6

3

D

1

3

C

9

1

E

6

6

Cena (w zł)

1,2

1,8

ID,2013/2014

x

2

x

1

20

40

60

80

20

40

60

80

(1) 6x

1

+ 3x

2

≥

120

(2) 6x

1

+ 3x

2

≤

240

(3) 1x

1

+ 3x

2

≥

60

(

4) 9x

1

+ 1x

2

≥

36

(5) 6x

1

+ 6x

2

≥

180

(6) x

1

, x

2

≥

0

Przykład 2

Przykład 2 –

– rozwiązanie (

rozwiązanie (cd

cd.)

.)

Obszar A,B,C,D,E to obszar rozwi

ą

za

ń

dopuszczalnych, w którym nale

ż

y poszukiwa

ć

rozwi

ą

zania optymalnego.

0

A

A

Bior

ą

c dowoln

ą

wspóln

ą

wielokrotno

ść

parametrów

funkcji celu, tj. 1,2 i 1,8 np. 54 wyznaczamy lini

ę

jednakowego kosztu.

Nast

ę

pnie lini

ę

t

ę

przesuwamy równolegle, a

ż

do

znalezienia punktu(ów) stycznych le

żą

cych jak najbli

ż

ej

od pocz

ą

tku układu współrz

ę

dnych.

(6) F(x

1

,x

2

) = 1,2x

1

+1,8x

2

→

min

B

B

C

C

D

D

E

E

Punkt C ma
współrz

ę

dne:

x

1

=15 i x

2

=15, a

F(x

1

,x

2

)=45

ID,2013/2014

2013-10-15

29

Pami

ę

tajcie ,aby nie poprzesta

ć

na tym……..

ale pouczy

ć

si

ę

samodzielnie