Пример задачи нелинейной оптимизации

Задача. Необходимо сформировать оптимальный портфель Марковица (минимального риска) трех ценных бумаг с эффективностями и рисками: (4,10), (10,40), (40,80). Нижняя граница доходности портфеля задана равной 15.

Экономико-математическая модель

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

Решение.

Приведенная ЭММ является моделью задачи нелинейного программирования. Специальный (рабочий) лист может быть подготовлен в виде:

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

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

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

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

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

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

1. Предприятие располагает двумя способами производства данного вида продукции. В течение рассматриваемого периода времени необходимый объем продукции равен 100= Х₁ + Х₂, где Х₁ и Х₂ – объемы производства по соответствующему технологическому способу. Затраты производства S при каждом способе зависят от объемов нелинейно:

, .

Необходимо так распределить объем производства между технологическими способами, чтобы минимизировать общие затраты производства.

2. Найти максимальное значение функции при ограничениях:

3. Необходимо сформировать оптимальный портфель Марковица (минимального риска) трех ценных бумаг с эффективностями и рисками: (6,10), (10,50), (60,80). Нижняя граница доходности портфеля задана равной 20.

4. Найти минимум функции при ограничениях:

Лабораторная работа №4. Метод кусочно-линейной аппроксимации

Пусть дана система неравенств вида и целевая функция, причем все функцииявляются выпуклыми, а функцияz выпукла или вогнута на некотором выпуклом множестве М.

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

Функция F(X)=F(,…,x_n) называется сепарабельной, если ее можно представить в виде суммы функций, каждая из которых зависит только от одной переменной, т. е. если

или

(не исключено, что при некоторыхi).

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

.

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

Для построения приближенной задачи рассмотрим кусочно-линейную аппроксимацию функции одной переменной h(x), заданной на отрезке [0,a]. Разобьем этот отрезок на r частей точками x<x<…<xтак, чтобы x=0, x=a. Вычислим значения функции h(x) (k=0,…,r) в этих точках. Соединим попарно точки (x;h) и (x;h) отрезками прямых. Состоящая из этих отрезков ломанаяаппроксимирует функциюh(x) на отрезке[0,a].

Уравнение участка ломаной между точками (x;h)и (x;h) имеет вид(уравнение прямой, построенной по двум заданным точкам).

Если каждое из отношений в этом равенстве обозначить через , то получим:

и , причем.

Обозначив , можно переписать в виде:

Таким образом, для любого x[0,a] уравнение ломаной можно записать в виде:

,

причем всегда отличны от нуля только для значения _k (если x является внутренней точкой k-го отрезка разбиения), или одно, (если x совпадает с концом отрезка).

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