Алгоритм метода секущих плоскостей

Шаг 1. Задать (не обязательно допустимое),  (точность попадания в допустимую область).

Шаг 2. Положить

Шаг 3. Найти - решение задачи линейного программирования

Шаг 4. Если     , то останов

Шаг 5. Положить  

;

         k = k +1. Перейти к шагу 3.

  Пример 1. Решить методом секущих плоскостей задачу

 

Решение. Выберем . Вычислим , . Тогда

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

Ее решением является точка . Однако в этой точке нарушаются первое и второе ограничение, причем величина невязок достаточно велика, поэтому строим отсекающие плоскости:

 

        

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

Пример 2. Решить методом секущих плоскостей задачу

Решение. Выберем . Вычислим . Тогда

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

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

 

Метод гладких штрафов

 

    Данный метод относится к методам последовательной безусловной минимизации.

Рассмотрим задачу

.

Решение задачи сводится к решению последовательности задач поиска безусловного минимума вспомогательной функции

,

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

 

1)

2) при невыполнении ограничений и  должно выполняться условие .

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

 

где . Данная функция удовлетворяет всем требованиям, предъявляемым к штрафным функциям, и является дифференцируемой. Что позволяет при безусловной оптимизации использовать градиентные процедуры.

Алгоритм

    Шаг 1. Задать начальную точку , начальное значение параметра штрафа , число  для увеличения параметра, характеристика точности алгоритма .

    Шаг 2. Положить .

    Шаг 3. Составить вспомогательную функцию .

    Шаг 4. Используя заданные на шаге 1 параметры данного алгоритма, решить задачу безусловной минимизации  одним из численных методов безусловной минимизации.

    Шаг 5. Вычислить значение функции  в полученной на шаге 4 точке минимума .

    Шаг 6. Если , то процесс поиска закончить и положить . В противном случае положить  и перейти к шагу 3.

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

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

    Пример 1. Найти минимум в задаче

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

.

Найдем в общем виде минимум функции  с помощью необходимых и достаточных условий:

 

.

 

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

По полученной формуле проведем численные расчеты при  

 

k
0	1	5/3	-3,66
1	2	3/2	-3,5
2	10	7/6	-3,166
3	100	52/51	-3,019
4	1000	502/501	-3,002
5		1	-3

      x *

                 1               2   

                

                                                          

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

    Пример 2. Найти минимум в задаче

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

.

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

.

При  получим

 .

Однако при всех  имеем  что противоречит условию  для рассматриваемого случая.

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

 

k
0	1	0	5/9	-2/3
1	2	0	3/4	-1
2	10	0	35/36	-5/3
3	100	0	2600/2601	-100/51
4	1000	0	251000/251001	-1000/501
5		0	1	-2

 

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

 

Задачи для самостоятельного решения

1. Методом секущих плоскостей решить следующие задачи:

1)           

2. Методом штрафных функций решить следующие задачи:

 

1)                 2)

;                            ;

3)        4)

                                  

  ;                             .

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

1)                2)

                                        

  ;                                   

                                                                    ;

3)

.

4. Решить методом линеаризации:                                                   

                    

 

 

1. Постановка задачи квадратичного программирования 2. Использование симплексного метода для решения задачи квадратичного программирования.

Глава 11

 

 

Задача квадратичного программирования

 

 

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

,

,

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

    В данном параграфе рассмотрим задачу квадратичного программирования вида

.

    Для данной задачи условной оптимизации можно рассмотреть функцию Лагранжа вида

.

    При этом условия Куна - Таккера запишутся в виде следующей системы равенств и неравенств:

 

 

 

   

.

По теореме Куна - Таккера решение этой системы является искомой точкой минимума функции  на множестве . Введя дополнительные переменные , полученную систему перепишем в виде системы равенств

                                          (1)

   

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

.

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

     

,

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

    Пример 1. Решить задачу квадратичного программирования:

.

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

.

Найдем допустимое базисное решение этой системы, путем решения вспомогательной задачи линейного программирования с искусственными переменными

 

,

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

 

 

-1	5	2	2	-2	0	0	1	-1	-1	0
-1	6	6	-2	4	0	0	1	2	0	-1
0	3	2	1	1	1	0	0	0	0	0
0	4	2	-1	2	0	1	0	0	0	0
		-8	0	-2	0	0	-2	-1	1	1
-1	5	4	1	0	0	1	1	-1	-1	0
-1	6	2	0	0	0	-2	1	2	0	1
0	3	1	3/2	0	1	-1/2	0	0	0	0
0	2	1	-1/2	1	0	1/2	0	0	0	0
		-6	-1	0	0	1	-2	-1	1	1
-1	5	10/3	0	0	-2/3	4/3	1	-1	-1	0
-1	6	2	0	0	0	-2	1	2	0	-1
0	1	2/3	1	0	2/3	-1/3	0	0	0	0
0	2	4/3	0	1	1/3	1/3	0	0	0	0
		-16/3	0	0	2/3	2/3	-2	-1	1	1
-1	5	4/3	0	0	-2/3	10/3	0	-3	-1	1
0		2	0	0	0	-2	1	2	0	-1
0	1	2/3	1	0	2/3	-1/3	0	0	0	0
0	2	4/3	0	1	1/3	1/3	0	0	0	0
		-4/3	0	0	2/3	-10/3	0	3	1	-1
0	4	4/10
0		28/10
0	1	4/5
0	2	6/5
		0	0	0	0	0	0	0	0	0

 

    В последней симплексной таблице мы получили допустимое базисное решение

.

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

Задачи для самостоятельного решения

1. Решить задачи квадратичного программирования:

1)

   

 

 

     

     

2)

     

      

 

 

       

3)

     

  

     

     

  

     

1. Простейшая задача вариационного исчисления. 2. Алгоритм решения простейшей задачи вариационного исчисления 3. Частные случаи уравнения Эйлера. 4. Задача Больца. 5. Алгоритм решения задачи Больца

Глава 12

Классическое

Вариационное

Исчисление