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

	1	2	3	4	Запасы
1	3[12]	9[18]	4	6	30
2	7	5[22]	3[3]	8	25
3	4	7	4[18]	11	18
4	2	6	10[4]	12[6]	10
5	0	0	0	0[24]	24
Потребности	12	40	25	30

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. 2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 3*12 + 9*18 + 5*22 + 3*3 + 4*18 + 10*4 + 12*6 + 0*24 = 501 3. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

	1	2	3	4	Запасы
1	3[2]	9	4[25]	6[3]	30
2	7	5[25]	3	8	25
3	4	7[15]	4	11[3]	18
4	2[10]	6	10	12	10
5	0	0	0	0[24]	24
Потребности	12	40	25	30

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. 4. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 3*2 + 4*25 + 6*3 + 5*25 + 7*15 + 11*3 + 2*10 + 0*24 = 407 Этап II. Улучшение опорного плана. Используем опорный план, построенный методом минимального элемента. Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0. u₁ + v₁ = 3; 0 + v₁ = 3; v₁ = 3 u₄ + v₁ = 2; 3 + u₄ = 2; u₄ = -1 u₁ + v₃ = 4; 0 + v₃ = 4; v₃ = 4 u₁ + v₄ = 6; 0 + v₄ = 6; v₄ = 6 u₃ + v₄ = 11; 6 + u₃ = 11; u₃ = 5 u₃ + v₂ = 7; 5 + v₂ = 7; v₂ = 2 u₂ + v₂ = 5; 2 + u₂ = 5; u₂ = 3 u₅ + v₄ = 0; 6 + u₅ = 0; u₅ = -6

	v1=3	v2=2	v3=4	v4=6
u1=0	3[2]	9	4[25]	6[3]
u2=3	7	5[25]	3	8
u3=5	4	7[15]	4	11[3]
u4=-1	2[10]	6	10	12
u5=-6	0	0	0	0[24]

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

	1	2	3	4	Запасы
1	3[2]	9	4[25][-]	6[3][+]	30
2	7	5[25]	3	8	25
3	4	7[15]	4[+]	11[3][-]	18
4	2[10]	6	10	12	10
5	0	0	0	0[24]	24
Потребности	12	40	25	30

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

	1	2	3	4	Запасы
1	3[2]	9	4[22]	6[6]	30
2	7	5[25]	3	8	25
3	4	7[15]	4[3]	11	18
4	2[10]	6	10	12	10
5	0	0	0	0[24]	24
Потребности	12	40	25	30

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

	v1=3	v2=7	v3=4	v4=6
u1=0	3[2]	9	4[22]	6[6]
u2=-2	7	5[25]	3	8
u3=0	4	7[15]	4[3]	11
u4=-1	2[10]	6	10	12
u5=-6	0	0	0	0[24]

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

	1	2	3	4	Запасы
1	3[2]	9	4[22][-]	6[6][+]	30
2	7	5[25]	3	8	25
3	4	7[15][-]	4[3][+]	11	18
4	2[10]	6	10	12	10
5	0	0[+]	0	0[24][-]	24
Потребности	12	40	25	30

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

	1	2	3	4	Запасы
1	3[2]	9	4[7]	6[21]	30
2	7	5[25]	3	8	25
3	4	7	4[18]	11	18
4	2[10]	6	10	12	10
5	0	0[15]	0	0[9]	24
Потребности	12	40	25	30

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

	v1=3	v2=6	v3=4	v4=6
u1=0	3[2]	9	4[7]	6[21]
u2=-1	7	5[25]	3	8
u3=0	4	7	4[18]	11
u4=-1	2[10]	6	10	12
u5=-6	0	0[15]	0	0[9]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij. Минимальные затраты составят: F(x) = 3*2 + 4*7 + 6*21 + 5*25 + 4*18 + 2*10 + 0*15 + 0*9 = 377 Анализ оптимального плана. Из 1-го склада необходимо груз направить в 1-й магазин (2), в 3-й магазин (7), в 4-й магазин (21) Из 2-го склада необходимо весь груз направить в 2-й магазин Из 3-го склада необходимо весь груз направить в 3-й магазин Из 4-го склада необходимо весь груз направить в 1-й магазин Потребность 2-го магазина остается неудовлетворенной на 15 ед. Оптимальный план является вырожденным, так как базисная переменная x₅₂=0. Потребность 4-го магазина остается неудовлетворенной на 9 ед. Оптимальный план является вырожденным, так как базисная переменная x₅₄=0.