Microsoft PowerPoint - Badania operacyjne

2013-10-15

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

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

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

Abtowa J., Piasecki K., Ró

ski T.,

witalski Z.: Matematyka

wspomagaj

ca zarz

dzanie. AE, Pozna

2002 (rozdział 7.4).

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

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

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

Szapiro T. (red.): Decyzje mened

erskie z Excelem. PWE, Warszawa

2000.

Krawczyk S.: Badania operacyjne dla mened

erów. Wydawnictwo AE

im. Oskara Lanego we Wrocławiu 1996.

ID,2013/2014

2013-10-15

Źródła wiedzy (

Źródła wiedzy (cd

cd.)

Siwak T.: Badania operacyjne dla in

ynierów zarz

dzania.

Wydawnictwa AGH, Kraków 1998.

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

1997.

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

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:

Zaj

cia podzielone s

na 2 bloki:

wykłady (15h) - obecno

ść

nie jest obowi

zkowa

wiczenia (15h) - obecno

ść

jest obowi

zkowa

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

Ukierunkowanie na podejmowanie decyzji.

liwo

ść

oceny działania (decyzji) na

podstawie okre

lonych kryteriów.

Konieczno

ść

budowy modelu (na ogół

matematycznego) sytuacji decyzyjnej.

liwo

ść

realizacji oblicze

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

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

upraszczaj

cych

Tworzenie modelu matematycznego

Poszukiwanie metod rozwi

zywania modelu

Uzyskanie rozwi

zania modelu

Weryfikacja i ocena modelu oraz rozwi

zania

ID,2013/2014

2013-10-15

Badania operacyjne

Badania operacyjne –

– metodyka (

metodyka (cd

cd.)

Czy model i rozwi

zanie

poprawne i przydatne?

Wdro

enie rozwi

zania

Obserwacja zmian zachodz

cych pod wpływem

wprowadzonego rozwi

zania

Czy problem został

rozwi

zany?

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

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

oraz ewentualna weryfikacja

modelu decyzyjnego.

Przedstawienie rozwi

decydentowi i

ostateczne przygotowanie decyzji.

ID,2013/2014

2013-10-15

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

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

ce ograniczenia zasobów, jakimi

dysponujemy, b

wymagania, które musz

spełnione.

ID,2013/2014

2013-10-15

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

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

ci matematycznych, z

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

Warto

ść

funkcji celu jest miernikiem efektywno

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

Rozwi

zanie modelu polega na ustaleniu warto

Rozwi

zanie modelu polega na ustaleniu warto

optymalnej funkcji celu w zbiorze decyzji dopuszczalnych.

ID,2013/2014

2013-10-15

Ogólny zapis problemu PM (

Ogólny zapis problemu PM (cd

cd.)

ID,2013/2014

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

Model deterministyczny

Model deterministyczny – wszystkie parametry wyst

puj

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

problemy masowej obsługi.

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

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)

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

(zadania programowania liniowego

--ZPL)

ZPL)

ID,2013/2014

2013-10-15

Model programowania liniowego

Funkcja celu (1) jest to funkcja liniowa,

Równania i nierówno

ci generuj

ce zbiór

decyzji dopuszczalnych X s

formami

liniowymi

ID,2013/2014

Standardowa postać ZPL

+ a

+ ... + a

≤≤

(≥) b

+ a

+ ... + a

≤≤

(≥) b

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

+ a

+ ... + a

≤≤

(≥) b

≥

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

F(x

,…,x

) = c

+ c

+ ... + c

→

max (min)

Funkcja

+ c

+ ... + c

- funkcja celu

Liczby

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

współczynniki techniczno-ekonomiczne

Liczby b

, i = 1, ... , m

elementy wektora ograniczeń

Liczby c

, i = 1, ... , n to

współczynniki funkcji celu

Zmienne

, k = 1, ... , n

zmienne decyzyjne

ID,2013/2014

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

2013-10-15

Ogólna postać ZPL

∑

→

max(min)

)

,...

(

∑

≥

≤

)

(

,...,

,...

≥

Kanoniczna postać ZPL

+ a

+ ... + a

n+1

+ a

+ ... + a

n+2

= b

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

+ a

+ ... + a

n+m

= b

≥

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

F(x

,…,x

) = c

+ c

+ ... + c

n+m

→

max

ID,2013/2014

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

n+1

,…,x

n+m

≥0

2013-10-15

Macierzowa postać ZPL













...













...













...

[

]

...

)

(

max(min)

≥

≤

→

- wektor wierszowy współczynników funkcji celu

- macierz o rozmiarze mn składaj

ca si

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

Przedsi

biorstwo posiada m ró

nych

rodków produkcji S

,…,S

odpowiednio w ilo

ciach: b

,…,b

. 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

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

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

,…,c

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

ID,2013/2014

2013-10-15

Budowa modelu

Zmiennymi decyzyjnymi w tym zadaniu s

ilo

ci produkowanych

wyrobów z ka

dego rodzaju asortymentu – x

. Je

eli wyprodukujemy x

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

yjemy do produkcji a

rodka S

. Rozpatruj

pełen asortyment wyrobów wykorzystamy czynnika produkcji S

(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

spełnione warunki brzegowe dane w postaci:

Przykłady modeli PL

Przykłady modeli PL
--

wybór asortymentu produkcji (2)

∑

≤

≥

ID,2013/2014

Budowa modelu

W przypadku, kiedy produkowany przez firm

asortyment mierzony jest w

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

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)

∈

]

[

∑

Zadanie polega na wyznaczeniu takich warto

ci zmiennych decyzyjnych x

Zadanie polega na wyznaczeniu takich warto

ci zmiennych decyzyjnych x

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

cej kryterium wyboru decyzji.

maksimum funkcji celu, b

cej kryterium wyboru decyzji.

ID,2013/2014

2013-10-15

Przykłady modeli PL

Przykłady modeli PL
--

wyznaczanie optymalnej diety (1)

Sformułowanie problemu

Danych jest n produktów, które zawieraj

m składników S

,…,S

odpowiednio w ilo

ciach: b

,…,b

. Z analiz wynika,

e w jednostce produktu

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

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

składniki od

ywcze zostały tak uporz

dkowane,

e podanie pierwszych p<m

składników (tzn. S

,…,S

) w nadmiernych ilo

ciach jest szkodliwe i ich

zawarto

ść

w diecie nie powinna przekracza

odpowiednio d

,…,d

jednostek.

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

p+1

p+2

,…,S

) musz

zosta

dostarczone przynajmniej w dawkach

p+1

p+2

,…,d

. Oznaczaj

c przez c

,…,c

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

Zmiennymi decyzyjnymi x

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

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

, 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)

∑

≤

∑

≤

∑

≥

∑

ID,2013/2014

2013-10-15

Przykłady modeli PL

Przykłady modeli PL
--

zagadnienie optymalnego wykroju (1)

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

ąć

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

ciu arkusza blachy j-tym sposobem

otrzymuje si

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

wielko

ść

oszacowano na c

jednostek.

Zadanie polega na wyznaczeniu optymalnego programu ci

cia minimalizuj

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)

Budowa modelu

Oznaczmy przez x

liczb

arkuszy, z których wycina

dzie detale j-tym

sposobem. Liczb

detali i-tego rodzaju wyci

tych z jednego arkusza blachy

tego j-tym sposobem czyli a

oraz pozostałe dane do zadania tj. b

i c

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

…

….

…

Odpady

…

ID,2013/2014

2013-10-15

Przykłady modeli PL

Przykłady modeli PL
--

zagadnienie optymalnego wykroju (3)

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:

∑

≤

∈

≥

∑

→

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.

ID,2013/2014

Przykłady modeli PL

Przykłady modeli PL
--

problem załadunku (plecaka) (1)

Sformułowanie problemu

Wybieraj

c si

na wycieczk

chcemy zabra

m rzeczy, o obj

ci a

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

czna obj

ść

pakowanych przedmiotów wynosi

Wszystko to nale

y spakowa

do plecaka, którego pojemno

ść

wynosi b, czy

czym Pojawia si

c konieczno

ść

rezygnacji z jednego lub kilku

przedmiotów. Wiedz

e nale

y spakowa

przynajmniej d przedmiotów,

dokonaj wyboru rzeczy, które nale

y spakowa

przyjmuj

c jedno kryterium

wyboru:

Jak najlepsze wykorzystanie miejsca w plecaku,

Spakowanie przedmiotów najbardziej niezb

dnych,

Spakowanie jak najwi

kszej liczy przedmiotów.

∑

ID,2013/2014

2013-10-15

Przykłady modeli PL

Przykłady modeli PL
--

problem załadunku (plecaka) (2)

Budowa modelu

Zmienne decyzyjne x

przyjmowa

warto

ci jeden lub zero, co

oznacza

dzie,

e j-ty przedmiot zostanie spakowany (kiedy x

=1) lub nie

zostanie spakowany (x

=0). Obj

ść

wszystkich spakowanych rzeczy nie mo

przekroczy

pojemno

ci plecaka, czyli:

Zało

enie dotycz

ce minimalnej liczby przedmiotów, które nale

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:

co oznacza,

e minimalizowana jest pojemno

ść

plecaka, która nie zostanie wykorzystana.

∑

≤

∑

≥

}

{

∈

∑

→

−

min

ID,2013/2014

Przykłady modeli PL

Przykłady modeli PL
--

problem załadunku (plecaka) (3)

Budowa modelu

, gdzie c

jest wyra

onym w punktach poziomem u

yteczno

poszczególnych przedmiotów. W praktyce ustala si

pewn

hierarchi

„wa

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

tzw. wag

zgodnie z przyj

przez konstruktora modelu skal

. Mo

e przy tym okaza

e niektóre przedmioty b

równie wa

ne, wówczas maj

one takie

same wagi, przyjmuje si

e czym wy

szy poziom u

yteczno

ci tym c

ksze.

,co oznacza,

e nale

y spakowa

jak najwi

cej przedmiotów.

∑

→

max

∑

→

max

ID,2013/2014

2013-10-15

Przykłady modeli PL

Przykłady modeli PL
--

zadanie transportowe (1)

Sformułowanie problemu

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

odpowiednio: a

,…,a

jednostek towaru. Ładunek ten powinien zosta

dostarczony do n odbiorców,

którzy zgłosili zapotrzebowanie w ilo

ciach: b

,…,b

jednostek. Wiadomo

jest,

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

wynosz

(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)

Budowa modelu

Zmienne decyzyjne x

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:













...

ID,2013/2014

2013-10-15

Przykłady modeli PL

Przykłady modeli PL
--

zadanie transportowe (3)

∑

≤

∑

li:

∑

≥

∑

≤

∑

≤

li:

∑

li:

∑

)

,...,

(

)

,...,

(

Funkcja kryterium postaci:

zapewnia minimalizacj

cznych kosztów transportu.

∑∑

→

min

ID,2013/2014

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

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

Rozwiązywanie zadań PL –
metoda graficzna

Wyznaczenie zbioru rozwi

dopuszczalnych,

Wyznaczenie zbioru rozwi

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

dopuszczalnych w postaci nieregularnej figury geometrycznej.

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

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

Przykład 1

Przykład 1 -- wybór optymalnego

wybór optymalnego

planu produkcji

Przedsi

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

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

Wiadomo tak

e zdolno

ci produkcyjne jednego z wydziałów, stanowi

cego w

skie

gardło procesu produkcyjnego, nie pozwalaj

produkowa

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

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

przedstawion

sytuacj

Oznaczmy x

oznacza wielko

ść

produkcji wyrobu W1, a x

- wielko

ść

produkcji wyrobu W2.

Pierwsze dwa warunki ograniczaj

ce dotycz

limitów na

rodki

produkcji I i II:

(1) 16x

+ 24x

≤

96000

(2) 16x

+ 10x

≤

80000

Nale

y uwzgl

dni

informacj

pochodz

z komórki analizy rynku:

(3) x

= 2/3 x

Po uwzgl

dnieniu ograniczonych zdolno

ci jednego z wydziałów

produkcyjnych: warunki brzegowe przybior

posta

(4) 0

≤

3000

(5) 0

≤

4000

ID,2013/2014

2013-10-15

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:

F(x

) = 30x

+ 40x

→

max

emy zatem zapisa

nasz model w nast

puj

cej postaci:

(1) 16x

+ 24x

≤

96000

(2) 16x

+ 10x

≤

80000

(3)

= 2/3 x

(4) 0

≤

3000

(5) 0

≤

4000

(6) F(x

) = 30x

+ 40x

→

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

2000

4000

6000

8000

2000

4000

6000

8000

(1) 16x

+ 24x

≤

96000

(2) 16x

+ 10x

≤

80000

(3)

= 2/3 x

(4) 0

≤

3000

(5) 0

≤

4000

Przykład 1

Przykład 1 –

– rozwiązanie (

rozwiązanie (cd

cd.)

Odcinek OA jest odcinkiem rozwi

dopuszczalnych, st

d rozwi

zania optymalnego

nale

y poszukiwa

w tym wła

nie odcinku.

Bior

c dowoln

wspóln

wielokrotno

ść

parametrów

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

jednakowego przychodu.

Nast

pnie lini

przesuwamy równolegle wzdłu

odcinka OA jak najdalej od pocz

tku układu

współrz

dnych

(6) F(x

) = 30x

+40x

→

max

ID,2013/2014

2013-10-15

2000

4000

6000

8000

2000

4000

6000

Przykład 1

Przykład 1 –

– rozwiązanie (

rozwiązanie (cd

cd.)

F(x

) = 30x

+40x

→

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:

=3000 i x

=2000, a F(x

)=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

ywienie dziecka z produktów P1 i P2, aby

zapewni

dziecku wymagane witaminy po jak najni

szym koszcie?

Witaminy

Cena (w zł)

1,2

1,8

ID,2013/2014

2013-10-15

Przykład 2

Przykład 2 –

– rozwiązanie

rozwiązanie

Budujemy model matematyczny

Zmienne decyzyjne:

Warunki ograniczaj

ce dotycz

…

Warunki brzegowe

Funkcja celu

, x

– ilo

ść

produktu P1, P2, któr

nale

zakupi

i poda

dziecku,

A) 6x

+3x

≥

120 6x

+3x

≤

240

D) 1x

+3x

≥

C) 9x

+1x

≥

E) 6x

+6x

≥

180

≥

F(x

) = 1,2x

+1,8x

→MIN

Witaminy

Cena (w zł)

1,2

1,8

ID,2013/2014

(1) 6x

+ 3x

≥

120

(2) 6x

+ 3x

≤

240

(3) 1x

+ 3x

≥

(

4) 9x

+ 1x

≥

(5) 6x

+ 6x

≥

180

(6) x

, x

≥

Przykład 2

Przykład 2 –

– rozwiązanie (

rozwiązanie (cd

cd.)

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

dopuszczalnych, w którym nale

y poszukiwa

rozwi

zania optymalnego.

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

przesuwamy równolegle, a

znalezienia punktu(ów) stycznych le

żą

cych jak najbli

od pocz

tku układu współrz

dnych.

(6) F(x

) = 1,2x

+1,8x

→

min

Punkt C ma
współrz

dne:

=15 i x

=15, a

F(x

)=45

ID,2013/2014