Метод Гаусса
Метод Гаусса — это последовательное изменение состава опорного решения до получения оптимального варианта, не допускающего улучшения, это способ решения оптимизационной задачи, у которой оценка и ограничения являются линейными функциями. Рассмотрим алгоритм метода Гаусса на числовом примере. Постановка задачи: максимизировать
2x(1) + 3x(2) + 7x(3) + 9x(4)
при ограничениях:
x(1) + x(2) + x(3) + x(5) = 9;
x(1) + 2x(2) + 4x(3) + 8x(4) + x(6) = 24.
При наличии двух ограничений в конечном оптимизационном решении будут две переменные, отличные от нуля. Примем для первого варианта решения в качестве этих переменных x(2) и x(3).
Из второго уравнения вычтем первое, умноженное на 2. Получим
x(3) = 3 + x(1)/2 - 3x(4) + x(5) - x(6)/2.
Из первого уравнения вычтем полученное:
x(2) = 6 - 3x(1)/2 +2x(4) - 2x(5) + x(6)/2.
Если принять x(1) = x(4) = x(5) = x(6) = 0, то x(2) = 6, x(3) = 3. Значение оценки при этом составит 39.
Рассмотрим второй вариант решения, при котором в составе оптимизационного решения будут x(1) и x(3), не равные нулю. По аналогичной процедуре получим
x(1) = 4 - 2x(2)/3 + 4x(5)/3 + x(6)/3;
x(3) = 5 - x(2)/3 + 7x(4)/3 + x(5)/3 - x(6)/3.
Если принять x(2) = x(4) = x(5) = x(6) = 0, то получим x(1) = 4, x(3) = 5. Значение оценки составит 43.
Любые изменения второй, четвертой, пятой и шестой переменных ведут к уменьшению значения оценки, поэтому можно утверждать, что найденное решение является оптимальным.
Похожие рефераты:
