Задачи выпуклого программирования. Постановка задачи выпуклого программирования Выпуклое программирование необходимые и достаточные условия

Лекция 11. Выпуклое программирование

Определение 1. З адачей выпуклого программирования называется задача нелинейного программирования, где все функции являются выпуклыми.

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

(1)

, (2)

. (3)

Нам понадобятся некоторые вспомогательные построения в пространстве
векторов
. Вектор из первых
компонент точки будем обозначать через . Итак,
.

Для задачи (1) – (3) определим множество

где
.

Лемма . Для задачи выпуклого программирования (1) – (3) множество выпукло .

Доказательство. Выберем произвольные векторы
из множества и число
. Тогда существуют точки и из такие, что и . Умножим эти неравенства на и
, соответственно, и сложим их. В силу выпуклости всех функций получаем

Из полученных неравенств и вытекает выпуклость множества .

Теорема 1. (Теорема Куна-Таккера в форме о седловой точке функции Лагранжа задачи выпуклого программирования ) Пусть в задаче выпуклого программирования (1) – (3) система (2) удовлетворяет условию Слейтера относительно был решением задачи (1) – (3), необходимо и достаточно, чтобы существовал неотрицательный вектор такой, что
– седловая точка функции Лагранжа.

Доказательство. Поскольку достаточность этого условия уже доказана для произвольной задачи нелинейного программирования (см. теорему 2.6 введения), осталось доказать только необходимость.

Необходимость. Пусть – решение задачи (1) – (3). Положим
. Очевидно, что
, так как
,
и
.

Убедимся, что
. Предположим противное. Это означает, что найдется точка
такая, что
. Следовательно, – такая допустимая точка, значение целевой функции в которой меньше минимального. Получаем противоречие с тем, что – решение задачи выпуклого программирования.

Итак,
. Согласно лемме множество выпукло. Следовательно, выполняются все требования теоремы 8.2. Поэтому существует ненулевой

вектор
опорный в точке ко множеству :

Убедимся далее, что все координаты вектора неположительны. Предположим противное. Пусть существует координата
. Зафиксируем у вектора все компоненты, кроме -ой. Тогда, учитывая, что произведение
может принимать сколь угодно большие значения (в силу неограниченности сверху координаты ), получаем противоречие с неравенством (4).

Легко увидеть, что при любом
векторы
включаются во множество . Тогда из (4) имеем:

Покажем, что
. Пусть это не так. Тогда
. Следовательно,
. По условию Слейтера существует вектор
такой, что
. Поэтому
. Полученное противоречие и означает, что
.

Обозначим
. Покажем, что построенный вектор представляет собой искомый вектор множителей Лагранжа. Очевидно, что
и из (5) получаем

Отсюда при
следует

. (7)

С другой стороны, так как
(поскольку
) и
, получаем неравенство

. Отсюда и из (7) следует, что в точке
выполняется условие дополняющей нежесткости:

. (8)

Из (6) и (8) имеем

или, что то же самое,

Далее, пусть
. Тогда
. Отсюда и из (8) получаем неравенство

Неравенства (9), (10) и означают, что
– седловая точка функции Лагранжа задачи выпук-

лого программирования. Что и требовалось.

Прежде, чем познакомиться с еще одним вариантом теоремы Куна-Таккера, приведем следующую теорему, которая представляет собой критерий условного минимума в терминах конусов опорных векторов.

Теорема 2. Пусть – выпуклая и дифференцируемая на
функция, множество
выпукло. Тогда для того, чтобы точка
была условным минимумом функции на множестве
, необходимо и достаточно, чтобы выполнялось включение

. (11)

Доказательство следует непосредственно из теоремы 6.5 и определения конуса
опорных векторов в точке ко множеству
.

Теорема 3. (Теорема Куна-Таккера в дифференциальной форме для задачи выпуклого программирования ) Пусть дана задача выпуклого программирования в виде (1), (2), где все функции
непрерывно дифференцируемы, система (2) удовлетворяет условию Слейтера. Тогда для того, чтобы вектор
был решением задачи (1), (2), необходимо и достаточно, чтобы существовал неотрицательный вектор такой, что выполняются условия

, (12)

.

Доказательство. Покажем, что условия (12) и (13) эквивалентны включению (11). Пусть точка
такова, что
. Тогда
и
.

Пусть теперь
. Тогда из теорем 2 и 10.5 следует, что необходимым и достаточным условием экстремума является существование таких множителей
,
, для которых
. Положим
для всех
и получим из последнего равенства условия (12) и (13). Что и требовалось.

В заключение параграфа приведем формулировки двух теорем Куна-Таккера для задачи вы-

пуклого программирования с линейными ограничениями.

Теорема 4. Пусть в задаче выпуклого программирования (1) – (3) система ограничений (2) имеет вид

, b – вектор размерности
. Тогда для того, чтобы неотрицательный вектор был решением задачи, необходимо и достаточно, чтобы

существовал неотрицательный вектор такой, что
– седловая точка функции Лагранжа данной задачи.

Отметим, что в этом случае функция Лагранжа имеет вид .

Теорема 5. Пусть в задаче выпуклого программирования (1), (2) целевая функция непрерывно дифференцируема, система ограничений (2) имеет вид
, где A – матрица размерности
, b – вектор размерности
. Тогда для того, чтобы вектор
был решением задачи, необходимо и достаточно, чтобы существовал неотрицательный вектор такой, что выполняются условия
,
.

Заметим, что в теоремах 4 и 5 не требуется выполнения условия Слейтера, поэтому они не являются частными случаями теорем 1 и 3 и требуют самостоятельного доказательства.

Функция заданная на выпуклом множестве называется выпуклой если для любых точек и любого выполняется неравенство. Линейная комбинация с неотрицательными коэффициентами выпуклых на выпуклом множестве функций есть выпуклая функция на данном множестве. Пусть функции определенные на выпуклом множестве является выпуклым на.

Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск

Лекция №12

ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ

Широкий класс задач математического программирования связан с минимизацией выпуклых функций многих переменных, определенных на выпуклом множестве. Такие задачи называют задачами выпуклого программирования (ЗВП).

Задача математического программирования

(12.1)

называется задачей выпуклого программирования, если все функции являются выпуклыми функциями.

Остановимся на элементах выпуклого анализа – области математики, в которой изучаются свойства выпуклых множеств и выпуклых функций, и которая играет фундаментальную роль в теории и методах решения экстремальных задач.

Элементы выпуклого анализа

Приведем некоторые определения и рассмотрим конкретные примеры выпуклых множеств. Мы будем в дальнейшем иметь дело с функциями, определенными на множествах конечномерного евклидова пространства E n .

Определение 12.1. Множество вида

(12.2)

называется отрезком, соединяющим точки и, и обозначаемым.

Очевидно, при точка X совпадет с одним из концов отрезка (), при – с другим (), а при - с некоторой внутренней точкой отрезка.

Определение 12.2. Множество называется выпуклым , если вместе с любыми двумя точками и ему принадлежит и отрезок их соединяющий.

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

Очевидно, в выпуклы отрезок, полупрямая, прямая, круг, треугольник, полуплоскость и вся плоскость.

Все пространство, очевидно, образует выпуклое множество. Пустое множество и множество, состоящее из одной точки, удобно считать выпуклыми.

Теорема 12.1 . Теорема Фаркаша. Пусть заданы матрица размерности и вектор. Неравенство выполняется для всех в том и только том случае, если существует вектор такой, что.

Д о к а з а т е л ь с т в о. Достаточность. Пусть выполняются соотношения и. Тогда для любого вектора будет

Необходимость. Пусть для всех справедливо. Рассмотрим конус. Если, то теорема доказана. Предположим, что. Множество, по определению 12.2, выпукло и замкнуто, поэтому в силу теоремы отделимости существует вектор такой, что

(12.3)

для всех.

Так как при всех, то из (12.3) получаем, что при всех. Значит. С другой стороны. То есть и так как это имеет место для всех, то

. (12.4)

Но, поэтому из (12.3) следует

. (12.5)

Взяв, из (12.4) и (12.5) получаем противоречие условиям теоремы.

Замечание. Приведем геометрическое истолкование теоремы Фаркаша. Пусть

и. Конус есть совокупность всех векторов, которые образуют с каждым из векторов неострые углы. На рис 12.1 конус заштрихован вертикальными линиями, а конус - горизонтальными. Геометрический смысл теоремы таков. Чтобы для любого вектора угол между и был неострым, необходимо и достаточно, чтобы принадлежал конусу.

Рис 12.1

Определение 12.3. Функция, заданная на выпуклом множестве, называется выпуклой , если для любых точек и любого выполняется неравенство

(12.6)

Функция называется строго выпуклой , если для всех неравенство (12.6) выполняется как строгое. Функция называется сильно выпуклой , если существует такое число, (константа сильной выпуклости ), что для всех и любого выполняется неравенство

(12.7)

Всякая сильно выпуклая функция является строго выпуклой и тем более выпуклой функцией, но не наоборот.

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

Теорема 12.2 . Линейная комбинация с неотрицательными коэффициентами выпуклых на выпуклом множестве функций есть выпуклая функция на данном множестве.

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

, (12.8)

где выпукла на.

Для произвольных точек и из и любого числа имеем

В этой цепочке соотношений первое неравенство справедливо, поскольку функции выпуклые. Полученный результат показывает, что функция, определяемая формулой (12.8) является выпуклой на множестве.

Теорема 12.3. Если выпукла на выпуклом множестве, то для любых точек и любых чисел, таких что выполняется неравенство Йенсена

. (12.9)

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

При этом, если, то и в (12.9) очевидно равенство. Если же. То из выпуклости и индуктивного предположения следует

Говорят, что множество удовлетворяет условию регулярности , если для каждого существует точка такая, что, т.е.

(12.10)

Нетрудно показать, что условию (12.10) эквивалентно другое условие, называемое условием регулярности Слейтера .

Теорема 12.4. Если для множества выполняется условие регулярности (12.10) , то множество регулярно по Слейтеру , а именно существует точка, в которой все ограничения выполняются строго

. (12.11)

Д о к а з а т е л ь с т в о. Пусть выполняется условие регулярности (12.10). Выберем точку, являющуюся выпуклой комбинацией точек и, следовательно, принадлежащую. Тогда при любом будем иметь

т.е. . В этой цепочке соотношений первое неравенство справедливо в силу неравенства Йенсена, а второе – поскольку, по крайней мере, один член суммы, а именно строго меньше. Эти неравенства показывают, что для рассматриваемого имеет место условие регулярности Слейтера.

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

Выпуклая функция, определенная на выпуклом множестве непрерывна в каждой внутренней точке этого множества и имеет в каждой внутренней точке производную по любому направлению

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

Теорема 12.5. Функция, дифференцируемая на выпуклом множестве, выпукла тогда и только тогда, когда для любых и, принадлежащих выполняется неравенство

. (12.12)

Д о к а з а т е л ь с т в о. Необходимость . Пусть выпукла. Тогда для любых и, () и всех таких, что справедливо неравенство

или

откуда

Переходя к пределу в последнем неравенстве при, получим

Достаточность . Пусть теперь выполняется условие (12.12) для любых двух точек множества. Тогда для точки при, принадлежащей, справедливы неравенства

Умножив первое неравенство на, второе - на и сложив полученные неравенства, имеем

или, учитывая, что имеем

т.е, что выпуклая функция на множестве.

Рассмотрим ряд экстремальных свойств выпуклых функций на выпуклом множестве, играющих существенную роль при решении задачи отыскания точки выпуклого множества, в которой выпуклая функция, определенная на достигает минимального значения: .

Теорема 12.6 . Любая точка локального минимума функции на выпуклом множестве является точкой глобального минимума

Д о к а з а т е л ь с т в о. Пусть - точка локального минимума функции на . Тогда по определению точки локального минимума существует некоторая окрестность этой точки такая, что выполняется неравенство

. (12.13)

Предположим, что не является точкой глобального минимума функции, то есть что существует точка такая, что. Рассмотрим точки вида.

т.е. . Но это противоречит условию, что - точка локального минимума, поскольку при достаточно малых точка находится в окрестности, где имеет место (12.13).

Следовательно, - точка глобального минимума на.

Теорема 12.7. Множество точек минимума выпуклой функции на выпуклом множестве является выпуклым множеством.

Д о к а з а т е л ь с т в о. Пусть - множество точек минимума выпуклой функции на выпуклом множестве, т.е.

Выберем две любые точки и. Поскольку и - выпуклое множество, то для любого будет

а ввиду выпуклости функции имеем

То есть. Кроме того, поскольку - минимальное значение функции на, то. А, значит, т.е. . Следовательно, - выпуклое множество.

Теорема 12.8. Строго выпуклая функция на выпуклом множестве достигает своего минимума не более чем в одной точке.

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

Пусть =.

Предположим, что найдется точка, такая, что

Тогда для любого точка принадлежит множеству и в силу строгой выпуклости функции будет

т.е. . Это противоречит условию, что - точка минимума. Следовательно, точка единственна.

Контрольные работы

1. Приведите постановку задачи выпуклого программирования.

2. Дайте определение выпуклого множества.

3.Приведите формулировку теоремы Фаркаша.

4. Дайте геометрическое истолкование теоремы Фаркаша.

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

6. Приведите примеры выпуклых функций.

7. Сформулируйте условие регулярности множества.

8. Сформулируйте условие регулярности по Слейтеру, множества.

9. Приведите необходимое и достаточное условие выпуклости функции , дифференцируемой на выпуклом множестве .

10. Перчислите основные экстремальные свойства выпуклых функций на выпуклом множестве.

PAGE 131

Рассмотрение этого класса задач обычно начинается с изложения метода неопределенных множителей Лагранжа. Для этого положим, что/(х ь..., х„) и g(x b ..., х„) - непрерывные функции вместе со своими частными производными, снимем пока условия неотрицательности переменных и сформулируем следующую задачу на условный экстремум:

Чтобы найти ее решение, введем множители Лагранжа у ь / = 1, т и составим так называемую функцию Лагранжа :

найдем и приравняем к нулю ее частные производные по всем переменным

получив систему п + т уравнений относительно неизвестных х ь х п,

Уи -,Уп-

Если функция f(x h ..., х„) в точке имеет экстремум, то существует такой вектор У (0> = (у, 0 ,..., у° ), что точка (А г(0) , F (0)) является решением системы (2.23). Следовательно, решая систему (2.23), мы получим точки, в которых функция (2.20) может иметь экстремум. Далее найденные точки исследуют так же, как при решении задачи на безусловный экстремум.

Таким образом, метод множителей Лагранжа включает выполнение следующих этапов.

• 1. Составить функцию Лагранжа.
• 2. Найти частные производные по Xj и у, от функции Лагранжа и приравнять их к нулю.
• 3. Решая систему (2.23), найти точки, в которых целевая функция может иметь экстремум.
• 4. Среди точек-претендентов на экстремум найти такие, в которых экстремум достигается, и вычислить значения функции f{x, ..., х„) в этих точках.

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

Определение 1. Функция f{x ,..., х п), заданная на выпуклом множестве X, называется выпуклой, если для любых точекХ,Х 2 из Хи для любого числа X, 0 X 1 выполняется неравенство

Определение 2. Функция/(*,х „), заданная на выпуклом множестве X, называется вогнутой, если для любых точек Х х, Х 2 из Хи для любого числа X, 0 X

Определение 3. Множество допустимых решений задачи выпуклого программирования удовлетворяет условию регулярности, если существует по крайней мере одна точка Xj, принадлежащая области допустимых решений, для которой g^XJ) = b h i = 1, т.

Теорема 1. Любой локальный экстремум задачи выпуклого программирования является глобальным.

Определение 4. Функцией Лагранжа задачи выпуклого программирования является функция

где у, - множитель Лагранжа.

Определение 5. Точка (Х (0) , Т (0)) = (х,°,..., х (’, у, 0 , ..., у”) называется седловой точкой функции Лагранжа, если

Приведем две короткие теоремы, носящие вспомогательный характер.

Теорема 2. Оптимальный план Х (0) задачи НП - это

где ДА) - нелинейная дифференцируемая функция, удовлетворяющая условиям

где - градиент функции /

в точке А" (0) .

Доказательство.

Разложим целевую функцию в ряд Тейлора в окрестности точки Х ({))

где АХ - вектор малых приращений Х (0) ;

I - обозначение нормы (длины) вектора.

Из выражения (2.26) следует, что если какое-либо значение координаты вектора х| 0) > 0, то обязательно будет равна нулю производная

, так как в противном случае по координате х к можно,

при фиксированных значениях остальных переменных, продолжить минимизацию целевой функции, уменьшая значение х[ 0) , если производная больше нуля, или увеличивая xf если производная меньше

нуля. Если же х| 0) = 0, то должно быть поскольку

в противном случае можно было бы уменьшить значение f(X m), увеличив 4 0) на величину Дх*, не изменяя значений остальных переменных. Следовательно, для любого к выполняется равенство:

Теорема доказана.

Определим теперь необходимые и достаточные условия существования седловой точки функции Лагранжа.

Теорема 3. Чтобы точка (А 10 *, И 0)) с неотрицательными координатами являлась седловой точкой дифференцируемой функции L(X, Y), должны выполняться условия:

Доказательство.

1) Необходимость. Пусть (Х (0) , У" (0)) - седловая точка, т.е.:

Формула (2.29) равносильна выражению

На основании (2.29) и (2.30) условия (2.27) и (2.28) выполнены. Необходимость, таким образом, доказана.

• 2) Достаточность. Положим, что выполнены условия (2.27) и (2.28). Разложим функцию L{X, Y) в ряд Тейлора в окрестности точки

Из разложения (2.31) и с учетом условий (2.27) и (2.28) следует, что

Два последних выражения равносильны формуле (2.29). Теорема доказана.

После приведенных теорем сформулируем практически очевидную теперь уже теорему Куна - Таккера.

Теорема 4 (Куна - Таккера). Для задачи выпуклого программирования (2.20) - (2.21), множество допустимых решений которой обладает свойством регулярности, точка Х (0) = (xj 0 *,..., х’ 0)), х,- 0> >0, / = 1, п является оптимальным планом тогда, и только тогда, когда существует такой вектор Т =(у 1 (0) ,..., yi 0)), У/ 0) >0, / = 1, т, что точка (Т (0) , Н 0>) является седловой точкой функции Лагранжа.

Если в задаче выпуклого программирования (2.20) - (2.21) целевая функция и ограничения непрерывно дифференцируемы, то теорему Куна - Таккера можно дополнить аналитическими выражениями, определяющими необходимые и достаточные условия того, чтобы точка (Х (0) , У i(l),) была седловой точкой функции Лагранжа, т.е. являлась решением задачи выпуклого программирования. Это выражения (2.27) и (2.28). Им удовлетворяет задача квадратичного программирования. Для ее окончательной формулировки приведем несколько определений и одну теорему.

Определение 6. Квадратичной формой относительно переменных Х[, ..., х„ называется числовая функция этих переменных, имеющая вид:

Определение 7. Квадратичная форма F называется положитель- но/отрицательно определенной, если F(X) > 0/F(X) 0 для всех значений переменных, составляющих вектор X.

Определение 8. Квадратичная форма F называется положитель- но/отрицательно полуопределенной, если F(X") > О /ДА") X, и, кроме того, существует такой набор переменных - компонент вектора X", что F(X") = 0.

Теорема 5. Квадратичная форма является выпуклой/вогнутой функцией, если она положительно/отрицательно полуопределена.

Определение 9. Задача, состоящая в минимизации/максимизации значения функции

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

где - положительно/отрицательно полуопределенная квадратичная форма, называется задачей квадратичного программирования (ЗКП).

Для этой задачи функция Лагранжа имеет вид:

Если функция Лагранжа имеет седловую точку, то в ней выполняются условия (2.27), (2.28). Вводя теперь дополнительные переменные, обращающие неравенства в равенства (этот прием используется и при решении задач ЛП), запишем эти условия в виде:

Для нахождения решения ЗКП надо определить неотрицательное решение системы линейных алгебраических уравнений (2.32). Такое решение можно найти методом искусственного базиса, примененного для нахождения минимального значения искусственной целевой функции F = ^Pj, гдеру-искусственные переменные. Метод, какиз-

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

Итак, процесс нахождения решения ЗКП включает выполнение следующих этапов.

• 1. Составляют функцию Лагранжа.
• 2. В виде выражений (2.27), (2.28) записывают необходимые и достаточные условия существования седловой точки функции Лагранжа.
• 3. Используя метод искусственного базиса, устанавливают отсутствие седловой точки для функции Лагранжа либо находят ее координаты.
• 4. Записывают оптимальное решение исходной задачи и находят значение целевой функции.

Рассмотрим элементарный числовой пример (№ 1) из книги И. Л. Акулича «Математическое программирование в примерах и задачах». По плану производства продукции предприятие должно изготовить 180 изделий. Они могут быть изготовлены по двум технологиям. При производстве Х изделий 1-м способом затраты составили xf +4х, руб., а при изготовлении х 2 изделий 2-м способом они равны х + 8х 2 руб. Определить, сколько изделий каждым способом следует изготовить для минимизации стоимости заказа.

Решение. Минимизировать следует следующую функцию:

при условиях:

Функция Лагранжа в этом случае будет выглядеть следующим образом:

Вычислим частные производные этой функции по Х, х 2 , у и приравняем их к нулю:

Перенося в первом и втором уравнении у в правую часть и приравнивая левые части, получим после очевидных сокращений:

Решая это уравнение совместно с третьим уравнением системы, найдем, что Это точка - претендент на экстремум.

Используя вторые частные производные, нетрудно показать, что найденная точка есть условный минимум функции/

Задачи, подобные рассмотренной, во множестве выдвигает экономическая практика. Правда, реальные задачи содержат, как правило, большое число переменных и ограничений, что делает невозможным их решение без применения компьютера. Однако эффективность использования стандартизованного программного обеспечения определяется знанием исследователя существа выполняемых компьютером преобразований. Это помогает ему верно ориентироваться во множестве предлагаемых для решения оптимизационных задач методов, вычислительных процедур и программных комплексов.

Для закрепления темы рассмотрим еше один числовой пример (№ 2). Найти максимальное значение функции

при условиях:

Решение. Функция/является вогнутой, так как является суммой линейной функции f = 2х 2 + 4х ъ которую можно рассматривать как вогнутую, и квадратичной формы / 2 = -х -2x1, которая отрицательно определена. Ограничения содержат только линейные ограничения. Следовательно, можно воспользоваться теоремой Куна - Таккера и схемой решения ЗКП.

1. Составим функцию Лагранжа:

2. Запишем необходимые и достаточные условия существования седловой точки функции L.

3. Введем в систему линейных неравенств дополнительные неотрицательные переменные v b V2, w, w 2 , обращающие неравенства в равенства. Получим систему уравнений:

При этом, естественно, выполняются условия:

Необходимо найти базисное решение системы уравнений (2.33) для определения координат седловой точки функции Лагранжа. С этой целью воспользуемся методом искусственного базиса. Минимизируем искусственную целевую функцию

где Zi, Zi - искусственные переменные, при условиях:

Здесь очевидное базисное допустимое решение выглядит следующим образом:

Целевую функцию F выразим через небазисные переменные:

Заканчивая рассуждения, отметим, что она обращается в ноль при Xj (0) = 1, = 1 и остальных переменных с нулевыми значениями. Таким образом, Т (0) = (1, 1) - это оптимальный план исходной задачи,

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

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