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

-1/7

0

1

0

-4/7

11/7

3/7

2552 0 0 5/2 0 1

Из табл. видно, что найденный новый опорный план исходной задачи X* = (64;56; 0; 60; 0) является оптимальным. При этом maxz = 2552.

Итак, выручка от реализации будет наибольшей, если в плане по производству содержится выпуск 64 изделий А1 и 56 изделий А2 , и, составляет 2552 ден. ед.

4)Для данной задачи , тогда . Число переменных в двойственной задаче равно числу уравнений в исходной задаче, т.е. 3. Коэффициенты в целевой функции двойственной задачи являются свободными членами неравенств-ограничений, т.е. числами 848, 532, 432. Т.к., в исходной системе ограничения представлены неравенствами, то в двойственной задаче переменные являются неотрицательными.

Следовательно, двойственная задача такова: найти минимум функции z ^* (x) = 848·y₁ + 532·y₂ + 432·y₃ при условиях

Из последней симплекс-таблицы (итерация 3) видно, что двойственная задача имеет решение , , .

1) Распределительный метод

Примем некоторые обозначения: 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

Решаем задачу распределительным методом:

Этап 1

Определим значения оценок 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,2 +c_2,2 -c_2,3 +c_3,3 -c_3,4 = 4 S_1,5 = c_1,5 -c_1,2 +c_2,2 -c_2,3 +c_3,3 -c_3,5 = -3 S_2,1 = c_2,1 -c_2,2 +c_1,2 -c_1,1 = 5 S_2,4 = c_2,4 -c_2,3 +c_3,3 -c_3,4 = 8 S_2,5 = c_2,5 -c_2,3 +c_3,3 -c_3,5 = -2 S_3,1 = c_3,1 -c_3,3 +c_2,3 -c_2,2 +c_1,2 -c_1,1 = -14 S_3,2 = c_3,2 -c_3,3 +c_2,3 -c_2,2 = -6

B1	B2	B3	B4	B5
A1	12	4	-3
A2	5	8	-2
A3	-14	-6

Если имеется несколько клеток с одним и тем же наименьшим значением оценки, то из них выбирается клетка, имеющая наименьший тариф. Наиболее перспективной является клетка (3,1) . Для нее оценка равна -14 . Строим для нее цикл, помечая клетки цикла знаками "плюс" и "минус".

Поставщик	Потребитель					Запасы груза
	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

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

Поставщик	Потребитель					Запасы груза
	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

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

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

Этап 2

Определим значения оценок 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_1,5 = c_1,5 -c_1,1 +c_3,1 -c_3,5 = -17 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,1 +c_3,1 -c_3,5 = -16 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

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