Выпуклое программирование

03.03.2020

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

на множестве допустимых решений, заданных ограничениями

1) целевая функция является дифференцируемой и вогнутой, т.е. для нее выполняется условие:

При любых ,

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

При любых ,

Тогда задача (4.7)-(4.8) называется задачей выпуклого программирования .

Любая линейная функция одновременно удовлетворяет условиям и выпуклости, и вогнутости; т.е. её можно считать как выпуклой, так и вогнутой. Это позволяет считать линейные задачи частным случаем задач выпуклого программирования.

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

Введём три определения:

1). Функцией Лагранжа задачи выпуклого программирования (4.7)-(4.8) называется функция:

, (4.9)

2). Говорят, что задача выпуклого программирования (4.7)-(4.8) удовлетворяет условию регулярности , если существует хотя бы одна внутренняя точка множества допустимых решений , определяемого строгими неравенствами, полученными из (4.8) (т.е. ).

3). Точка называется седловой точкой функции , если для всех выполнено:

Если целевая функция (убрать)

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

Теорема Куна-Таккера. Если задача выпуклого программирования (4.7)-(4.8) удовлетворяет условию регулярности, то точка является оптимальным решением этой задачи тогда и только тогда, когда существует такая точка с неотрицательными координатами, что является седловой точкой функции Лагранжа данной задачи.

Условия Каруша- Куна- Таккера в дифференциальной форме:

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

Пример .Теорема Куна-Таккера обосновывает сведение задачи выпуклого программирования к задаче поиска седловой точки функции Лагранжа. Чтобы такое сведение имело практический смысл, необходимо, чтобы получившаяся задача была в чём-то проще исходной. Это происходит не всегда, поэтому разработан ряд прямых методов поиска решения нелинейной задачи (4.5), (4.6). Рассмотрим некоторые из них.

Рассмотрение этого класса задач обычно начинается с изложения метода неопределенных множителей Лагранжа. Для этого положим, что/(х ь..., х„) и 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) - это оптимальный план исходной задачи,

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

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

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

Рис. 3.3. Выпуклая функция

Рис. 3.4. Вогнутая функция

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

Задачей выпуклого программирования называется частный случай общей задачи математического программирования (3.7), (3.8), когда целевая функция и функции ограничений являются вогнутыми на выпуклом множестве R .

Так как задача максимизации функции эквивалентна задаче минимизации этой функции со знаком «минус», ограничение эквивалентно неравенству и из вогнутости следует выпуклость и наоборот. Отсюда

задачей выпуклого программирования называется также задача минимизации выпуклой функции при ограничениях:

, ,

где – выпуклые функции; R – выпуклое множество. Это просто другая форма задачи.

Следует обратить внимание, что если задача выпуклого программирования формулируется как задача на максимум, то целевая функция обязательно вогнута, а если формулируется как задача на минимум – то выпукла, Если ограничения записываются в виде , то функции ограничений вогнуты, если ограничения записываются в виде , то функции ограничений выпуклы. Эта связь обусловлена наличием определенных свойств у задачи выпуклого программирования, которые при нарушении такой связи могут отсутствовать. Два основных таких свойства сформулированы в следующей лемме.

Лемма 1

Множество допустимых планов задачивыпуклого программирования

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

Если бы функции ограничений были выпуклы, то для определяемого множества Х (3.14) выпуклость уже бы не следовала. В этом случае можно доказать выпуклость множества:

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

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

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

Лемма 2

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

Теорема 1

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

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

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

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

Линейная функция представляет собой единственный пример одновременно выпуклой и вогнутой функции, значит, она не является строго выпуклой (строго вогнутой). Квадратичная функция может быть не выпуклой (вогнутой), а может быть строго выпуклой (строго вогнутой); все это определяется матрицей D . Элементы матрицы D представляют собой вторые частные производные квадратичной функции, т.е.

Обозначим матрицу вторых частных производных через .

Лемма 3

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

то строго выпукла (строго вогнута).

Задача максимизации (минимизации) квадратичной функции при линейных ограничениях, где D – отрицательно (положительно) определенная матрица, причем D T = D , называется задачей квадратичного программирования .

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

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

Теорема 2

(О существовании седловой точки у вогнуто-выпуклой функции). Пусть X и Y суть выпуклые замкнутые ограниченные подмножества конечномерных евклидовых пространств, а функция – непрерывна по и , вогнута по и выпукла по , тогда имеет на седловую точку.

Рассмотрим функцию Лагранжа для задачи выпуклого программирования:

(3.15)

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

Однако нельзя утверждать на основании теоремы 1, что она имеет седловую точку, так как множество R не обязательно является замкнутым и ограниченным, а Y заведомо неограниченно. Тем не менее, можно ожидать, что при некоторых условиях седловая точка все же будет существовать.

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

Теорема Куна-Таккера

Если задача выпуклого программирования удовлетворяет условию Слейтера, то необходимым и достаточным условием оптимальности плана является существование такого , что пара является седловой точкой функции Лагранжа (3.15) на .

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

Пример 1

Дана задача выпуклого программирования:

Здесь, очевидно, что x = 0 есть решение задачи, но у функции Лагранжа седловой точки нет, так как внешняя грань в минимаксной задаче не достигается:

Разбиение ограничений в задаче выпуклого программирования на и , как уже говорилось, является условным. Поэтому обычно под R понимается множество простого вида, это либо все пространство E n , либо неотрицательный ортант, либо параллелепипед. Сложность же задачи выпуклого программирования определяется системой ограничений:

Так как седловая точка функции Лагранжа ищется на произведении множеств , где Y также является множеством простого вида (неотрицательным ортантом), то смысл теоремы Куна-Таккера состоит в сведении задачи поиска экстремума функции со сложными ограничениями на переменные к задаче поиска экстремума новой функции с простыми ограничениями.

Если множество R совпадает с E n , то условия экстремума, как известно, имеют вид:

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

Теорема 3

Для того чтобы непрерывно дифференцируемая вогнутая функция имела в точке максимум на E n , необходимо и достаточно, чтобы градиент функции в точке был равен нулю, т.е. .

Вспомним, что градиент функции равен:

Таким образом, для нахождения седловой точки функции Лагранжа на произведении , а следовательно, и для нахождения решения задачи выпуклого программирования при R = E n надо решить систему уравнений (3.16). Но в этой системе n уравнений, а неизвестных n + m , так как помимо n -мерного вектора нам неизвестен и m -мерный вектор множителей Лагранжа . Однако для седловой точки функции Лагранжа выполняется очень важное свойство:

. (3.17)

Из уравнения (3.17) вытекает, что либо , либо , либо то и другое одновременно. Это свойство аналогично второй теореме двойственности (подразд. 2.5) линейного программирования. Ограничения, которые выполняются в некоторой точке как равенства, называются активными .

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

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

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

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

(Документ)

Курсовой проект - Стили программирования. Практическая часть - игра 100 спичек (Курсовая)

Лабораторная работа №4. Многомерный поиск. Нелинейное программирование. Методы безусловной минимизации (Лабораторная работа)

Веселов С.Л. Программирование мини-АТС Samsung и Panasonic (Документ)

Презентация - Линейное программирование (Реферат)

Тихомирова Л.С. Методы минимизации булевых функций (Документ)

Кирсанова О.В., Семёнова Г.А. Математическое программирование (типовой расчёт) (Документ)

Козырев Д.В. 1C: Предприятие 7.7 Конфигурирование и программирование. Компонента Бухгалтерский учет. Курс дистанционного обучения (Документ)

Лабораторная работа №1. Безусловная одномерная оптимизация (Лабораторная работа)

Мощевикин А.П. Презентации лекций "Теория принятия решений" (Документ)

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 Индивидуальное задание: решение задачи методом Баранкина-Дорфмана