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

 

1.6.1. Понятие двойственной задачи ЛП. Пусть задана КЗЛП (1.7). Если целевая функция f (x) = cx достигает макси­мального значения на множестве D, то обоснованным представ­ляется вопрос о том, каким образом можно построить верхнюю оценку для нее. Очевидно, что если через и обозначить некото­рый m -мерный вектор, то

 

 

Предположим, что и можно выбрать таким образом, чтобы иА ≥ с. Тогда при любых х ≥ 0 справедливо неравенство

 

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

 

F Если задана каноническая задача ЛП

 

 

то задача ЛП

 

называется двойственной по отношению к ней. Соот­ветственно, задача (D, f) no отношению к

(D*,f *) назы­вается прямой (или исходной).

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

 

F Если задана общая задача ЛП

 

f (x) = c ₁ x ₁ +... + с_jх_j + с_{j +1} х_{j+ 1} +... + с_nx_{n →} max, x Î D, (1.50)

 

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

 

 

то двойственной по отношению к ней называется об­щая задача ЛП

 

 

где D* определяется системой уравнений и неравенств:

 

 

Правила построения задачи, двойственной по отношению к ОЗЛП, наглядно представлены схемой, показанной на рис. 1.9.

 

 

Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной:

1. Тип оптимума меняется на противоположный, т. е. макси­мум на минимум, и наоборот.

2. Вектор коэффициентов целевой функции с и столбец огра­ничений b меняются местами.

3. Матрица ограничений задачи A транспонируется.

4. Множество индексов переменных, на которые наложено условие неотрицательности в прямой задаче (например, х_j ≥ 0 или u_j ≥ 0), определяют номера ограничений, имеющих форму неравенств в двойственной задаче (a^ju ≥ с_j или a_ix ≤ b_j).

5. Множество номеров ограничений, имеющих форму нера­венств в прямой задаче (например, a_ix ≤ b_j или a^ju ≥ с_j), опреде­ляют множество индексов переменных, на которые накладыва­ется условие неотрицательности, в двойственной задаче (u_i ≥ 0 или x_i ≥ 0).

F F Из приведенного определения вытекает важное свой­ство — симметричность отношения двойственности, т. е. задача, двойственная по отношению к двойственной, со­впадает с прямой (исходной) задачей:

 

Тем самым имеет смысл говорить о паре взаимно двой­ственных задач.

 

В матричной форме пара двойственных общих задач линей­ного программирования может быть кратко записана как:

 

Рассмотрим процесс построения двойственной задачи на конкретном примере. Пусть задана ОЗЛП (D, f):

 

тогда двойственной к ней будет задача (D*, f*):

 

 

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

 

Теорема 1.4. Если х, и— допустимые планы для пары двойственных задач (D,f) и (D*,f*), тo f (x) ≤ f (u).

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

Достаточно доказать теорему для случая, когда задача (D, f) является канонической. Рассмотрим пару двойственных задач

 

Из того, что вектор и является допустимым планом задачи (D *, f *), следует, что иА ≥ с. Умножив левую и правую части дан­ного неравенства на вектор х ≥ 0, получим равносильную сис­тему неравенств

 

 

Одновременно для вектора х, являющегося допустимым планом задачи (D, f), справедливо равенство Ax=b. Тем самым доказа­но, что иb ≥ сх. A

Замечание. Теорема 1.4, разумеется, верна и для оптималь­ных планов взаимно двойственных задач: f(x*) ≤ f*(u*), где х* и u*— любые оптимальные планы задач (D, f) и (D*,f *). На самом деле, как будет видно из дальнейшего, справедливо равенство f(x*) = f*(u*).

Теорема 1.5.Если для некоторых допустимых планов и взаимно двойственных задач (D, f) и (D *, f *) вы­полняется равенство f( )=f*( ), то и являются оптимальными планами для этих задач.

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

Согласно теореме 1.4, для всех допустимых планов х задачи (D, f) справедливо неравенство сх < b. По условию теоремы f( )=f( ) или, что то же самое, с = b. Следовательно, верно утверждение: для любого x Î D с >сх, т. е. х является опти­мальным планом для задачи (D, f).

Рассуждения, доказывающие оптимальность плана для за­дачи (D*, f *), проводятся аналогично. A

Теорема 1.6.Если целевая функция f в задаче (D, f) не ограничена сверху, то двойственная к ней задача (D*,f*) не имеет допустимых планов.

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

Если предположить, что у двойственной задачи (D *, f *) су­ществует хотя бы один допустимый план и̃, то, согласно теоре­ме 1.4, для любого допустимого плана х задачи (D, f) справед­ливо неравенство f(x) ≤ f *( ) <+∞. Последнее означает, что целевая функция f задачи (D, f) ограничена сверху. Поскольку это противоречит условию теоремы, предположение о сущест­вовании допустимых планов двойственной задачи (D*,f *) не­верно. A

Следующее утверждение, известное как теорема равнове­сия, используется при проверке оптимальности планов ЗЛП.

Теорема 1.7. Пусть х* и u* — оптимальные планы ка­нонической задачи (D, f) и двойственной по отноше­нию к ней задачи (D*,f*). Если j-я компонента плана х* строго положительна (xj*>0), то соответствующее j-e ограничение двойственной задачи выполняется как равенство: а 1, ju 1* +...+аm,jum*= сj; если же j-й компо­нент плана х* имеет нулевое значение (хj* =0), то j-e ограничение двойственной задачи выполняется как неравенство: а 1, ju 1* +...+аm,jum*≥ сj.

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

Векторы х* и и*, будучи допустимыми планами соответствую­щих задач, удовлетворяют условиям: Ах* = b, х* > 0 и и*А-с ≥ 0. Найдем скалярное произведение

 

 

Согласно замечанию к теореме 1.2, оптимальные значения целевых функций взаимно двойственных задач совпадают, т. е. u*b=сх*. Последнее означает, что (u*А-с)х* = 0. Однако ска­лярное произведение двух неотрицательных векторов может быть равно нулю только в том случае, когда все попарные про­изведения их соответствующих координат равны нулю. Следо­вательно, если x_j* > 0, то u*а^j – с_j = 0, если же x_j = 0, то возмож­но u*а^j – с_j ≥ 0, что и утверждается в теореме. A

Практическое значение теорем двойственности состоит в том, что они позволяют заменить процесс решения основной задачи на решение двойственной, которое в определенных случаях может оказаться более простым. Например, задача, область до­пустимых значений которой описывается двумя уравнениями, связывающими шесть переменных (m = 2, n = 6), не может быть решена графическим методом. Однако данный метод может быть применен для решения двойственной к ней задачи, которая име­ет только две переменные.

Еще раз вернемся к таблице Т ₂^{( q )} (рис. 1.8), получаемой на финальной итерации процедуры модифицированного симплекс-метода. Более подробно рассмотрим нулевую строку матрицы Δ^-1(β^{( q )}), для которой было введено обозначение δ₀(β^{( q )}). По­элементно она может быть записана в следующем виде:

 

Введем вектор = (δ_0,1(β^(q)), δ_0,2(β^(q)),..., δ_{0, m} (β^(q))). Нетруд­но проверить, что строка оценок a ₀(β^{( q )}) может быть представ­лена следующим образом:

 

 

Согласно критерию оптимальности, на последней итерации данная строка неотрицательна, т. е. ũА≥с. Следовательно, век­тор и является допустимым планом двойственной задачи.

В то же время элемент b ₀(β^{( q )}), содержащий текущее значе­ние целевой функции и равный на последней итерации f(x*), до­пускает представление

 

 

Согласно теореме 1.5 из равенства f (х*) = f *(ũ) вытекает, что вектор ũ служит оптимальным планом двойственной задачи: u = ũ.

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

 

 

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

 

Читателю в качестве самостоятельного упражнения предла­гается построить задачу, двойственную к (1.34)-(1.35), реше­ние которой было приведено в п. 1.5.2, и убедиться, что вектор u = (-10, 32, 2), полученный в таблице Т ₂⁽³⁾, является для нее допустимым и оптимальным планом.

1.6.4. Экономическая интерпретация. Традиционная экономическая интерпретация двойственной задачи ЛП бази­руется на модели простейшей задачи производственного планирования, описанной во введении. Напомним, что в ней каждый (j -й) элемент вектора х рассматривается как план вы­пуска продукции данного вида в натуральных единицах, с_j — цена единицы продукции j -го вида, а^j — вектор, определяющий технологию расходования имеющихся m ресурсов на производ­ство единицы продукции j -го вида, b — вектор ограничений на объемы этих ресурсов.

Предположим, что для некоторых значений A, b и с найден оптимальный план х*, максимизирующий суммарный доход max{ cx }= cx *. Достаточно естественным представляется во­прос: как будет изменяться оптимальный план х * при измене­нии компонент вектора ограничений b и, в частности, при ка­ких вариациях b оптимальный план х * останется неизменным? Данная задача получила название проблемы устойчивости оптимального плана. Очевидно, что исследование устойчи­вости х * имеет и непосредственное практическое значение, так как в реальном производстве объемы доступных ресурсов b_i; могут существенно колебаться после принятия планового решения х *.

Когда вектор ограничений b изменяется на Δ b или, как еще говорят, получает приращение Δ b, то возникают соответству­ющие вариации для оптимального плана х*(b+ Δ b) и значения целевой функции f(х *(b+ Δ b)). Допустим, приращение Δ b та­ково, что оно не приводит к изменению оптимального базиса задачи, т. е. х*(b+ Δ b) ≥0. Определим функцию F (b), возвраща­ющую оптимальное значение целевой функции задачи (D (b), f) для различных значений вектора ограничений b

 

Рассмотрим отношение ее приращения F(b+ Δ b)-F(b) к при­ращению аргумента Δ b. Если для некоторого i устремить Δ b_{i →} 0, то мы получим

 

 

Учитывая, что в соответствии с теоремой 1.5

 

 

и подставив (1.57) в (1.56), приходим к выражению

 

 

F F Из формулы (1.58) вытекает экономическая интерпре­тация оптимальных переменных двойственной зада­чи. Каждый элемент u_i* может рассматриваться как предель­ная (мгновенная) оценка вклада i -го ресурса в суммарный доход F при оптимальном решении х *. Грубо говоря, величи­на u_i* равна приросту дохода, возникающему при увеличе­нии ресурса i на единицу при условии оптимального ис­пользования ресурсов.

 

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

На основе теорем двойственности для пары задач ЛП в об­щей форме могут быть сформулированы некоторые важные (с точки зрения экономической интерпретации) следствия.

 

F F Если при использовании оптимального плана прямой за­дачи i-e ограничение выполняется как строгое неравен­ство, то оптимальное значение соответствующей двой­ственной переменной равно нулю, т.е. если

 

В рамках рассматриваемой задачи производственного плани­рования это означает, что если некоторый ресурс b_i, имеется в избыточном количестве (не используется полностью при реа­лизации оптимального плана), то i -e ограничение становится несущественным и оценка такого ресурса равна 0.

 

F F Если при использовании оптимального плана двойствен­ной задачи j-e ограничение выполняется как строгое не­равенство, то оптимальное значение соответствую­щей переменной прямой задачи должно быть равно нулю, т. е. если a _{1, j}u ₁^* +...а_m,j и_m – с_j > 0, то х_j^* = 0.

 

Учитывая экономическое содержание двойственных оценок u ₁*,..., u_m, выражение а _{1, j}u ₁* +… a_m,ju_m^* может быть интерпретиро­вано как удельные затраты на j -й технологический процесс. Сле­довательно, если эти затраты превышают прибыль от реализа­ции единицы j -го продукта, то производство j -го продукта является нерентабельным и не должно присутствовать в опти­мальном производственном плане (x_j^* =0).

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

1.6.5. Анализ параметрической устойчивости реше­ний ЗЛП. В предыдущем пункте мы затронули некоторые ас­пекты чувствительности и устойчивости оптимального плана по отношению к изменению вектора ограничений b. Очевидно, что аналогичные вопросы могут быть поставлены для случая вариации коэффициентов целевой функции с_j, j Î1: n.

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

Также содержание проблемы устойчивости оптимального плана ЗЛП по отношению к вариациям целевой функции может быть проиллюстрировано с помощью первой геометрической интерпретации. На рис. 1.10 изображено множество допусти­мых планов D некоторой задачи ЛП. Как видно из рисунка, це­левая функция f (ее поведение отражает линия уровня, пока­занная жирным пунктиром) достигает экстремального значе­ния в точке х *, а изменению ее коэффициентов от с к с' или с" на рисунке соответствует поворот линии уровня относительно х *. Активным, т. е. обращающимся в равенство, ограничениям в точке х * соответствуют линии (1) и (2). До тех пор, пока при повороте, вызванном изменением вектора с, линия уровня целе­вой функции не выходит за пределы образуемого линиями огра­ничений конуса, х* остается оптимальным планом. Как показа­но на рис. 1.10, этот план не меняется при переходе от с к с', и, наоборот, при переходе от с к с" линия уровня целевой функции f(x)=c"x пересечет линию (2), что вызовет изменение опти­мального базисного плана, которым теперь станет точка .

Используя условия оптимальности плана ЗЛП

 

 

нетрудно получить количественные оценки для пределов коле­баний коэффициентов целевой функции, при которых не проис­ходит изменение оптимального плана. Допустим, вариации под­вергся некоторый элемент с_r : с_r^′ = с_r + ε_r. Возможны два случая:

1. Столбец r не входит в оптимальный базис (r Î N (β^{( q )})). Тог­да для неизменности оптимального плана необходимо и доста­точно выполнение условия

 

 

Отсюда можно получить значение для допустимой вариации

 

 

2. Столбец r входит в оптимальный базис (r Î N (β^{( q )})). В этом случае для сохранения оптимальности текущего плана потре­буется выполнение для всех небазисных столбцов (j Ï N (β^{( q )})) условий

 

 

Следовательно, в этом случае допустимая вариация должна удовлетворять условиям

 

 

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