Решение транспортной задачи открытого типа

Решение транспортной задачи открытого типа

Правила ввода данных

Поиск

Процесс

Сообщение

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

Проверим необходимое и достаточное условие разрешимости задачи. Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 30 (230-200). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.
Занесем исходные данные в распределительную таблицу.

	1	2	3	4	5	6	Запасы
1	3	20	8	13	4	0	80
2	4	4	18	14	3	0	60
3	10	4	18	8	6	0	30
4	7	19	17	10	1	0	60
Потребности	10	30	40	50	70	30

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

	1	2	3	4	5	6	Запасы
1	3[10]	20	8[40]	13[20]	4	0[10]	80
2	4	4[30]	18	14	3[10]	0[20]	60
3	10	4	18	8[30]	6	0	30
4	7	19	17	10	1[60]	0	60
Потребности	10	30	40	50	70	30

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 9, а должно быть m + n - 1 = 9. Следовательно, опорный план является невырожденным.
4. Проверим оптимальность опорного плана. Найдем потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₁ = 3; 0 + v₁ = 3; v₁ = 3
u₁ + v₃ = 8; 0 + v₃ = 8; v₃ = 8
u₁ + v₄ = 13; 0 + v₄ = 13; v₄ = 13
u₃ + v₄ = 8; 13 + u₃ = 8; u₃ = -5
u₁ + v₆ = 0; 0 + v₆ = 0; v₆ = 0
u₂ + v₆ = 0; 0 + u₂ = 0; u₂ = 0
u₂ + v₂ = 4; 0 + v₂ = 4; v₂ = 4
u₂ + v₅ = 3; 0 + v₅ = 3; v₅ = 3
u₄ + v₅ = 1; 3 + u₄ = 1; u₄ = -2

	v₁=3	v₂=4	v₃=8	v₄=13	v₅=3	v₆=0
u₁=0	3[10]	20	8[40]	13[20]	4	0[10]
u₂=0	4	4[30]	18	14	3[10]	0[20]
u₃=-5	10	4	18	8[30]	6	0
u₄=-2	7	19	17	10	1[60]	0

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij
(4;4): -2 + 13 > 10; ∆₄₄ = -2 + 13 - 10 = 1
Выбираем максимальную оценку свободной клетки (4;4): 10
Для этого в перспективную клетку (4;4) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.

	1	2	3	4	5	6	Запасы
1	3[10]	20	8[40]	13[20][-]	4	0[10][+]	80
2	4	4[30]	18	14	3[10][+]	0[20][-]	60
3	10	4	18	8[30]	6	0	30
4	7	19	17	10[+]	1[60][-]	0	60
Потребности	10	30	40	50	70	30

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 6) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	6	Запасы
1	3[10]	20	8[40]	13[0]	4	0[30]	80
2	4	4[30]	18	14	3[30]	0	60
3	10	4	18	8[30]	6	0	30
4	7	19	17	10[20]	1[40]	0	60
Потребности	10	30	40	50	70	30

4. Проверим оптимальность опорного плана. Найдем потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₁ = 3; 0 + v₁ = 3; v₁ = 3
u₁ + v₃ = 8; 0 + v₃ = 8; v₃ = 8
u₁ + v₄ = 13; 0 + v₄ = 13; v₄ = 13
u₃ + v₄ = 8; 13 + u₃ = 8; u₃ = -5
u₄ + v₄ = 10; 13 + u₄ = 10; u₄ = -3
u₄ + v₅ = 1; -3 + v₅ = 1; v₅ = 4
u₂ + v₅ = 3; 4 + u₂ = 3; u₂ = -1
u₂ + v₂ = 4; -1 + v₂ = 4; v₂ = 5
u₁ + v₆ = 0; 0 + v₆ = 0; v₆ = 0

	v₁=3	v₂=5	v₃=8	v₄=13	v₅=4	v₆=0
u₁=0	3[10]	20	8[40]	13[0]	4	0[30]
u₂=-1	4	4[30]	18	14	3[30]	0
u₃=-5	10	4	18	8[30]	6	0
u₄=-3	7	19	17	10[20]	1[40]	0

Опорный план является оптимальным.
Затраты составят:
F(x) = 3*10 + 8*40 + 0*30 + 4*30 + 3*30 + 8*30 + 10*20 + 1*40 = 1040

Скачать в формате doc

Потребности