3.2 Метод множителей Лагранжа

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

F (,

,

где функции f и , i= непрерывны, и непрерывны их частные производные по , l=.

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

g=b.

Будем исходить из геометрической интерпретации задачи. А именно, заметим, что линия уровня с максимальным значением параметра С будет касаться линии границы в точке, являющейся оптимальным решением задачи (рис.3.3).

Рисунок 3.3 - Геометрическая интерпретация задачи

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

f' () =

g' () =

Из условия пропорциональности в точке имеем

;

.

Для определения значений и в которых функция f достигает максимума, к этим уравнениям надо добавить условие принадлежности точки графику функции g (,) =b.

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

Введем новую функцию

F

Тогда последняя система перепишется в виде

Функцию F называют функцией Лагранжа.

Приведем ниже алгоритм метода множителей Лагранжа решения задач нелинейного программирования.

Этап 1. Составляют функцию Лагранжа

F () =f (.

Этап 2. Находят частные производные функции Лагранжа по и i=1,n; j=1,m и приравнивают их к нулю

.

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

Этап 4. Проверяют полученные на этапе 3 точки на экстремум и определяют экстремальное значение функции f найденной точки.

Рассмотрим применение изученных методов на примере решения задачи оптимальной реализации продукции, в частности для расчета экономико-математической модели при нелинейных затратах на производство. Фирма реализует автомобили двумя способами: через магазин и через торговых агентов. При реализации автомобилей через магазин расходы на реализацию составляют 4усл. ед., а при продаже автомобилей через торговых агентов расходы составляют усл. ед. Найти оптимальный способ реализации автомобилей, минимизирующий суммарные расходы, если общее число предназначенных для продажи автомобилей составляет 200 шт. Составим математическую модель задачи. Целью является минимизация суммарных расходов R =4. Управляющие переменные - это число автомобилей, реализуемых первым и вторым способом: и соответственно (200 шт.). Окончательно математическая модель имеет следующий вид:

R =4,

Для ее расчета применим метод множителей Лагранжа. Функция Лагранжа имеет вид

F ( 4+л (200-.

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

Получим следующую систему уравнений:

Решая систему, найдем 99, = 101, = 202, f () = 20 398.

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

3.3.1 Решение задач нелинейного программирования в среде приложения Excel

Рассмотрим примеры нелинейной оптимизационной экономической задачи, её экономико-математическую модель и метод компьютерной реализации в среде пакета Excel.

Особенности компьютерной реализации

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

f (,., ),

(,., ) {.

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

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

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

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

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

назначаются начальные значения искомых переменных так, чтобы ЦФ в начальной точке не была равна нулю,

в диалоговом окне Поиск решения в режиме Параметры не надо вводить Линейная модель.

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

Примером задачи нелинейного программирования является модель оптимального формирования портфеля ценных бумаг (модель Марковица минимального риска).

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

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

- средняя ожидаемая доходность j-й ценной бумаги, (mj называют эффективностью j-й ценной бумаги);

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

В предположении о некоррелированности ценных бумаг (их независимости) модель Марковица имеет вид:

Найти ,j=1,…,n, минимизирующие риск портфеля ценных бумаг

при условии, что обеспечивается заданное значение эффективности портфеля mp, т.е.

.

Нелинейной является целевой функции.

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

min (max) f (,., )

(,., ) {

Если множество индексов ={1,2,.,n}, то задачу называют полностью целочисленной, если, то - частично целочисленной.

Рассмотрим задачу оптимального формирования портфеля ценных бумаг. Необходимо сформировать оптимальный портфель Марковица (минимального риска) трех ценных бумаг с эффективностями и рисками: (4,10), (10, 40), (40, 80). Нижняя граница доходности портфеля задана равной 15. Построим экономико-математическая модель. Введем необходимые обозначения, пусть х_j (j =1, 2,3) - число предметов j-го типа, которое следует погрузить на баржу. Тогда математическая модель задачи о подборе для баржи допустимого груза максимальной ценности запишется следующим образом:

4x₁ + 10x₂ + 40х₃ ? 15

x₁ + x₂ + x₃ = 1

x_j ? 0, j = 1, 2, 3.

Заполняем рабочий лист данными.

x₁ = 0,5213, х₂ = 0, 2078, х₃ = 0,2709,т.е. доли ценных бумаг оказались равными 52,13 %; 20,78 % и 27,09 %. При этом минимальный риск - 23,79, доходность портфеля оказалась равной заданной - 15.

3.3.2 Решение задач нелинейного программирования в среде приложения Matlab

Метод покоординатного спуска (Гаусса - Зейделя)

На каждом шаге метод "приближается" к решению последовательно по каждой из координат. Переход от точки к точке +1 назовем "внешней" итерацией. Внутри каждой "внешней" итерации находятся n "внутренних" для последовательного вычисления координат точки +1.

.

,

,

,

.

,

.

Блок-схема алгоритма метода покоординатного спуска с постоянным

шагом и программа приведены в Приложении 1. Графическая

иллюстрация решения приведена на Рис.3.9.

Рисунок 3.9 - Графическая иллюстрация движения к максимуму методом покоординатного спуска.

Градиентный метод с постоянным шагом.

На каждой итерации метод "приближается" к решению, вычисляя новое значение каждой координаты в соответствии с формулой. Блок-схема алгоритма метода с постоянным шагом и программа приведены в Приложении. Графическая иллюстрация решения приведена на Рис.3.10.

Рисунок 3.10 - Движение к максимуму с постоянным шагом.

В примере Рис.3.11 происходит дробление шага на первой итерации алгоритма. В этом можно убедиться, поставив точку останова на строке 56.

Рисунок 3.11 - Графическая иллюстрация метода с дроблением шага

Градиентный метод наискорейшего спуска.

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

.

Новые координаты вычисляются с помощью этого значения:

Скалярное произведение векторов-градиентов на двух смежных итерациях равно нулю:

Это означает, что движение от точки к точке происходит по взаимно-ортогональным направлениям. (Рис.3.12).

Рис.3.12 - Движение к экстремуму по взаимно-ортогональным направлениям в методе наискорейшего спуска.

Сравнение методов.

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

f (

В таблице 3.1 для каждого метода приводится число итераций к, за которое из одной и той же начальной точки алгоритм приходит в точку хк, норма вектора-градиента в которой становится меньше заданного числа д =0,01 - точности метода. Точка хк является решением задачи. Методы сравниваются по значению отклонения этой точки от точки х*=0 - точного безусловного максимума.

Таблица 3.1 - Сравнения точности и быстродействия методов

Выводы