10.2. Задача выпуклого программирования

Пусть дана система неравенств вида

(10.6)

и функция

(10.7)

причем все функции φ;(Χ) являются выпуклыми на некотором выпуклом множестве А7, а функция Ζ либо выпукла на множестве А/, либо вогнута. Задача выпуклого программирования (ВП) состоит в отыскании такого решения системы ограничений (10.6), при котором целевая функция Ζ достигает минимального значения или вогнутая функция Ζ достигает максимального значения. Условия неотрицательности переменных можно считать включенными в систему (10.6).

Ввиду свойства 3 (см. параграф 10.1) всякая задача линейного программирования является частным случаем задачи ВП. В общем случае задачи ВП являются задачами нелинейного программирования. Выделение задач ВП в специальный класс объясняется экстремальными свойствами выпуклых функций: всякий локальный минимум выпуклой функции (локальный максимум вогнутой функции) является одновременно и глобальным; кроме того, ввиду свойства 2 выпуклая (вогнутая) функция, заданная на замкнутом ограниченном множестве, достигает на этом множестве глобального максимума и глобального минимума. Отсюда вытекает, что если целевая функция Z является строго выпуклой (строго вогнутой) и если область решений системы ограничений не пуста и ограничена, то задача ВП всегда имеет единственное решение. В этом случае минимум выпуклой (максимум вогнутой) функции достигается внутри области решений, если там имеется стационарная точка, или на границе этой области, если внутри нее нет стационарной точки. В общем случае можно утверждать лишь, что множество оптимальных решений любой задачи ВП является выпуклым множеством.

10.4. Геометрически решить следующую задачу ВП: найти минимум функциипри ограничениях:

Решение. Строим область допустимых решений данной задачи:

а)– окружность с центром в начале коорди

нат и радиусом R = 2 (рис. 10.3). Область решений неравенствасостоит из точек, лежащих внутри этой окружности и на ней самой;

• б)– прямая, которую можно построить, например, по точкам (0; 0) и (2; 1). Область решений неравенства
• – полуплоскость, лежащая над этой прямой, включая и саму прямую;
• в) х2 = 2х{ – прямая, которая строится, например, по точкам (0; 0) и (1; 2). Область решений неравенства

Рис. 10.3

х2 ≤ 2.Г, – полуплоскость, лежащая под этой прямой, включая и саму прямую. Таким образом, с учетом условий неотрицательности переменных, областью допустимых решений данной задачи является замкнутый сектор ОАВ (см. рис. 10.3).

Теперь построим линию уровня функции Z и определим направление убывания Z. Все линии уровня имеют уравнениеПри С = 3 получаем линию уровня– это окружность

с центром в точке Ol (1; 1) и радиусом R = 1. Ясно, что в любой точке этой линии уровня при перемещении от центра окружности О, функция Z возрастает, а при перемещении к центру убывает. Таким образом, минимум Z достигается в точке (1; 1),(нетрудно убедиться, что точка (1; 1) является стационарной точкой функции Z). ►

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

Функцияназывается сепарабельной,

если ее можно представить в виде суммы функций, каждая из которых зависит только от одной переменной, т.е. если

• src="/imag/econom/krem_islopek/image966.jpg">(10.8)
• (не исключено, чтопри некоторых г).

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

функциипри ограничениях".

(10.9)

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

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

Уравнение участка ломаной между точками (xk hk) иимеет вид:(уравнение

Рис. 10.4

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

(10.10)

причем

Отметим, что для каждогосуществует единственное значение λ, удовлетворяющее условиям (10.10) (см. уравнение отрезка (10.2)). Обозначив,

, можно переписать (10.10) в виде

(10.11)

где

Уравнения (10.11) называются параметрическими уравнениями отрезка. Если h(x) = 0, то второе из этих уравнений обращается в тождество 0 = 0, а первое принимает вид (10.2) – уравнение отрезка, лежащего па оси абсцисс.

Таким образом, для любогоуравнение лома

ной можно записать в виде

(10.12)

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

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

найти максимум функции

при ограничениях(10.13)

Поскольку приближенная задача (10.13) является задачей линейного программирования и мы обычно решаем ее симплексным методом, условия неотрицательности переменных записываются отдельно от остальных ограничений. Отличие полученной задачи (10.13) от обычной задачи линейного программирования состоит в том, что для каждого X- имеется не более двух соседних ненулевыхи, значит, нельзя брать в качестве основных переменных два с одинаковыми j и несоседними к. Заметим также, что для условий неотрицательности переменных слагаемых f- ухjj и (если таковые окажутся) кусочно-линейную ап

проксимацию проводить, конечно, не нужно.

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

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

Решение. Прежде всего рекомендуем самостоятельно убедиться в том, что данная задача является задачей ВП (используйте критерий Сильвестра, см. задачу (10.2)). Далее, при условии неотрицательности переменных неравенствопоказывает, что .г, может изменяться лишь

от 0 до 2, а х2 – от 0 до 4 (рис. 10.5).

Отрезок [0; 2] разобьем точками а отрезок [О; 4] – точками

. Сравнивая условие данной задачи с (10.9), видим, что

Рис. 10.5

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

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

Таким образом, приближенная задача (10.13) для данной задачи ВП имеет вид: найти минимум функции

при ограничениях:

Получили задачу линейного программирования с 8 переменными. Для решения ее симплексным методом первое ограничение-неравенство нужно преобразовать в уравнение путем введения дополнительной неотрицательной переменной, которую обозначим и:

Тогда система ограничений станет системой грех уравнений с 9 переменными, т.е. 3 переменные нужно взять за основные (берем, так как они входят только в одно уравнение каждая), а остальные 6 являются свободными. Как обычно, на каждом шаге решения основные переменные и функция цели выражаются через свободные (неосновные) переменные.

I шаг.

Так как в выражении Z имеются свободные переменные с отрицательными коэффициентами, то первое базисное решение неоптимальное (хотя идопустимое), и согласно алгоритму симплексного метода, следует перевести в основные переменные. Находим min., выделяем третье уравнение и переменнуюпереводим в свободные переменные.

II шаг. Основные переменные λ22, λ10, и.

III шаг. Основные переменные λ,,, λ22, и.

Критерий оптимальности симплексного метода выполнен, значит, на 111 шаге получено оптимальное базисное решение:

Переходя к исходным переменнымполучаем:

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

Можно было бы геометрически решить исходную задачу ВП и убедиться в том, что оптимальное решение приближенной задачи в точности совпадает с оптимальным решением исходной задачи. Э го совпадение случайное. В общем случае полученное решение является лишь некоторым приближением оптимального решения исходной задачи. Улучшить точность приближения можно, разбивая на более мелкие части уже не исходные отрезки изменения переменных, а другие, меньшие, взятые в окрестности полученного первого приближения. Недостатком метода является большое увеличение размерности задачи (т.е. числа переменных) при переходе к приближенной линейной модели.