Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. (Решение → 28619)

Заказ №38652

Этап II. Улучшение опорного плана. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. 111 u1 + v1 = 3; 0 + v1 = 3; v1 = 3 u2 + v1 = 1; 3 + u2 = 1; u2 = -2 u3 + v1 = 1; 3 + u3 = 1; u3 = -2 u3 + v2 = 5; -2 + v2 = 5; v2 = 7 u4 + v2 = 1; 7 + u4 = 1; u4 = -6 u4 + v3 = 4; -6 + v3 = 4; v3 = 10 u4 + v4 = 1; -6 + v4 = 1; v4 = 7 v1=3 v2=7 v3=10 v4=7 u1=0 3[5] 2 3 4 u2=-2 1[10] 3 2 1 u3=-2 1[9] 5[19] 1 4 u4=-6 0 1[5] 4[26] 1[15] Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (1;2): 0 + 7 > 2; ∆12 = 0 + 7 - 2 = 5 > 0 (1;3): 0 + 10 > 3; ∆13 = 0 + 10 - 3 = 7 > 0 (1;4): 0 + 7 > 4; ∆14 = 0 + 7 - 4 = 3 > 0 (2;2): -2 + 7 > 3; ∆22 = -2 + 7 - 3 = 2 > 0 (2;3): -2 + 10 > 2; ∆23 = -2 + 10 - 2 = 6 > 0 (2;4): -2 + 7 > 1; ∆24 = -2 + 7 - 1 = 4 > 0 (3;3): -2 + 10 > 1; ∆33 = -2 + 10 - 1 = 7 > 0 (3;4): -2 + 7 > 4; ∆34 = -2 + 7 - 4 = 1 > 0 max(5,7,3,2,6,4,7,1) = 7 Выбираем максимальную оценку свободной клетки (1;3): 3 Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 1 2 3 4 Запасы 1 3[5][-] 2 3[+] 4 5 2 1[10] 3 2 1 10 112 3 1[9][+] 5[19][-] 1 4 28 4 0 1[5][+] 4[26][-] 1[15] 46 Потребности 24 24 26 15 Цикл приведен в таблице (1,3 → 1,1 → 3,1 → 3,2 → 4,2 → 4,3). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 5. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план. B1 B2 B3 B4 Запасы A1 3 2 3[5] 4 5 A2 1[10] 3 2 1 10 A3 1[14] 5[14] 1 4 28 A4 0 1[10] 4[21] 1[15] 46 Потребности 24 24 26 15 Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v3 = 3; 0 + v3 = 3; v3 = 3 u4 + v3 = 4; 3 + u4 = 4; u4 = 1 u4 + v2 = 1; 1 + v2 = 1; v2 = 0 u3 + v2 = 5; 0 + u3 = 5; u3 = 5 u3 + v1 = 1; 5 + v1 = 1; v1 = -4 u2 + v1 = 1; -4 + u2 = 1; u2 = 5 u4 + v4 = 1; 1 + v4 = 1; v4 = 0 v1=-4 v2=0 v3=3 v4=0 u1=0 3 2 3[5] 4