Сантылова Л.И. Вариационное исчисление и методы оптимизации

Подождите немного. Документ загружается.

Федеральное агентство по образованию Российской Федерации

ГОУВПО «Ростовский государственный университет»

Л.И. Сантылова

ВАРИАЦИОННОЕ ИСЧИСЛЕНИЕ И МЕТОДЫ ОПТИМИЗАЦИИ

(методические указания для студентов специальности «Прикладная

математика и информатика»)

РУКОВОДСТВО ПО РЕШЕНИЮ ЗАДАЧ

Часть 1

Ростов-на-Дону 2006

Методические указания печатаются по решению кафедры исследования

операций механико-математического факультета РГУ: протокол № 2 от

19 сентября 2006г.

СОДЕРЖАНИЕ

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

І. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ ………………………..…………………4

Тема 1. Геометрическое решение задач линейного программирования………...5

Тема 2. Решение задачи линейного программирования

симплекс-методом………………………………………………………….…..7

Тема 3. Метод искусственного базиса………………………………..…………..10

Тема 4. Теория двойственности в линейном программировании…..…………..12

ІІ. ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ…...…………………...............…….…17

Тема 5.Геометрическое решение задач нелинейного программирования…….17

Тема 6. Условия Куна-Таккера. Теоремы Куна-Таккера……….………………20

Тема 7. Метод возможных направлений……..…………………….……………23

ІІІ. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ………………………………...26

ЛИТЕРАТУРА.……………………………………………………………………….32

ВВЕДЕНИЕ

В связи с уменьшением количества аудиторных часов и увеличением

объема самостоятельной работы студентов алгоритмический подход к

изложению материала представляется наиболее эффективным.

Данные методические указания рекомендуется использовать на

семинарских занятиях по курсу «Математические методы исследования

операций». Студент, освоивший на занятиях принцип использования данного

методического материала, сможет достаточно легко перейти к применению

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

І. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Теоретические предпосылки

Определение 1. Задача линейного программирования – это задача

оптимизации линейной функции в области, задаваемой линейными

ограничениями.

В общем виде задача линейного программирования выглядит следующим

образом:

f (x )=( c, x ) → max (min )

( A

, x )≤ b

, i=1, m

( A

, x )≥b

, i=m

+1, m

(1)

( A

, x )=b

, i=m

+1, m

≥0 , j=1, n

−∀ , j=n

+1, n

Определение 2. Оптимизируемая функция f(x) называется критерием,

функцией цели или целевой функцией задачи.

Определение 3. Допустимым решением задачи называется точка

x=( x

, x

,. .., x

)

, удовлетворяющая всем ограничениям задачи. Допустимые

решения образуют область допустимых решений задачи (ОДР).

Определение 4. Оптимальным решением задачи называется допустимое

решение, доставляющее целевой функции наибольшее (наименьшее) значение.

Указанное в определении наибольшее (наименьшее) значение называется

оптимальным значением целевой функции.

Решить задачу линейного программирования означает следующее:

1) если задача разрешима, то необходимо найти среди допустимых решений

задачи оптимальные решения и вычислить оптимальное значение целевой

функции;

2) если задача неразрешима, то требуется установить причину

неразрешимости задачи.

Тема 1. Геометрическое решение задач линейного программирования.

Теоретические напоминания

Геометрически рекомендуется решать задачу линейного программирования

с двумя переменными или задачу, сводимую к таковой эквивалентными

преобразованиями.

Определение 5. Градиент функции – это вектор, координаты которого

равны частным производным первого порядка.

 Градиент линейной функции

f (x

, x

)=c

равен вектору

коэффициентов функции

c=(c

, c

)

 Градиент функции в точке определяет направление наискорейшего

возрастания функции в этой точке.

 Геометрическим местом точек, удовлетворяющих линейному

уравнению, является прямая.

 Геометрическим местом точек, удовлетворяющих линейному

неравенству, является полуплоскость.

 Линии уровня – это прямые, перпендикулярные градиенту.

Алгоритм геометрического решения задачи линейного программирования

1) Строим на плоскости прямоугольную декартову систему координат.

2) Для каждого ограничения находим геометрическое место точек,

удовлетворяющее этому ограничению. Выделяем пересечение полученных

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

решений (ОДР).

Если ограничения противоречивы, то ОДР окажется пустым множеством.

Всегда в задаче линейного программирования ОДР будет выпуклым и

замкнутым множеством. В некоторых задачах ОДР будет ограниченным

множеством, а иногда не ограниченным.

3) Если ОДР - пустое множество, то делаем вывод: задача не имеет решения

(неразрешимость 1), и алгоритм завершает работу.

4) Находим градиент целевой функции – вектор, координаты которого равны

коэффициентам целевой функции.

5) Рисуем найденный градиент в виде вектора, исходящего из начала

координат.

6) Проводим прямую, перпендикулярную градиенту и разбивающую ОДР

на две части.

7) Перемещаем прямую при максимизации в направлении градиента (при

минимизации в направлении, противоположном градиенту) до первого

положения, при котором ОДР будет располагаться по одну сторону от

прямой.

8) Если при сколь угодно длительном перемещении такое положение не

достижимо, делаем вывод о неограниченности целевой функции в ОДР

сверху при максимизации (снизу при минимизации) (это –

неразрешимость 2) , и алгоритм завершает работу.

9) Если указанное в пункте 7 положение найдено, то в этом положении

находим точки, лежащие на пересечении прямой и ОДР. Они являются

оптимальными решениями задачи. Точное значение координат этих точек

определяем аналитически. Вычисляем оптимальное значение целевой

функции. Алгоритм завершает работу.

Выводы:

1. Оптимальных решений может не быть (возможна одна из двух

указанных в алгоритме причин).

2. Оптимальное решение может быть единственно.

3. Оптимальных решений может быть бесконечно много.

4. Оптимальные решения всегда располагаются на границе ОДР, и среди

них всегда есть хотя бы одна вершина ОДР.

Тема 2. Решение задачи линейного программирования симплекс-

методом

Таблица 1

Эквивалентные преобразования

Название преобразования До

преобразования

После преобразования

Преобразование неравенства в

равенство







ijj,i

bxa







iijj,i

buxa



Преобразование неравенства в

равенство







ijj,i

bxa







iijj,i

buxa



Переход от решения задачи

минимизации к решению задачи

макси- мизации

minxc







maxxc







Переход от свободной

переменной к пере- менным,

ограниченным по знаку



0x,0x,xxx



Использование перечисленных преобразований (табл. 1) позволяет любую

задачу линейного программирования свести к следующему виду:

1) требуется максимизировать целевую функцию,

2) все ограничения, кроме ограничений на знак, имеют вид равенств,

3) все переменные предполагаются неотрицательными.

Математическая модель такой задачи выглядит следующим образом

f (x )=( c , x ) → max (min)

( A

, x )=b

, i=1 , m

( 2)

≥0 , j=1, n

Этот вид задачи линейного программирования будем называть

канонической формой.

Алгоритм 1 - построение начальной симплекс-таблицы

1) Используя преобразования таблицы 1, свести задачу к каноническому виду

(2).

2) Преобразовать все ограничения–равенства к виду, при котором правая часть

ограничения – неотрицательное число.

3) Выписать матрицу ограничений и проверить, есть ли в этой матрице набор

столбцов, образующих единичную матрицу.

4) Если такого набора нет, то перейти к пункту 7.

5) Набор есть. Разбейте переменные

( j=1 ,n )

на две группы: базисные

переменные и небазисные переменные. Базисные переменные – это те,

которые соответствуют столбцам, образующим единичную матрицу.

Остальные переменные – небазисные.

Полагая всякую небазисную переменную равной нулю, а базисную

правой части ограничения, в котором эта переменная присутствует,

получаем опорное решение.

6) Построить симплекс-таблицу, отвечающую полученному опорному

решению. Базисные переменные записать в крайнем левом столбце, а

небазисные – в самой верхней строке. Завершить работу алгоритма 1.

7) Сделать вывод: для построения начальной симплекс-таблицы необходимо

применить метод искусственного базиса.

8) Завершить работу алгоритма 1.

Алгоритм 2 - решение симплекс-методом задачи линейного

программирования

Начальная симплекс-таблица построена.

1) Если оценки симплекс-таблицы неотрицательны, то таблица

оптимальная, и соответствующее ей опорное решение оптимальное.

Полагая всякую небазисную переменную равной нулю, а

базисную равной элементу из столбца свободных членов, получаем

оптимальное опорное решение.

Алгоритм завершает работу.

2) Если в таблице есть столбец с отрицательной оценкой, и все элементы в

нем не положительны, то оптимальное решение не существует, так как

целевая функция неограниченна сверху в ОДР (Неразрешимость 2).

Алгоритм завершает работу.

3) Если в таблице есть столбец с отрицательной оценкой, и в нем есть

положительные элементы, то среди этих элементов выбираем

главный. Для этого находим для каждого такого элемента частное от

деления правой части ограничения на этот элемент. Полученные

частные сравним для того, чтобы главным элементом выбрать тот,

которому соответствует наименьшее частное. Главный элемент

определяет главную строку и главный столбец, так как он стоит на их

пересечении.

4) Выполним жордановы преобразования симплекс-таблицы

относительно выбранного главного элемента и перейдем к пункту 1.

Жордановы преобразования симплекс-таблицы относительно

выбранного главного элемента

1) Поменять местами переменные, стоящие в главной строке и главном

столбце.

2) Главный элемент заменить ему обратным.

3) Все остальные элементы главной строки разделить на главный элемент.

4) Все остальные элементы главного столбца разделить на главный элемент и

поменять у них знаки на противоположные.

5) Все оставшиеся элементы пересчитать по правилу, сходному с правилом

вычисления определителя второго порядка (в качестве главной диагонали

нужно брать ту, на которой стоит главный элемент), и разделить на главный

элемент.

Замечание. Во всех перечисленных действиях используйте числа из

старой таблицы, а результаты вычислений записывайте в новую таблицу.

Тема 3. Метод искусственного базиса

Алгоритм 3 - построение начальной симплекс-таблицы с помощью

метода искусственного базиса.

1) Используя эквивалентные преобразования, преобразовать задачу к

каноническому виду (I).

2) Преобразовать все ограничения–равенства к виду, когда правая часть –

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

3) Построить вспомогательную задачу. Для этого из исходной

преобразованной задачи возьмем только ограничения. Прибавим по

необходимости к левым частям ограничений новые переменные