Теория двойственности в линейном программировании

из "Математические исследования операций в экономике "

Стремясь получить наилучшую оценку (1.47), мы приходим к формулировке некоторой новой экстремальной задачи, которая в некотором смысле логически сопряжена с задачей (1.7) и называется двойственной. Оговоримся, что приведенные рассуждения не носят строгого характера и предназначены только для того, чтобы подготовить читателя к приводимому ниже формальному определению двойственной задачи линейного программирования. [c.56]
Тем самым имеет смысл говорить о паре взаимно двойственных задач. [c.59]
Теорема 1.4. Если х, и — допустимые планы для пары двойственных задач (Д /) и (/), / ), то f(x) f(u). [c.60]
Теорема 1.5. Если для некоторых допустимых планов х и и взаимно двойственных задач (Д /) и (D f) выполняется равенство f(x) = f(u),mo х и и являются оптимальными планами для этих задач. [c.60]
Теорема 1.6. Если целевая функция f в задаче (Д /) не ограничена сверху, то двойственная к ней задача (/), / ) не имеет допустимых планов. [c.61]
Следующее утверждение, известное как теорема равновесия, используется при проверке оптимальности планов ЗЛП. [c.61]
Практическое значение теорем двойственности состоит в том, что они позволяют заменить процесс решения основной задачи на решение двойственной, которое в определенных случаях может оказаться более простым. Например, задача, область допустимых значений которой описывается двумя уравнениями, связывающими шесть переменных (т = 2, п = 6), не может быть решена графическим методом. Однако данный метод может быть применен для решения двойственной к ней задачи, которая имеет только две переменные. [c.62]
Согласно критерию оптимальности, на последней итерации данная строка неотрицательна, т. е. йА с. Следовательно, вектор и является допустимым планом двойственной задачи. [c.62]
Таким образом, существенным преимуществом модифицированного симплекс-метода является то, что он позволяет одновременно найти оптимальные планы как прямой, так и двойственной задачи. [c.63]
Читателю в качестве самостоятельного упражнения предлагается построить задачу, двойственную к (1.34)-(1.35), решение которой было приведено в п. 1.5.2, и убедиться, что вектор и = (-10, 32, 2), полученный в таблице 72(3), является для нее допустимым и оптимальным планом. [c.63]
В различных источниках компоненты оптимального плана двойственной задачи также называются двойственными оценками или теневыми ценами, а Л. В. Канторович предлагал такой термин, как объективно обусловленные оценки. [c.65]
На основе теорем двойственности для пары задач ЛП в общей форме могут быть сформулированы некоторые важные (с точки зрения экономической интерпретации) следствия. [c.65]
В рамках рассматриваемой задачи производственного планирования это означает, что если некоторый ресурс Ь имеется в избыточном количестве (не используется полностью при реализации оптимального плана), то 1-е ограничение становится несущественным и оценка такого ресурса равна 0. [c.65]
С точки зрения экономической интерпретации задача исследования параметрической устойчивости может быть рассмотрена как изучение тех пределов колебания цен на продукцию управляемого предприятия (фирмы), при которых принятый план выпуска продукции продолжает оставаться оптимальным. [c.66]
Приведенный пример исследования чувствительности оптимального плана по отношению к изменению параметров задачи является весьма простым. Очевидно, что существуют и более сложные задачи, в которых, например, исследуются совместные вариации параметров разных типов. Они составляют предмет специального раздела исследования операций, получившего название параметрического программирования. Заинтересованный читатель может получить дополнительную информацию по данному предмету в [1, 6]. [c.68]

Вернуться к основной статье