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

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

F(X)= F1(x1)+F2(x2)+...+Fn(xn),

(не исключено, что F­i(xi)=0 при некоторых i).

Пусть задана ЗВП: ограничения ji(x1, x2, ... , xn) £ bi , i=1,2,...,m (1)

x1, x2, ... ,xn ³ 0,

и целевая функция Z=f(x1, x2, ... , xn), (2)

причем все функции ji(Х) являются выпуклыми на некотором выпуклом множестве М, а функция Z либо выпукла на множестве М, либо вогнута. Пусть функция цели и ограничения ji являются сепарабельными. Тогда исходная задача имеет вид: найти минимум выпуклой (максимум вогнутой) функции Z= f1(x1)+f2(x2)+...+f(xn) при ограничениях

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

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

       
  Приближенное решение задач выпуклого программирования методом кусочно-линейной аппроксимации - student2.ru
   
h’(x)
 

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

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

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

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

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

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

Уравнение участка ломаной h’(x) между точками (xk;hk) и (xk+1;hk+1) имеет вид Приближенное решение задач выпуклого программирования методом кусочно-линейной аппроксимации - student2.ru (уравнение прямой по двум точкам). Если каждое из отношений в этом равенстве обозначить через l, то получим:

Приближенное решение задач выпуклого программирования методом кусочно-линейной аппроксимации - student2.ru (*) причем 0£l£1.

Отметим, что для каждого xÎ[xk;xk+1] существует единственное значение l, удовлетворяющее условиям (*) ( см. уравнение отрезка из определения выпуклого множества точек). Обозначив 1-l=lк, l=lк+1, можно переписать (*) в виде:

Приближенное решение задач выпуклого программирования методом кусочно-линейной аппроксимации - student2.ru где lк+lк+1=1, lк³0, lк+1³0.

Данные уравнения называются параметрическими уравнениями отрезка.

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

Приближенное решение задач выпуклого программирования методом кусочно-линейной аппроксимации - student2.ru (**)

причем всегда отличны от 0 только два значения lк (если х является внутренней точкой к-го отрезка разбиения) или одно (если х совпадает с концами отрезка).

Возвращаясь к ЗВП с сепарабельными функциями, отметим, что прежде всего (в зависимости от системы ограничений) нужно определить интервал изменения каждой переменной xj. Затем каждый этот интервал разбивается на части точками xjk и с использованием формул (**) строится кусочно-линейная аппроксимация для функций fi и jij . После этого можно для исходной задачи записать приближенную задачу:найти максимум функции Z’= f’1(x1)+f’2(x2)+...+f’(xn) при ограничениях

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

Пример. Найти минимум функции Z=2(x1-1)2+(x2-2)2 при ограничениях Приближенное решение задач выпуклого программирования методом кусочно-линейной аппроксимации - student2.ru

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

Решить задачу методом кусочно-линейной аппроксимации.

Решение. При условии неотрицательности переменных неравенство Приближенное решение задач выпуклого программирования методом кусочно-линейной аппроксимации - student2.ru показывает, что х1 может изменяться от 0 до 2, а х2 – от 0 до 4.

Отрезок [0;2] разобьем точками х10=0, х11=1, х12=2, а отрезок [0;4] - точками х20=0, х21=1, х22=2, х23=3, х24=4. Функция Z – сепарабельная, т.к. f1=2(x1-1)2, f2=(x2-2)2.

Удобно сначала вычислить необходимые значения этих функций (т.к. имеем лишь одно ограничение, т.е. m=1, будем писать j1 и j2).

Х1 Х10 Х11 Х12   Х2 Х20 Х21 Х22 Х23 Х24
Х1   Х2
j1   j2
f1   f2

По формулам (**) имеем:

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

Т.о., приближенная задача для данной задачи имеет вид: найти максимум функции

Z’= 2l10+2l12+4l20+l21+l23+4l24 при ограничениях

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

Это ЗЛП с 8 переменными lij. Решаем ее симплексным методом. На 3-ем шаге получаем оптимальное базисное решение: l11=l22=1, l10=l12=l20=l21=l23=l24=0. Переходя к исходным переменным х1, х2, получаем:

x1=l11+2l12=1, x2=l21+2l22+3l23+4l24=2.

Т.о., оптимальное решение приближенной задачи (1;2) и Zmin=0.

Контрольные вопросы

1. Загальна задача нелінійного програмування, класи задач нелінійного програмування.

2. Графічна інтерпретація нелінійних задач.

3. Умовний екстремум, методи множників Лагранжа.

4. Поняття про опуклість та угнутість функцій. Моделі опуклого програмування.

5. Квадратичне програмування. Особливості розв’язку задач квадратичного програмування.

6. Основні поняття та постановка задачі динамічного програмування.

7. Задачі динамічного програмування про звільнення і наймання робітників.

8. Задачі про мінімізацію розходу горючого літаком за набором висоти та швидкості.

Рекомендованная литература: [ 3, 6, 7, 8, 11]

Бібліографічний список

1. Кутиковецький В.Я. Дослідження операцій/ Навч.посібник. – Київ,2004.

2. Хемді А. Таха Введення в дослідження операцій/ Навч.посібник. – М.,С-П.,К.,2001.

3. Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем/ Учебн.пособие. – М. Финансы и статистика, 2002.

4. Кремер Н.Ш. Исследование операций в экономике/ Учебн.пособие. – М. Юнити, 2000.

5. Кабак Л.Ф., Суворовский А.А. Математическое программирование. – К.: ІМКВО, 1992.

6. Калихман И.С. Сборник задач по математическому программировани. – М.: Высш. шк., 1975.

7. Б.Ф.Капуснин. Практические занятия по курсу математического программирования. Ленинград, ЛГУ, 1976г.

8. Карманов В.Г. Математическое программирование. – М.: Наука, 1986.

9. Костевич Л.С., Лапко А.А. Теория игр. Исследование операций. Минск, Вишэйшая школа, 1982.

10. Кубонива M., Табата М.,Табата С., Хасаба Ю. Математическая экономика на персональном компьютере. М.: Финансы и статистика, 1991г.

11. Лотов В.А., Иванилов Н.И. Экономико-математические модели экономических ситуаци, М., Наука, 1982.

12. Таха Х. Введение в исследование операций. М.: Мир, 1985г.

Наши рекомендации