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

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

F(X)= F₁(x₁)+F₂(x₂)+...+F_n(x_n),

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

Пусть задана ЗВП: ограничения j_i(x₁, x₂,..., x_n) £ b_i, i=1,2,...,m (1)

x₁, x₂,...,x_n ³ 0,

и целевая функция Z=f(x₁, x₂,..., x_n), (2)

причем все функции j_i(Х) являются выпуклыми на некотором выпуклом множестве М, а функция Z либо выпукла на множестве М, либо вогнута. Пусть функция цели и ограничения j_i являются сепарабельными. Тогда исходная задача имеет вид: найти минимум выпуклой (максимум вогнутой) функции Z= f₁(x₁)+f₂(x₂)+...+f(x_n) при ограничениях

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

		h’(x)

 

 

 

 

 

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

Уравнение участка ломаной h’(x) между точками (x_k;h_k) и (x_k+1;h_k+1) имеет вид (уравнение прямой по двум точкам). Если каждое из отношений в этом равенстве обозначить через l, то получим:

(*) причем 0£l£1.

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

где l_к+l_к+1=1, l_к³0, l_к+1³0.

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

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

(**)

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

Возвращаясь к ЗВП с сепарабельными функциями, отметим, что прежде всего (в зависимости от системы ограничений) нужно определить интервал изменения каждой переменной x_j. Затем каждый этот интервал разбивается на части точками x_jk и с использованием формул (**) строится кусочно-линейная аппроксимация для функций f_i и j_ij. После этого можно для исходной задачи записать приближенную задачу:найти максимум функции Z’= f’₁(x₁)+f’₂(x₂)+...+f’(x_n) при ограничениях

Пример. Найти минимум функции Z=2(x₁-1)²+(x₂-2)² при ограничениях

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

Решение. При условии неотрицательности переменных неравенство показывает, что х₁ может изменяться от 0 до 2, а х₂ – от 0 до 4.

Отрезок [0;2] разобьем точками х₁₀=0, х₁₁=1, х₁₂=2, а отрезок [0;4] - точками х₂₀=0, х₂₁=1, х₂₂=2, х₂₃=3, х₂₄=4. Функция Z – сепарабельная, т.к. f₁=2(x₁-1)², f₂=(x₂-2)².

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

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

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

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

Z’= 2l₁₀+2l₁₂+4l₂₀+l₂₁+l₂₃+4l₂₄ при ограничениях

Это ЗЛП с 8 переменными l_ij. Решаем ее симплексным методом. На 3-ем шаге получаем оптимальное базисное решение: l₁₁=l₂₂=1, l₁₀=l₁₂=l₂₀=l₂₁=l₂₃=l₂₄=0. Переходя к исходным переменным х₁, х₂, получаем:

x₁=l₁₁+2l₁₂=1, x₂=l₂₁+2l₂₂+3l₂₃+4l₂₄=2.

Т.о., оптимальное решение приближенной задачи (1;2) и Z_min=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г.