Математические методы исследования операций в экономике (стр. 11 из 37)

Повторяя те же самые действия (их легко проследить по приводимым здесь таблицам Т₂⁽²⁾ и Т₂⁽³⁾, на третьей итерации мы получим оптимальный план задачи и оптимальное значение целевой функции, которые извлекаются из второго столбца таблицы Т₂⁽³⁾. Легко заметить, что в процессе решения мы «прошли» по той же самой последовательности допустимых базисных планов, которая встречалась в п. 1.4.3.

1.6. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

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

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

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

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

то задача ЛП

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

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

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

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

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).

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

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

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

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

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

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

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

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

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

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

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

Замечание. Теорема 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*), проводятся аналогично. -

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

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

Если предположить, что у двойственной задачи (D*,f*) существует хотя бы один допустимый план и̃, то, согласно теореме 1.4, для любого допустимого плана х задачи (D, f) справедливо неравенство f(x) ≤ f*(

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

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

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

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