Задачи линейного программирования. _Готовое 84-04-3. Задача 1 3 Задача 2 6 Задача 3 9 Задача 4 15
![]()
|
Этап II. Улучшение опорного плана. Проверим оптимальность опорного плана методом потенциалов. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v1 = 13; 0 + v1 = 13; v1 = 13 u1 + v4 = 11; 0 + v4 = 11; v4 = 11 u3 + v4 = 9; 11 + u3 = 9; u3 = -2 u3 + v2 = 8; -2 + v2 = 8; v2 = 10 u2 + v2 = 4; 10 + u2 = 4; u2 = -6 u2 + v3 = 2; -6 + v3 = 2; v3 = 8 u1 + v5 = 3; 0 + v5 = 3; v5 = 3
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (1;3): 0 + 8 > 6; ∆13 = 0 + 8 - 6 = 2 > 0 (3;3): -2 + 8 > 5; ∆33 = -2 + 8 - 5 = 1 > 0 max(2,1) = 2 Выбираем максимальную оценку свободной клетки (1;3): 6 Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (1,3 → 1,4 → 3,4 → 3,2 → 2,2 → 2,3). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 4) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v1 = 13; 0 + v1 = 13; v1 = 13 u1 + v3 = 6; 0 + v3 = 6; v3 = 6 u2 + v3 = 2; 6 + u2 = 2; u2 = -4 u2 + v2 = 4; -4 + v2 = 4; v2 = 8 u3 + v2 = 8; 8 + u3 = 8; u3 = 0 u3 + v4 = 9; 0 + v4 = 9; v4 = 9 u1 + v5 = 3; 0 + v5 = 3; v5 = 3
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (2;1): -4 + 13 > 7; ∆21 = -4 + 13 - 7 = 2 > 0 (3;3): 0 + 6 > 5; ∆33 = 0 + 6 - 5 = 1 > 0 max(2,1) = 2 Выбираем максимальную оценку свободной клетки (2;1): 7 Для этого в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (2,1 → 2,3 → 1,3 → 1,1). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 60. Прибавляем 60 к объемам грузов, стоящих в плюсовых клетках и вычитаем 60 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v3 = 6; 0 + v3 = 6; v3 = 6 u2 + v3 = 2; 6 + u2 = 2; u2 = -4 u2 + v1 = 7; -4 + v1 = 7; v1 = 11 u2 + v2 = 4; -4 + v2 = 4; v2 = 8 u3 + v2 = 8; 8 + u3 = 8; u3 = 0 u3 + v4 = 9; 0 + v4 = 9; v4 = 9 u1 + v5 = 3; 0 + v5 = 3; v5 = 3
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (3;3): 0 + 6 > 5; ∆33 = 0 + 6 - 5 = 1 > 0 Выбираем максимальную оценку свободной клетки (3;3): 5 Для этого в перспективную клетку (3;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Цикл приведен в таблице (3,3 → 3,2 → 2,2 → 2,3). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 90. Прибавляем 90 к объемам грузов, стоящих в плюсовых клетках и вычитаем 90 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v3 = 6; 0 + v3 = 6; v3 = 6 u3 + v3 = 5; 6 + u3 = 5; u3 = -1 u3 + v2 = 8; -1 + v2 = 8; v2 = 9 u2 + v2 = 4; 9 + u2 = 4; u2 = -5 u2 + v1 = 7; -5 + v1 = 7; v1 = 12 u3 + v4 = 9; -1 + v4 = 9; v4 = 10 u1 + v5 = 3; 0 + v5 = 3; v5 = 3
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij. Минимальные затраты составят: F(x) = 6*70 + 3*150 + 7*60 + 4*120 + 8*60 + 5*90 + 9*50 = 3150 ус. ед. Анализ оптимального плана. Из 1-го склада необходимо груз направить в 3-й пункт (70 ед.), в 5-й пункт (150 ед.) Из 2-го склада необходимо груз направить в 1-й пункт (60 ед.), в 2-й пункт (120 ед.) Из 3-го склада необходимо груз направить в 2-й пункт (60 ед.), в 3-й пункт (90 ед.), в 4-й пункт (50 ед.) |