«Аналитическое исследование на оптимум экономических функций одной переменной»

80 + 400 40	- 60	- 72	520 - 400 20	600
A 2	400 - 400 50	400 60	- 90	+ 400 0 30	800
A 3	- 60	350 20	300 40	- 40	650
Потребность	480	750	300	520

X 2 опт =		480	0	0	120
		0	400	0	400
		0	350	300	0

Данную задачу можно решить также методом северо-западного угла, методом Фогеля.
Решение задачи с ограничительным условием № 1:
«Повторно решите задачу минимизации суммарных транспортных затрат при дополнительном условии, состоящем в том, что запрещена перевозка груза от 1-го поставщика к 4-му потребителю. Определите, на сколько увеличилось значение суммы затрат».
Математическая модель транспортной задачи:
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	Запасы
1	40	60	72	-	600
2	50	60	90	30	800
3	60	20	40	40	650
Потребности	480	750	300	520

Поскольку в матрице присутствуют запрещенные к размещению клетки, то для отыскания оптимального плана достаточно заменить их на максимальные тарифы (90 умноженное на 3).

	1	2	3	4	Запасы
1	40	60	72	270	600
2	50	60	90	30	800
3	60	20	40	40	650
Потребности	480	750	300	520

Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 600 + 800 + 650 = 2050
∑b = 480 + 750 + 300 + 520 = 2050
Занесем исходные данные в распределительную таблицу.

	1	2	3	4	Запасы
1	40	60	72	270	600
2	50	60	90	30	800
3	60	20	40	40	650
Потребности	480	750	300	520

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

	1	2	3	4	Запасы
1	40[480]	60[120]	72	270	600
2	50	60[630]	90[170]	30	800
3	60	20	40[130]	40[520]	650
Потребности	480	750	300	520

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

	v1=40	V2=60	v3=90	v4=90
u1=0	40[480]	60[120]	72	270
u2=0	50	60[630]	90[170]	30
u3=-50	60	20	40[130]	40[520]

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

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

	1	2	3	4	Запасы
1	40[480]	60[120]	72	270	600
2	50	60[630]	90[170][-]	30[+]	800
3	60	20	40[130][+]	40[520][-]	650
Потребности	480	750	300	520

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

	1	2	3	4	Запасы
1	40[480]	60[120]	72	270	600
2	50	60[630]	90	30[170]	800
3	60	20	40[300]	40[350]	650
Потребности	480	750	300	520

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

	v1=40	v2=60	v3=30	v4=30
u1=0	40[480]	60[120]	72	270
u2=0	50	60[630]	90	30[170]
u3=10	60	20	40[300]	40[350]

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

	1	2	3	4	Запасы
1	40[480]	60[120]	72	270	600
2	50	60[630][-]	90	30[170][+]	800
3	60	20[+]	40[300]	40[350][-]	650
Потребности	480	750	300	520

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

	1	2	3	4	Запасы
1	40[480]	60[120]	72	270	600
2	50	60[280]	90	30[520]	800
3	60	20[350]	40[300]	40	650
Потребности	480	750	300	520

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

	v1=40	v2=60	v3=80	v4=30
U1=0	40[480]	60[120]	72	270
U2=0	50	60[280]	90	30[520]
U3=-40	60	20[350]	40[300]	40

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

	1	2	3	4	Запасы
1	40[480]	60[120][-]	72[+]	270	600
2	50	60[280]	90	30[520]	800
3	60	20[350][+]	40[300][-]	40	650
Потребности	480	750	300	520

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

	1	2	3	4	Запасы
1	40[480]	60	72[120]	270	600
2	50	60[280]	90	30[520]	800
3	60	20[470]	40[180]	40	650
Потребности	480	750	300	520

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

	v1=40	v2=52	v3=72	v4=22
U1=0	40[480]	60	72[120]	270
U2=8	50	60[280]	90	30[520]
U3=-32	60	20[470]	40[180]	40

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij. Минимальные затраты составят:
F(x) = 40*480 + 72*120 + 60*280 + 30*520 + 20*470 + 40*180 = 76840 ден.ед.