Основные понятия теории оптимизации

СОДЕРЖАНИЕ

Введение………………………………………………………………………....3

1. Основные понятия теории оптимизации……………………………...…5

1.1. Общая постановка задачи оптимизации…………………………………..5

1.2. Ограничения  на допустимое множество……………………………...…6

1.3. Классическая  задача оптимизации……………………………………….6

1.4. Функция Лагранжа…………………………………………………………6

2. Линейное программирование: формулировка задач и их 

графическое решение………………………………………………………….8

2.1. Задача ЛП……………………………………………………………………8

2.2. Графическое решение  задачи ЛП………………………………………….9

3. Алгебраический  метод решения задач……………………………………11

3.1. Стандартная форма  линейных оптимизационных моделей……………...11

3.2. Симплекс-метод………………………………………………………….....12

4. Двойственность………………………………………………………………25

Заключение……………………………………………………………………...29

Библиографический список ……………………………………………...…..30

 

 

 

 

 

 

Введение

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

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

· оптимизации производственной программы  предприятий;

· оптимального размещения и концентрации производства;

· составления оптимального плана  перевозок, работы транспорта;

· управления производственными запасами;

· и многие другие, принадлежащие  сфере оптимального планирования.

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

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

Математическое программирование - это прикладная отрасль математики, которая является теоретической  основой решения задач оптимального планирования.

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

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

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

 

 

 

 

 

 

 

 

 

1. Основные понятия теории оптимизации

1.1. Общая постановка задачи оптимизации

В общей задаче требуется  найти вектор

из допустимой области  , который обращает в минимум целевую функцию q(x), т.е. такой , для которого

 (1)

Если  существует, то он определяет слабый, глобальный (абсолютный) минимум q*(x) в допустимой . Слабый, т.к. удовлетворяет нестрогому неравенству. Глобальный, т.к. неравенство справедливо для любых x из области X. Минимум при сильный, если для . Если поменять знаки неравенств – получим сильный и слабый максимумы. Минимум в точке называется локальным (относительным), если найдётся такая окрестность O(x*) точки , что для всех имеет место . Если дифференцируема, то задача отыскания локальных минимумов сводится к нахождению стационарных точек, в которых обращаются в ноль частные производные q(x):

  (2)

(2) – необходимое, но  не достаточное условие. Достаточным  условием существования в стационарной  точке относительного минимума  является положительная определённость квадратичной формы.

 

1.2. Ограничения на допустимое множество

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

 

1.3. Классическая задача оптимизации

Состоит в нахождении минимума целевой функции , где – точка в пространстве при начальных ограничениях типа равенств

  (3)

Если (3) имеют место, то минимум q(x) называется условным минимумом. Если ограничения (3) отсутствуют, то говорят о безусловном минимуме.

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

  (4)

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

 

1.4. Функция Лагранжа

Введём в рассмотрение вектор и исследуем свойства функции

  (5)

– функция Лагранжа, - множители Лагранжа.

– функция n+m переменных .

Рассмотрим  стационарные точки функции  , которые получим, приравняв к нулю частные производные по и по :

  (6)

 (7)

Если в стационарной точке (x*, y*) функция достигает минимума, то обеспечивает минимум функции q(x) и при выполнении ограничений (3), т.е. даёт решение задачи.

Задача на условный минимум  целевой функции q(x) при наличии ограничений типа равенств сводится к задаче на определение стационарных точек функции Лагранжа .

 

2. Линейное программирование: формулировка задач и их графическое решение

2.1. Задача ЛП

Рассмотрим на примере задачи фирмы. Небольшая фабрика изготовляет два вида красок: для наружных (E) и внутренних (I) работ. Продукция поступает в оптовую продажу. Для производства красок используется два исходных продукта – A и B. Максимально возможные суточные запасы этих продуктов составляют 6т и 8т соответственно. Расходы A и B на производство 1т соответствующих красок приведены в таблице.

 

Исходный продукт	Расход на тонну  краски		Максимальный  запас, т.
	краска E	краска I
A	1	2	6
B	2	1	8

 

Суточный спрос на краску I никогда не превышает спроса на краску E более чем на 1т. Спрос  на I не превышает 2т. Оптовая цена за 1т краски E – 3000$, I – 2000$. Какое количество краски каждого вида фабрика должна производить, чтобы доход от реализации продуктов был максимальным?

Так как нужно определить объём производства каждого вида краски, переменными в модели являются:

xE – суточный объём производства краски E (в тоннах);

xI – суточный объём производства краски I (в тоннах).

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

Ограничения на расход исходных продуктов:

(для A)

(для B)

Ограничения на величину спроса на продукцию:

Потребуем выполнения условия  неотрицательности переменных:

Получили математическую модель:

Определить суточные объёмы производства (в т.) краски I и E, при которых достигается

(целевая функция)

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

2.2. Графическое решение задачи ЛП

Построим область допустимых решений, в которой одновременно выполняются  все ограничения. Искомое пространство решений – многоугольник ABCDEF. Пространство решений содержит бесконечное число точек, являющихся допустимыми решениями, но, несмотря на это, можно найти оптимальное решение, если выяснить, в каком направлении возрастает целевая функция модели z=3xE+2xI. На график наносят ряд параллельных линий, соответствующих уравнению целевой функции при нескольких произвольно выбранных и последовательно возрастающих значениях , что позволяет определить наклон целевой функции и направление её увеличения. На видно, что оптимальному решению соответствует точка C, являющаяся пересечением прямых

Решив систему, получим

 Тогда получаемый  доход

тыс $.

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

 

 

 

 

 

 

 

 

 

 

3. Алгебраический метод решения задач

Использование графического метода удобно при решении задач ЛП с двумя  переменными. При большем их числе необходимо применение алгебраичского аппарата.

Процесс решения задачи ЛП симплекс-методом носит итерационный характер: однотипные вычислительные процедуры в определённой последовательности выполняются до тех пор, пока не будет  получено оптимальное решение.

 

3.1. Стандартная форма линейных оптимизационных моделей

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

Например,

Введём остаточную переменную s1>0, тогда

Правую часть равенства  можно сделать неотрицательной, умножив обе части на –1.

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

При любом допустимом решении только одна из этих переменных может принимать положительное  значение, т.к. если , то , и наоборот. Это позволяет рассматривать как остаточную переменную, а – как избыточную.

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

 

3.2. Симплекс-метод

Общую идею симплекс-метода проиллюстрируем на примере. На исходная точка алгоритма – начало координат (т. A) – начальное решение. От исходной точки осуществляется переход к некоторой смежной угловой точке (т. B или т. F). Её выбор зависит от коэффициентов целевой функции. Т.к. коэффициент при xE больше коэффициента при xI, а целевая функция подлежит максимизации, требуемое направление перехода соответствует увеличению xE (т. B). Далее указанный процесс повторяется для выяснения, существует ли другая экстремальная точка, соответствующая лучшему допустимому решению.

Правила выбора экстремальной  точки:

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

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

 

Геометрическое  определение (графический метод)	Алгебраическое  определение (симплекс-метод)
Пространство  решений	Ограничения модели стандартной формы
Угловые точки	Базисные решения  задачи в стандартном виде