Program_lin.pdf

(958 KB) Pobierz

Microsoft PowerPoint - Mot_Programowanie liniowe.ppt

Programowanie liniowe

Piotr Sawicki

Wydział Maszyn Roboczych i Transportu

pok. 719, tel. 665 22 30, 665 21 29

E-mail: piotr.sawicki@put.poznan.pl

URL: www.put.poznan.pl/~piotrs

Maszyn Roboczych i Transportu

pok. 719, tel. 665 22 30, 665 21 29

pok. 719, tel. 665 22 30, 665 21 29

E- mail

mail :

: piotr.sawicki@put.poznan.pl

piotr.sawicki@put.poznan.pl

URL: www.put.poznan.pl

www.put.poznan.pl/~ piotrs

piotrs

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

• metoda algebraiczna - SIMPLEX

• zastosowanie Solvera MS Excel

Podsumowanie

Piotr Sawicki / Programowanie liniowe

2

52

Piotr Sawicki

Wydzia

Wydzia ł ł Maszyn Roboczych i Transportu

URL:

141786681.065.png

141786681.076.png

141786681.087.png

141786681.098.png

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

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

najczęściej polegają na

• maksymalizacji zysku

• minimalizacji kosztów

Piotr Sawicki / Programowanie liniowe

3

52

Programowanie liniowe

Istota

Problem maksymalizacji zysku

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

transportowych

• 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

Piotr Sawicki / Programowanie liniowe

4

52

konkurencyjnych operacji

141786681.001.png

141786681.012.png

141786681.017.png

141786681.018.png

141786681.019.png

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

Min

Z

(

x

1

,

x

2

)

=

2

x

1

+

3

x

2

2

Min

Z

(

x

,

x

)

=

3

1

2

x

+

x

1

2

2

x

+ x

3

2

2

≤

45

1

• sformułowanie równań i nierówności

w postaci liniowej

Min

Z

(

x

1

,

x

2

)

=

2

x

1

+

x

2

3

x

1

+ x

4

x

2

3

≥

10

• liniowość w praktyce oznacza, że

zależność funkcyjna pomiędzy

zmiennymi decyzyjnymi posiada

graficzną reprezentację w postaci

linii prostych

Piotr Sawicki / Programowanie liniowe

5

52

Programowanie liniowe

Ogólne sformułowanie

Ogólne sformułowanie zadania programowania liniowego

• funkcja celu

Max Z = c 1 x 1 + c 2 x 2 + ... + c n x n

• ograniczenia (ograniczone zasoby)

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 1 ≥ 0, x 2 ≥ 0, ..., x 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;

zmienne decyzyjne

Piotr Sawicki / Programowanie liniowe

6

52

parametry;

x 1 , x 2 , ..., x 3 – zmienne decyzyjne

141786681.020.png

141786681.021.png

141786681.022.png

141786681.023.png

141786681.024.png

Programowanie liniowe

Proces rozwiązywania problemu

Proces rozwiązywania

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ć?

Identyfikacja problemu

decyzyjnego

Model matematyczny

problemu

Dobór metody rozw.

Rozwiązanie problemu

Interpretacja rozw.

Analiza wrażliwości

Piotr Sawicki / Programowanie liniowe

7

52

Programowanie liniowe

Proces rozwiązywania problemu

Proces rozwiązywania

problemu decyzyjnego

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

Identyfikacja problemu

decyzyjnego

Model matematyczny

problemu

Dobór metody rozw.

Rozwiązanie problemu

Interpretacja rozw.

Analiza wrażliwości

Piotr Sawicki / Programowanie liniowe

8

52

141786681.025.png

141786681.026.png

141786681.027.png

141786681.028.png

141786681.029.png

141786681.030.png

141786681.031.png

141786681.032.png

141786681.033.png

141786681.034.png

141786681.035.png

141786681.036.png

141786681.037.png

141786681.038.png

141786681.039.png

141786681.040.png

141786681.041.png

141786681.042.png

141786681.043.png

141786681.044.png

141786681.045.png

141786681.046.png

141786681.047.png

141786681.048.png

141786681.049.png

141786681.050.png

141786681.051.png

141786681.052.png

141786681.053.png

141786681.054.png

141786681.055.png

141786681.056.png

141786681.057.png

141786681.058.png

141786681.059.png

141786681.060.png

141786681.061.png

141786681.062.png

141786681.063.png

141786681.064.png

141786681.066.png

141786681.067.png

141786681.068.png

141786681.069.png

141786681.070.png

141786681.071.png

141786681.072.png

141786681.073.png

141786681.074.png

141786681.075.png

141786681.077.png

141786681.078.png

141786681.079.png

141786681.080.png

141786681.081.png

141786681.082.png

141786681.083.png

141786681.084.png

141786681.085.png

141786681.086.png

141786681.088.png

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

Identyfikacja problemu

decyzyjnego

Model matematyczny

problemu

Dobór metody rozw.

Rozwiązanie problemu

Interpretacja rozw.

Analiza wrażliwości

Piotr Sawicki / Programowanie liniowe

9

52

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

Piotr Sawicki / Programowanie liniowe

10

52

Proces rozwiązywania

problemu decyzyjnego

141786681.089.png

141786681.090.png

141786681.091.png

141786681.092.png

141786681.093.png

141786681.094.png

141786681.095.png

141786681.096.png

141786681.097.png

141786681.099.png

141786681.100.png

141786681.101.png

141786681.102.png

141786681.103.png

141786681.104.png

141786681.105.png

141786681.106.png

141786681.107.png

141786681.108.png

141786681.002.png

141786681.003.png

141786681.004.png

141786681.005.png

141786681.006.png

141786681.007.png

141786681.008.png

141786681.009.png

141786681.010.png

141786681.011.png

141786681.013.png

141786681.014.png

141786681.015.png

141786681.016.png

Plik z chomika:

Inne pliki z tego folderu:

Kopia Mrpd_Met_przydz_wielokr.pdf (245 KB)
Kopia Mrpd_Bud_sieci_transp.pdf (438 KB)
Kopia Mot_Prob_transp_wielokryt.pdf (747 KB)
Kopia Mot_Prob_transp.pdf (1862 KB)
Kopia Mot_01_Wskaz.pdf (973 KB)

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin