Технология компьютерной реализации

Задача (модель) нелинейного программирования (НЛП) формулируется так же, как и общая задача оптимального программирования со следующими требованиями к целевой функции (ЦФ) и допустимой области:

ЦФ f (х ₁, х ₂,…, х_n) и (или) одна из функций g (х ₁, х ₂,…, х_n)являются нелинейными:

min (max) f (х ₁, х ₂,…, х_n);

g (х ₁, х ₂,…, х_n){≤¸=¸≥} b_i, i = 1,…, m; x_j ≥0, j=1, …, n.

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

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

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

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

Решение задачи НЛП (реализация модели нелинейной оптимизации) средствами Ехсеl отличается от решения ЗЛП следующим:

– назначаются начальные значения искомых переменных х⁰ _j, j = 1,…, п так, чтобы ЦФ в начальной точке не была равна нулю, f(х ⁰₁, х ⁰₂,…, х ⁰ _n)≠0;

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

В Ехсеl признаком достижения оптимума является величина относительного приращения ЦФ на каждой итерации

Оптимум считается достигнутым, если выполняется условие Δ f_k ≤ Δ f _зад, где Δ f _зад – точность, назначаемая при решении задачи в режиме Параметры.

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

В этой модели приняты следующие обозначения (j = 1,…, п):

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

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

v _j – дисперсия случайной доходности j -й ценной бумаги;

r_j = – называют риском j -й ценной бумаги.

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

Найти x _j,минимизирующие риск портфеля ценных бумаг

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

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

x _j ≥0, j = 1,…, п

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

Рассмотрим некоторые типовые задачи (модели) нелинейной оптимизации.