Задачи нелинейного программирования

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.

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

Рисунок 3.4 - Рабочий лист программы

Рабочий лист может быть подготовлен в виде, представленном на рис.3.5, формулы этого листа приведены в ячейках.

Рисунок 3.5 - Рабочий лист

Диалоговое окно, отвечающее приведенному выше рабочему листу, представлено на рис.3.6.

Рис. 3.6 - Диалоговое окно

Реализуя приведенную модель средствами пакета Excel (рис. 2.9), будем иметь оптимальный портфель Марковица:

x₁ = 0,5213, х₂ = 0,2078, х₃ = 0,2709,

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

Рисунок 3.7 - Результаты решения

Проиллюстрируем результаты с помощью Мастера диаграмм

Рисунок 3.8 - Графическая иллюстрация результатов

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 - Сравнения точности и быстродействия методов