Методы решения транспортных задач

= c1,3 - (u1 + v3) = 12. S1,4 = c1,4 - (u1 + v4) = -10.S1,5 = c1,5 - (u1 + v5) = -17. S2,1 = c2,1 - (u2 + v1) = 5. S2,4 = c2,4 - (u2 + v4) = -6.S2,5 = c2,5 - (u2 + v5) = -16. S3,2 = c3,2 - (u3 + v2) = 8. S3,3 = c3,3 - (u3 + v3) = 14. Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (1,5). Для нее оценка равна -17. Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".


Поставщик Потребитель Запасы груза

B1 B2 B3 B4 B5
A1

-

14


210


 

8


160


 

17


 


 

5


 


+

3


 


370






A2

 

21


 


 

10


120


 

7


330


 

11


 


 

6


 


450






A3

+

3


90


 

5


 


 

8


 


 

4


290


-

9


100


480






Потребность 300 280 330 290 100

Перемещаем по циклу груз величиной в 100 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план:Поставщик Потребитель Запасы груза

B1 B2 B3 B4 B5
A1

 

14


110


 

8


160


 

17


 


 

5


 


 

3


100


370






A2

 

21


 


 

10


120


 

7


330


 

11


 


 

6


 


450






A3

 

3


190


 

5


 


 

8


 


 

4


290


 

9


 


480






Потребность 300 280 330 290 100

Целевая функция F= 8360

Значение целевой функции изменилось на 1700 единиц по сравнению с предыдущим этапом.

Этап 3

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки. Потенциалы Ui, Vj: U1=0 V1=C1,1-U1= 14 V2=C1,2-U1= 8 V5=C1,5-U1= 3 U3=C1,3-V1= -11 U2=C2,2-V2= 2 V3=C2,3-U2= 5 V4=C3,4-U3= 15 Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток (неоптимальные выделены красным цветом) S1,3 = c1,3 - (u1 + v3) = 12. S1,4 = c1,4 - (u1 + v4) = -10. S2,1 = c2,1 - (u2 + v1) = 5. S2,4 = c2,4 - (u2 + v4) = -6. S2,5 = c2,5 - (u2 + v5) = 1. S3,2 = c3,2 - (u3 + v2) = 8. S3,3 = c3,3 - (u3 + v3) = 14. S3,5 = c3,5 - (u3 + v5) = 17. Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (1,4). Для нее оценка равна -10. Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".


Поставщик Потребитель Запасы груза

B1

B2

B3

B4

B5


A1

-

14


110


8


160


17


+

5


3


100


370






A2


21


10


120


7


330


11


6


450






A3

+

3


190


5


8


-

4


290


9


480






Потребность 300 280 330 290 100

Перемещаем по циклу груз величиной в 110 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план:


Поставщик Потребитель Запасы груза

B1 B2 B3 B4 B5
A1

 

14


 


 

8


160


 

17


 


 

5


110


 

3


100


370






A2

 

21


 


 

10


120


 

7


330


 

11


 


 

6


 


450






A3

 

3


300


 

5


 


 

8


 


 

4


180


 

9


 


480






Потребность 300 280 330 290 100

Целевая функция F= 7260

Значение целевой функции изменилось на 1100 единиц по сравнению с предыдущим этапом.

Этап 4

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки. Потенциалы Ui, Vj: U1=0 V2=C1,2-U1= 8 V4=C1,4-U1= 5 V5=C1,5-U1= 3 U2=C2,2-V2= 2 U3=C4,3-V4= -1 V3=C2,3-U2= 5 V1=C3,1-U3= 4 Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток (неоптимальные выделены красным цветом) S1,1 = c1,1 - (u1 + v1) = 10. S1,3 = c1,3 - (u1 + v3) = 12. S2,1 = c2,1 - (u2 + v1) = 15. S2,4 = c2,4 - (u2 + v4) = 4. S2,5 = c2,5 - (u2 + v5) = 1. S3,2 = c3,2 - (u3 + v2) = -2. S3,3 = c3,3 - (u3 + v3) = 4. S3,5 = c3,5 - (u3 + v5) = 7. Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (3,2). Для нее оценка равна -2. Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".


Поставщик Потребитель Запасы груза

B1

B2

B3

B4

B5


A1


14


-

8


160


17


+

5


110


3


100


370






A2


21


10


120


7


330


11


6


450






A3


3


300


+

5


8


-

4


180


9


480






Потребность 300 280 330 290 100

Перемещаем по циклу груз величиной в 160 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план:


Поставщик Потребитель Запасы груза

B1

B2

B3

B4

B5


A1


14


8


17


5


270


3


100


370






A2


21


10


120


7


330


11


6


450






A3


3


300


5


160


8


4


20


9


480






Потребность 300 280 330 290 100

Целевая функция F= 6940

Значение целевой функции изменилось на 320 единиц по сравнению с предыдущим этапом.

Этап 5

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки. Потенциалы Ui, Vj: U1=0 V4=C1,4-U1= 5 V5=C1,5-U1= 3 U3=C4,3-V4= -1 V1=C3,1-U3= 4 V2=C3,2-U3= 6 U2=C2,2-V2= 4 V3=C2,3-U2= 3 Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток (неоптимальные выделены красным цветом) S1,1 = c1,1 - (u1 + v1) = 10. S1,2 = c1,2 - (u1 + v2) = 2. S1,3 = c1,3 - (u1 + v3) = 14. S2,1 = c2,1 - (u2 + v1) = 13. S2,4 = c2,4 - (u2 + v4) = 2. S2,5 = c2,5 - (u2 + v5) = -1. S3,3 = c3,3 - (u3 + v3) = 6. S3,5 = c3,5 - (u3 + v5) = 7. Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее потенциальной является клетка (2,5). Для нее оценка равна -1. Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".


Поставщик Потребитель Запасы груза

B1

B2

B3

B4

B5


A1


14


8


17


+

5


270


-

3


100


370






A2


21


-

10


120


7


330


11


+

6


450






A3


3


300


+

5


160


8


-

4


20


9


480






Потребность 300 280 330 290 100

Перемещаем по циклу груз величиной в 20 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план:


Поставщик Потребитель Запасы груза

B1

B2

B3

B4

B5


A1


14


8


17


5


290


3


80


370






A2


21


10


100


7


330


11


6


20


450






A3


3


300


5


180


8


4


9


480






Потребность 300 280 330 290 100

Целевая функция F= 6920

Значение целевой функции изменилось на 20 единиц по сравнению с предыдущим этапом.

Этап 6

Полагая потенциал U1=0, определяем остальные потенциалы из соотношения Ui+Vj=Ci,j(i=1..m, j=1..n), просматривая все занятые клетки.

Потенциалы Ui, Vj: U1=0 V4=C1,4-U1= 5 V5=C1,5-U1= 3 U2=C5,2-V5= 3 V2=C2,2-U2= 7 V3=C2,3-U2= 4 U3=C2,3-V2= -2 V1=C3,1-U3= 5 Определяем значения оценок Si,j=Ci,j-(Ui+Vj) для всех свободных клеток (неоптимальные выделены красным цветом) S1,1 = c1,1 - (u1 + v1) = 9. S1,2 = c1,2 - (u1 + v2) = 1. S1,3 = c1,3 - (u1 + v3) = 13. S2,1 = c2,1 - (u2 + v1) = 13. S2,4 = c2,4 - (u2 + v4) = 3. S3,3 = c3,3 - (u3 + v3) = 6. S3,4 = c3,4 - (u3 + v4) = 1. S3,5 = c3,5 - (u3 + v5) = 8. Так как все оценки Si,j>=0, то полученный план является оптимальным. Транспортная задача решена.


Поставщик Потребитель Запасы груза

B1

B2

B3

B4

B5


A1


14


8


17


5


290


3


80


370






A2


21


10


100


7


330


11


6


20


450






A3


3


300


5


180


8


4


9


480






Потребность 300 280 330 290 100

Целевая функция F= 6920

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: