1118 логистика. Оглавление 1 Основные направления расширения комплекса услуг сбытовой деятельности предприятия
 Скачать 59.77 Kb.
|
|
предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v1 = 8; 0 + v1 = 8; v1 = 8 u2 + v1 = 9; 8 + u2 = 9; u2 = 1 u2 + v2 = 11; 1 + v2 = 11; v2 = 10 u4 + v2 = 12; 10 + u4 = 12; u4 = 2 u4 + v6 = 13; 2 + v6 = 13; v6 = 11 u3 + v1 = 6; 8 + u3 = 6; u3 = -2 u3 + v5 = 7; -2 + v5 = 7; v5 = 9 u5 + v5 = 8; 9 + u5 = 8; u5 = -1 u5 + v3 = 10; -1 + v3 = 10; v3 = 11 u5 + v4 = 9; -1 + v4 = 9; v4 = 10 u3 + v8 = 0; -2 + v8 = 0; v8 = 2 u1 + v7 = 9; 0 + v7 = 9; v7 = 9
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (3;2): -2 + 10 < 10; ∆32 = -2 + 10 - 10 = -2 > 0 (3;7): -2 + 9 < 8; ∆37 = -2 + 9 - 8 = -1 > 0 max(2,1) = -2 Выбираем максимальную оценку свободной клетки (3;2): 10 Для этого в перспективную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (3,2 → 3,1 → 2,1 → 2,2). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 100. Прибавляем 100 к объемам грузов, стоящих в плюсовых клетках и вычитаем 100 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v1 = 8; 0 + v1 = 8; v1 = 8 u2 + v1 = 9; 8 + u2 = 9; u2 = 1 u3 + v1 = 6; 8 + u3 = 6; u3 = -2 u3 + v2 = 10; -2 + v2 = 10; v2 = 12 u4 + v2 = 12; 12 + u4 = 12; u4 = 0 u4 + v6 = 13; 0 + v6 = 13; v6 = 13 u3 + v5 = 7; -2 + v5 = 7; v5 = 9 u5 + v5 = 8; 9 + u5 = 8; u5 = -1 u5 + v3 = 10; -1 + v3 = 10; v3 = 11 u5 + v4 = 9; -1 + v4 = 9; v4 = 10 u3 + v8 = 0; -2 + v8 = 0; v8 = 2 u1 + v7 = 9; 0 + v7 = 9; v7 = 9
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (3;7): -2 + 9 < 8; ∆37 = -2 + 9 - 8 = -1 > 0 (4;5): 0 + 9 < 10; ∆45 = 0 + 9 - 10 = -1 > 0 max(1,1) = -1 Выбираем максимальную оценку свободной клетки (3;7): 8 Для этого в перспективную клетку (3;7) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (3,7 → 3,1 → 1,1 → 1,7). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 1) = 100. Прибавляем 100 к объемам грузов, стоящих в плюсовых клетках и вычитаем 100 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Проверим оптимальность опорного плана. Найдем |