Program_calkow.pdf

(503 KB) Pobierz

Microsoft PowerPoint - ZSTD_03_Programowanie ca³kowitoliczb.ppt

Programowanie

całkowitoliczbowe

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

Plan prezentacji

Istota programowania całkowitoliczbowego

• informacje wprowadzające

• przykładowe problemy

Ogólne sformułowanie zadania programowania całkowitoliczbowego

Programowanie całkowitoliczbowe na przykładzie

• identyfikacja problemu

• konstrukcja modelu matematycznego

• rozwiązanie problemu

• interpretacja rozwiązania

Procedura rozwiązywania zadania programowania całkowitoliczbowego

• metoda płaszczyzn odcinających

• metoda rozgałęzień i ograniczeń

Podsumowanie

Piotr Sawicki / Programowanie całkowitoliczbowe

2

141786611.051.png

141786611.062.png

141786611.065.png

141786611.066.png

141786611.001.png

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 / Programowanie całkowitoliczbowe

3

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

140

S=10

S = 100

100

6S + 4H = 520

75

H=75

Z max = 448.400

(10; 66,96)

19S +33H = 2 400

Obszar dalszej analizy

20

5

H=5

0

20

100 120

S

Piotr Sawicki / Programowanie całkowitoliczbowe

4

141786611.002.png

141786611.003.png

141786611.004.png

141786611.005.png

141786611.006.png

141786611.007.png

141786611.008.png

141786611.009.png

141786611.010.png

141786611.011.png

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

S=10

H=75

75

74

73

72

71

70

69

68

67

66

65

19S +33H = 2 400

„siatka” rozwiązań

całkowitoliczbowych

(10; 66,96); Z = 448.400

(10,67); Z = 448.590

(10; 66,96)

i

(10,66); Z = 442.320

(11,66); Z = 445.170

Obszar rozwiązań dopuszczalnych

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

S

Piotr Sawicki / Programowanie całkowitoliczbowe

5

Programowanie całkowitoliczbowe

Istota

Programowanie całkowitoliczbowe znajduje zastosowanie przy

rozwiązywaniu problemów alokacji (przydziału) ograniczonych zasobów

zasobów do

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

Piotr Sawicki / Programowanie całkowitoliczbowe

6

konkurencyjnych operacji

141786611.012.png

141786611.013.png

141786611.014.png

141786611.015.png

141786611.016.png

141786611.017.png

141786611.018.png

141786611.019.png

141786611.020.png

141786611.021.png

Programowanie całkowitoliczbowe

Ogólne sformułowanie

Ogólne sformułowanie zadania programowania całkowitoliczbowego

• 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

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

zmienne decyzyjne

Piotr Sawicki / Programowanie całkowitoliczbowe

7

Programowanie całkowitoliczbowe

Proces rozwiązywania problemu

Proces rozwiązywania

problemu decyzyjnego

Przebieg procesu

• identyfikacja problemu decyzyjnego

• konstrukcja modelu matematycznego

• rozwiązanie problemu

• interpretacja rozwiązania

Analiza procesu rozwiązywania problemu

sformułowanego w postaci zadania programowania

całkowitoliczbowego Æ analiza przypadku FLS

• identyfikacja problemu i konstrukcja modelu

matematycznego nie ulega zmianie

• rozwiązanie problemu decyzyjnego

– metoda płaszczyzn odcinających (metoda Gomory’ego)

– metoda rozgałęzień i ograniczeń ( ang . branch-and-bound)

• interpretacja rozwiązania

Identyfikacja problemu

decyzyjnego

Model matematyczny

problemu

Dobór metody rozw.

Rozwiązanie problemu

Interpretacja rozw.

Analiza wrażliwości

Piotr Sawicki / Programowanie całkowitoliczbowe

8

parametry;

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

141786611.022.png

141786611.023.png

141786611.024.png

141786611.025.png

141786611.026.png

141786611.027.png

141786611.028.png

141786611.029.png

141786611.030.png

141786611.031.png

141786611.032.png

141786611.033.png

141786611.034.png

141786611.035.png

141786611.036.png

141786611.037.png

141786611.038.png

141786611.039.png

141786611.040.png

141786611.041.png

141786611.042.png

141786611.043.png

141786611.044.png

141786611.045.png

141786611.046.png

141786611.047.png

141786611.048.png

141786611.049.png

141786611.050.png

141786611.052.png

141786611.053.png

141786611.054.png

Programowanie całkowitoliczbowe

Metoda płaszczyzn odcinających –

metoda Gomory’ego

Piotr Sawicki / Programowanie całkowitoliczbowe

9

Programowanie całkowitoliczbowe

Proces rozwiązywania problemu / Metoda Gomory’ego

Założenia metody Gomory’ego

• metoda bazuje na redukcji Gaussa-Jordana, stosowanej w metodzie SIMPLEX

• metoda rozpoczyna się od rozwiązywania problemu z pominięciem ograniczenia o

całkowitoliczbowym charakterze zmiennych decyzyjnych

problem decyzyjny

rozwiązanie optymalne

(metoda SIMPLEX)

czy rozwiązanie jest

całkowitoliczbowe?

Nie

dodatkowe ograniczenia

„płaszczyzn odcinających”

Tak

problem rozwiązany

Piotr Sawicki / Programowanie całkowitoliczbowe

10

141786611.055.png

141786611.056.png

141786611.057.png

141786611.058.png

141786611.059.png

141786611.060.png

141786611.061.png

141786611.063.png

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