транспортная задача

	300	200	300	100	400
300	3	4	3	1	5
200	2	3	5	6	8
100	1	2	3	3	4
200	4	5	7	9	9
300	5	6	8	4	7

_{Решение.}

Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 300 + 200 + 100 + 200 + 300 = 1100

∑b = 300 + 200 + 300 + 100 + 400 = 1300

Занесем исходные данные в распределительную таблицу.

	1	2	3	4	5	Запасы
1	3	4	3	1	5	300
2	2	3	5	6	8	200
3	1	2	3	3	4	100
4	4	5	7	9	9	200
5	5	6	8	4	7	300
6	0	0	0	0	0	200
Потребности	300	200	300	100	400

Этап I. Поиск первого опорного плана.

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

	1	2	3	4	5	Запасы
1	3	4	3[200]	1[100]	5	300
2	2[200]	3	5	6	8	200
3	1[100]	2	3	3	4	100
4	4	5[200]	7	9	9	200
5	5	6	8	4	7[300]	300
6	0	0	0[100]	0	0[100]	200
Потребности	300	200	300	100	400

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

	1	2	3	4	5	Запасы
1	3	4	3[200]	1[100]	5	300
2	2[200]	3	5	6	8	200
3	1[100]	2	3	3	4	100
4	4	5[200]	7	9	9	200
5	5	6	8	4	7[300]	300
6	0	0	0[100]	0	0[100]	200
Потребности	300	200	300	100	400

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

	1	2	3	4	5	Запасы
1	3	4	3[200]	1[100]	5	300
2	2[200]	3	5	6	8	200
3	1[100]	2	3	3	4	100
4	4	5[200]	7	9	9	200
5	5	6	8	4	7[300]	300
6	0	0	0[100]	0	0[100]	200
Потребности	300	200	300	100	400

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

	1	2	3	4	5	Запасы
1	3[100]	4	3[100]	1[100]	5	300
2	2[200]	3	5	6	8	200
3	1	2[100]	3	3	4	100
4	4	5[100]	7[100]	9	9	200
5	5	6	8	4	7[300]	300
6	0	0	0[100]	0	0[100]	200
Потребности	300	200	300	100	400

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.

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

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

	v1=3	v2=1	v3=3	v4=1	v5=3
u1=0	3[100]	4	3[100]	1[100]	5
u2=-1	2[200]	3	5	6	8
u3=1	1	2[100]	3	3	4
u4=4	4	5[100]	7[100]	9	9
u5=4	5	6	8	4	7[300]
u6=-3	0	0	0[100]	0	0[100]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

Выбираем максимальную оценку свободной клетки (3;1): 1

Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	3[100][-]	4	3[100][+]	1[100]	5	300
2	2[200]	3	5	6	8	200
3	1[+]	2[100][-]	3	3	4	100
4	4	5[100][+]	7[100][-]	9	9	200
5	5	6	8	4	7[300]	300
6	0	0	0[100]	0	0[100]	200
Потребности	300	200	300	100	400

Цикл приведен в таблице (3,1; 3,2; 4,2; 4,3; 1,3; 1,1; ).

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

	1	2	3	4	5	Запасы
1	3[0]	4	3[200]	1[100]	5	300
2	2[200]	3	5	6	8	200
3	1[100]	2	3	3	4	100
4	4	5[200]	7[0]	9	9	200
5	5	6	8	4	7[300]	300
6	0	0	0[100]	0	0[100]	200
Потребности	300	200	300	100	400

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

	v1=3	v2=1	v3=3	v4=1	v5=3
u1=0	3[0]	4	3[200]	1[100]	5
u2=-1	2[200]	3	5	6	8
u3=-2	1[100]	2	3	3	4
u4=4	4	5[200]	7[0]	9	9
u5=4	5	6	8	4	7[300]
u6=-3	0	0	0[100]	0	0[100]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

Выбираем максимальную оценку свободной клетки (4;1): 4

Для этого в перспективную клетку (4;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	Запасы
1	3[0][-]	4	3[200][+]	1[100]	5	300
2	2[200]	3	5	6	8	200
3	1[100]	2	3	3	4	100
4	4[+]	5[200]	7[0][-]	9	9	200
5	5	6	8	4	7[300]	300
6	0	0	0[100]	0	0[100]	200
Потребности	300	200	300	100	400

Цикл приведен в таблице (4,1; 4,3; 1,3; 1,1; ).

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

	1	2	3	4	5	Запасы
1	3	4	3[200]	1[100]	5	300
2	2[200]	3	5	6	8	200
3	1[100]	2	3	3	4	100
4	4[0]	5[200]	7[0]	9	9	200
5	5	6	8	4	7[300]	300
6	0	0	0[100]	0	0[100]	200
Потребности	300	200	300	100	400

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

	v1=0	v2=1	v3=3	v4=1	v5=3
u1=0	3	4	3[200]	1[100]	5
u2=2	2[200]	3	5	6	8
u3=1	1[100]	2	3	3	4
u4=4	4[0]	5[200]	7[0]	9	9
u5=4	5	6	8	4	7[300]
u6=-3	0	0	0[100]	0	0[100]