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

Заказ №38652

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