Monika Rapacz

Gr lab 8

Metody Optymalizacji Dyskretnej

Przepływy w sieciach
Sprawozdanie nr 7

1. Zapis modelu matematycznego w AMPL-u:

`zmienna decyzyjna

var x {i in wierz, j in wierz} integer>=0;

`funkcja celu

minimize z: sum{i in wierz, j in wierz:(i,j) in kraw}c[i,j]*x[i,j];

`ograniczenia

subject to ogr1 {i in pocz}:sum{j in wierz:(i,j) in kraw}x[i,j]-sum{j in wierz:(j,i) in kraw}x[i,j]=a[i];

subject to ogr2 {i in posr}: sum{j in wierz:(i,j) in kraw}x[i,j] - sum{j in wierz:(j,i) in kraw}x[i,j]=0;

subject to ogr3 {i in konc}: sum{j in wierz:(i,j) in kraw}x[i,j] - sum{j in wierz:(j,i) In kraw}x[i,j]=-b[i];

subject to ogr4 {i in wierz, j in wierz:(i,j) in kraw}: x[i,j]<=d[i,j];

param a:= W1 60 W2 70 W3 45; `parametr a_i - zapas towarów

param b:= W6 50 W7 20 W8 27 `parametr b_i - zapotrzebowanie na towar

`parametr c_ij - koszt przesłania jednostki towaru przez łuk (i,j)

`parametr d_ij - pojemność każdego łuku (i,j)

param: c d := W1 W4 2 49 W1 W5 3 45 W2 W4 3 35 W2 W5 2 19 W3 W4 4 34 W3 W5 2 24 W4 W6 2 45 W4 W7 3 45 W4 W8 2 25 W5 W6 3 45 W5 W7 2 34 W5 W8 3 42;

2. Analiza otrzymanych wyników.

• Minimalny koszt przepływu wynosi 416 .

Objective: fc = 416 (MINimum) 416 (LP)

x[W1,W4] * 49

x[W1,W5] * 0

x[W2,W4] * 5

x[W2,W5] * 19

x[W3,W4] * 0

x[W3,W5] * 24

x[W4,W6] * 45

x[W4,W7] * 0

x[W4,W8] * 9

x[W5,W6] * 5

x[W5,W7] * 20

x[W5,W8] * 18

• Ograniczenie 1 informuje, iż ilość towaru w punktach początkowych nie może przekroczyć odpowiednio zapasów w wierzchołkach początkowych: 49, 24, 24.

Ogr1[W1] 49 60

Ogr1[W2] 24 70

Ogr1[W3] 24 45

• Ograniczenie 2 informuje, iż ilość towaru pobieranego i zapotrzebowanego musi się równoważyć.

Ogr2[W4] 0

Ogr2[W5] 0

• Ograniczenie 3 informuje, iż zapotrzebowanie na towar w punktach końcowych nie może przekroczyć odpowiednio -50, -20, -27.

Ogr4[W6] -50

Ogr4[W7] -20

Ogr4[W8] -27

• Ograniczenie 4 informuje, iż przepływ towarów przez łuk nie może być większy niż jego przepustowość.

x[i,j]<=d[i,j]

ogr1[W1,W4] 49 49

ogr1[W1,W5] 0 45

ogr1[W2,W4] 5 35

ogr1[W2,W5] 19 19

ogr1[W3,W4] 0 34

ogr1[W3,W5] 24 24

ogr1[W4,W6] 45 45

ogr1[W4,W7] 0 45

ogr1[W4,W8] 9 25

ogr1[W5,W6] 5 45

ogr1[W5,W7] 20 34

ogr1[W5,W8] 18 42

2

---