Etel 02 progr lin+calkow

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

1

Ekotransport i ekologistyka

Ekotransport i ekologistyka

Piotr Sawicki

Piotr Sawicki

Wydział Maszyn Roboczych i Transportu
pok. 719, tel. 665 22 30
E-mail: piotr.sawicki@put.poznan.pl
URL: www.put.poznan.pl/~piotrs

Wydział Maszyn Roboczych i Transportu
pok. 719, tel. 665 22 30
E-mail: piotr.sawicki@put.poznan.pl
URL: www.put.poznan.pl/~piotrs

Programowanie
liniowe
i całkowitoliczbowe

Programowanie
liniowe
i całkowitoliczbowe

Alokacja zasobów

Alokacja zasobów

Piotr Sawicki / Ekotransport i ekologistyka

2

30

Plan prezentacji



Istota programowania liniowego

informacje wprowadzające

przykładowe problemy



Ogólne sformułowanie zadania programowania liniowego



Programowanie liniowe na przykładzie

identyfikacja problemu

konstrukcja modelu matematycznego

rozwiązanie problemu

interpretacja rozwiązania i analiza wrażliwości



Procedura rozwiązywania zadania programowania liniowego

metoda graficzna

zastosowanie Solvera MS Excel



Istota programowania całkowitoliczbowego



Podsumowanie

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

2

Piotr Sawicki / Ekotransport i ekologistyka

3

30

Programowanie liniowe

Istota



Jedna z najpopularniejszych i najbardziej użytecznych technik
menedżerskich

wywodzi się z badań operacyjnych



Programowanie liniowe znajduje powszechne zastosowanie przy
rozwiązywaniu problemów alokacji (przydziału) ograniczonych

zasobów

zasobów

do

konkurencyjnych

operacji

operacji

(zadań), np.:

wybór portfela oferowanych usług transportowych przy ustalonych kosztach przewozu i
posiadanym taborze

określenie rodzaju magazynowanych wyrobów przy uwzględnieniu ich zyskowności
oraz możliwościach magazynowych



Problemy sformułowane w kategoriach programowania liniowego
polegają na

maksymalizacji zysku

minimalizacji kosztów

osiągnięciu zakładanej wartości

Piotr Sawicki / Ekotransport i ekologistyka

4

30

Programowanie liniowe

Istota



Problem maksymalizacji zysku

osiągany poprzez realizację zestawu czynności (zadań) lub rodzajów usług
transportowych / logistycznych

każdemu zadaniu (rodzajowi usługi) odpowiada zmienna decyzyjna

– np.: oferta przewozu pasażerów na odległość do 50km – zmienna x

1

oferta przewozów dalekobieżnych – zmienna x

2


oferta przewozów towarowych do 12 ton – zmienna x

n

osiągnięcie maksymalnego zysku ograniczają dostępne (limitowane) zasoby

– np.: posiadanie: 15 zestawów autobusów podmiejskich, 20 autobusów dalekobieżnych,

3 autobusy turystyczne,….3 zestawy drogowe (do 24 ton),…



Problem minimalizacji kosztów

osiągany poprzez realizację zestawu czynności (zadań) lub rodzajów usług
transportowych

każdemu zadaniu (rodzajowi usługi) odpowiada zmienna decyzyjna

osiągnięcie minimalnego kosztu wymaga dostępności zasobów

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

3

Piotr Sawicki / Ekotransport i ekologistyka

5

30

Programowanie liniowe

Istota



Model matematyczny problemu

sformułowany w postaci zadania

programowania liniowego

funkcja celu (kryterium „jakości/
doskonałości” rozwiązania)

– funkcja liniowa
– zmienne decyzyjne w pierwszej

potędze

ograniczenia

– funkcja liniowa
– zmienne decyzyjne w pierwszej

potędze

– zależności w postaci >, <, =



Przykłady

sformułowanie równań i nierówności
w postaci nieliniowej

sformułowanie równań i nierówności
w postaci liniowej

liniowość w praktyce oznacza, że
zależność funkcyjna pomiędzy
zmiennymi decyzyjnymi posiada
graficzną reprezentację w postaci
linii prostych

2

2

1

2

1

3

2

Min

x

x

x

x

Z

+

=

)

,

(

2

1

2

1

3

Min

x

x

x

x

Z

+

=

)

,

(

45

3

2

2

2

1

+ x

x

2

1

2

1

2

Min

x

x

x

x

Z

+

=

)

,

(

10

4

3

3

2

1

+

+

x

x

x

Piotr Sawicki / Ekotransport i ekologistyka

6

30

Programowanie liniowe

Ogólne sformułowanie



Ogólne sformułowanie zadania programowania liniowego

funkcja celu
Max Z = c

1

x

x

1

1

+ c

2

x

x

2

2

+ ... + c

n

x

x

n

n

ograniczenia

(ograniczone zasoby)

a

11

x

x

1

1

+ a

12

x

x

2

2

+ ... + a

1n

x

x

n

n

b

1

a

21

x

x

1

1

+ a

22

x

x

2

2

+ ... + a

2n

x

x

n

n

b

2

...

a

m1

x

x

1

1

+ a

m2

x

x

2

2

+ ... + a

mn

x

x

n

n

b

m

x

x

1

1

0,

x

x

2

2

0, ...,

x

x

n

n

0

c

j

– jednostkowy przyrost j – tej czynności w ocenie globalnej Z (j = 1, 2, ...,n)

b

i

ilość i – tego zasobu dostępnego do alokacji do czynności (i = 1, 2, ...,m)

a

ij

– ilość i – tego zasobu konsumowanego przez j – tą czynność

c

j

, b

i

, a

ij

parametry;

parametry;

x

1

, x

2

, ..., x

3

zmienne decyzyjne

zmienne decyzyjne

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

4

Piotr Sawicki / Ekotransport i ekologistyka

7

30

Programowanie liniowe

Proces rozwiązywania problemu

Model matematyczny

problemu

Dobór metody rozw.

Rozwiązanie problemu

Interpretacja rozw.

Analiza wrażliwości

Proces rozwiązywania

problemu decyzyjnego

Proces rozwiązywania

problemu decyzyjnego

Identyfikacja problemu

decyzyjnego



Identyfikacja problemu decyzyjnego

zidentyfikuj stan aktualny

– rozpoznaj realizowane działania
– określ trudności w podjęciu decyzji

opisz sytuację (zaistniały problem)



Konstrukcja modelu matematycznego

zidentyfikuj zmienne decyzyjne

– czego poszukujesz?
– jakie wielkości mają być wyznaczone?
– ile jest niewiadomych?

zidentyfikuj parametry zadania

– jakie wielkości są znane (stałe)?

zdefiniuj cel swoich poszukiwań Æ skonstruuj funkcję celu

– jaki cel chcesz osiągnąć?

określ wszystkie ograniczenia podjęcia decyzji Æ
skonstruuj warunki ograniczające

– co stanowi ograniczenie dla podjęcia Twojej decyzji?
– z jakimi ograniczeniami musisz się liczyć?

Piotr Sawicki / Ekotransport i ekologistyka

8

30

Programowanie liniowe

Proces rozwiązywania problemu



Rozwiązanie problemu (sformułowanego modelu)

poszukiwanie rozwiązania

– maksymalizacja funkcji celu
– minimalizacja funkcji celu

rozwiązanie problemu za pomocą dostępnych metod

– metoda graficzna (stosowana tylko dla 2 zmiennych

decyzyjnych)

– metoda algebraiczna SIMPLEX (nie ma ograniczenia liczby

zmiennych decyzyjnych)



Interpretacja rozwiązania

wartość zmiennych decyzyjnych

pozostające zasoby

analiza wrażliwości

– zmiana dostępności zasobów

Model matematyczny

problemu

Dobór metody rozw.

Rozwiązanie problemu

Interpretacja rozw.

Analiza wrażliwości

Proces rozwiązywania

problemu decyzyjnego

Proces rozwiązywania

problemu decyzyjnego

Identyfikacja problemu

decyzyjnego

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

5

Piotr Sawicki / Ekotransport i ekologistyka

9

30

Programowanie liniowe

Proces rozwiązywania problemu



Tok postępowania przy rozwiązywaniu problemu
sformułowanego w postaci zadania programowania
liniowego
Æ analiza przykładu

„Firma ForkLift Service (FLS) jest jednym z (…)”

zobacz treść zadania

Model matematyczny

problemu

Dobór metody rozw.

Rozwiązanie problemu

Interpretacja rozw.

Analiza wrażliwości

Identyfikacja problemu

decyzyjnego

Proces rozwiązywania

problemu decyzyjnego

Proces rozwiązywania

problemu decyzyjnego

Piotr Sawicki / Ekotransport i ekologistyka

10

30

Programowanie liniowe

Proces rozwiązywania problemu / Model



Konstrukcja modelu matematycznego

zmienne decyzyjne w analizowanym problemie

S

– liczba zakupionych przez FLS wózków widłowych typu 20S

H

– liczba zakupionych przez FLS wózków widłowych typu 45H

funkcja celu Æ cel postawiony przez firmę FLS

– maksymalizacja zysku ze sprzedaży wózków widłowych typu 20S i 45H
– zysk całkowity:

Z = z

s

+z

H

– z

s

- jednostkowy zysk ze sprzedaży wózków typu 20S

z

s

= 15% • 19.000

S

= 2.850

S

– z

H

– jednostkowy zysk ze sprzedaży wózków typu 45H

z

H

= 19% • 33.000

H

= 6.270

H

– ostateczne sformułowanie funkcji celu

Max Z(S, H) = 2.850

S

+ 6.270

H

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

6

Piotr Sawicki / Ekotransport i ekologistyka

11

30

Programowanie liniowe

Proces rozwiązywania problemu / Model



Konstrukcja modelu matematycznego … cd

identyfikacja ograniczeń

– zasoby finansowe firmy FLS Æ max. 2.400.000 zł/rok
– dostępny fundusz czasu pracy poświęcany przez pracowników FLS na sprzedaż wózków

20S i 45H Æ max. 520 rbh/rok

– dostępność wózków u producenta

{

max 100 szt./rok 20S

{

max 75 szt./rok 45H

– rynkowy popyt na wózki widłowe

{

min 10 szt. 20S

{

min 5 szt. 45H

matematyczny zapis ograniczeń

– zasoby finansowe firmy FLS ograniczają na przestrzeni roku możliwość zakupu wózków

widłowych u producenta

19.000

S

+ 33.000

H

2.400.000

– czas pracy ludzi zatrudnionych w FLS i zajmujących się sprzedażą wózków 20S i 45H jest

ograniczony

6

S

+ 4

H

520

Piotr Sawicki / Ekotransport i ekologistyka

12

30

Programowanie liniowe

Proces rozwiązywania problemu / Model

matematyczny zapis ograniczeń … cd

– możliwości produkcyjne firmy Clark w zakresie dostarczenia firmie FLS wózków widłowych

typu 20S i 45H

{

dostępność wózków 20S

S

100

{

dostępność wózków 45H

H

75

– minimalna liczba wózków w jednorazowym zamówieniu, zapewniająca ciągłość sprzedaży

przy jednoczesnym zachowaniu satysfakcji klientów firmy FLS

{

zapotrzebowanie firmy FLS na wózki typu 20S

S

10

{

zapotrzebowanie firmy FLS na wózki typu 45H

H

5

– formalnie Æ poszukiwane rozwiązanie (S, H) nie powinno przyjmować wartości ujemnych

S

0

H

0

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

7

Piotr Sawicki / Ekotransport i ekologistyka

13

30

Programowanie liniowe

Proces rozwiązywania problemu / Model



Ostateczna postać modelu matematycznego problemu decyzyjnego
sformułowanego w postaci zadania programowania liniowego

funkcja celu
Max Z(S, H) = 2.850

S

+ 6.270

H

przy ograniczeniach
(1) 19

S

+ 33

H

2.400

(2) 6

S

+ 4

H

520

(3)

S

100

(4)

H

75

(5)

S

10

(6)

H

5

(7)

S

0

(8)

H

0

Piotr Sawicki / Ekotransport i ekologistyka

14

30

Programowanie
liniowe
Graficzna metoda
rozwiązywania
zadania
programowania
liniowego

Programowanie
liniowe
Graficzna metoda
rozwiązywania
zadania
programowania
liniowego

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

8

Piotr Sawicki / Ekotransport i ekologistyka

15

30

Programowanie liniowe

Proces rozwiązywania problemu / Rozwiązywanie



Graficzne rozwiązanie problemu
programowania liniowego

rysowanie obszaru rozwiązań
dopuszczalnych
(1) 19

S

+ 33

H

2.400

(2) 6

S

+ 4

H

520

(3)

S

100

(4)

H

75

(5)

S

10

(6)

H

5

(7)

S

0

(8)

H

0

H

0

20

100

140

S

20

100

120

S ≥ 0

(7)

H ≥ 0

(8)

5

(6)

H ≥ 5

S ≥ 10

(5)

10

S ≤ 100

(3)

Obszar rozwiązań dopuszczalnych

dla ograniczeń (3) – (8)

Ograniczenia (7) i (8) są nieaktywne

(4)

H ≤ 75

75

Obszar rozwiązań niedopuszczalnych

Piotr Sawicki / Ekotransport i ekologistyka

16

30

Programowanie liniowe

Proces rozwiązywania problemu / Rozwiązywanie



Graficzne rozwiązanie problemu
programowania liniowego

rysowanie obszaru rozwiązań
dopuszczalnych
(1) 19

S

+ 33

H

2.400

(2) 6

S

+ 4

H

520

(3)

S

100

(4)

H

75

(5)

S

10

(6)

H

5

(7)

S

0

(8)

H

0

ograniczenie (2)
6

S

+ 4

H

= 520

S = 0 Æ H = 130 Æ (0;130)
H = 0
Æ S = 86,7 Æ (86,7;0)

H

0

20

100

140

S

20

100

120

S ≥ 0

(7)

H ≥ 0

(8)

5

(6)

H ≥ 5

S ≥ 10

(5)

10

S ≤ 100

(0;130)

(86,7; 0)

(4)

H ≤ 75

75

(3)

(2)

6S + 4H ≤ 520

Ograniczenia (3) staje się nieaktywne

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

9

Piotr Sawicki / Ekotransport i ekologistyka

17

30

Programowanie liniowe

Proces rozwiązywania problemu / Rozwiązywanie



Graficzne rozwiązanie problemu
programowania liniowego

rysowanie obszaru rozwiązań
dopuszczalnych
(1) 19

S

+ 33

H

2.400

(2) 6

S

+ 4

H

520

(3)

S

100

(4)

H

75

(5)

S

10

(6)

H

5

(7)

S

0

(8)

H

0

ograniczenie (1)
19

S

+ 33

H

= 2.400

S = 0 Æ H = 72,7 Æ (0; 72,7)
H = 0
Æ S = 126,3 Æ (126,3; 0)

H

0

20

100

140

S

20

100

120

S ≥ 0

(7)

H ≥ 0

(8)

5

(6)

H ≥ 5

S ≤ 100

(0;130)

(86,7; 0)

(3)

(2)

6S + 4H ≤ 520

(126,3; 0)

(0; 72,7)

S ≥ 10

(5)

10

19S +33H ≤ 2 400

(1)

(4)

H ≤ 75

75

Piotr Sawicki / Ekotransport i ekologistyka

18

30

Programowanie liniowe

Proces rozwiązywania problemu / Rozwiązywanie



Graficzne rozwiązanie problemu
programowania liniowego

określanie kierunku zmiany wartości
funkcji celu (tu kierunek przyrostu)

Max Z(S, H) = 2.850

S

+ 6.270

H

2.850

S

+ 6.270

H

= 0

S = 10 Æ H = - 4,5 Æ (10; - 4,5)
S = 20
Æ H = - 9 Æ (20; - 9)

H

0

20

100

140

S

20

100

120

5

H ≥ 5

S ≤ 100

(0;130)

(86,7; 0)

6S + 4H ≤ 520

(126,3; 0)

S ≥ 10

19S +33H ≤ 2 400

H ≤ 75

75

S

0,45

S

270

6

850

2

H

=

=

-4,5

-9

Z= 2 850S + 6 270H

40

(40; 20)

Z

1

=239 400

Z

2

=364 800

Ostatni wierzchołek”

Ostatni wierzchołek”

(40; 40)

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

10

Piotr Sawicki / Ekotransport i ekologistyka

19

30

Programowanie liniowe

Proces rozwiązywania problemu / Rozwiązywanie



Graficzne rozwiązanie problemu
programowania liniowego

określenie punktu przecięcia
prostych
S = 10
19

S

+ 33

H

= 2.400

H

= - 19/33

S

+ 2.400/33

S = 10 Æ H = 66,96

określenie wartości funkcji celu

S=10 i H=66,96

È

Z=448.400

È

Z

max

H

0

20

100

140

S

20

100

120

5

H ≥ 5

S ≤ 100

(0;130)

(86,7; 0)

6S + 4H ≤ 520

(126,3; 0)

S = 10

19S +33H = 2 400

H ≤ 75

75

-4,5

-9

40

(40; 20)

(40; 40)

(10; 66,96)

Piotr Sawicki / Ekotransport i ekologistyka

20

30

Programowanie liniowe

Proces rozwiązywania problemu / Rozwiązywanie



Graficzne rozwiązanie problemu programowania liniowego

(1) narysuj obszar rozwiązań dopuszczalnych i określ jego wierzchołki

– jeżeli obszar rozwiązań jest pusty Æ wszystkie rozwiązania są niedopuszczalne Æ

ponownie rozważ sformułowanie ograniczeń

(2) narysuj 2 różne wykresy funkcji celu (FC) i określ kierunek optymalizacji
(max vs. min)

– jeżeli problem dotyczy maksymalizacji FC równolegle przesuń linię reprezentującą FC w

kierunku przyrostu jej wartości

– jeżeli problem polega na minimalizacji FC przesuń linię w kierunku przeciwnym, tj.

zmniejszania się wartości FC

(3) przesuń funkcję celu znajdując „ostatni wierzchołek”

– w przypadku, gdy FC jest równoległa do jednego z boków obszaru rozwiązań

dopuszczalnych (ORD), wówczas problem posiada szereg rozwiązań alternatywnych
leżących pomiędzy wierzchołkami ORD

(4) równania prostych, które przecinają się w punkcie wierzchołkowym (patrz p.3)
tworzą układ równań określających współrzędne punktu optymalnego

Algorytm metody

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

11

Piotr Sawicki / Ekotransport i ekologistyka

21

30

Programowanie liniowe

Proces rozwiązywania problemu / Interpretacja rozwiązania



Rozwiązanie optymalne

optymalna liczba sprzedanych wózków widłowych 20S wynosi S=10 szt.

optymalna liczba sprzedanych wózków widłowych 45H wynosi H=66,96 szt.

– w praktyce H=66 lub H=67 (rozwiązanie poza obszarem rozwiązań dopuszczalnych)

zysk ze sprzedaży wózków obu typów
Z=2.850 S + 6.270 H
S=10 szt. i H=66,96 szt. Æ Z=448.400 € Æ maksymalny zysk
lub
S=10 i H=66 Æ Z=442.320

analiza ograniczeń
(1) 19.000

S

+ 33.000

H

2.400.000 (dostępne zasoby finansowe)

dla S=10 szt. i H=66,96 szt. LHS

1

= 2.400.000 € Æ 0 rezerwy finansowej

(2) 6

S

+ 4

H

520 (dostępna liczba roboczogodzin)

dla S=10 szt. i H=66,96 szt. LHS

2

= 327,84 rbh Æ 192,16 rbh rezerwy czasu

LHS

Piotr Sawicki / Ekotransport i ekologistyka

22

30

Programowanie liniowe

Proces rozwiązywania problemu / Interpretacja rozwiązania

analiza ograniczeń… cd
(3)

S

100 (maksymalna dostępność wózków typu 20S)

dla S=10 szt. i H=66,96 szt. LHS

3

= 10 szt. Æ 90 szt. rezerwy

(4)

H

75

dla S=10 szt. i H=66,96 szt. LHS

4

= 66,96 szt. Æ 8,04 szt. rezerwy

(5)

S

10

(6)

H

5

(7)

S

0

(8)

H

0

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

12

Piotr Sawicki / Ekotransport i ekologistyka

23

30

Programowanie liniowe

Zastosowanie Solvera Excel / Rozwiązanie problemu



Zapis modelu matematycznego w obszarze roboczym arkusza kalkulacyjnego

Przykład

Przykład

Piotr Sawicki / Ekotransport i ekologistyka

24

30

Programowanie liniowe

Zastosowanie Solvera Excel / Analiza wrażliwości



Raport wyników

Maksymalna wartość FC

Wartość zmiennych

decyzyjnych (S, H)

Status ograniczenia
„wiążące” – zasób w pełni wykorzystany
„niewiążący” – pozostają rezerwy

Wartość ograniczenia (LHS) przy
uzyskanych wartościach zmiennych
decyzyjnych

Pozostała do wykorzystania
rezerwa „luz”
analizowanych zasobów

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

13

Piotr Sawicki / Ekotransport i ekologistyka

25

30

Programowanie liniowe

Zastosowanie Solvera Excel / Analiza wrażliwości



Raport wrażliwości

Optymalna
wartość
zmiennych
decyzyjnych

Współczynniki
funkcji celu

Przedziały zmienności współczynników FC dla których
wartości zmiennych decyzyjnych nie ulegną zmianie

O ile zmieni się wartość FC jeżeli prawa
strona (RHS) odpowiedniego warunku
ograniczającego ulegnie zmianie o 1

Wartość RHS
warunków
ograniczających

Krańce przedziałów zmienności RHS,
przy których nie nastąpi zmiana zestawu
zmiennych decyzyjnych

Piotr Sawicki / Ekotransport i ekologistyka

26

30

Programowanie liniowe

Zastosowanie Solvera Excel / Analiza wrażliwości



Raport granic

Wartość (max)
funkcji celu

Optymalna wartość
zmiennych
decyzyjnych

Obszar rozwiązań dopuszczalnych
S – nie ulega zmianie DG=10, GG=10
H – ulega zmianie: DG=5, GG=66,96

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

14

Piotr Sawicki / Ekotransport i ekologistyka

27

30

Programowanie liniowe

Zastosowanie Solvera Excel / Analiza wrażliwości



Raport granic –
interpretacja dolnej i górnej
granicy

H

0

20

100

140

S

20

100

120

5

H ≥ 5

S ≤ 100

(0;130)

(86,7; 0)

6S + 4H ≤ 520

(126,3; 0)

S ≥ 10

19S +33H ≤ 2 400

H ≤ 75

75

(10; 66,96)

(10; 5)

Z(min)=59.850

Z(max)=448.400

Piotr Sawicki / Ekotransport i ekologistyka

28

30

Programowanie
liniowe

Programowanie
całkowitoliczbowe

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

15

Piotr Sawicki / Ekotransport i ekologistyka

29

30

Programowanie całkowitoliczbowe

Istota



Programowanie całkowitoliczbowe

problem z liniową funkcja celu i ograniczeniami

niektóre lub wszystkie zmienne decyzyjne muszą być

– nieujemne

i

– całkowite

możliwe jest zastosowanie metody SIMPLEX do rozwiązania zadania programowania
całkowitoliczbowego

– jeżeli rozwiązanie optymalne zawiera wartości ułamkowe (rozwiązanie niecałowitoliczbowe)

ułamkowa część rozwiązania jest

{

zaokrąglana do najbliższej liczby całkowitej

{

pomijana

– zaokrąglenie lub pominięcie części ułamkowej powoduje, że rozwiązanie może być

nieoptymalne

programowanie liniowe

Piotr Sawicki / Ekotransport i ekologistyka

30

30

Programowanie całkowitoliczbowe

Istota



Analiza rozwiązania zadania
sformułowanego w postaci
zadania programowania
liniowego

Max Z(S, H) = 2.850

S

+ 6.270

H

H

0

20

100

140

S

20

100

120

5

H = 5

S = 100

6S + 4H = 520

S = 10

19S +33H = 2 400

H = 75

75

Z

max

= 448.400

(10; 66,96)

Obszar dalszej analizy

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

16

Piotr Sawicki / Ekotransport i ekologistyka

31

30

Programowanie całkowitoliczbowe

Istota



Analiza rozwiązania zadania
sformułowanego w postaci
zadania programowania
liniowego

Max Z(S, H) = 2.850

S

+ 6.270

H

S = 10

19S +33H = 2 400

H = 75

S

0 1 2 3 4 5 6 7 8 9 10 11 12 13

H

73

72
71

70
69

68

67

66
65

74

75

(10; 66,96)

Obszar rozwiązań dopuszczalnych

i

„siatka” rozwiązań

całkowitoliczbowych

(10,66); Z = 442.320

(10,67); Z = 448.590

(10; 66,96); Z = 448.400

(11,66); Z = 445.170

Piotr Sawicki / Ekotransport i ekologistyka

32

30

Programowanie całkowitoliczbowe

Istota



Programowanie całkowitoliczbowe znajduje zastosowanie przy
rozwiązywaniu problemów alokacji (przydziału) ograniczonych

zasobów

zasobów

do

konkurencyjnych

operacji

operacji

, w przypadku gdy niektóre lub wszystkie zmienne

są liczbami całkowitymi

ustalenie liczebności taboru

określenie liczby obsług pojazdów w skali roku

sprzedaż pojazdów przez przedstawiciela handlowego



Problemy sformułowane w kategoriach programowania całkowitoliczbowego
najczęściej polegają na

maksymalizacji

– zysku
– efektywności
– …innych maksymentów

minimalizacji

– kosztów
– czasu
– …innych minimentów

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

17

Piotr Sawicki / Ekotransport i ekologistyka

33

30

Programowanie całkowitoliczbowe

Ogólne sformułowanie



Ogólne sformułowanie zadania programowania całkowitoliczbowego

funkcja celu
Max Z = c

1

x

x

1

1

+ c

2

x

x

2

2

+ ... + c

n

x

x

n

n

ograniczenia

(ograniczone zasoby)

a

11

x

x

1

1

+ a

12

x

x

2

2

+ ... + a

1n

x

x

n

n

b

1

a

21

x

x

1

1

+ a

22

x

x

2

2

+ ... + a

2n

x

x

n

n

b

2

...

a

m1

x

x

1

1

+ a

m2

x

x

2

2

+ ... + a

mn

x

x

n

n

b

m

x

x

1

1

0,

x

x

2

2

0, ...,

x

x

n

n

0

x

x

1

1

,

x

x

2

2

, ...,

x

x

n

n

C

c

j

– jednostkowy przyrost j – tej czynności w ocenie globalnej Z (j = 1, 2, ...,n)

b

i

ilość i – tego zasobu dostępnego do alokacji do czynności (i = 1, 2, ...,m)

a

ij

– ilość i – tego zasobu konsumowanego przez j – tą czynność

c

j

, b

i

, a

ij

parametry;

parametry;

x

1

, x

2

, ..., x

3

zmienne decyzyjne

zmienne decyzyjne

Piotr Sawicki / Ekotransport i ekologistyka

34

30

Programowanie
całkowitoliczbowe
Metoda rozgałęzień
i ograniczeń
(branch-and-bound)

Programowanie
całkowitoliczbowe
Metoda rozgałęzień
i ograniczeń
(branch-and-bound)

Podsumowanie

Podsumowanie

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

18

Piotr Sawicki / Ekotransport i ekologistyka

35

30

Programowanie całkowitoliczbowe

Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń



Istota metody rozgałęzień i ograniczeń (RiO)

dwufazowa metoda rozwiązywania problemów sformułowanych jako zadanie
programowania całkowitoliczbowego

– faza I Æ rozgałęzień

polega na systematycznym podziale pierwotnego obszaru rozwiązań dopuszczalnych (ORD)
na mniejsze obszary (podobszary)

– faza II Æ ograniczeń

polega na przyjęciu zasady, że

{

rozwiązanie uzyskane przy pominięciu warunku całkowitoliczbowości zmiennych
decyzyjnych stanowi górne ograniczenie wartości FC

{

każdy punkt należący do ORD o współrzędnych całkowitoliczbowych wyznacza dolną
granicę wartości FC



Analiza metody rozgałęzień i ograniczeń zostanie przeprowadzona na
przykładzie przypadku FLS

Piotr Sawicki / Ekotransport i ekologistyka

36

30

Programowanie całkowitoliczbowe

Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń



Zakładamy, że rozwiązanie problemu z pominięciem warunku o
całkowitoliczbowym charakterze zmiennych decyzyjnych jest znane

funkcja celu

Max Z(S, H) = 2.850

S

+ 6.270

H

wartość zmiennych decyzyjnych (wartości optymalne)

S

= 10

H

= 66,96

wartość funkcji celu Æ maksymalny zysk ze sprzedaży wózków widłowych 20S i 45H

Max Z = 448.400 €

należy przyjąć, że żadne całkowitoliczbowe rozwiązanie problemu FLS nie może
osiągnąć rozwiązania wyższego niż 448.400 Æ wartość ta stanowi górne
ograniczenie
wartości FC



Metoda RiO zakłada, że rozwiązanie leży w obszarze wyznaczonym przez
górne i dolne przybliżenia aktualnej wartości niecałkowitoliczbowej zmiennej
decyzyjnej

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

19

Piotr Sawicki / Ekotransport i ekologistyka

37

30

Programowanie całkowitoliczbowe

Istota



Analiza obszaru rozwiązań dopuszczalnych

H

0

20

100

140

S

20

100

120

5

H = 5

S = 100

6S + 4H = 520

S = 10

19S +33H = 2 400

H = 75

75

Z

max

= 448.400

(10; 66,96)

Obszar dalszej analizy

Piotr Sawicki / Ekotransport i ekologistyka

38

30

Programowanie całkowitoliczbowe

Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń



Analiza rozwiązania

skoro S = 10 a H = 66,96
to rozwiązania należące do
C poszukać należy w
podobszarach, w którym H
spełnia zależność:
66 ≥ (H=66,96) ≥ 67

podział na dwa podobszary

– R

1

: H ≤ 66

– R

2

: H ≥ 67

(10; 66,96); Z = 448.400

S

10 11 12 13 14 15 16 17 18 19

H

68

67

66

65
64

63

62

61
60

69

70

S = 10

19S +33H = 2 400

R

0

H ≥67

H ≤ 66

S = 10
H = 66,96
Z=448.400

R

0

S = ?
H = ?
Z = ?

R

1

S = ?
H = ?
Z = ?

R

2

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

20

Piotr Sawicki / Ekotransport i ekologistyka

39

30

Programowanie całkowitoliczbowe

Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń



Analiza obszarów R

1

i R

2

analiza R

1

jeżeli H = 66, to powstają
dwa punkty

– H = 66 i S = 10

Z = 442.320

– oraz

H = 66
19S + 33H = 2.400
S = 11,68
stąd
H = 66 i S = 11,68
Z = 447.108

analiza R

2

obszar R

2

stanowi punkt o

współrzędnych S=10 i
H = 67

– punkt ten znajduje się

poza ORD

(10; 67)

S

10 11 12 13 14 15 16 17 18 19

H

68

67

66

65
64

63

62

61
60

69

70

S = 10

19S +33H = 2.400

R

1

H ≥67

H ≤ 66

R

2

(10; 66)

{

(11,68; 66)

Piotr Sawicki / Ekotransport i ekologistyka

40

30

Programowanie całkowitoliczbowe

Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń



Analiza obszarów R

1

i R

2

..cd

analiza rozgałęzień

jeżeli S = 11,68 to wartość
całkowita S będzie
poszukiwana w przedziale
11 ≥ (S=11,68) ≥ 12

– R

3

: S ≤ 11

– R

4

: S ≥ 12

(10; 67)

S

10 11 12 13 14 15 16 17 18 19

H

68

67

66

65
64

63

62

61
60

69

70

S = 10

19S +33H = 2.400

R

1

H ≥67

H ≤ 66

R

2

(10; 66)

(11,68; 66)

S = 10
H = 66,96
Z=448.400

R

0

S = 11,68
H = 66
Z = 447.108

R

1

poza ORD

R

2

S ≤11

S ≥12

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

21

Piotr Sawicki / Ekotransport i ekologistyka

41

30

Programowanie całkowitoliczbowe

Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń



Analiza obszarów R

3

i R

4

analiza obszaru R

3

dwa punkty charakterystyczne

– S = 10 i H = 66

Z = 442.320

– oraz

S = 11 i H = 66
Z = 445.170

analiza obszaru R

4

– jeden punkt

S = 12
19S + 33H = 2.400
H = 65,81
S = 12 i H = 65,81
Z = 446.828,7

S

10 11 12 13 14 15 16 17 18 19

H

68

67

66

65
64

63

62

61
60

69

70

S = 10

19S +33H = 2.400

H ≥67

H ≤ 66

(10; 66)

(11, 66)

R

3

R

4

S ≤11

S ≥12

{

(12, 65;81)

Piotr Sawicki / Ekotransport i ekologistyka

42

30

Programowanie całkowitoliczbowe

Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń



Analiza obszarów R

3

i R

4

..cd

analiza rozgałęzienia obszaru
R

1

na R

3

i R

4

jeżeli H = 65,81, to całkowita
wartość H poszukiwana będzie
w przedziale
65 ≥ (H=65,81) ≥ 66

– R

5

: H ≤ 65

– R

6

: H ≥ 66

S

10 11 12 13 14 15 16 17 18 19

H

68

67

66

65
64

63

62

61
60

69

70

S = 10

19S +33H = 2.400

H ≥66

(10; 66)

(11, 66)

R

3

R

4

S ≤11

S ≥12

(12, 65;81)

S = 11
H = 66
Z = 445.170

R

3

S = 12
H = 65,81
Z = 446.828,7

R

4

S = 11,68
H = 66
Z=447.108

R

1

H ≤ 65

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

22

Piotr Sawicki / Ekotransport i ekologistyka

43

30

Programowanie całkowitoliczbowe

Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń



Analiza obszarów R

5

i R

6

analiza obszaru R

5

2 punkty charakterystyczne

– S = 12 i H = 65

Z = 441.750

– oraz

H = 65
19S + 33H = 2400
S = 13,42
jeżeli S = 13,42 i H = 65
to Z = 445.797

analiza obszaru R

6

– jeden punkt

S = 12 i H = 65

– punkt znajduje się poza ORD

S

10 11 12 13 14 15 16 17 18 19

H

68

67

66

65
64

63

62

61
60

69

70

S = 10

19S +33H = 2.400

H ≥66

(10; 66)

R

3

R

4

S ≤11

S ≥12

(13,42; 65)

H ≤ 65

R

5

{

R

6

Piotr Sawicki / Ekotransport i ekologistyka

44

30

Programowanie całkowitoliczbowe

Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń



Analiza obszarów R

5

i R

6

…cd

analiza rozgałęzień obszaru
R

4

na R

5

i R

6

jeżeli S=13,42, to całkowita
wartość S poszukiwana będzie
w przedziale wartości

13 ≥ (S=13,42) ≥ 14

– R

7

: H ≤ 13

– R

8

: H ≥ 14

S = 13,42
H = 65
Z = 445.797

R

5

poza ORD

R

6

S = 12
H = 65,81
Z=447.108

R

4

S

10 11 12 13 14 15 16 17 18 19

H

68

67

66

65
64

63

62

61
60

69

70

S = 10

19S +33H = 2.400

H ≥66

(10; 66)

R

3

R

4

S ≤11

S ≥12

(13,42; 65)

H ≤ 65

R

5

R

6

S ≥14

S ≤ 13

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

23

Piotr Sawicki / Ekotransport i ekologistyka

45

30

Programowanie całkowitoliczbowe

Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń



Analiza obszarów R

7

i R

8

analiza obszaru R

7

2 punkty charakterystyczne

– S = 12 i H = 65

Z = 441.750

– oraz

S = 13 i H = 65
Z = 444.600

analiza obszaru R

8

– punkt o współrzędnych

S = 14
19S + 33H = 2.400
H = 64,67
jeżeli S = 14 i H = 64,67
to Z = 445.380,9

S

10 11 12 13 14 15 16 17 18 19

H

68

67

66

65
64

63

62

61
60

69

70

S = 10

19S +33H = 2.400

(12; 65)

R

5

R

7

R

8

(13; 65)

{

(14; 64,67)

Piotr Sawicki / Ekotransport i ekologistyka

46

30

Programowanie całkowitoliczbowe

Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń



Analiza obszarów R

7

i R

8

analiza rozgałęzień obszaru
R

5

na R

7

i R

8

S

10 11 12 13 14 15 16 17 18 19

H

68

67

66

65
64

63

62

61
60

69

70

S = 10

19S +33H = 2.400

(12; 65)

R

5

R

7

R

8

(13; 65)

(14; 64,67)

S = 13
H = 65
Z = 444.600

R

7

S = 14
H = 64,67
Z = 445.380,9

R

8

S = 13,42
H = 65
Z=445.797

R

5

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

24

Piotr Sawicki / Ekotransport i ekologistyka

47

30

Programowanie całkowitoliczbowe

Proces rozwiązywania problemu / Metoda rozgałęzień i ograniczeń



Analiza wszystkich rozgałęzień

poszukiwanie kolejnych rozwiązań
całkowitoliczbowych nie ma
uzasadnienia Æ wartość FC ulega
systematycznemu obniżaniu

rozwiązaniem optymalnym jest
S = 11
H = 66
wówczas
Z = 445.170€

S = 10
H = 66,96
Z=448.400

R

0

S = 11,68
H = 66
Z = 447.108

R

1

poza ORD

R

2

S = 11
H = 66
Z = 445.170

R

3

S = 12
H = 65,81
Z = 446.828,7

R

4

S = 13,42
H = 65
Z = 445.797

R

5

poza ORD

R

6

S = 13
H = 65
Z = 444.600

R

7

S = 14
H = 64,67
Z = 445.380,9

R

8

Piotr Sawicki / Ekotransport i ekologistyka

48

30

Programowanie matematyczne

Podsumowanie

Alokacja niepodzielnych
zasobów do konkurencyjnych
prac (zadań)

Alokacja podzielnych
zasobów do konkurencyjnych
prac (zadań)

Zastosowanie

Metoda graficzna,
zmodyfikowana metoda
SIMPLEX, metoda ograniczeń
i rozgałęzień
Solver MS Excel

Metoda graficzna, metoda
SIMPLEX

Solver MS Excel

Metoda rozwiązania

liniowa – addytywna

liniowa - addytywna

Model matematyczny:
Funkcja celu

liniowa - addytywna

liniowa - addytywna

Model matematyczny:
Funkcja celu

liniowa – w pierwszej potędze

programowanie
liniowe

liniowa – w pierwszej potędze

postać zmiennej
decyzyjnej

programowanie
całkowitoliczbowe

parametr

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

25

Piotr Sawicki / Ekotransport i ekologistyka

49

30



Przykłady obszarów rozwiązań
dopuszczalnych

funkcja celu może przyjmować
nieograniczone wartości

obszar rozwiązań dopuszczalnych jest
pusty

Programowanie matematyczne

Podsumowanie



Podstawowe pojęcia do zapamiętania

rozwiązanie dopuszczalne
rozwiązanie dla którego spełnione są
wszystkie ograniczenia

rozwiązania niedopuszczalnych
rozwiązania znajdujące się poza
obszarem rozwiązań dopuszczalnych

rozwiązanie optymalne (optimum) –
rozwiązanie dopuszczalne osiągające
wartość ekstremalną

ograniczenie aktywne – ograniczenie
wyznaczające obszar rozwiązań
dopuszczalnych

ograniczenie nieaktywne
ograniczenie nie należące do obszaru
rozwiązań dopuszczalnych

Piotr Sawicki / Ekotransport i ekologistyka

50

30

Programowanie matematyczne

Podsumowanie



Warunki sformułowania problemu w postaci zadania programowania
liniowego i całkowitoliczbowego

identyfikacja ograniczonych zasobów (w przeciwnym wypadku nie ma problemu)

– ograniczona liczba pracowników,
– ograniczona dostępność środków transportowych,
– limitowane zasoby finansowe,…

określony kierunek zmiany wartości funkcji celu

– maksymalizacja zysku
– minimalizacja kosztów (czasu transportu)

liniowość funkcji celu i ograniczeń

– np.: zysk z kursu 2 zestawów drogowych typu A jest dwa razy większy jak zysk z kursu

jednego zestawu drogowego typu A

podzielność zasobów dla programowania liniowego

– 0,5 dm

3

oleju napędowego

– 45,3 kWh zużytej energii

niepodzielność zasobów dla programowania całkowitoliczbowego

– przejazd 5 zestawów drogowych w relacji: Poznań-Warszawa

background image

Ekotrasport i ekologistyka

Piotr Sawicki / PP/ WMRiT

26

Ekotransport i ekologistyka

Ekotransport i ekologistyka

Piotr Sawicki

Piotr Sawicki

Wydział Maszyn Roboczych i Transportu
pok. 719, tel. 665 22 30
E-mail: piotr.sawicki@put.poznan.pl
URL: www.put.poznan.pl/~piotrs

Wydział Maszyn Roboczych i Transportu
pok. 719, tel. 665 22 30
E-mail: piotr.sawicki@put.poznan.pl
URL: www.put.poznan.pl/~piotrs

Programowanie
liniowe
i całkowitoliczbowe

Programowanie
liniowe
i całkowitoliczbowe

Alokacja zasobów

Alokacja zasobów


Wyszukiwarka

Podobne podstrony:
Algebra 2 02 arytmetyka liczb całkowitych
javaczeni, 08.02.21 Egzamin Progr, Zad
Wyk 02 Pneumatyczne elementy
02 OperowanieDanymiid 3913 ppt
02 Boża radość Ne MSZA ŚWIĘTAid 3583 ppt
OC 02
PD W1 Wprowadzenie do PD(2010 10 02) 1 1
02 Pojęcie i podziały prawaid 3482 ppt
WYKŁAD 02 SterowCyfrowe
02 filtracja
02 poniedziałek
21 02 2014 Wykład 1 Sala
Genetyka 2[1] 02

więcej podobnych podstron