задачи / 17

Транспортная задача. Математическая модель транспортной задачи: F = ∑∑c_ijx_ij, (1) при условиях: ∑x_ij = a_i, i = 1,2,…, m, (2) ∑x_ij = b_j, j = 1,2,…, n, (3) Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

	1	2	3	4	5	6	Запасы
1	8	7	5	10	13	12	360
2	13	8	10	7	11	6	180
3	12	4	11	9	140	10	120
4	14	6	12	130	13	7	150
5	9	12	14	15	8	8	240
Потребности	230	220	130	170	190	110

Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 360 + 180 + 120 + 150 + 240 = 1050 ∑b = 230 + 220 + 130 + 170 + 190 + 110 = 1050 Занесем исходные данные в распределительную таблицу.

	1	2	3	4	5	6	Запасы
1	8	7	5	10	13	12	360
2	13	8	10	7	11	6	180
3	12	4	11	9	140	10	120
4	14	6	12	130	13	7	150
5	9	12	14	15	8	8	240
Потребности	230	220	130	170	190	110

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

	1	2	3	4	5	6	Запасы
1	8[230]	7	5[130]	10	13	12	360
2	13	8	10	7[70]	11	6[110]	180
3	12	4[120]	11	9	140	10	120
4	14	6[100]	12	130[50]	13	7	150
5	9	12	14	15[50]	8[190]	8	240
Потребности	230	220	130	170	190	110

2. Подсчитаем число занятых клеток таблицы, их 9, а должно быть m + n - 1 = 10. Следовательно, опорный план является вырожденным. Строим новый план. Значение целевой функции для этого опорного плана равно:

	1	2	3	4	5	6	Запасы
1	8[230]	7	5[130]	10	13	12	360
2	13	8	10	7[70]	11	6[110]	180
3	12	4[120]	11	9	140	10	120
4	14	6[100]	12	130[50]	13	7	150
5	9	12	14	15[50]	8[190]	8	240
Потребности	230	220	130	170	190	110

2. Подсчитаем число занятых клеток таблицы, их 9, а должно быть m + n - 1 = 10. Следовательно, опорный план является вырожденным. Строим новый план. Значение целевой функции для этого опорного плана равно:

	1	2	3	4	5	6	Запасы
1	8[230]	7	5[130]	10	13	12	360
2	13	8	10	7[70]	11	6[110]	180
3	12	4[120]	11	9	140	10	120
4	14	6[100]	12	130[50]	13	7	150
5	9	12	14	15[50]	8[190]	8	240
Потребности	230	220	130	170	190	110

2. Подсчитаем число занятых клеток таблицы, их 9, а должно быть m + n - 1 = 10. Следовательно, опорный план является вырожденным. Строим новый план. Значение целевой функции для этого опорного плана равно:

	1	2	3	4	5	6	Запасы
1	8[230]	7	5[130]	10	13	12	360
2	13	8	10	7[70]	11	6[110]	180
3	12	4[70]	11	9[50]	140	10	120
4	14	6[150]	12	130	13	7	150
5	9	12	14	15[50]	8[190]	8	240
Потребности	230	220	130	170	190	110

2. Подсчитаем число занятых клеток таблицы, их 9, а должно быть m + n - 1 = 10. Следовательно, опорный план является вырожденным. Строим новый план. Значение целевой функции для этого опорного плана равно:

	1	2	3	4	5	6	Запасы
1	8[10]	7[220]	5[130]	10	13	12	360
2	13	8	10	7[70]	11	6[110]	180
3	12[20]	4	11	9[100]	140	10	120
4	14[150]	6	12	130	13	7	150
5	9[50]	12	14	15	8[190]	8	240
Потребности	230	220	130	170	190	110

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. 2. Подсчитаем число занятых клеток таблицы, их 10, а должно быть m + n - 1 = 10. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: Этап II. Улучшение опорного плана. Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=8	v2=7	v3=5	v4=5	v5=7	v6=4
u1=0	8[10]	7[220]	5[130]	10	13	12
u2=2	13	8	10	7[70]	11	6[110]
u3=4	12[20]	4	11	9[100]	140	10
u4=6	14[150]	6	12	130	13	7
u5=1	9[50]	12	14	15	8[190]	8

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij Выбираем максимальную оценку свободной клетки (3;2): 4 Для этого в перспективную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	6	Запасы
1	8[10][+]	7[220][-]	5[130]	10	13	12	360
2	13	8	10	7[70]	11	6[110]	180
3	12[20][-]	4[+]	11	9[100]	140	10	120
4	14[150]	6	12	130	13	7	150
5	9[50]	12	14	15	8[190]	8	240
Потребности	230	220	130	170	190	110

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

	1	2	3	4	5	6	Запасы
1	8[30]	7[200]	5[130]	10	13	12	360
2	13	8	10	7[70]	11	6[110]	180
3	12	4[20]	11	9[100]	140	10	120
4	14[150]	6	12	130	13	7	150
5	9[50]	12	14	15	8[190]	8	240
Потребности	230	220	130	170	190	110

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=8	v2=7	v3=5	v4=12	v5=7	v6=11
u1=0	8[30]	7[200]	5[130]	10	13	12
u2=-5	13	8	10	7[70]	11	6[110]
u3=-3	12	4[20]	11	9[100]	140	10
u4=6	14[150]	6	12	130	13	7
u5=1	9[50]	12	14	15	8[190]	8

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij Выбираем максимальную оценку свободной клетки (4;6): 7 Для этого в перспективную клетку (4;6) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	6	Запасы
1	8[30][+]	7[200][-]	5[130]	10	13	12	360
2	13	8	10	7[70][+]	11	6[110][-]	180
3	12	4[20][+]	11	9[100][-]	140	10	120
4	14[150][-]	6	12	130	13	7[+]	150
5	9[50]	12	14	15	8[190]	8	240
Потребности	230	220	130	170	190	110

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

	1	2	3	4	5	6	Запасы
1	8[130]	7[100]	5[130]	10	13	12	360
2	13	8	10	7[170]	11	6[10]	180
3	12	4[120]	11	9	140	10	120
4	14[50]	6	12	130	13	7[100]	150
5	9[50]	12	14	15	8[190]	8	240
Потребности	230	220	130	170	190	110