Прямые методы безусловной оптимизации

Кроме методов, использующих аппарат дифференциального исчисления, в практике безусловной оптимизации находят широкое применение так называемые графические методы.

Проиллюстрируем применение графического метода на примере решения задачи линейного программирования.

Итак, экономико-математическая задача формулируется следующим образом:

Найти такой план выпуска продукции x=(x₁,x₂), при котором целевая функция принимает максимальное значение.

Примем без доказательства следующее утверждение: множество допустимых решений (многогранник решений) задачи линейного программирования представляет собой выпуклый многогранник (или выпуклую многогранную область), а оптимальное решение задачи находится, по крайней мере, в одной из угловых точек многогранника решений.

Пусть геометрическим изображением решения данной задачи является многоугольник ABCDE (рис.16).

X₂ F=F_max

F=F_min B

A

F=0 E

F=a

x₁

Рис. 13. Иллюстрация графического метода

Необходимо найти такую точку среди всех точек многоугольника, в которой линейная функция F=c₁x₁+c₂x₂ принимает максимальное или минимальное значение.

Рассмотрим так называемую линию уровня линейной функции F, т.е. линию, вдоль которой эта функция принимает одно и тоже фиксированное значение a или c₁x₁+c₂x₂=a.

Это уравнение есть уравнение прямой линии. При различных значениях a линии уровня параллельны, т.к. их угловые коэффициенты определяются только соотношением между c₁ и c₂. И все они параллельны. Важное свойство линии уровня линейной функции состоит в том, что при параллельном смещении линии в одну сторону от F=a уровень возрастает, в другую убывает.

Смысл графического метода заключается в следующем. Для определения экстремума (максимума или минимума) необходимо вычислить и изобразить две линии уровня и определить, на которой из них уровень больше. Например, одну из линий можно взять, проходящую через начало координат. Другую линию можно провести произвольно, например через множество решений. Далее, определив направление возрастания линейной функции (обозначим его через вектор ), найдем точку, в которой функция принимает max или min значение. На рис.15- соответственно т.C и т.A(F_max и F_min).

Для вычисления целевой функции необходимо решить систему линейных уравнений вида:

a₁₁x₁+a₁₂x₂ b₁

a₂₁x₁+a₂₂x₂ b₂

……………….

……………….

……………….

a_m1x₁+a_m2x₂ b_{m ,}

которые обычно задаются в виде неравенств и являются ограничениями. Сама же оптимизируемая функция при линейном программировании соответственно представляет собой линейную функцию f=c₁x₁+c₂x₂+…+c_nx_n+c.

Для решения задачи необходимо среди неотрицательных решений системы (10) нужно найти такое, которое минимизирует(максимизирует) функцию f

F= max (или min).

Если система ограничений (10) состоит из одних неравенств, то такая задача называется стандартной, если система ограничений (10) состоит из одних уравнений, то задача называется канонической.

Таким образом, графический метод состоит в следующем.

1. Строится множество x всех допустимых решений.

2. Если x=0, то задача неразрешима.

3. Если x 0, то рассматриваются линии уровня

F=a при монотонном изменении a от - .

При увеличении a прямая f=a смещается параллельно в направлении вектора . Если A- первая точка встречи линии уровня с областью x. F(A)=a₀, то прямая уровня f(x)=a при a<a₀ не имеет общих точек с x. Отсюда следует, что a₀=min f на x. Аналогичным образом, если A- последняя точка пересечения линии уровня с x, то f(A)=max f на A.

Дата добавления: 2015-07-26; просмотров: 145; Нарушение авторских прав

Мы поможем в написании ваших работ!