ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ, раздел математического программирования, в котором исследуется задача максимизации вогнутой целевой функции f(х) векторного аргумента х = (x 1 , ..., х n), удовлетворяющего ограничениям g i (х) ≥ 0, х Є Х, i = 1, ..., m, где g i - вогнутые функции, Х - выпуклое множество. Точка х, удовлетворяющая этим ограничениям, называется допустимой. Основным результатом теории выпуклого программирования является теорема о седловой точке: для того чтобы допустимая точка х* задачи выпуклого программирования была оптимальной, необходимо (при довольно широких условиях) и достаточно существование вектора у* = (у* 1 , ..., y m *) с неотрицательными компонентами у* такого, что точка (х*, у*) является седловой для функции Лагранжа
задачи выпуклого программирования, то есть для любых х Є Х и у с неотрицательными компонентами выполняются неравенства
На теорему о седловой точке опирается ряд методов выпуклого программирования, в которых либо минимизируется функция φ(y 1 , ..., у m) = max x Є X L(x, у) при у i ≥ 0, i = 1, ..., m, либо непосредственно отыскивается седловая точка, причём вместо функции Лагранжа иногда используются некоторые её модификации. Другой подход к решению задачи выпуклого программирования связан с поиском возможных направлений движения допустимой точки х, которые не выводят из множества допустимых точек и при движении вдоль которых целевая функция возрастает. Этот подход реализуется с помощью последовательности итераций. На каждой итерации вычисляется возможное направление, исходящее из очередной точки, после чего производится сдвиг по этому направлению на некоторое расстояние до следующей точки. Существуют методы решения задач выпуклого программирования, специально приспособленные к тому случаю, когда целевая функция нелинейна, а ограничения линейны. Как правило, методы выпуклого программирования требуют для точного определения оптимальной точки бесконечного числа итераций. Исключением являются задачи квадратичного программирования (целевая функция - сумма вогнутой квадратичной и линейной функций, ограничения линейны) и линейного программирования (целевая функция и ограничения линейны), для которых в основном используются конечные методы. Многие вычислительные методы выпуклого программирования реализованы в виде программ для ЭВМ; существуют также пакеты программ, охватывающие задачи линейного программирования и выпуклого программирования. Смотри также Исследование операций.
Лит.: Гольштейн Е. Г. Выпуклое программирование. Элементы теории. М., 1970; Зангвилл У. И. Нелинейное программирование. Единый подход. М., 1973.
(Документ)
n1.doc
Выпуклое программирование. Теорема Куна-Таккера. Условия Куна-Таккера
При условиях
(1.3)
Где функции 
предполагаются выпуклыми.
Если 
и являются вогнутыми функциями, то имеем задачу максимизации 
при ограничениях 
и 
Составим функцию Лагранжа для данной задачи:
Точка называется седловой точкой функции (1.4), если точка является точкой минимума функции 
, а точка - точкой максимума функции . Другими словами, для седловой точки при всех 
и 
выполняется соотношение
(1.5)
Теорема 1 (Теорема Куна-таккера).
Пусть существует по крайней мере одна точка 
, для которой 
. Тогда необходимым и достаточным условием оптимальности вектора 
, принадлежащего области допустимых решений задачи (1.1)-(1.5), является существование такого вектора 
, что для всех и 
имеют место неравенства (1.5)
Эту теорему примем без доказательства
Теорема Куна-Таккера также называется теоремой о седловой точке.
Если 
и 
- дифференцируемые функции, то неравенства в (1.5) эквивалентны следующим локальным условиям Куна-Таккера:
Данные выражения означают, что значения производных берутся в точке 
.
1.2. Квадратичное программирование. Метод Баранкина-Дорфмана.
Частным случаем задачи выпуклого программирования является задача квадратичного программирования. В качестве основной в квадратичном программировании рассматривается задача минимизации функции Z, являющейся суммой линейной и квадратичной функции:
При линейных ограничениях
Матрица D предполагается симметрической и неотрицательно определенной. В этом случае функция (2.1) будет выпуклой.
Составим для задачи (2.1) - (2.3) локальные условия Куна-Таккера (1.6) – (1.7), являющиеся необходимыми и достаточными условиями оптимальности решения задачи (2.1) – (2.3).
Функция Лагранжа в данном случае имеет вид:
Найдем частные производные этой функции:
Обозначим
С учетом этих обозначений, соотношений (2.4) и (2.5) условия Куна-Таккера (1.6) – (1.7) примут следующий вид
Равенства (2.6) и (2.7) образуют систему N=n+m линейных уравнений с 2N=2(n+m) неизвестными: .
Итак, в соответствии с теоремой Куна-Таккера решение 
задачи (2.1) – (2.3) квадратичного программирования является оптимальным тогда и только тогда, когда совместно с решением 
существуют решения 
и 
такие, что является решением системы (2.6) – (2.8) при условии выполнения равенства (2.9).
Условие (2.9) для задачи (2.1) – (2.3) равносильно выполнению условия
Существует несколько методов решения задачи квадратичного программирования. Рассмотрим один из них – метод Баранкина-Дорфмана.
При этом методе сначала система уравнений (2.6) – (2.7) приводится к виду:
Где 
(базисные переменные) и 
(свободные переменные) являются различными элементами некоторой перестановки переменных , а все 
являются неотрицательными числами (i=1,2,…,N).
Затем из системы (2.11) находится начальное опорное решение
Системы (2.6) – (2.8), причем компоненты вектора 
расположены в порядке .
Если для решения 
выполняется условие (2.10), то задача (2.1) – (2.3) решена и ее оптимальное решение 
находится из соответствующих компонент вектора .
Если же для условие (2.10) не выполняется, то для перехода к другому опорному решению составляется нижеследующая таблица (табл. 2.1). В основную часть этой таблицы включаются строки для всех переменных, расположенных в порядке . Для базисных переменных элементы строк берутся из системы (2.11), а для свободных переменных – из соотношений
Параметры же дополнительной части таблицы 2.1 находятся следующим образом:
А) 
находятся из формулы 
где 
- вектор, составленный из элементов s-го столбца основной части таблицы;
Б) для тех s, для которых 
, вычисляются остальные параметры: 
(элементы соответствующих столбцов, доставляющих минимум 
, отмечаются звездочкой), 
.
Столбец, которому соответствует наименьший из отрицательных 
, назначается разрешающим столбцом, строка с отмеченным звездочкой элементом этого столбца – разрешающей строкой, а сам этот элемент – разрешающим элементом, и с их помощью выполняется симплексное преобразование таблицы 2.1.
При этом:
В результате получается новое опорное решение системы (2.6) – (2.8). Этот процесс продолжается до тех пор, пока не будет выполнено условие (2.10). Если же все 
, а 
, то в качестве начального выбирается другое решение.
1.3 Пример решения задачи методом Баранкина-Дорфмана
Минимизировать функцию
При ограничениях:
; 
.
Решение
Находим начальное опорное решение системы (2.12). При этом значение целевой функции равно .
То не выполняется условие (2.10) и, следовательно, решение не является оптимальным.
Составим таблицу 2.2 для перехода к новому опорному решению системы (2.12) - (2.13). Основную часть этой таблицы заполним, используя систему (2.12).
А) для дополнительной части таблицы найдем:
Б) для положительных 
и 
вычислим остальные параметры:
Четвертый столбец, которому соответствует наименьший отрицательный 
, назначаем разрешающим столбцом, строку с элементом 3 этого столбца – разрешающей строкой, а сам элемент 3 – разрешающим элементом, и с их помощью выполняем симплексное преобразование таблицы 2.2.
В результате получаем таблицу 2.3, содержащую новое опорное решение .
Для этого решения
Поэтому заполним дополнительную часть таблицы 2.3 аналогично тому, как это делалось в предыдущем случае, для перехода к новому опорному решению системы (2.12) – (2.13).
Подвергнув таблицу 2.3 симплексному преобразованию с разрешающим элементом 13.30, получим очередную таблицу с опорным решением , для которого 
.
Тем самым найдено оптимальное решение 
, при котором целевая функция Z данной задачи минимизируется. При этом 
1.4 Индивидуальное задание: решение задачи методом Баранкина-Дорфмана
;
Решение
Из соотношений (2.6) - (2.7) получаем следующую систему уравнений:
После несложных преобразований приводим эту систему к виду:
(2.14)
Откуда с учетом неотрицательности
Находим начальное базисное решение 
системы (2.14). При этом значение целевой функции равно 
.
Так как , то не выполняется условие (2.10) и, следовательно, решение не является оптимальным.
Составим таблицу 2.4 для перехода к новому базисному решению системы (2.14) - (2.15).
Таблица 2.4
| 1 | -  | -  | -  |
||||
| | 0 | -1 | 0 | 0 |
|||
| | 0 | 0 | -1 | 0 |
|||
 | 4 | 1 | -2 | 0 |
|||
| | 0 | 0 | 0 | -1 |
|||
 | 2 | 4 * | -6 | -2 |
|||
 | 4 | 2 | 0 | -1 |
|||
 | 32 | ||||||
 | 12 | -10 | -4 |
||||
 | 4 | ||||||
 | 1/2 | Таблица 2.5 | 0 | 0 | -1 |
||
| | 0 | -1 | 0 | 0 |
|||
| | 3 | -1/2 | 3 * | 0 |
|||
| | 110,25 | ||||||
| | -2,5 | 9 | -2 |
||||
| | -3 |
Пусть дана система неравенств вида
(4.3) и функция
Z = f (x 1 , x 2 , …, x n), (4.4)
причем все функции является выпуклыми на некотором выпуклом множестве M, а функция Z либо выпукла на множестве М, либо вогнута.
Задача выпуклого программирования состоит в отыскании такого решения системы ограничений (4.3), при котором целевая функция Z достигает минимального значения, или вогнутая функция Z достигает максимального значения. (Условия неотрицательности переменных можно считать включенными в систему (4.3)).
Ввиду свойства 3 0 всякая задача линейного программирования является частным случаем задачи выпуклого программирования. В общем случае задачи выпуклого программирования являются задачами нелинейного программирования. Выделение задач выпуклого программирования в специальный класс объясняется экстремальными свойствами выпуклых функций: всякий локальный минимум выпуклой функции (локальный максимум вогнутой функции) является одновременно и глобальным; кроме того, ввиду свойства 2 0 выпуклая (вогнутая) функция, заданная на замкнутом ограниченном множестве, достигает на этом множестве глобального максимума и глобального минимума. Отсюда вытекает, что если целевая функция Z является строго выпуклой (строго вогнутой) и если область решений системы ограничений не пуста и ограничена, то задача выпуклого программирования всегда имеет единственное решение .
Функция F(X) = F(x 1 , x 2 , …, x n) называется сепарабельной , если ее можно представить в виде суммы функций, каждая из которых зависит только от одной переменной, т.е. если
(не исключено, что F i (x i) = 0 при некоторых i).
Пусть в задаче выпуклого программирования заданы система ограничений (4.3) и целевая функция (4.4), при этом и функция цели Z, и все ограничения, являются сепарабельными. Тогда задача имеет вид:
Найти минимум выпуклой (максимум -- вогнутой) функции
при ограничениях
Идея метода кусочно-линейной аппроксимации состоит в том, что все f i , и все заменяются ломаными линиями, состоящими из прямолинейных отрезков. При этом исходная задача выпуклого программирования заменяется новой, приближенной задачей, которая является задачей линейного программирования. Эта задача решается обычно симплексным методом, и ее решение является приближенным решением исходной задачи выпуклого программирования.
Рисунок 12. Решение задачи выпуклого программирование методом кусочно-линейной аппроксимации
Для построения приближенной задачи рассмотрим кусочно-линейную аппроксимацию функции одной переменной h(х), заданной на отрезке . Разобьем этот отрезок на r частей точками x 0 Уравнение участка ломаной между точками (x k ; h k) и (x k+1 ; h k+1) имеет вид (уравнение прямой по двум точкам). Если каждое из отношений в этом равенстве обозначить через, то получим: Отметим, что для каждого существует единственное значение, удовлетворяющее условиям (4.7). Обозначив можно переписать (4.7) в виде: [Уравнения (4.8) называются параметрическими уравнениями отрезка. Если h(x) = 0, то второе из этих уравнений обращается в тождество 0 = 0, а первое принимает вид (4.1) - уравнение отрезка, лежащего на оси абсцисс]. Таким образом, для любого уравнение ломаной можно записать в виде: причем всегда отличны от нуля только два значения (если х является внутренней точкой k-гo отрезка разбиения) или одно (если х совпадает с концом отрезка). Возвращаясь к задаче выпуклого программирования с сепарабельными функциями, отметим, что прежде всего (в зависимости от системы ограничений) нужно определить интервал изменения каждой переменной x j . Затем каждый этот интервал разбивается на части точками x jk и с использованием формул (4.9) строится кусочно-линейная аппроксимация для функций f j и. После этого можно для исходной задачи (4.6) записать приближенную задачу: Найти максимум функции при ограничениях (4.10) Поскольку приближенная задача (4.10) является задачей линейного программирования, которая обычно решается симплексным методом, условия неотрицательности переменных записываются отдельно от остальных ограничений. Отличие полученной задачи (4.10) от обычной задачи линейного программирования состоит в том, что для каждого x j имеется не более двух соседних ненулевых и, значит, нельзя брать в качестве основных переменных два с одинаковым j и несоседними k. Заметим также, что для условий неотрицательности переменных слагаемых f j (x j) и (если таковые окажутся) кусочно-линейную аппроксимацию проводить, конечно, не нужно. В настоящей главе были рассмотрены лишь некоторые методы оптимизации, применяемые менеджерами для принятия эффективных решений на предприятиях. Однако описанные приемы дают возможность понять основной принцип использования математического аппарата в экономике, позволяющего выбрать из множества альтернативных вариантов оптимальный для данного конкретного случая или ситуации. Большое число практических экономических ситуаций, исследование которых является предметом математического программирования, либо вообще не может быть сведено к линейным задачам, либо (даже когда такая линеаризация на каком-то этапе производится) попытка более детального рассмотрения все же приводит к нелинейности. Наиболее общая задача нелинейного программирования может быть сформулирована следующим образом: требуется определить значения n переменных x 1 , x 2 , ..., x n , которые удовлетворяют m уравнениям или неравенствам вида i = 1, 2, ..., m.
и обращают в максимум (или минимум) функцию цели f (X) = f (x 1 , x 2 , ..., x n).
(2.2) Предположим, что f и g i - нелинейные заданные функции, b i - известные константы. Обычно считается, что все или по крайней мере некоторые переменные должны быть неотрицательными. В частном случае линейного программирования предполагается, что функции f и g i являются линейными, т. е. Всякая другая задача математического программирования, отличная от этой, считается нелинейной задачей. В соответствующих разделах математики разработаны общие (классические) методы определения максимумов и минимумов функций различного вида. Однако такой общий подход к решению задач практически находит ограниченное применение для получения численных результатов, поскольку приводит к необходимости решать нелинейные системы уравнений со многими неизвестными и не годится для нахождения краевых экстремумов. Поэтому в математическом программировании в основном изучаются методы, которые могут служить алгоритмом, т. е. вычислительной процедурой при численном решении специальных задач, имеющих конкретные экономические приложения. Укажем некоторые из таких задач. Наиболее основательно изучены задачи с линейными ограничениями и нелинейной функцией цели. Однако даже для этих задач вычислительные методы разработаны лишь в случаях, когда функция цели обладает определенными свойствами. В частности, например, функция цели может быть представлена в виде где на функции f j (x j) должны в свою очередь быть наложены некоторые ограничения. Это так называемая сепарабельная функция. В другом случае целевая функция может быть записана как сумма линейной и квадратичной функций: Нелинейные задачи такого типа называются задачами квадратичного программирования. Для того чтобы найти оптимальное решение, на величины d ij необходимо наложить некоторые дополнительные ограничения. Задачи с нелинейными ограничениями более трудны, чем с линейными. Чтобы в этих задачах получить оптимальное решение, к функциям g i и f должны быть предъявлены весьма жесткие требования. В частности, оптимальное решение нелинейной задачи может быть получено в том случае, если ограничения g i , заданные нелинейными неравенствами, определяют выпуклое множество в пространстве Переменных (см. гл. 1, § 3) и функция цели является нелинейной гладкой выпуклой или вогнутой функцией. В дальнейшем будет дано строгое определение выпуклой и вогнутой функций. Здесь же только необходимо указать, что свойство выпуклости функций f обеспечивает существование лишь одного минимума, а свойство вогнутости f - лишь одного максимума f внутри области, задаваемой ограничениями. На этом и строятся алгоритмы определения оптимального значения функции цели. При отсутствии выпуклости или вогнутости решение задачи математического программирования наталкивается на наличие локальных минимумов или максимумов, к отысканию которых в общем случае применимы классические методы.
