4Progr_calkowit.pdf

(566 KB) Pobierz

Microsoft PowerPoint - ZSTD_03_Programowanie całkowitoliczb.ppt

Zarządzanie systemami transportu drog.

Zarządzanie systemami

transportu drogowego

Programowanie

całkowitoliczbowe

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/~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/~piotr.sawicki

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

27

Piotr Sawicki, WMRiT, PP

1

Piotr Sawicki

399686658.380.png

399686658.391.png

399686658.402.png

399686658.413.png

399686658.001.png

399686658.012.png

399686658.023.png

399686658.034.png

399686658.045.png

Zarządzanie systemami transportu drog.

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

27

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

27

Piotr Sawicki, WMRiT, PP

2

399686658.056.png

399686658.067.png

399686658.078.png

399686658.089.png

399686658.100.png

399686658.111.png

399686658.122.png

399686658.133.png

399686658.144.png

399686658.155.png

399686658.166.png

399686658.177.png

399686658.188.png

399686658.199.png

399686658.210.png

399686658.221.png

399686658.232.png

399686658.243.png

399686658.254.png

399686658.265.png

399686658.276.png

399686658.287.png

399686658.298.png

399686658.309.png

399686658.320.png

399686658.331.png

399686658.342.png

399686658.353.png

399686658.363.png

399686658.364.png

399686658.365.png

399686658.366.png

399686658.367.png

399686658.368.png

399686658.369.png

399686658.370.png

399686658.371.png

399686658.372.png

399686658.373.png

399686658.374.png

399686658.375.png

399686658.376.png

399686658.377.png

399686658.378.png

399686658.379.png

399686658.381.png

399686658.382.png

399686658.383.png

399686658.384.png

399686658.385.png

399686658.386.png

399686658.387.png

399686658.388.png

399686658.389.png

399686658.390.png

399686658.392.png

399686658.393.png

399686658.394.png

399686658.395.png

399686658.396.png

399686658.397.png

399686658.398.png

399686658.399.png

399686658.400.png

399686658.401.png

399686658.403.png

399686658.404.png

399686658.405.png

399686658.406.png

399686658.407.png

399686658.408.png

399686658.409.png

399686658.410.png

399686658.411.png

399686658.412.png

399686658.414.png

399686658.415.png

399686658.416.png

399686658.417.png

399686658.418.png

399686658.419.png

399686658.420.png

399686658.421.png

399686658.422.png

399686658.423.png

399686658.002.png

399686658.003.png

399686658.004.png

399686658.005.png

399686658.006.png

399686658.007.png

399686658.008.png

399686658.009.png

399686658.010.png

399686658.011.png

399686658.013.png

399686658.014.png

399686658.015.png

399686658.016.png

399686658.017.png

399686658.018.png

399686658.019.png

399686658.020.png

399686658.021.png

399686658.022.png

399686658.024.png

399686658.025.png

399686658.026.png

399686658.027.png

399686658.028.png

399686658.029.png

399686658.030.png

399686658.031.png

399686658.032.png

399686658.033.png

399686658.035.png

399686658.036.png

399686658.037.png

399686658.038.png

399686658.039.png

399686658.040.png

399686658.041.png

399686658.042.png

399686658.043.png

399686658.044.png

399686658.046.png

399686658.047.png

399686658.048.png

399686658.049.png

399686658.050.png

399686658.051.png

399686658.052.png

399686658.053.png

399686658.054.png

399686658.055.png

399686658.057.png

399686658.058.png

399686658.059.png

399686658.060.png

399686658.061.png

399686658.062.png

399686658.063.png

399686658.064.png

399686658.065.png

399686658.066.png

399686658.068.png

399686658.069.png

399686658.070.png

399686658.071.png

399686658.072.png

399686658.073.png

399686658.074.png

399686658.075.png

399686658.076.png

399686658.077.png

399686658.079.png

399686658.080.png

399686658.081.png

399686658.082.png

399686658.083.png

399686658.084.png

399686658.085.png

399686658.086.png

399686658.087.png

399686658.088.png

399686658.090.png

399686658.091.png

399686658.092.png

399686658.093.png

399686658.094.png

399686658.095.png

399686658.096.png

399686658.097.png

399686658.098.png

399686658.099.png

399686658.101.png

399686658.102.png

399686658.103.png

399686658.104.png

399686658.105.png

399686658.106.png

399686658.107.png

399686658.108.png

399686658.109.png

399686658.110.png

399686658.112.png

399686658.113.png

399686658.114.png

399686658.115.png

399686658.116.png

399686658.117.png

399686658.118.png

399686658.119.png

399686658.120.png

399686658.121.png

399686658.123.png

399686658.124.png

399686658.125.png

399686658.126.png

399686658.127.png

399686658.128.png

399686658.129.png

399686658.130.png

399686658.131.png

399686658.132.png

399686658.134.png

399686658.135.png

399686658.136.png

399686658.137.png

399686658.138.png

399686658.139.png

399686658.140.png

399686658.141.png

399686658.142.png

399686658.143.png

399686658.145.png

399686658.146.png

399686658.147.png

399686658.148.png

399686658.149.png

399686658.150.png

399686658.151.png

399686658.152.png

399686658.153.png

399686658.154.png

399686658.156.png

399686658.157.png

399686658.158.png

399686658.159.png

399686658.160.png

399686658.161.png

399686658.162.png

399686658.163.png

399686658.164.png

399686658.165.png

399686658.167.png

399686658.168.png

399686658.169.png

399686658.170.png

399686658.171.png

399686658.172.png

399686658.173.png

399686658.174.png

399686658.175.png

399686658.176.png

399686658.178.png

399686658.179.png

399686658.180.png

399686658.181.png

399686658.182.png

399686658.183.png

399686658.184.png

399686658.185.png

399686658.186.png

399686658.187.png

399686658.189.png

399686658.190.png

399686658.191.png

399686658.192.png

399686658.193.png

399686658.194.png

399686658.195.png

399686658.196.png

399686658.197.png

399686658.198.png

399686658.200.png

399686658.201.png

399686658.202.png

399686658.203.png

399686658.204.png

399686658.205.png

399686658.206.png

399686658.207.png

399686658.208.png

399686658.209.png

399686658.211.png

399686658.212.png

399686658.213.png

399686658.214.png

399686658.215.png

399686658.216.png

399686658.217.png

399686658.218.png

399686658.219.png

Zarządzanie systemami transportu drog.

Programowanie całkowitoliczbowe

Istota

Analiza rozwiązania

problemu 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

27

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

konkurencyjnych operacji

Piotr Sawicki / Programowanie całkowitoliczbowe

6

27

Piotr Sawicki, WMRiT, PP

3

399686658.220.png

399686658.222.png

399686658.223.png

399686658.224.png

399686658.225.png

399686658.226.png

399686658.227.png

Zarządzanie systemami transportu drog.

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

27

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

27

Piotr Sawicki, WMRiT, PP

4

parametry;

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

399686658.228.png

399686658.229.png

399686658.230.png

399686658.231.png

399686658.233.png

399686658.234.png

399686658.235.png

399686658.236.png

399686658.237.png

399686658.238.png

399686658.239.png

399686658.240.png

399686658.241.png

399686658.242.png

399686658.244.png

399686658.245.png

399686658.246.png

399686658.247.png

399686658.248.png

399686658.249.png

399686658.250.png

399686658.251.png

399686658.252.png

399686658.253.png

399686658.255.png

399686658.256.png

399686658.257.png

399686658.258.png

399686658.259.png

399686658.260.png

399686658.261.png

399686658.262.png

399686658.263.png

399686658.264.png

399686658.266.png

399686658.267.png

399686658.268.png

399686658.269.png

399686658.270.png

399686658.271.png

399686658.272.png

399686658.273.png

399686658.274.png

399686658.275.png

399686658.277.png

399686658.278.png

399686658.279.png

399686658.280.png

399686658.281.png

399686658.282.png

399686658.283.png

399686658.284.png

399686658.285.png

399686658.286.png

399686658.288.png

399686658.289.png

399686658.290.png

399686658.291.png

399686658.292.png

399686658.293.png

399686658.294.png

399686658.295.png

399686658.296.png

399686658.297.png

399686658.299.png

399686658.300.png

399686658.301.png

399686658.302.png

399686658.303.png

399686658.304.png

399686658.305.png

399686658.306.png

399686658.307.png

399686658.308.png

399686658.310.png

399686658.311.png

399686658.312.png

399686658.313.png

399686658.314.png

399686658.315.png

399686658.316.png

399686658.317.png

399686658.318.png

399686658.319.png

399686658.321.png

399686658.322.png

399686658.323.png

399686658.324.png

399686658.325.png

399686658.326.png

399686658.327.png

399686658.328.png

399686658.329.png

399686658.330.png

399686658.332.png

399686658.333.png

399686658.334.png

399686658.335.png

399686658.336.png

399686658.337.png

399686658.338.png

399686658.339.png

399686658.340.png

399686658.341.png

399686658.343.png

399686658.344.png

399686658.345.png

399686658.346.png

399686658.347.png

399686658.348.png

399686658.349.png

399686658.350.png

399686658.351.png

Zarządzanie systemami transportu drog.

Programowanie całkowitoliczbowe

Metoda rozgałęzień i ograniczeń

ang. branch-and-bound

Piotr Sawicki / Programowanie całkowitoliczbowe

9

27

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

10

27

Piotr Sawicki, WMRiT, PP

5

399686658.352.png

399686658.354.png

399686658.355.png

399686658.356.png

399686658.357.png

399686658.358.png

399686658.359.png

399686658.360.png

399686658.361.png

399686658.362.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin