Куна — Таккера точки 228 [c.328]
По теореме Куна - Таккера [56J, в точке оптимума задачи (4.78) - (4.80) необходимо и достаточно выполняются условия [c.136]
Достигает ли функция Лагранжа максимума в точке ж Условие (9.79) теоремы Куна-Таккера совпадает по форме с необходимым условием максимума функции Лагранжа R на множестве Vx. В связи с этим возникает желание заменить условие (9.79) условием [c.335]
Теорема Куна—Таккера. Центральное место в теории нелинейного программирования занимает теорема Куна— Таккера, которая связывает решение ЗИП с наличием седловой точки у соответствующей функции Лагранжа. [c.103]
Значение теоремы Куна — Таккера состоит в том, что она позволяет связать процесс решения оптимизационной задачи с поиском седловых точек функции Лагранжа, т. е., грубо говоря, с максимизацией этой функции по х и минимизацией по и. [c.105]
Обратная теорема Куна-Таккера (достаточное условие оптимальности) при условиях вогнутости всех функций (.), (.) утверждает, что если в допустимой точке х нашлись множители Лагранжа удовлетворяющие требованиям прямой теоремы (условиям первого порядка), то точка х оптимальна. [c.12]
Для применимости к задаче (27) теоремы Куна-Таккера нужно проверить, что все "активные" ограничения (т.е. выполняющиеся в точке х как равенства) линейно независимы. Это проводится проверкой ранга матрицы градиентов ограничений, [c.19]
Предполагая опять, что исследуемая нами точка (р, ж, а, у) внутренняя (0 < (ж, а)), пользуясь, как и ранее тем, что градиенты не равны нулю и, следовательно, теоремой Куна-Таккера — найдем дифференциальную характеристику оптимума [c.26]
I) Если выполнены предположения утверждения, то и к задаче оптимума (используем ненулевой градиент) и к задаче равновесия применима теорема Куна-Таккера, и можно проверить совпадение условий первого порядка. Диф. характеристика равновесия (x,y,p,q) будет иметь вид [c.34]
Предполагая обычные условия ВЫПУКЛ, ГРАД, и что точка равновесия (f,x,y) — внутренняя (в смысле t > О, х 3> 0) применим теорему Куна-Таккера и получим дифференциальные соотношения первого порядка. При нахождении условия равновесия потребителя г для которого Ц > О, подставим выражение для х = у1 прямо в целевую функцию [c.36]
Если, кроме того, при некотором ж 0 справедливо д(х ) >0, и для каждого j выполнено одно из условий либо 1) д х) вогнута либо 2) для каждого ж О верно Vg3(x) Ф 0, то условия Куна-Таккера являются необходимыми и достаточными. [c.62]
Применим теперь эту теорему к рассматриваемой нами задаче потребителя в случае, когда X = R+. Рассмотрим вначале несколько вариантов условий на предпочтения, гарантирующих то, что условия Куна-Таккера определяют решение задачи потребителя. Одним из наиболее простых вариантов состоит в том, чтобы предположить условие 3, то есть неравенство градиента нулю и дважды непрерывную дифференцируемость функции полезности. Но мы рассмотрим также другой комплекс условий, который будет востребован нами в дальнейших рассуждениях. [c.62]
Это свойство известно читателю из вводного курса микроэкономики и означает, что решение задачи потребителя характеризуется равенством предельной нормы замещения любых двух благ отношению цен этих благ. Так как Л > 0, то по условию дополняющей не-жесткости теоремы Куна-Таккера получаем, что бюджетное ограничение должно выходить на равенство px=R. Это второе условие первого порядка, которому должен удовлетворять оптимум рассматриваемой задачи. [c.64]
Так как Л,(р, х) — решение задачи взаимности, то по теореме Куна-Таккера существует множитель Лагранжа А, ограничения задачи такой, что [c.82]
Если в рассматриваемом оптимуме Парето существует подобное благо, то, как можно проверить, выполнены условия регулярности теоремы Куна — Таккера, и можно считать, что w0= 1 (для всех г0= 1,. .., т). Это позволяет исключить из полученных соотношений множители Лагранжа и представить дифференциальную характеристику в терминах предельных норм замещения. [c.345]
Как и в предыдущих теоремах, ограничимся схемой доказательства. Поскольку (ж, у) — Парето-оптимум, то по теореме Куна—Таккера он удовлетворяет уравнениям (5) и (6). [c.366]
Если функции прибыли вогнуты, и выпуск у > 0 то возможно уменьшить его, увеличив тем самым прибыль прочих участников. Это означает, что выполнено условие Слейтера и теорема Куна-Таккера применима. [c.552]
Теорема Джона не гарантирует, что множитель Лагранжа целевой функции, Х0, отличен от нуля. Однако если Х0 = 0, то условия Куна-Таккера характеризуют не решение рассматриваемой задачи, а структуру множества ограничений в точке х и теорема не имеет непосредственной связи с интересующей нас задачей максимизации функции ф(-), поскольку градиент самой функции ф(-) пропадает из условий Куна — Таккера. Поэтому важно [c.700]
Заметим, что если Х0>0, то без потери общности можно считать Я0 = 1, что обычно и делается. Соответствующую теорему и называют собственно (прямой) теоремой Куна — Таккера. [c.701]
Один из вариантов обратной теорема Куна — Таккера утверждает, что при вогнутости функций ф(-), (Vf ( ) выполнение этих условий в допустимом решении х (т.е. точке, удовлетворяющей ограничениям) при некоторых множителях Лагранжа, удовлетворяющих требованиям прямой теоремы, гарантирует, что х является решением задачи. [c.701]
Точка М0 (xl . .. j . .. ) R" является точкой Куна—Таккера для за дачи (9.59) — (9.61), если существует точка Р0 (у . .. / . .. у"т) (Ra)+ такая, что справедливы условия Куна—Таккера [c.228]
О Оптимальное решение задачи (9.62) — (9.64) находится среди точек Куна — Таккера этой задачи М1(х1 0), где— 2<д 1<01 и М2( 2 3]/2). Так как /(М1)=.0, а /(М2) = 3, то М2 (J/2 3/1/2) — оптимальное решение задачи (9.62)— (9.64). [c.229]
Следует отметить, что необходимое условие оптимальности малопригодно для решения большинства задач нелинейного программирования, так как лишь в редких случаях удается найти все точки Куна — Таккера задачи нелинейного программирования. [c.229]
Если функции f(M) и ФДМ) t == 1, 2,. .., т, дифференцируемы в точке М0 R , то эта точка является оптимальным решением задачи (9.59)—(9.61) тогда и только тогда, когда она является точкой Куна—Таккера для этой задачи. [c.231]
Полагая в этой системе дг = 1, х = 1, xs = 1, найдем Hi =1/6, г/а = 0. Поэтому Л1,(1 1 1) является точкой Куна - Таккера для задачи (9.65) — (9.67). Следовательно, Л в(1 1 1) — оптимальное решение этой задачи. [c.231]
Между решением общей задачи нелинейного программирования и седловой точкой функции Лаг-ранжа существует тесная связь. Для известного оптимального вектора можно при некоторых естественных предположениях подобрать такой вектор А, чтобы пара векторов (г, А) являлась седловой точкой функции L (х, К). Этот факт утверждается известной теоремой Куна и Таккера вектор я является оптимальным вектором нелинейной задачи - тогда и только тогда, когда существует такой вектор А > О, что пара (я, А) есть седловая точка функции L (х, А). Значит, вместо того, чтобы специально решать задачу нелинейного программирования, можно (что зачастую проще) искать седловую точку функции, Лагранжа L (х, А). Зная ее, мы будем знать и решение задачи 1. Не будем утомлять читателей-экономистов доказатель- [c.106]
КУНА—ТАККЕРА УСЛОВИЯ [Kuhn—Tu ker onditions] — условия существования оптимальной точки (оптимального решения) в задачах выпуклого программирования и, в частности, — линейного программирования. Соответственно этим условиям для того чтобы точка х была оптимальной, необходимо и достаточно, чтобы пара точек (х, X ) образовала седло функции Лагранжа (см. Лагранжиан, Седловая точка). Таким образом, задача сводится к нахождению совместного решения прямой (поиск ж ) и двойственной (поиск X ) задач. Сформулированы американскими математиками X. Куном и А. Таккером. [c.165]
См. также Ассортиментные задачи, Базисное решение, Блочное программирование, Булево линейное программирование, Ведущий столбец, Ведущая строка, Вершина допустимого многогранника, Вырожденная задача, Гомори способ, Граничная точка, Двойственная задача, Двойственность в линейном программировании, Дифференциальные ренты, Дополняющая нежесткостъ, Жесткость и нежесткость ограничений ЛП, Задача диеты, Задача о назначениях, Задача о раскрое, Задачи размещения, Исходные уравнения, Куна— Таккера условия, Множители Лагранжа, Область допустимых решений, Опорная прямая, Оптимальное распределение ресурсов, Распределительные задачи, Седловая точка, Симплексная таблица, Симплексный метод, Транспортная задача. [c.173]
Еще более простой в применении оказывается технология, предполагающая максимизацию не одного, "главного", частного критерия, а линейной свертки от всех критериев. Эта технология построена на результатах теоремы, доказанной тремя учеными — Куном, Таккером и Карлиным. Было показано, что если множество альтернатив, задаваемых характеристиками х, выпукло, а все ги.(а) — вогнуты, то для всякой эффективной стратегии а° найдутся такие неотрицательные числа у,, в сумме равные единице, что [c.179]
Другое требование определения "равновесия" — полусбалансированность — вытекает из допустимости Парето-оптимальной точки ж, а третье требование — закон Вальраса — следует из дополняющей нежесткости условий Куна-Таккера для задачи (27). Действительно, если оценка pk = ak какого-то товара k положительна, то ограничение (баланс) по нему выполнено как равенство, что и означает (17). [c.20]
Пусть функция полезности равна и(х) = (xi+X2-2)3. Цена на первый товар равна 1, а на второй равен 2. Доход потребителя равен 3. Проверьте, что целевая функция квазивогнута и локально ненасыщаема. Покажите, что точка (1, 1) удовлетворяет условиям Куна-Таккера, но не является оптимальной. [c.79]
Это одно из условий первого порядка, т.е. необходимое условие максимума. Поскольку, как мы предположили, градиент не равен нулю, то vz> 0, и по условию дополняющей нежесткости теоремы Куна — Таккера получаем, что бюджетное ограничение выходит на равенство [c.158]
Этому требованию удовлетворяет к ц -. Условие дополняющей нежесткости для технологического ограничения выполнено, поскольку соответствующее условие с точностью до замены на к,- выполнено в Парето-оптимуме. Таким образом, выполнены условия Куна—Таккера, и поскольку производственная функция вогнута, то у — решение задачи производителя. [c.194]
М2 0/2 3/1/2), которые являютс я искомыми точками Куна — Таккера. [c.229]
Необходимое условие оптимальности для задачи нелинейного программирования можно сформулировать следующим образом. Пурть М — оптимальное решение задачи (9.59)— (9.61), причем функции /(УИ) Ф,(Л1),1 = 1,2,. . ., m, дифференцируемы в этой точке. Если МЛ — неособая точка допустимого множества задачи (9.59) — (9.61), то она является точкой Куна — Таккера этой задачи. [c.229]
Таким образом, если допустимре множество Q задачи (9.59) — (9.61) не имеет особых точек, а функции f(M), Ф (М), t=l, 2,. .., т, дифференщидгуемы во всех точках Q, то оптимальное решение этой задачи следует искать среди точек Куна— -Таккера. [c.229]