Контрольная работа: Методы решения транспортных задач

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

Этап 3

Определим значения оценок S_i,j для всех свободных клеток (неоптимальные выделены красным цветом ). Для этого строим цикл для каждой свободной клетки и, перемещаясь по клеткам цикла, складываем тарифы клеток. При этом тарифы в нечетных клетках берутся со знаком "плюс", в четных - со знаком "минус". S_1,3 = c_1,3 -c_1,2 +c_2,2 -c_2,3 = 12 S_1,4 = c_1,4 -c_1,1 +c_3,1 -c_3,4 = -10 S_2,1 = c_2,1 -c_2,2 +c_1,2 -c_1,1 = 5 S_2,4 = c_2,4 -c_2,2 +c_1,2 -c_1,1 +c_3,1 -c_3,4 = -6 S_2,5 = c_2,5 -c_2,2 +c_1,2 -c_1,5 = 1 S_3,2 = c_3,2 -c_3,1 +c_1,1 -c_1,2 = 8 S_3,3 = c_3,3 -c_3,1 +c_1,1 -c_1,2 +c_2,2 -c_2,3 = 14 S_3,5 = c_3,5 -c_3,1 +c_1,1 -c_1,5 = 17

B1	B2	B3	B4	B5
A1	12	-10
A2	5	-6	1
A3	8	14	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

Определим значения оценок S_i,j для всех свободных клеток (неоптимальные выделены красным цветом ). Для этого строим цикл для каждой свободной клетки и, перемещаясь по клеткам цикла, складываем тарифы клеток. При этом тарифы в нечетных клетках берутся со знаком "плюс", в четных - со знаком "минус". S_1,1 = c_1,1 -c_1,4 +c_3,4 -c_3,1 = 10 S_1,3 = c_1,3 -c_1,2 +c_2,2 -c_2,3 = 12 S_2,1 = c_2,1 -c_2,2 +c_1,2 -c_1,4 +c_3,4 -c_3,1 = 15 S_2,4 = c_2,4 -c_2,2 +c_1,2 -c_1,4 = 4 S_2,5 = c_2,5 -c_2,2 +c_1,2 -c_1,5 = 1 S_3,2 = c_3,2 -c_3,4 +c_1,4 -c_1,2 = -2 S_3,3 = c_3,3 -c_3,4 +c_1,4 -c_1,2 +c_2,2 -c_2,3 = 4 S_3,5 = c_3,5 -c_3,4 +c_1,4 -c_1,5 = 7

B1	B2	B3	B4	B5
A1	10	12
A2	15	4	1
A3	-2	4	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

Определим значения оценок S_i,j для всех свободных клеток (неоптимальные выделены красным цветом ). Для этого строим цикл для каждой свободной клетки и, перемещаясь по клеткам цикла, складываем тарифы клеток. При этом тарифы в нечетных клетках берутся со знаком "плюс", в четных - со знаком "минус". S_1,1 = c_1,1 -c_1,4 +c_3,4 -c_3,1 = 10 S_1,2 = c_1,2 -c_1,4 +c_3,4 -c_3,2 = 2 S_1,3 = c_1,3 -c_1,4 +c_3,4 -c_3,2 +c_2,2 -c_2,3 = 14 S_2,1 = c_2,1 -c_2,2 +c_3,2 -c_3,1 = 13 S_2,4 = c_2,4 -c_2,2 +c_3,2 -c_3,4 = 2 S_2,5 = c_2,5 -c_2,2 +c_3,2 -c_3,4 +c_1,4 -c_1,5 = -1 S_3,3 = c_3,3 -c_3,2 +c_2,2 -c_2,3 = 6 S_3,5 = c_3,5 -c_3,4 +c_1,4 -c_1,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	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

Определим значения оценок S_i,j для всех свободных клеток (неоптимальные выделены красным цветом ). Для этого строим цикл для каждой свободной клетки и, перемещаясь по клеткам цикла, складываем тарифы клеток. При этом тарифы в нечетных клетках берутся со знаком "плюс", в четных - со знаком "минус". S_1,1 = c_1,1 -c_1,5 +c_2,5 -c_2,2 +c_3,2 -c_3,1 = 9 S_1,2 = c_1,2 -c_1,5 +c_2,5 -c_2,2 = 1 S_1,3 = c_1,3 -c_1,5 +c_2,5 -c_2,3 = 13 S_2,1 = c_2,1 -c_2,2 +c_3,2 -c_3,1 = 13 S_2,4 = c_2,4 -c_2,5 +c_1,5 -c_1,4 = 3 S_3,3 = c_3,3 -c_3,2 +c_2,2 -c_2,3 = 6 S_3,4 = c_3,4 -c_3,2 +c_2,2 -c_2,5 +c_1,5 -c_1,4 = 1 S_3,5 = c_3,5 -c_3,2 +c_2,2 -c_2,5 = 8

B1	B2	B3	B4	B5
A1	9	1	13
A2	13	3
A3	6	1	8

Так как все оценки S_i,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

2) Метод потенциалов

Примем некоторые обозначения: i - индекс строки j - индекс столбца m - количество поставщиков n - количество потребителей X_i,j - перевозка между поставщиком A_i и потребителем B_j .

Поставщик	Потребитель					Запасы груза
	B1	B2	B3	B4	B5
A1	14 0	8 0	17 0	5 0	3 0	370
A2	21 0	10 0	7 0	11 0	6 0	450
A3	3 0	5 0	8 0	4 0	9 0	480
Потребность	300	280	330	290	100

Транспортная задача имеет закрытый тип, так как суммарный запас груза равен суммарным потребностям. Находим опорный план по правилу северо-западного угла: Введем некоторые обозначения: A_i ^* - излишек нераспределенного груза от поставщика A_i B_j ^* - недостача в поставке груза потребителю B_j

Помещаем в клетку (1,1) меньшее из чисел A₁ ^* =370 и B₁ ^* =300 Так как спрос потребителя B₁ удовлетворен, то столбец 1 в дальнейшем в расчет не принимается Помещаем в клетку (1,2) меньшее из чисел A₁ ^* =70 и B₂ ^* =280 Так как запасы поставщика A₁ исчерпаны, то строка 1 в дальнейшем в расчет не принимается Помещаем в клетку (2,2) меньшее из чисел A₂ ^* =450 и B₂ ^* =210 Так как спрос потребителя B₂ удовлетворен, то столбец 2 в дальнейшем в расчет не принимается Помещаем в клетку (2,3) меньшее из чисел A₂ ^* =240 и B₃ ^* =330 Так как запасы поставщика A₂ исчерпаны, то строка 2 в дальнейшем в расчет не принимается Помещаем в клетку (3,3) меньшее из чисел A₃ ^* =480 и B₃ ^* =90 Так как спрос потребителя B₃ удовлетворен, то столбец 3 в дальнейшем в расчет не принимается Помещаем в клетку (3,4) меньшее из чисел A₃ ^* =390 и B₄ ^* =290 Так как спрос потребителя B₄ удовлетворен, то столбец 4 в дальнейшем в расчет не принимается Помещаем в клетку (3,5) меньшее из чисел A₃ ^* =100 и B₅ ^* =100

Поставщик	Потребитель					Запасы груза
	B1	B2	B3	B4	B5
A1	14 300	8 70	17	5	3	370
A2	21	10 210	7 240	11	6	450
A3	3	5	8 90	4 290	9 100	480
Потребность	300	280	330	290	100

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

Решаем задачу методом потенциалов: