Пример задачи нелинейной оптимизации
Задача. Необходимо сформировать оптимальный портфель Марковица (минимального риска) трех ценных бумаг с эффективностями и рисками: (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; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!