183762 (584788), страница 4
Текст из файла (страница 4)
Значение целевой функции изменилось на 320 единиц по сравнению с предыдущим этапом.
Этап 5
Определим значения оценок Si,j для всех свободных клеток (неоптимальные выделены красным цветом). Для этого строим цикл для каждой свободной клетки и, перемещаясь по клеткам цикла, складываем тарифы клеток. При этом тарифы в нечетных клетках берутся со знаком "плюс", в четных - со знаком "минус". S1,1 = c1,1-c1,4+c3,4-c3,1 = 10 S1,2 = c1,2-c1,4+c3,4-c3,2 = 2 S1,3 = c1,3-c1,4+c3,4-c3,2+c2,2-c2,3 = 14 S2,1 = c2,1-c2,2+c3,2-c3,1 = 13 S2,4 = c2,4-c2,2+c3,2-c3,4 = 2 S2,5 = c2,5-c2,2+c3,2-c3,4+c1,4-c1,5 = -1 S3,3 = c3,3-c3,2+c2,2-c2,3 = 6 S3,5 = c3,5-c3,4+c1,4-c1,5 = 7
| B1 | B2 | B3 | B4 | B5 |
A1 | 10 | 2 | 14 |
|
|
A2 | 13 |
|
| 2 | -1 |
A3 |
|
| 6 |
| 7 |
Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее перспективной является клетка (2,5). Для нее оценка равна -1. Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".
Поставщик | Потребитель | Запасы груза | ||||||||||||||||||||||||
B1 | B2 | B3 | B4 | B5 | ||||||||||||||||||||||
A1 |
|
|
|
|
| 370 | ||||||||||||||||||||
A2 |
|
|
|
|
| 450 | ||||||||||||||||||||
A3 |
|
|
|
|
| 480 | ||||||||||||||||||||
Потребность | 300 | 280 | 330 | 290 | 100 |
|
Перемещаем по циклу груз величиной в 20 единиц, прибавляя эту величину к грузу в клетках со знаком "плюс" и отнимая ее от груза в клетках со знаком "минус". В результате перемещения по циклу получим новый план:
Поставщик | Потребитель | Запасы груза | ||||||||||||||||||||||||||
B1 | B2 | B3 | B4 | B5 | ||||||||||||||||||||||||
A1 |
|
|
|
|
| 370 | ||||||||||||||||||||||
A2 |
|
|
|
|
| 450 | ||||||||||||||||||||||
A3 |
|
|
|
|
| 480 | ||||||||||||||||||||||
Потребность | 300 | 280 | 330 | 290 | 100 |
|
Целевая функция F= 6920
Значение целевой функции изменилось на 20 единиц по сравнению с предыдущим этапом.
Этап 6
Определим значения оценок Si,j для всех свободных клеток (неоптимальные выделены красным цветом). Для этого строим цикл для каждой свободной клетки и, перемещаясь по клеткам цикла, складываем тарифы клеток. При этом тарифы в нечетных клетках берутся со знаком "плюс", в четных - со знаком "минус". S1,1 = c1,1-c1,5+c2,5-c2,2+c3,2-c3,1 = 9 S1,2 = c1,2-c1,5+c2,5-c2,2 = 1 S1,3 = c1,3-c1,5+c2,5-c2,3 = 13 S2,1 = c2,1-c2,2+c3,2-c3,1 = 13 S2,4 = c2,4-c2,5+c1,5-c1,4 = 3 S3,3 = c3,3-c3,2+c2,2-c2,3 = 6 S3,4 = c3,4-c3,2+c2,2-c2,5+c1,5-c1,4 = 1 S3,5 = c3,5-c3,2+c2,2-c2,5 = 8
| B1 | B2 | B3 | B4 | B5 |
A1 | 9 | 1 | 13 |
|
|
A2 | 13 |
|
| 3 |
|
A3 |
|
| 6 | 1 | 8 |
Так как все оценки Si,j>=0, то полученный план является оптимальным. Транспортная задача решена.
Поставщик | Потребитель | Запасы груза | ||||||||||||||||||||||||||
B1 | B2 | B3 | B4 | B5 | ||||||||||||||||||||||||
A1 |
|
|
|
|
| 370 | ||||||||||||||||||||||
A2 |
|
|
|
|
| 450 | ||||||||||||||||||||||
A3 |
|
|
|
|
| 480 | ||||||||||||||||||||||
Потребность | 300 | 280 | 330 | 290 | 100 |
|
Целевая функция F= 6920