ПРИКЛАДНЫЕ МЕТОДЫ ОПТИМИЗАЦИИ

3.      Полученное неравенство (1.5.5) преобразуется в равенство путем добавления новой неотрицательной переменной

и присоединяется к задаче, рассмотренной в п. 1.

4.      Решаем задачу с добавленным в п. 3 ограничением. Если ее решение оказывается целочисленным, то оно будет решением поставленной задачи. В противном случае переходим к п. 2.

Правило построения правильных сечений заключается в следующем. Пусть решение исходной задачи без требования целочисленности симплекс-методом на последнем шаге дало решение, в котором базисные переменные x1, ..., xm связаны с небазисными переменными xm+1, ... , xn формулами

т.е., в этом случае вектор является оптимальным решением. Пусть имеет положительную дробную часть {b'io} > 0. В этом случае в качестве правильного сечения можно взять неравенство

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

Метод ветвей и границ.

Изложим теперь метод ветвей и границ для решения задачи ЦЛП. Соответствующий алгоритм был впервые предложен А.Лэнд и А.Дойг и в отличие от метода Гомори применим как к полностью, так и к частично целочисленным задачам.

На первом шаге задача ЦЛП решается как задача линейного программирования, т.е. без требования целочисленности переменных. Предположим, что в полученном оптимальном решении переменная является дробной. Тогда можно утверждать, что искомое целочисленное решение должно строго удовлетворять одному из неравенств

или

Введение каждого из этих неравенств в решаемую задачу линейного программирования (без требования целочисленности) порождает две несвязанные между собой задачи. Таким образом, исходная задача как бы разветвляется на две подзадачи.

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

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

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

1.6 Динамическое программирование

Динамическое программирование (ДП) применяется к решению задач, в которых процесс принятия решений может быть разбит на ряд этапов. ДП начало развиваться в 50-х годах XX благодаря работам Р.Беллмана. Впервые этим методом решались задачи оптимального управления запасами, затем класс решаемых задач значительно расширился.

В основе метода ДП лежит принцип оптимальности, сформулированный Р.Беллманом. Этот принцип и идея включения конкретной задачи оптимизации в семейство аналогичных многошаговых задач приводят к рекуррентным соотношениям и функциональным уравнениям для оптимального значения целевой функции. Их анализ позволяет последовательно получить решение для исходной задачи оптимизации.

Рассматривается управляемый процесс. В результате управления система (объект управления) переводится из начального состояния в0 в состояние s. Предполагается, что управление можно разбить на n шагов, то есть решение принимается последовательно на каждом шаге, а управление, переводящее систему из начального состояния в конечное, представляет собой совокупность n пошаговых управлений.

Обозначим через Xk управление на k-м шаге k = 1, 2,... ,n. Переменные Xi удовлетворяют некоторым ограничениям и в этом смысле называются допустимыми (Xk может быть числом, точкой в n-мерном пространстве, качественным признаком).

Пусть X(X1, X2,... , Xn) - управление, переводящее систему S из состояния S0 в состояние ŝ. Обозначим через sk состояние системы после k-го шага управления. Получаем последовательность состояний

Показатель эффективности рассматриваемой управляемой операции–целевая функция – зависит от начального состояния и управления:

Предположения:

1.      Состояние sk системы в конце k-го шага зависит только от предшествующего состояния sk-1 и управления на k-м шаге Xk. Это требование называется отсутствием последствий. Сформулированное положение записывается в виде уравнений:

которые называются уравнениями состояний.

2.      Целевая функция является аддитивной от показателя эффективности каждого шага. Обозначим показатель эффективности k-го шага через

тогда

Задача пошаговой оптимизации формируется так: определить такое допустимое управление X, переводящее систему S из состояния s0 в состояние ŝ, при котором целевая функция принимает наибольшее значение.

Замечания:

1.      Задача оптимизации интерпретируется как n-шаговый процесс управления.

2.      Целевая функция равна сумме целевых функций каждого шага.

3.      Выбор управления на каждом k-м шаге зависит только от состояния системы к этому шагу, не влияет на предшествующие шаги (нет обратной связи).

4.      Состояние sk после k-го шага управления зависит только от предшествующего состояния sk-1 и управления Xk (отсутствуют последствия).

5.      На каждом шаге управление Xk зависит от конечного числа управляющих переменных, а состояние sk - от конечного числа параметров.

Особое значение при решении задачи динамического программирования имеет принцип оптимальности, который был сформулирован Р.Беллманом в 1953 году.Он звучит так:

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

К задаче динамического программирования относится задача о распределении средств между предприятиями и оптимизационная задача потребительского выбора.

2 Практическая задача на нахождение градиента функции

В практической части курсовой работы предложено рассмотреть задачу нелинейной оптимизации на нахождение градиента функции.

Задача:

Для функции вычислить градиент в точках , , , .

Решение:

Градиентом (обозначается f'(x)) непрерывно дифференцируемой функции f(x) в точке x называется вектор–столбец, элементами которого являются частные производные первого порядка, вычисленные в данной точке:

, где Т–вектор-столбец.

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

Вычислим частную производную этой функции, т.е.: найдем градиент целевой функции:

;

;

Затем вычисляем значение градиента целевой функции в каждой из заданных точек:

1.      Для точки : ,  ;

.

2.      Для точки :, ;

.

3.      Для точки :, ;

.

4.      Для точки :, ;

.

Ответ:

Градиент целевой функции ; градиенты функции в заданных точках: ; ; ; .

Заключение

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

Значения переменных могут подчиняться ограничениям или изменяться без ограничений. Любое решение оптимизационной задачи должно учитывать эти ограничения.

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

Также в курсовой работе подробно разобран пример решения задачи на нахождение градиента функции, что относится к задаче нелинейной оптимизации.

Список использованной литературы

1.      Банди Б. Методы оптимизации. Вводный курс /  Б.  Банди. – М.: Высшая школа, 1986. – 127 с.

2.      Голубев А.Д. Методы оптимизации – Киров: ВятГТУ, 1997. – 259 с.

3.      Дегтярев Ю. И. Методы оптимизации – М.: Советское радио, 1980. – 272 с.

4.      Дрогобыцкий И.Н.  Экономико-математическое  моделирование / И. Н. Дрогобыцкий. – М.: Экзамен, 2006. – 797 с.

5.      Курс методов оптимизации: Учебное пособие для вузов / А. Г. Сухарев, А. В. Тимохов, В. В. Федоров; Московский государственный университет им. М. В. Ломоносова. - 2-е изд. - М.: Физматлит, 2005. - 367 с.

6.      Коршунова Н.И.  Математика  в  экономике:  учебное  пособие / Н. И. Коршунова, В. С. Плясунов. – М.: ВИТА, 1996. – 364 с.

7.      Красс М.С. Основы  математики  и  ее  приложения  в  экономическом образовании / М. С. Красс. – М.: Дело, 2000. – 688 с.

8.      Кремер Н. Ш. Исследование  операций  в  экономике ;  учебник / Н. Ш. Кремер – М. : ЮНИТИ, 1997. – 407 с

9.      Минюк С.А. Математические  методы  и  модели  в  экономике : учеб. пособие / С. А. Минюк, Е. А. Ровба, К. К. Кузьмич. – Мн.: ТетраСистемс, 2002. – 432 с.

10. Мицель А.А. Методы оптимизации : Учебное пособие / А. А. Мицель, А. А. Шелестов - Томск : ТУСУР, 2004. - 255с.

11. Пантелеев А.В. Методы оптимизации в примерах и задачах: Учебное пособие для втузов. - М.: Высшая школа, 2002. - 544 с

12. Шапкин А.С. Математические методы и модели исследования операций: учебник для вузов / А. С. Шапкин, Н. П. Мазаев. – 3-е изд. – М.: Дашков и К, 2006. – 400 с.

29