Курсовая работа: Решение задач о планировании перевозок

U3=4 180 180

U4=6 120 40 80

U5=9 150 40 110

3.Определяем целевую функцию Z для первого этапа по формуле

Z = Σ C_ij * X_ij

Z 1=90*5+150*8+80*13+170*7+110*6+180*4+40*6+80*7+40*14+110*15=8270

4.Определим потенциалы для заданных клеток, где U1=0 по формуле

U_i +V_j =C_ij

5.определим оценки свободных клеток, исходя из условия:

Δ_ij =C_ij -( U_i +V_j )

Δ₁₂ =7 Δ₃₅ =5

Δ₁₄ =8 Δ₃₆ =1

Δ₁₅ =11 Δ₄₁ =0

Δ₁₆ =2 Δ₄₃ =1

Δ₂₂ =3 Δ₄₄ =5

Δ₂₃ =0 Δ₄₆ =2

Δ₂₆ =2 Δ₅₁ =-8

Δ₃₁ =0 Δ₅₂ =3

Δ₃₃ =2 Δ₅₄ =4

Δ₃₄ =3 Δ₅₅ =-2

Т.к среди оценок свободных клеток есть отрицательная оценка Δ₅₁ =-8 то решение является не оптимальным, значит, продолжаем решение задачи.

6.Для перехода к следующей итерации строим цикл по λ=min|X_ij | по четным клеткам λ=min|150;40|=40

7.Определим целевую функцию для второго этапа

Z2=Z-λ|X_ij |=8270-40*8=7950

V1=8 V2=0 V3=5 V4=2 V5=1 V6=14

230 220 130 170 190 110

U1=0 240 110 130

U2=5 360 80 170 110

U3=4 180 180