Пример задачи нелинейной оптимизации
Задача. Необходимо сформировать оптимальный портфель Марковица (минимального риска) трех ценных бумаг с эффективностями и рисками: (4,10), (10,40), (40,80). Нижняя граница доходности портфеля задана равной 15.
Экономико-математическая модель
Пусть xj, j= 1,2,3 – доля капитала, потраченная на покупку ценных бумагу j-го вида (весь выделенный капитал принимается за 1)
Решение.
Приведенная ЭММ является моделью задачи нелинейного программирования. Специальный (рабочий) лист может быть подготовлен в виде:
формулы этого листа приведены в ячейках.
Диалоговое окно Поиск решения с введенными ограничениями, соответствующее приведенному выше рабочему листу:
Реализуя приведенную модель средствами MS Excel, будем иметь оптимальный портфель Марковица:
х1 = 0,5213, х2 = 0,2078, х3 = 0,2709,
т.е. доли ценных бумаг оказались равными 52,13%; 20,78% и 27,09%. При этом минимальный риск – 23,79, доходность портфеля оказалась равной заданной – 15.
Метод кусочно-линейной аппроксимации
Пусть дана система неравенств вида 
и целевая функция 
, причем все функции 
являются выпуклыми, а функция 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] уравнение ломаной можно записать в виде:
,
причем всегда отличны от нуля только для значения l k (если x является внутренней точкой k-го отрезка разбиения), или одно, (если x совпадает с концом отрезка).
Возвращаясь к задаче ВП с сепарабельными функциями, отметим, что, прежде всего (в зависимости от системы ограничений) нужно определить интервал изменения каждой переменной x 
. Затем каждый этот интервал разбивается на части точками x 
и, с использованием полученных формул строится кусочно-линейная аппроксимация для функций f 
и 
. После этого можно для исходной задачи записать приближенную задачу: найти максимум функции 
при ограничениях:
Дата добавления: 2019-02-22; просмотров: 381; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!