Построение оптимального производственного плана химической компании
Реферат - Математика и статистика
Другие рефераты по предмету Математика и статистика
? алгоритм решения задачи.
Пусть Xk допустимая точка, полученная на k-ой итерации. Раскладывая исходную функцию в ряд Тейлора, имеем . Здесь, очевидно, X и Xk векторы. Необходимо определить допустимую точку X=X*, в которой достигается максимум функции f(X) при выполнении линейных ограничений задачи. Так как - постоянное слагаемое, задача определения X* сводится к решению задачи линейного программирования:
Так как целевая функция wk определяется градиентом функции f(X) в точке Xk, улучшение имеющегося решения может быть обеспечено тогда и только тогда, когда . Из вышеуказанного разложения функции в ряд Тейлора не следует, что f(X*) > f(Xk), так как X* не обязательно находится в малой окрестности точки Xk. Но при выполнении условия на отрезке [Xk,X*] должна существовать точка Xk+1, такая, что f(Xk+1) > f(Xk). Следовательно, задача сводится к нахождению такой точки Xk+1. Определим указанную точку следующим образом:
Отсюда следует, что точка Xk+1 является линейной комбинацией точек Xk и X*, значит это точки выпуклой области допустимых решений, поэтому точка Xk+1 также является допустимой. Так как Xk+1 зависит лишь от r, то Xk+1 определяется путём максимизации функции . Данная итерационная процедура повторяется до тех пор, пока на k-ой итерации не будет выполнено условие . В этой точке дальнейшее улучшение невозможно, процесс вычислений завершается, точка Xk считается наилучшим решением. Поскольку задачи линейного программирования, возникающие на каждой итерации, отличаются друг от друга лишь коэффициентами целевой функции, можно применить анализ чувствительности к соответствующим изменениям.
Теперь вкратце необходимо описать применение обобщённого симплекс-метода (сочетает в себе прямой и двойственный симплекс методы) для решения задачи линейного программирования. Рассмотрим для начала симплекс-таблицу и правила её построения.
Таблица 2
Пример симплекс-таблицы
БазисX1X2X3X4РешениеZ-1-2000X321103X434012
Эта таблица представляет собой начальную симплекс-таблицу и эквивалентна следующей задаче линейного программирования:
Здесь переменные X3, X4 являются вспомогательными для получения начального базисного решения. Если бы неравенства имели знак ?, то они вычитались бы из их левых частей.
После того как сформировано начальное базисное решение, проводятся операции по его улучшению, сохраняя при этом допустимость решения. В задаче максимизации целевой функции оптимум достигается тогда и только тогда, когда коэффициенты при небазисных переменных становятся положительными. Итерации симплекс-метода подвергаются условиям оптимальности и допустимости.
Условие допустимости: в качестве исключаемой переменной из базиса выбирается такая, для которой отношение значения правой части ограничения к положительному коэффициенту ведущего столбца минимально. Если переменных с таким свойством несколько, то выбирается любая из них.
Условие оптимальности: в качестве вводимой переменной в задаче максимизации является небазисная переменная, имеющая наибольший отрицательный коэффициент в z-строке. Если переменных с таким свойством несколько, то выбирается любая из них.
Теперь можно привести последовательность действий прямого симплекс-метода:
находится начальное допустимое базисное решение;
на основе условия оптимальности определяется вводимая переменная. Если вводимых переменных нет, вычисления заканчиваются;
на основе условия допустимости выбирается исключаемая переменная;
методом Гаусса вычисляется новое базисное решение. Переход к шагу 2.
К сожалению, нахождение начального базисного решения можно обеспечить только лишь в случае, когда все ограничения задачи линейного программирования имеют знак ?. В противном случае либо используют искусственные переменные, либо используют двойственный симплекс-метод в комбинации с прямым симплекс-методом (обобщённый симплекс-метод).
Идея двойственного симплекс-метода состоит в рассмотрении в качестве начального базиса оптимальное, но недопустимое решение (супероптимальное решение). То есть умножают неравенства со знаком ? на (-1). Таким образом, если в z-строке находится изначально оптимальное решение, то применим двойственный симплекс-метод.
Условие допустимости: в качестве исключаемой переменной выбирается такая, которая имеет наибольшее по абсолютной величине отрицательное значение. Если все базисные переменные неотрицательны, процесс вычислений заканчивается.
Условие оптимальности: вводимая переменная определяется, соответствующая условию , где arj коэффициент из симплекс-таблицы, расположенный на пересечении ведущей строки (соответствующей исключаемой переменной xr), соответствующего переменной xj. При наличии альтернативы выбор делается произвольно.
Однако, при умножении неравенств со знаком ? на (-1) начальное базисное решение может оказаться неоптимальным и недопустимым. В таких случаях применяется обобщённый симплекс-метод: сначала применяем двойственное условие допустимости. Выбор вводимой переменной осуществляется с применением двойственного условия оптимальности. Описанная процедура повторяется до тех пор, пока не будет получено допустимое решение. Далее применяется прямой симплекс-метод, где начальное базисное решение уже соответствует условию допустимости, но не является оптимальным.
В завершении обзора алгоритма решения и