ZADANIE – PRZYDIAŁU

S – zbiór numerów typów środka transportowego S={w} ; S={w: w=1,2,3,…,W} S={1,2,3}

Z – zbiór numerów zadań przewozowych Z={z: z=1,2,3,…,Z} ; Z={1,2,3}

Wektor liczby środków transportowych różnych typów L=[l(w) : w є S] ; L=[l(1), l(2), l(3)]=[3,4,3]

Wektor ładowności środków transportowych P=[p(w) : w є S] ; P=[p(1), p(2), p(3)]=[10,12,8]

Wektor jednostkowego kosztu przewozu śr. trans. K=[k(w) : w є S] ; K=[k(1), k(2), k(3)]=[6,4,3]

Wektor wielkości przewozu Q=[q(z) : z є Z] ; Q=[q(1), q(2), q(3)]=[25,40,30]

Wektor odległości D=[d(z) : z є Z] ; D=[d(1), d(2), d(3)]=[220,180,240]

Zmienne decyzyjne X=[x(w,z): w є S, z є Z] x(w,z) є C⁺ u {0} , C⁺ ∪ {0}=N

x(w,z) – liczba środków transportowych typu w wykorzystanych w zadaniu z $X = \begin{matrix} x(1,1) & x(1,2) & x(1,3) \\ x(2,1) & x(2,2) & x(2,3) \\ x(3,1) & x(3,2) & x(3,3) \\ \end{matrix}$

OGRANICZENIA:

1)Na typ zmiennych decyzyjnych ∀ w є S, ∀z є Z x(w,z) є N

x(1,1) є N, x(1,2) є N, x(1,3) є N, x(2,1) є N, x(2,2) є N, x(2,3) є N, x(3,1) є N, x(3,2) є N, x(3,3) є N

2) Na Realizację zadań dla każdego z є Z; $\sum_{\text{wϵs}}^{}{x\left( w,z \right) \bullet p(w) \geq q(z)}$

z=1 $\sum_{\text{wϵs}}^{}{x\left( w,1 \right) \bullet p(w) \geq q(1)}$ x(1,1)*p(1)+ x(2,1)*p(2)+ x(3,1)*p(3) ≥ q(1)

10x(1,1)+12x(2,1)+8x(3,1) ≥ 25

z=2 1 $\sum_{\text{wϵs}}^{}{x\left( w,2 \right) \bullet p(w) \geq q(2)}$ x(1,2)*p(1)+ x(2,2)*p(2)+ x(3,2)*p(3) ≥ q(2)

10x(1,2)+12x(2,2)+8x(3,2) ≥ 40

z=3 1 $\sum_{\text{wϵs}}^{}{x\left( w,3 \right) \bullet p(w) \geq q(3)}$ x(1,3)*p(1)+ x(2,3)*p(2)+ x(3,3)*p(3) ≥ q(3)

10x(1,3)+12x(2,3)+8x(3,3) ≥ 30

3) Ze względu na liczbę posiadanych środk. transportu $\forall\ w \in S\ \sum_{z \in Z}^{}{x\left( w,z \right) \leq l(w)}$

w=1 $\sum_{z \in Z}^{}{x\left( 1,z \right) \leq l(1)}$ x(1,1) + x(1,2) + x(1,3) ≤ l(1) = 3

w=2 $\sum_{z \in Z}^{}{x\left( 2,z \right) \leq l(2)}$ x(2,1) + x(2,2) + x(2,3) ≤ l(2) = 4

w=3 $\sum_{z \in Z}^{}{x\left( 3,z \right) \leq l(3)}$ x(3,1) + x(3,2) + x(3,3) ≤ l(3) = 3

Funkcja kryterium $F\left( X \right) = \ \sum_{w \in S}^{}{\sum_{z \in Z}^{}{x\left( w,z \right) \bullet k\left( w \right) \bullet d\left( z \right) \rightarrow min}}$

F(X) =  x(1,1) • 6 • 220 +  x(1,2) • 6 • 180 + x(1,3) • 6 • 240 + x(2,1) • 4 • 220+

x(2,2) • 4 • 180 + x(2,3) • 4 • 240 + x(3,1) • 3 • 220 + x(3,2) • 3 • 180 + x(3,3) • 3 • 240

=1320x(1,1) +  1800x(1,2) +  1440x(1,3) +  880x(2,1) +  720x(2,2) +  

960x(2,3) +  660x(3,1) +  540x(3,2) +  720x(3,3) = →min

ZADANIE - SIECIOWE

1) do grafu Bergea sprowadzamy przez przerwanie zdublowanego

łuku wstawienie kolejnego wierzchołka i podział kosztu przepustowość zostaje taka sama

2) Wyznaczyć zbiór dróg dla relacji przewozu (1,4) i 1(1,6) w = {1,2,3,4,5,6,7}; E = {(1,4) 1(1,6)}

p¹⁴ = {<1,3,4>;<1,2,4>;<1,2,3,4>}

p¹⁶ = {<1,5,6>;<1,7,5,6>;<1,3,5,6>;<1,2,3,5,6>}

3) Określić przepustowość wszystkich dróg relacji dla d^p,  ab =  {d_ij}

d^1,14 = min {d₁₃, d₃₄} = min {60,40} = 40

d^2,14 = min {d₁₂, d₂₄} = min {80,40} = 40

d^3,14 = min {d₁₂, d₂₃, d₃₄} = min {80,60,40} = 40

d^1,16 = min {d₁₅, d₅₆} = min {30,170} = 30

d^2,16 = min {d₁₇, d₇₅, d₅₆} = min {40,40,170} = 40

d^3,16 = min {d₁₃, d₃₅, d₅₆} = min {60,80,170} = 60

d^4,16 = min {d₁₂,d₂₃, d₃₅, d₅₆} = min {30,170} = 60

4) Droga o max przepustowości

d^{pk ab} =  {d^p} = max{30,40,60,60} = 60 =  d^3, 16 = d^4, 16 p = 3,  p = 4

5) Droga o min koszcie

$$C^{p,\ ab} = \sum_{(i,j) \in C^{p}}^{}C_{\text{ij}}$$

C^1,16 = C₁₅ + C₅₆ = 7 + 4 = 11

C^2,16 = C₁₇ + C₇₅ + C₅₆ = 2 + 3 + 4 = 9

C^3,16 = C₁₃ + C₃₅ + C₅₆ = 5 + 3 + 4 = 12

C^4,16 = C₁₂ + C₂₃ + C₃₅ + C₅₆ = 9 + 10 + 3 + 4 = 26

C^{p * , 16} = {C^p}=min{11,9,12,26} = C^2,  16 p = 2