Методы оптимизации

МИНИСТЕРСТВО ОБРАЗОВАНИЯ  И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ  УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

“САХАЛИНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ”

КАФЕДРА МАТЕМАТИКИ, ФИЗИКИ И ИНФОРМАТИКИ

 

 

 

 

 

 

 

 

 

 

 

 Методы  оптимизации

 

 

 

 

 

 

 

 

Выполнил:

 

 

 

 

 

 

 

 

 

 

 

Южно-Сахалинск, 2013

4.Задача условий оптимизации с ограничениями-равенствами. Метод множителей Лагранжа.

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

Будем предполагать, что m ≤ n. В дальнейшем нам потребуется  следующая

Теорема о неявных  функциях. Предположим, что:

1) дана  система из m уравнений с n неизвестными (m ≤ n)

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

точки , в которой

3) якобиан                                                                

Тогда:

а) в  некоторой окрестности точки  , содержащейся в , система уравнений (3) определяет как однозначные функции от      

б) при  эти функции принимают значения ;

в) все  функции  непрерывны и имеют непрерывные частные производные по всем аргументам.

Следует обратить внимание на локальный  характер теоремы существования  неявных функций: речь идет все время о некоторой окрестности рассматриваемой точки. Но и в таком виде эта теорема полезна.

Рассмотрим теперь задачу (1) о нахождении экстремума функции на множестве X , определяемом условием (2). Предполагается, что функции непрерывны и непрерывно дифференцируемы в окрестности некоторой экстремальной точки . Пусть в этой точке ранг матрицы частных производных

 
равен m. Для определенности будем считать, что определитель

Тогда, в силу теоремы  о неявных функциях, в некоторой  окрестности точки  система уравнений     

равносильна системе 

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

в точке  . Эти соображения приводят к методу нахождения точек, доставляющих экстремум функции при ограничениях-равенствах. Если каким-то образом удается разрешить систему уравнений относительно переменных и найти явные выражения для функций (5) , то дело сводится к нахождению безусловного экстремума для функции (6) . Этот метод называется методом исключения зависимых переменных. Можно указать другой путь для нахождения экстремальных точек, не предполагая, что мы имеем явные выражения для функций (5) , хотя существование этих функций использоваться будет. Лагранж предложил метод, в котором все переменные сохраняют одинаковую роль.

Метод неопределенных множителей Лагранжа. Введем в рассмотрение новые переменные  и функцию

Переменные  называются неопределенными множителями Лагранжа, а функция F(x, y) функцией Лагранжа. Пусть в точке , удовлетворяющей системе , выполнены условия теоремы о неявных функциях.

Тогда, для того чтобы точка  была точкой экстремума задачи (1) (2) ,

необходимо существование таких чисел , что выполняются равенства   

Условия (8) , очевидно, эквивалентны условиям . При решении задачи (1) (2) данным методом существенную роль играет предположение о ранге матрицы (4) . Чтобы быть уверенным в том, что не пропущена ни одна подозрительная точка, следует предварительно установить, что это предположение выполняется во всех точках множества X .

 

11.Целочисленное программирование. Метод Гомори. Метод ветвления.

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

(2.1.1)

(2.1.2)           

    (2.1.3)

- целые. (2.1.4)

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

1) новый многогранник  решений содержит все целые  точки, заключавшиеся в первоначальном  многограннике решений; любая его угловая точка является целой;

2) так как  линейная функция достигает оптимума  в угловой точке многогранника  решений, то построением такого  многогранника и обеспечивается  целочисленность оптимального решения.

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

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

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

Дополнительное ограничение  составляется следующим образом. Пусть  оптимальный план   получен на базисе ; тогда последняя симплексная таблица имеет следующий вид:

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

 

где  и   – неотрицательные.

Так как по условию   - неотрицательные целые числа, то и разность

 (2.1.5)

также целое неотрицательное  число.

Преобразуя это неравенство  в уравнение, вычитая из его левой  части целую неотрицательную  дополнительную переменную  , умножим уравнение на -1, добавим к последней симплексной таблице и, применяя двойственный симплексный метод, находим новый план. Если он не является целочисленным, то по последней симплексной таблице составляем новое дополнительное ограничение.

Если в оптимальном  плане несколько дробных  , то дополнительное ограничение составляется для максимального  . Это ускоряет процесс получения оптимального целочисленного решения.

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

1. Используя симплексный метод, находят решение задачи (2.1.1)-(2.1.3) без учета требования целочисленности переменных.
2. Составляют дополнительное ограничение для переменной, которая в оптимальном плане задачи (2.1.1)-(2.1.3) имеет максимальное дробное значение, а в оптимальном плане задачи (2.1.1)-(2.1.4) должна быть целочисленной.
3. Используя двойственный симплекс-метод, находят решение задачи, получающейся из задачи (2.1.1)-(2.1.3) в результате присоединения дополнительного ограничения.
4. В случае необходимости составляют еще одно дополнительное ограничение и продолжают итерационный процесс до получения оптимального плана задачи (2.1.1)-(2.1.4) или установления ее неразрешимости.

Метод ветвей и границ. Продолжим рассмотрение задачи (2.1.1)-(2.1.4),состоящей в определении минимального значения линейной функции

при ограничениях

- целые.

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

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

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

При решении задач  линейного программирования   и   возможен один из следующих четырех случаев:

1. Одна из задач неразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план и значение целевой функции на нем и дают решение исходной задачи.
2. Одна из задач неразрешима, а другая имеет оптимальный план, среди компонент которого есть дробные числа. Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному числу, и строим две задачи, аналогичные задачам   и  .
3. Обе задачи разрешимы. Одна из задач имеет оптимальный целочисленный план, а в оптимальном плане другой задачи есть дробные числа. Тогда вычисляем значения целевой функции на этих планах и сравниваем их между собой. Если на целочисленном оптимальном плане значение целевой функции больше или равно ее значению на плане, среди компонент которого есть дробные числа, то данный целочисленный план является оптимальным для исходной задачи и он вместе со значением целевой функции на нем дает исходное решение.

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

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

Итак, процесс нахождения решения задачи целочисленного программирования (2.1.1)-(2.1.4) методом ветвей и границ включает следующие основные этапы:

1. Находят решение  задачи целочисленного программирования (2.1.1)-(2.1.3).

2. Составляют дополнительные  ограничения для одной из переменных, значение которой в оптимальном  плане задачи (2.1.1)-(2.1.3) является дробным  числом.

3. Находят решение  задач   и  , которые получаются из задачи (2.1.1)-(2.1.3) в результате присоединения дополнительных ограничений.

4. В случае необходимости  составляют дополнительные ограничения для переменной, значение которой является дробным, формулируют задачи, аналогичные задачам   и  , и находят их решение. Итерационный процесс продолжается до тех пор, пока не будет найден оптимальный целочисленный план задачи (2.1.1)-(2.1.4).

14.Понятие седловой точки функции Лагранжа.

 

Возьмем пару двойственных задач ЛП.

Прямая задача .		Двойственная задача .
Запишем в другом виде
,		,

где  — двойственная оценка для прямой задачи;

 — двойственная оценка для  двойственной задачи.

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

               (5.15)

                (5.16)

Из (5.15)—(5.16) следует, что  для прямой ЗЛП двойственные оценки служат множителями Лагранжа, для двойственной ЗЛП множителями Лагранжа являются переменные Сложив почленно (5.15) и (5.16) получим

Определение. Функция имеет в точке седловую точку, если

                 (5.17)

для всех X из — окрестности и всех Y из — окрестности Если неравенства (5.17) выполняются для всех X и Y из области определения функции то она имеет глобальную седловую точку Оптимальные решения пары двойственных задач ЛП образуют седловую точку функции Лагранжа (5.15). Геометрическая интерпретация седловой точки функции Лагранжа показана на рис. 5.3.