Двойственная задача

Для каждой задачи Е можно сформулировать следующую двойственную задачу [c.238]

Двойственная задача имеет ряд особенностей по сравнению с исходной, называемой прямой. Если прямая задача требует максимизации целевой функции, то двойственная задача является задачей минимизации, и наоборот. Коэффициенты целевой функции прямой задачи а,,. .., Ор становятся правыми частями ограничений двойственной задачи, а правые части ограничений прямой задачи С],. .., с , — коэффициентами целевой функции двойственной задачи. [c.238]

Матрица коэффициентов функций ограничений двойственной задачи получается путем транспонирования соответствующей матрицы прямой задачи. Число ограничений двойственной задачи равно числу переменных прямой задачи, а число переменных двойственной задачи — числу ограничений прямой. Знаки неравенств в ограничениях двойственной задачи изменяются на обратные по сравнению с прямой задачей. Указанные особенности позволяют формализовать процесс построения двойственной задачи при заданной прямой и наоборот. [c.238]

Двойственная задача, соответствующая прямой задаче 3, принимает следующий вид (назовем ее задачей И) [c.257]

Таким образом, задача И отличается от двойственной задачи при отсутствии [c.258]

Множители X характеризуют чувствительность двойственной функции к уровню функций-ограничений. Появление множителей kj не вызывает принципиальных затруднений при решении двойственной задачи, так как значения kj зависят от б н определяются как линейные комбинации 6к. [c.258]

В теории геометрического программирования показывается, что максимум двойственной функции достигается в стационарной точке, которая совпадает со стационарной точкой функции In V ( ), являющейся вогнутой. Следовательно, заменяя в двойственной задаче функцию У функцией 1п V, получаем. необходимость максимизации вогнутой функции на выпуклом множестве, что представляет собой задачу вогнутого, программирования, которая решается такими же методами, что и задача выпуклого программирования. Это также существенно облегчает процесс численного решения двойственной задачи. [c.258]

Используя неравенства (П.54), можно построить итерационные процедуры последовательных приближений к искомому решению путем приближенных решений прямой и двойственной задач. Тогда на каждой итерации полученное значение На дает верхнюю оценку искомого решения, а значение V — нижнюю оценку. Следовательно, после каждой итерации искомое решение можно аппроксимировать с известной точностью. [c.258]

Наиболее значительного сокращения числа неизвестных в многокомпонентной многофазной системе можно достичь, исключая из (22.9) все переменные. ....n. Такая возможность представляется благодаря особой, седловидной форме поверхности функции L(n, к) вблизи экстремума и ввиду очевидного термодинамического смысла множителей "к (см. (16.20)). Вычислительный процесс при этом организуется иначе вместо минимизации функции L в пространстве переменных п ведется поиск максимума этой функции по переменным к. Такую замену называют переходом от решения прямой задачи к решению сопряженной с ней двойственной задачи. В теории выпуклого программирования доказывают теоремы, позволяющие из формулировки прямой задачи по стандартным правилам составить соответствующую ей двойственную. В общем случае часть целевой функции двойственной задачи, от которой зависят координаты максимума, представляет собой функцию Лагранжа прямой задачи, а вместо ограничений л/< >>0 в прямой задаче выступают ограничения (22.10) в двойственной. Для рассмотренного выше частного примера из области линейного программирования двойственная к (22.2), (22.3) задача формулируется следующим образом найти максимум функции [c.188]

Для постановки двойственной задачи надо вычислить [c.339]

Двойственная задача P приобретает вид [c.339]

Следовательно, двойственная задача имеет форму [c.340]

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

Здесь G (a) - общая потенциальная энергия напряжений. Вторая переменная Л ст представляет собой заданные объемные силы в J2, а функция F (-A a) совпадает с индикаторной функцией множества К, т.е. она равна нулю для а К и + > для остальных тензоров а [14]. Поэтому двойственная вариационная задача принимает вид sup [—(7 (а)]. Эта задача соответствует принципу максимума дополнительной энергии. В [14] указаны условия существования и единственности решения исходной задачи ы и существования решения двойственной задачи а. Для этих решений справедливо равенство функционалов J (ы, Л ) =/ (Л а, а), а также экстремальное соотношение [c.144]

Двойственная задача (хозяйственны расчет) [c.79]

Рассмотрим оптимальную производственную программу машиностроительного предприятия (объединения) с точки зрения формирования хозрасчетных показателей. Ограничения исходной задачи при этом формируют решение двойственной, а решение исходной задачи соответствует ограничениям двойственной задачи (табл. 2.4) [c.79]

Исходная задача Двойственная задача [c.85]

Для расчета взаимосвязанных заданий оптимального плана производства и экономических нормативов необходимо решить исходную и двойственную задачи оптимизации производственной программы предприятия (объединения) [c.99]

X (или у ) задачи ЛП (или двойственной задачи ЛП) всегда является опорным планом, который в этом случае называется оптимальным. [c.129]

Теорема существования. Для того чтобы задача ЛП имела решение, необходимо и достаточно, чтобы допустимые множества G и И как прямой, так и двойственной задачи были не пусты. [c.129]

Возможны две причины отсутствия решения прямой или двойственной задачи ЛП противоречивость ограничений (допустимое множество G или Н пусто) или неограниченность значения целевой функции в допустимой области. При этом если G не пусто, а И пусто, то не ограничено решение прямой задачи, если G пусто, а // не пусто, то не ограничено решение двойственной задачи. [c.129]

Если G не пусто и Я не пусто, то решения прямой и двойственной задач соответствуют одной или нескольким вершинам (крайним точкам) многогранников или замкнутых неограниченных многогранных множеств. В случае соответствия решения нескольким вершинам прямая задача имеет бесконечное множество решений, являюш,ихся линейными комбинациями 2 решения, со-1=1 [c.129]

Решения двойственной задачи представляются аналогично. [c.129]

Переменные г = 1,..., т, двойственной задачи ЛП являются множителями Лагранжа прямой задачи ЛП и называются двойственными переменными прямой задачи. Аналогично переменные Xf, /=1,..., га, прямой задачи являются двойственными переменными двойственной задачи ЛП. [c.129]

Пусть X и у — решения прямой и двойственной задач ЛП. Тогда f(x )=9(y ). Значения у], г=1..... т, двойственных переменных определяют чувствительность значения целевой функции f(x) в точке х к изменению значений констант 6,- в соответствующих [c.129]

Симплекс-метод решения двойственной задачи ЛП отличается тем, что на первом этапе, соответствующем нахождению опорного плана, выполняются действия, описанные выше для второго этапа симплекс-метода решения (прямой) задачи ЛП (устраняются отрицательные элементы b j). На втором же этапе, соответствующем нахождению оптимального плана, напротив, выполняются действия, описанные для первого этапа симплекс-метода решения прямой задачи ЛП (устраняются отрицательные элементы бго). При этом значение элемента оо соответствует значению целевой функции в достигнутой точке опорного плана. Решение прямой (или двойственной) задачи позволяет по мере выполнения этапа нахождения оптимального плана получать (как значения элементов boo) нижнюю (или верхнюю) оценку значения целевой функции в экстремальной точке. Одновременно решение прямой и двойственной задач позволяет, таким образом, на каждом шаге этапа нахождения оптимального плана оценивать сверху и снизу значение целевой функции в экстремальной точке и прекращать вычисления но достижении требуемой точности. [c.131]

Проверим эти соотношения. Согласно предложенному методу сведения к двойственной задаче оптимального управления надо наряду с непараметрической системой фильтрации рассмотреть вспомогательное скалярное уравнение [c.374]

Математические модели статического и кинематического методов являются парой двойственных задач математического программирования [98]. [c.244]

Таким образом, каждое возмущение Ф(г ,р) функционала 7(г>) порождает пару новых задач — двойственную задачу максимизации (83) и задачу разыскания седловой точки лагранжиана (88). [c.110]

В дальнейшем подробно изучается класс задач в определенной мере двойственных задаче о штампе — задачи о трещинах. Поскольку задачи [c.76]

Итак, задача о трещине отрыва в упругом пространстве эквивалентна смешанной задаче (2.1), (3.14), (3.15) для полупространства Хз > О, которая, очевидно, двойственна задаче о вдавливании штампа с острой кромкой (1.14). [c.83]

Решение этой задачи сводится к решению некоторой, двойственной задачи. При этом конструируется рекуррентная последовательность векторов таких, что последовательность векторов 2 (с< )) сходится к решению исходной задачи. Вычислительные процедуры, определяющие последовательные значения векторов и векторов 2 и образуют алого-ритм, разрешающий исходную задачу. [c.196]

Как отмечено, исходная задача геометрического программирования сводится к двойственной задаче, которую в общем случае формулируют следующим образом — найти максимальное значение двойственной функции [c.159]

Ржаницып А. Р. Двойственные задачи линейного программирования в расчете железобетонных пластинок и оболочек по предельному состоянию. В кн. III Всесоюзный съезд по теоретической и прикладной механике. Аннотации докладов . Изд. АН СССР. М., 1968. [c.126]

Двойственный метод также относится к конечным методам линейного программирования. Он представляет не что иное, как симплекс-метод (метод последовательного улучшения плана), примен-енный к решению двойственной, задачи. Вычислительная процедура формулируется в терминах прямой задачи. Каждый шаг уточняет план двойственной задачи. Каждый из опорных планов двойственной задачи можно рассматривать как приближенную систему оценок условий прямой задачи (отсюда название — метод последовательного уточнения оценок). Вектор г — опорный план г/ = У < , ytn) двойственной задачи. [c.166]

Общие методы решения соответствующих задач получили развитие в ряде работ А. А. Чираса и его сотрудников. Основные результаты этих работ приведены в монографиях [70, 71, 74]. Здесь для проектирования рам минимального веса было применено линейное программирование, детально исследованы особенности различных его алгоритмов, широко использована двойственность задач, сформулированных на основании статической и кинематической теорем. Применение методов математического программирования к задачам ироекти- [c.44]

Теорема даойственности для внутренней адаптивной задачи. Задача оптимальной адаптивной фильтрации с уравнениями объекта (12.1), наблюдения (12.2) и функционалом качества (12.6) эквивалентна двойственной задаче оптимального адаптивного управления для некоторой детерминированной управляемой системы с соответствуюш им интегральным квадратичным критерием качества. Покажем это. [c.363]

Энциклопедия по машиностроению XXL

Оборудование, материаловедение, механика и ...