Первая теорема двойственности

Теоремы двойственности позволяют установить связь между оптимальными решениями пары двойственных задач. Решив одну из пары двойственных задач, можно или найти оптимальное решение другой задачи, не решая ее, или установить его отсутствие. Возможны следующие случаи: 1) обе задачи из пары двойственных имеют оптимальные решения; 2) одна из задач не имеет решения ввиду неограниченности целевой функции, а другая не имеет решения ввиду несовместности системы ограничений; 3) обе задачи из пары двойственных не имеют решений из-за неограниченности целевых функций.

Теорема 5.1. Если одна из пары двойственных задач имеет оптимальное решение, то и двойственная к ней имеет оптимальное решение; причем значения целевых функций задач на своих оптимальных решениях совпадают. Если же одна из пары двойственных задач не имеет решения ввиду неограниченности целевой функции, то другая не имеет решения ввиду несовместности системы ограничений.

Доказательство. Пусть имеется несимметричная пара двойственных задач

Z(X) = CX Первая теорема двойственности - student2.ru max, Первая теорема двойственности - student2.ru ,

AX = Первая теорема двойственности - student2.ru , Первая теорема двойственности - student2.ru

Первая теорема двойственности - student2.ru .

Прежде, чем приступить к доказательству, получим ряд соотношений. Предположим, что первая (прямая) из задач решалась симплексным методом и получено оптимальное решение Первая теорема двойственности - student2.ru с базисом Первая теорема двойственности - student2.ru . Запишем последнюю симплексную таблицу (табл. 5.1).

Т а б л и ц а 5.1

Первая теорема двойственности - student2.ru

Запишем разложение вектора Первая теорема двойственности - student2.ru по базису оптимального решения

Первая теорема двойственности - student2.ru , k = 0, 1, 2, . . . , n.

Преобразуем данное разложение

Первая теорема двойственности - student2.ru =

= Первая теорема двойственности - student2.ru ,

k = 0, 1, 2, ..., n.

Обозначим

D = Первая теорема двойственности - student2.ru , Первая теорема двойственности - student2.ru Первая теорема двойственности - student2.ru ,

тогда

Первая теорема двойственности - student2.ru , k = 0, 1, 2, ..., n. (5.11)

Умножим данное матричное равенство на обратную матрицу Первая теорема двойственности - student2.ru слева:

Первая теорема двойственности - student2.ru Первая теорема двойственности - student2.ru Первая теорема двойственности - student2.ru D Первая теорема двойственности - student2.ru .

Так как Первая теорема двойственности - student2.ru D = Е, Е Первая теорема двойственности - student2.ru = Первая теорема двойственности - student2.ru ,то

Первая теорема двойственности - student2.ru = Первая теорема двойственности - student2.ru Первая теорема двойственности - student2.ru , k = 0, 1, 2, ..., n. (5.12)

Аналогично можно получить

Первая теорема двойственности - student2.ru . (5.13)

Запишем с учетом полученного оценки Первая теорема двойственности - student2.ru , k = 0, 1, 2, ..., n.

В общем случае формула для расчета оценок имеет вид (4.9)

Первая теорема двойственности - student2.ru .

Обозначим через С* матрицу-строку коэффициентов при базисных переменных в оптимальном решении. Тогда для оценок разложений векторов-условий по базису оптимального решения имеем

Первая теорема двойственности - student2.ru . (5.14)

Обозначим матрицу, составленную из векторов Первая теорема двойственности - student2.ru через Первая теорема двойственности - student2.ru , т. е. Первая теорема двойственности - student2.ru ; матрицу-строку из оценок Первая теорема двойственности - student2.ru через Первая теорема двойственности - student2.ru , т. е. Первая теорема двойственности - student2.ru и матрицу-строку коэффициентов целевой функции через С, т. е. Первая теорема двойственности - student2.ru . Кроме того, матрица системы уравнений-ограничений Первая теорема двойственности - student2.ru ,тогда из формул (5.12) и (5.14) следует

Первая теорема двойственности - student2.ru , (5.15)

Первая теорема двойственности - student2.ru . (5.16)

Теперь приступим к доказательству первого утверждения теоремы.

1. Докажем, что допустимое решение двойственной задачи имеет вид

Первая теорема двойственности - student2.ru . (5.17)

Поскольку решение прямой задачи Первая теорема двойственности - student2.ru на максимум оптимальное, то ее оценки неотрицательные

Первая теорема двойственности - student2.ru .

Отсюда

Первая теорема двойственности - student2.ru

т. е. Первая теорема двойственности - student2.ru удовлетворяет системе ограничений двойственной задачи.

2. Докажем, что при Первая теорема двойственности - student2.ru и Первая теорема двойственности - student2.ru

Первая теорема двойственности - student2.ru . (5.18)

Получаем

Первая теорема двойственности - student2.ru Первая теорема двойственности - student2.ru .

3. Докажем, что

Первая теорема двойственности - student2.ru , (5.19)

где Первая теорема двойственности - student2.ru - область допустимых решений прямой задачи; Первая теорема двойственности - student2.ru - область допустимых решений двойственной задачи.

Для этого систему ограничений прямой задачи умножим слева на допустимое решение двойственной задачи Y, а систему ограничений двойственной задачи умножим справа на допустимое решение Х исходной задачи, получим

Первая теорема двойственности - student2.ru

Так как Первая теорема двойственности - student2.ru то

Первая теорема двойственности - student2.ru

т. е. Первая теорема двойственности - student2.ru

4. Далее докажем, что Первая теорема двойственности - student2.ru является оптимальным решением. Так как прямая задача на максимум, а Первая теорема двойственности - student2.ru – оптимальное решение, то Первая теорема двойственности - student2.ru . Двойственная задача на минимум, поэтому значение ее целевой функции на оптимальном решении Первая теорема двойственности - student2.ru должно удовлетворять условию Первая теорема двойственности - student2.ru . Как показано в пункте 3, Первая теорема двойственности - student2.ru Первая теорема двойственности - student2.ru , поэтому значение Первая теорема двойственности - student2.ru не может быть меньше Первая теорема двойственности - student2.ru Первая теорема двойственности - student2.ru , а может быть только равно Первая теорема двойственности - student2.ru . Это равенство достигается при Первая теорема двойственности - student2.ru , которое и будет оптимальным решением двойственной задачи. Первое утверждение теоремы доказано.

Запишем полезное соотношение для нахождения оптимального решения двойственной задачи. Матричное равенство Первая теорема двойственности - student2.ru представим следующим образом:

Первая теорема двойственности - student2.ru ,

где Первая теорема двойственности - student2.ru – матрица обратная к матрице D, составленной из векторов-условий задачи, образующих базис оптимального решения. Матрица Первая теорема двойственности - student2.ru находится в последней симплексной таблице под единичными векторами первой симплексной таблицы.

Отсюда следует, что Первая теорема двойственности - student2.ru Так как Первая теорема двойственности - student2.ru , то Первая теорема двойственности - student2.ru или

Первая теорема двойственности - student2.ru . (5.20)

Данная формула позволяет, используя оценки последней симплексной таблицы решения прямой задачи, записывать оптимальное решение двойственной задачи как сумму оценок и коэффициентов целевой функции.

Докажем второе утверждение теоремы. Пусть прямая задача не имеет оптимального решения ввиду неограниченности целевой функции Z(X) ® +¥. Так как Первая теорема двойственности - student2.ru и Первая теорема двойственности - student2.ru , то или Первая теорема двойственности - student2.ru является пустым множеством, или Первая теорема двойственности - student2.ru .

Пример 5.3. Для данной задачи составить двойственную, решить ее симплексным методом и, используя первую теорему двойственности, найти решение исходной задачи:

Первая теорема двойственности - student2.ru

Решение. Используя вторую симметричную пару двойственных задач (5.8), составляем задачу, двойственную к исходной.

Первая теорема двойственности - student2.ru ,

Д
Первая теорема двойственности - student2.ru Первая теорема двойственности - student2.ru

Вводим неотрицательные дополнительные переменные Первая теорема двойственности - student2.ru для приведения задачи к каноническому виду, получаем

Первая теорема двойственности - student2.ru

Т а б л и ц а 5.2

Первая теорема двойственности - student2.ru

Находим начальное опорное решение Первая теорема двойственности - student2.ru = (0, 0, 0, 6, 7, 9) с единичным базисом Первая теорема двойственности - student2.ru . Решение задачи симплексным методом приведено в табл. 5.2.

Оптимальное решение двойственной задачи Первая теорема двойственности - student2.ru = (2, 3, 0), его базис Первая теорема двойственности - student2.ru , значение целевой функции
max F(Y) = F( Первая теорема двойственности - student2.ru ) = 16. Оптимальное решение исходной задачи, двойственной к решенной, найдем по формуле (5.17)

Первая теорема двойственности - student2.ru

Матрица D состоит из координат векторов Первая теорема двойственности - student2.ru , входящих в базис оптимального решения двойственной задачи

Первая теорема двойственности - student2.ru

Матрица Первая теорема двойственности - student2.ru находится в последней симплексной таблице. Ее столбцы располагаются под столбцами единичной матрицы, т. е. под единичными векторами Первая теорема двойственности - student2.ru , образующими базис начального опорного решения:

Первая теорема двойственности - student2.ru .

Координатами вектора Первая теорема двойственности - student2.ru являются коэффициенты целевой функции при базисных неизвестных оптимального решения Первая теорема двойственности - student2.ru . Данные коэффициенты записываются в том же порядке, в каком векторы условий входят в базис оптимального решения, т. е. Первая теорема двойственности - student2.ru (5, 2, 0).

Вычисляем

Первая теорема двойственности - student2.ru .

Оптимальное решение исходной задачи можно найти проще по формуле (5.20)

Первая теорема двойственности - student2.ru , i = 1, 2, 3.

Для этого необходимо к оценкам разложений векторов Первая теорема двойственности - student2.ru , входящих в базис начального опорного решения по базису оптимального решения, т. е. к оценкам этих векторов в последней симплексной таблице, прибавить соответствующие коэффициенты целевой функции (в таблице они расположены в верхней строке над оценками)

Первая теорема двойственности - student2.ru Первая теорема двойственности - student2.ru Первая теорема двойственности - student2.ru

Ответ: min Z(X) = 16 при Первая теорема двойственности - student2.ru = (0, 1, 1).

Пример 5.4. Найти решение данной задачи и двойственной к ней.

Первая теорема двойственности - student2.ru

Решение. Задача, двойственная к данной, имеет вид

Первая теорема двойственности - student2.ru

Первая теорема двойственности - student2.ru

В данной паре двойственных задач легче решить исходную задачу, так как она имеет начальное опорное решение Первая теорема двойственности - student2.ru = (0, 0, 1, 11, 2) с единичным базисом Первая теорема двойственности - student2.ru и ее без дополнительных преобразований можно решить симплексным методом. Решение исходной задачи приведено в табл. 5.3.

Т а б л и ц а 5.3

Первая теорема двойственности - student2.ru

Оптимальным решением исходной задачи является вектор
Первая теорема двойственности - student2.ru = (4, 1, 8), базис оптимального решения Первая теорема двойственности - student2.ru , значение целевой функции Первая теорема двойственности - student2.ru . По формуле (5.17) находим оптимальное решение двойственной задачи

Первая теорема двойственности - student2.ru .

Данное решение можно найти также по формулам (5.20) Первая теорема двойственности - student2.ru :

Первая теорема двойственности - student2.ru .

Таким образом, оптимальным решением двойственной задачи является вектор Первая теорема двойственности - student2.ru = (2, 2/7, 31/7), min F(Y) = F( Первая теорема двойственности - student2.ru ) = 14.

Ответ: max Z(X)=14 при Первая теорема двойственности - student2.ru =(4, 1, 8); min F(Y) =14 при Первая теорема двойственности - student2.ru =(2, 2/7, 31/7).

Наши рекомендации