Промежуточные вычислении 5 страница

Максимизировать z = бде, + 2х₂ + 8х₃ + 4x_t + 2x_s + 10х₆ при ограничениях

8х, +х₂ + 8х₃ + 2x_t + 2х_ъ + 4х₆ < 13, 0<x<l,j = l,2,...,6.

Глава 7. Теория линейного программирования

3. Решите следующие задачи ЛП методом решения задач с ограниченными пе­ременными.

a) Минимизировать z = бдс, - 2х₂ - Зх₃ при ограничениях

2х, + 4х₂ + 2х₃<8, х,-2х₂ + 3х₃<7, О < х, < 2, 0 < х₂ < 2, 0 < х₃ < 1.

b) Максимизировать z = Зх, + Ъх₂ + 2х₃ при ограничениях

х, + 2х₂ + 2х₃<10, 2х, +4х₂ + 3х₃< 15, О < х, < 4, 0 < х₂ < 3, 0 < х₃ < 3.

4. В следующих задачах некоторые переменные имеют положительные ниж­ние границы. Решите эти задачи методом решения задач с ограниченными переменными.

a) Максимизировать z = Зх, + 2х₂ - 2х₃ при ограничениях

2х,+ х₂ + х₃<8, х, + 2х₂ - х₃ > 3, 1<х,<3, 0<х₂<3, 2<х₃.

b) Максимизировать z = x_l + 2х₂ при ограничениях

-х, + 2х₂>0, Зх, +2х₂< 10, -х, + х₂< 1, 1<х,<3,0<х₂<1.

c) Максимизировать z = 4х, + 2х₂ + 6х₃ при ограничениях

4х, - х₂ < 9, -х, +х₂ + 2х₃<8, -Зх,+ х₂ + 4х₃<12, 1<х,<3,0<х₂<5, 0<х₃<2.

5. Рассмотрим матричное представление задачи с ограниченными переменны­ми. Разобьем вектор X на две части (Х_г, Х_ц), где элементами вектора Х_ц яв­ляются переменные, к которым в процессе выполнения алгоритма будет применена подстановка, эквивалентная их верхнему пределу. Тогда задачу ЛП с ограниченными переменными можно записать следующим образом.

f 7 ^

1 -с_; -с,Л

0 D, D.

7.3. Алгоритм решения задач с ограниченными переменными

Пусть В (и Х_в) — базисное решение текущей симплексной итерации, полу­ченное после подстановки Х_ц = U_u - Х'_и, где U„ — подмножество элементов вектора значений верхних границ U, соответствующего переменным Х_ц. По­кажите, что в данном случае симплекс-таблица имеет следующий вид.

Базис	К		Решение
z	CSB_1DZ-CZ	— СвВ 1Du + Си	CsB-1 ь' + с„иц
Xs	B"1D;	-В_1Оц	В"1 Ь'

Здесь b' = b - D_UU_U.

6. В задаче из примера 7.3.1 выполните следующее.

a) На этапе итерации 1, используя матричные представления, проверьте, что Х_в = (х₄, х₁)^г = (5/2,3/2)^г.

b) На этапе итерации 2 покажите, как на основе исходных данных задачи можно вычислить В"¹. Затем, используя матричные представления, про­верьте вычисленные в примере значения переменных х₄ и х,.

7. Решите задачу из упражнения 3.1 с помощью модифицированного (использующего матричные представления) симплекс-метода.

8. Двойственный симплекс-метод решения задач с ограниченными перемен­ными. Двойственный симплекс-метод (раздел 4.4) также можно модифици­ровать для учета явных ограничений, налагаемых на переменные. Для этого после подстановок x_t = u_;- x'_t (u_j — верхняя граница переменной х-, если u_f

бесконечна, заменяем ее достаточно большим положительным числом М) исходная задача записывается в двойственной форме. Далее выполняются следующие действия.

Шаг 1. Если значение какой-либо базисной переменной (Х_в), превышает ее верхнюю границу, выполняем замену (ХД = (U_B), - (Х₆).'.

Шаг 2. Если базисное решение допустимо, вычисления заканчиваются.

В противном случае среди базисных переменных определяем ис­ключаемую из базиса переменную х_г как имеющую наибольшее отрицательное значение.

Шаг 3. В соответствии с условием оптимальности двойственного сим­плекс-метода определяем вводимую в базис переменную.

Шаг 4. Выполняем пересчет базиса. Переходим к шагу 1.

Примените описанный алгоритм к следующим задачам.

а) Минимизировать г = -Зх, - 2х₂ + 2х₃

при ограничениях

2х, + х₂ + х₃ < 8, -х, + 2х₂ + х₃> 13, 0<х,<2, 0<х₂<3, 0<х₃<1.

Глава 7. Теория линейного программирования

Ь) Максимизировать г = х_г + Ъх₂ - 2х₃ при ограничениях

4x₁ + 2х₂ + 2х₃ < 26, + Здс₂ + 4х₃> 17, О < х, < 2, 0 < х₂ < 3, 0 < х₃ (х₃ сверху не ограничена).

7.4. МЕТОД ДЕКОМПОЗИЦИИ

Рассмотрим разработку производственного плана предприятия, состоящего из нескольких подразделений. Хотя каждое подразделение имеет собственные произ­водственные возможности и соответствующие ограничения, производственные планы отдельных подразделений обобщаются на уровне управления предприятием. Таким образом, результирующая модель рассматриваемого предприятия будет со­держать ограничения двух типов: общие, соответствующие уровню всего предпри­ятия, и независимые, отображающие производственные ограничения отдельных подразделений. На рис. 7.5 показана структура ограничений для л подразделений. Отсутствие общих ограничений означает, что все подразделения независимы.

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

Общие ограничения

Независимые ограничения'

Подразделение 1

Подразделение 2

Подразделение л

Рис. 7.5. Структура декомпозиции задачи линейного программирования

Математическую модель, к которой применяется метод декомпозиции, запи­шем в следующем виде.

Максимизировать г = С,Х, + С₂Х₂ +... + С_лХ_п

при ограничениях

7.4. Метод декомпозиции

+ АпХл = bo

= Ь,

= ь₂

D„X_n = Ь_л

Х_;>0,; = 1,2.....п.

При необходимости ограничения в виде неравенств с помощью дополнительных переменных преобразуются в равенства.

Метод декомпозиции основан на определении крайних точек множеств {Xj D_yX_y = b_;, Х_у > 0}, / = 1, 2, п. Для этого необходимо, чтобы каждое множество {Xj^X^b,, X.>0} было ограниченным. Это требование выполнимо всегда, по­скольку при необходимости для любого множества / можно добавить искусственное ограничение IX. < М, где М — достаточно большое положительное число.

Обозначим через Y_yt, k=l, 2, K_Jt крайние точки множества {X. |D_yX. = Ь_>, X. > 0}. Тогда можно записать

^ху=ЕРЛ' У-1,2,..., и,

^Ki

где Р_>4 > 0 для всех k и /*, причем = 1.

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

*1 к. к.

Максимизировать z = X^Ci^yi*Pu +Z^C2^Y2*p₂* + - + Z^c»^y«'p«4 при ограничениях

z ^a.^y.»p.* ⁺i ^a^*p^⁺-⁺i ^a»^y»»p»*=^ь° -

4=1 4=1 4 = 1

4=1

IP- =1-

4 = 1

P^ > 0 для всех k и j.

В главной задаче новыми переменными являются p_Jt. После того как будет най­дено оптимальное решение Рд этой задачи, оптимальное решение исходной задачи

вычисляется путем обратных подстановок по следующей формуле.

^Х,=1Р"Л, / = 1,2,...,п.

4 = 1

AiXi + D,X,

АгХ₂ + D₂X₂

Глава 7. Теория линейного программирования

Может показаться, что для решения главной задачи необходимо предварительно найти все крайние точки Y_lk, что является очень трудной задачей. К счастью, это не так.

При решении главной задачи с использованием модифицированного симплекс-метода (раздел 7.2) на каждой итерации нам необходимо определить вводимую и исключаемую переменные. Начнем с определения вводимой переменной. Зная текущий базис главной задачи (и, следовательно, матрицы С_в и В"¹), для любой не­базисной переменной p_yt. имеем

z.

где

■^-СвВ"Р^-Сд,

j ^Х1к

О

Напомним: чтобы определить, какая из небазисных переменных Р_ук должна войти в базис, следует найти

z,..,.-c_rt. = min {z_jk-c_jt\.

по всем] и к

Если z._к. -с_гк. <0, тогда в соответствии с условием оптимальности задачи мак­симизации переменная р _t, должна войти в базис. При выполнении обратного нера-

с_;,₄.. "Секрет" вычисле-

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

ний заключается в равенстве

mi" -^cj_t) = min{min{z_;< -с,}} ■

>bccm;hA^{j 1}; L * ^L ' ¹ i

Это равенство вытекает из того, что каждое выпуклое множество, определяемое огра­ничениями DX_y = Ь_у, Х_у > 0, имеет собственное независимое множество крайних точек. В соответствии с этим равенством мы можем найти разность z.j,_k. - c_J4. за два этапа.

1. Для каждого выпуклого множества {XjD^X^b^, Х_у>0} определяем край­нюю точку Y._t„ на которой достигается минимум разностей z_jk - c_jk, т.е. z_jk, -<:^ = mm_k{z_ik-c_jk}.

2. Далее определяем z_t._k,-с_гк. = min^,, - с_)к.}.

Из теории линейного программирования мы знаем, что конечное оптимальное решение ассоциируется с крайней точкой пространства решений. Поскольку ка­ждое из множеств {X. | D_yX. = b_jt X. > 0} ограничено по определению, действия, выполняемые в п. 1, математически эквивалентны решению л задач линейного программирования вида

минимизировать ш. = {г_; - с, | D.X. = Ь., Х_у > 0}.

Фактически здесь целевая функция ш_у является линейной функцией от Х_у (см. уп­ражнение 7.4.1.8).

Таким образом, определение вводимой переменной p_fk, в главной задаче сведено к решению л задач линейного программирования (меньшего размера) для вычис­

7.4. Метод декомпозиции

ления "вводимых" крайних точек Y_y,_t„. Такой подход не требует определения всех крайних точек всех п выпуклых множеств. После того как требуемая крайняя точ­ка определена, нетрудно определить все элементы вектора Р. На основе этой ин­формации мы можем определить исключаемую переменную. Далее с помощью мо­дифицированного симплекс-метода вычисляем следующую обратную матрицу В"¹.

Пример 7.4.1

Решим с помощью метода декомпозиции следующую задачу ЛП.

Максимизировать z = 3x_t + 5х₂ + х₃ + х₄

при ограничениях

я, + х₂ + х₃ + х₄ < 40, Ъх, + х₂<\2, х₃ + х₄> 5, х₃ + 5х₄ < 50, х₂, х₃, х₄ — 0.

Данную задачу можно разбить на две подзадачи, которым будут соответствовать следующие множества переменных:

X, = (x_v х₂), Х₂ = (х₃, х₄).

Основную задачу можно записать следующим образом.

Подзадача 1	Подзадача 2	Начальное базисное решение
Р" Р«- Р„,	Р21 Рг2 - Р2А:,	Х5 Хв х7
C,Yn C,Y12 C,YlK,	C2Y21 C2Y22... C,Y,,	0 -М -М
AiY,, A,Y12... A,Y,X] 1 1... 1 0 0... 0	AoY21 AoY22... A2Y2JCi 0 0... 0 1 1... 1	1 0 0 =40 0 1 0 =1 0 0 1 =1
С, = (3, 5), A, = (1, 1). Пространство решений D1X1 < Ьь 5xi +х2 < 12, xi, х2 >0.	С2 = (1, 1), Аа = (1, 1). Пространство решений 02Хг < Ь2: Хз + Х4 > 5, хз + 5х* < 50, Хз, Х4 > 0.

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

л;, + х₂ + х₃ + х₄ + х_ь = 40.

Эта переменная не входит ни в одну подзадачу, ее значение находится как часть решения главной задачи. Другие переменные в начальном базисе, х_е и х₇, являются искусственными переменными.

Глава 7. Теория линейного программирования

Итерация 0

Х„ = (*₅, х_е, х₇)^т = (40, 1, if, С_в = (0, -М, -М), В = В ¹ = I.

Итерация 1

Подзадача 1 (j = 1). Имеем

z,-c,=C_eB­1

0.1)

-с,х,=

= {о,-м,-м)

-(3.5)

= -Зх, - 5х, - М.

Таким образом, соответствующая задача ЛП имеет следующий вид.

Минимизировать ш, - -Здс, - 5х_г - М

при ограничениях

5х₁ + х₂< 12, Яр х₂>0.

Решив эту задачу (обычным симплекс-методом), получаем

y_u = (o, i2f, _z;-c; = w;=-6o-m.

Подзадача 2 (j — 2). Соответствующая задача ЛП имеет следующий вид.

Минимизировать г, -с, =С₆В

= (0,-Af,-Af)

(U)

С,Х, =

-(1.1)

= ~^хъ ~х_А-М.

при ограничениях

х₃ + х₄> 5, х₃ + 5х₄ < 50 *₄^0.

Находим оптимальное решение этой задачи.

y₂₁ = (50,0f, _z;-c;=-50-Af.

Поскольку главная задача — задача максимизации и z* - с' < z* - с], а также г,*-с*<0, следовательно, переменная Р_п, соответствующая крайней точке Y,,, должна быть введена в базисное решение.

7.4. Метод декомпозиции

Для определения исключаемой переменной запишем

^f (о"

Р„ =

A,Y„ 1 О

'12} 1

Отсюда В"'Р_П = (12, 1, 0)^т. Имея Х_в = (х₆, х₆, х₇)^т = (40, 1, 1)^г, делаем вывод, что из ба­зисного решения следует исключить переменную х_е (искусственную переменную).

Новый базис получается путем удаления из базиса вектора, соответствующего пе­ременной х₉, и введения в базис вектора Р„. Получим (проверьте!)

⁽\ 12 0\

В =

1 О О 1

-12 0} 1 о

0 1

и новое базисное решение

Х_в = (х„ р_п, х₇)^т = В'(40, 1, 1)^г = (28, 1, 1)^т, С_в = (0, C.Y,,, -М) = (0, 60, -М).

Итерация 2

Подзадача 1 (j = 1). Вы должны проверить, что соответствующая задача ЛП оста­нется такой же, как и на первой итерации (это простое совпадение, а не общее пра­вило). Ее оптимальное решение дает г,* -с\ = w_t = 0. Отсюда следует, что никакая из

оставшихся крайних точек пространства решений подзадачи 1 не может улучшить решение главной задачи. (Оптимальным решением этой подзадачи будет крайняя точка Y,,, которой соответствует переменная Р_п, уже входящая в состав базиса. Именно поэтому z' -с[ = 0.)

Подзадача 2 (j = 2). Снова вы должны проверить, что соответствующая задача ЛП такая же (опять совпадение), как и на первой итерации. Ее оптимальное решение

Y₂₂ = (50, Of, _z;-c;=-50-Af.

Отметим, что точка Y₂₂ фактически совпадает с крайней точкой Y₂₁, но мы исполь­зуем нижний индекс 2, чтобы показать, что эта точка соответствует второй итера­ции.

Из решений обеих подзадач следует, что zj - с\ < 0. Это указывает на то, что пере­менная р₂₂, соответствующая крайней точке Y₂₂, должна войти в базисное решение. Для определения исключаемой переменной запишем

р,, =

о 1

(1,1)

о

о

,1

Глава 7. Теория линейного программирования

Отсюда В"'Р₂₂ = (50, 0, if. Поскольку Х_в = (х₅, р_п, х₇)^т — (28, 1, if, из базисного решения следует исключить переменную х₅.

Находим новый базис и новую обратную матрицу В"¹ (проверьте!)

	'50		0"
в =
	ч 1		1,
	Г 1	_п
в' =
	V 50

Новое базисное решение равно

Х_в = (р₂₂, р_п, х₇)^т = В"^,(40, 1, If = (14/25, 1, 11/25)', С_в = (C₂Y₂₂, C,Y_U, -М) - (50, 60, -М).

Итерация 3

Подзадача 1 (j = 1). Вы должны проверить, что на этой итерации целевая функция для данной подзадачи имеет следующий вид.

(М А (М Л \2М _ло

Минимизировать w=\--2 \х, + \--4\х,---1-48.

' 150 J 1.50 J " 50

Соответствующее оптимальное решение дает

Y₁₃ = (o,of, z;-_c; =

12 М 50

•48.

Подзадача 2 (j = 2). Здесь целевая функция имеет следующий вид (проверьте!).

М

Минимизировать w₁=—(x_i+x_i)-M.

Находим оптимальное решение:

Y₂₃ = (5,0f, ^.-с\=~

Небазисная переменная х_ь. Исходя из вида главной задачи, разность z_; - c_j для пе­ременной л:_й необходимо вычислять отдельно.

₌ f₁₊^.48-^-,-MV,0,0f-0=l ₊ ^. I 50 50 Г 50

Отсюда вытекает, что переменная х_ь не может улучшить решение.

Из приведенных вычислений следует, что вводимой в базис будет переменная Р₂₃, соответствующая крайней точке Y₂₃. Для определения исключаемой переменной вычисляем следующее.

Рз =

0 1 (1,1)

5 0

7.4. Метод декомпозиции

Отсюда В"'Р₂₃ = (1/10, 0, 9/10). Поскольку Х_в = (р₂₂, р„, = (14/25, 1, 11/25)⁷", из базисного решения следует исключить искусственную переменную х₇.

Находим новый базис и новую обратную матрицу В"¹ (проверьте!).

В =

г			5Ч
V			К
/
V

Новое базисное решение равно

Х_в = (Р₂₂, Р„, Р₂/ = В'(40, 1, If = (23/45, 1, 22/45f, С_в = (C₂Y₂₂, C.Y,,, C₂Y₂₃) = (50, 60, 5).

Итерация 4

Подзадача 1 (j = 1). w₁ = -2х_г - 4х₂ + 48. Получаем z* -с[ = w_t = 0. Подзадача 2 (j = 2). w₂ = 0x₄ + 0х₅ + 48 = 48.

Небазисная переменная х_ь. г₅ - с₅ = 1. Отсюда следует, что решение, полученное на третьей итерации, оптимально.

С помощью обратной подстановки вычисляем оптимальное решение исходной задачи, х; = (*„ */ = p_uY_u = 1(0, 12f = (0, 12f, X, = (х₃, х₄) = P₂₂Y₂₂ + p₂₃Y₂₃ =

= — (50. Of +—(5, Of = (28, 0)^T. 45 45

Все остальные переменные равны нулю. Оптимальное значение целевой функции получим путем прямой подстановки в ее выражение значений соответствующих переменных.

УПРАЖНЕНИЯ 7.4.1

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

а)

х, + 2х₂ < 6, 2х_х + х_г < 8, -х, +х₂< 1, *₂<2, x_v х₂>0.

Глава 7. Теория линейного программирования

Ь)

2*! + х₂ < 2, Зх, + 4х₂> 12, ХрХ₂>0.

с)

х,-х₂<10,

2x^40,

ХрХ₂>0.

2. В примере 7.4.1 крайние точки подпространств {X, | = b„ Х,>0) и {Х₂1 D₂X₂ = b₂, Х₂ > 0} можно найти графически. Используйте эту информа­цию, чтобы сформулировать в явном виде главную задачу. Затем покажите, что применение к главной задаче модифицированного симплекс-метода по­рождает такую же последовательность вводимых в базис переменных pV_s, как и последовательное решение отдельных подзадач 1 и 2.

3. Дана следующая задача линейного программирования.

Максимизировать z = х, + Зх₂ + 5х₃ + 2х₄

при ограничениях

2^ + х₂ < 9,

х, + 4х₂ < 8,

5Х; + Зх₂ + 4х₃ > 10,

х₃ - 5х₄ < 4,

х₃ + х₄<10,

"^1* ^x2^{j X}Z^{7 X}i — ^"

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

4. Решите задачу из предыдущего упражнения методом декомпозиции и срав­ните процесс решения при использовании разных алгоритмов.

5. Примените метод декомпозиции к следующей задаче.

Максимизировать z = 6х, + 7х₂ + Зх₃ + 5х₄ + х₅ + х₆ при ограничениях

Xj + х₂ + х₃ + х₄ + х₅ + х₆ < 50,

Xj + х₂< 10,

х₂<8,

5х₃ + х₄<12,

х₅ + х₆>5,

х₅ + 5х₆ < 50,

Хр х₂, х₃, х₄, х₅, х₆ > 0.

6. Продумайте необходимые изменения в применении метода декомпозиции к задаче минимизации, затем решите следующую задачу.

Минимизировать z = 5Xj + Зх₂ + 8х₃ - 5х₄

7.5. Двойственность

при ограничениях

х, + х₂ + х₃ + х₄ > 25, ох, + х₂ < 20, 5л:, - х₂> 5, х₃ + х₄ = 20, Л-J, л:₂, л:₃, л:₄ ^ 0.

7. Решите следующую задачу методом декомпозиции.

Минимизировать z = 10y_i + 2у₂ + 4у₃ + 8(/₄ + у_ъ при ограничениях

Ух + 4(/₂ - у₃ > 8, 2у, + jy₂ + i/_a > 2, Зу, + г/₄ + i/₅ > 4, ^ + 2у₄-(/₆>Ю,

<Л.</₂> #3> У4>У^⁰-

(Совет. Рассмотрите сначала задачу, двойственную к данной.)

8. Пусть при применении метода декомпозиции количество общих ограничений в исходной задаче равно г. Покажите, что целевую функцию для подзадачи j можно записать следующим образом.

Минимизировать w_j = z_l-c_J = (C_sRA_y - С_;)Х_; + С^У^

Здесь матрица R состоит из первых г столбцов матрицы В"¹, а V — ее (г + у')-й столбец.

7.5. ДВОЙСТВЕННОСТЬ

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

7.5.1. Матричное представление двойственной задачи

Пусть прямая задача ЛП с т ограничениями и п переменными уже записана в стандартной форме.

Максимизировать z = СХ

при ограничениях

АХ = Ь, Х>0.

Обозначим через Y = (y_v у₂, у_т) вектор переменных двойственной задачи. В соответствии с правилами, представленными в табл. 4.2, получаем следующую двойственную задачу.

Минимизировать w = Yb

Глава 7. Теория линейного программирования

при ограничениях

YA>C,

Y — вектор свободных переменных (т.е. не имеющих ограничений в знаке). УПРАЖНЕНИЯ 7.5.1

1. Докажите, что задача, двойственная к двойственной задаче, совпадает с ис­ходной (прямой) задачей.

2. Пусть прямая задача имеет вид: минимизировать z = {СХ | АХ > b, X > 0}. Сформулируйте соответствующую двойственную задачу.

7.5.2. Оптимальное решение двойственной задачи

В этом разделе устанавливаются соотношения между прямой и двойственной задачами и показывается, как определить оптимальное решение двойственной за­дачи на основе оптимального решения прямой задачи. Обозначим через В опти­мальный базис прямой задачи, через С_в — вектор коэффициентов целевой функ­ции, соответствующих оптимальным базисным переменным Х_в.

Теорема 7.5.1. Первая теорема двойственности. Для любой пары допустимых ре­шений (X, Y) прямой и двойственной задач значение целевой функции в задаче ми­нимизации ограничивает сверху значение целевой функции в задаче максимизации. Для пары оптимальных решений (X*, Y) значения целевых функций совпадают.

Доказательство. Пара допустимых решений (X, Y) удовлетворяет всем огра­ничениям обеих задач. Умножая слева обе части ограничений задачи максимиза­ции на вектор (свободных) переменных Y, получим

YAX = Yb = ш.

Аналогично, умножая справа ограничения задачи минимизации на вектор (неотрицательных) переменных X, будем иметь

YAX>CX = 2.

(Неотрицательность вектора X здесь существенна, так как определяет "направленность" неравенства.) Комбинируя последние два выражения, получаем неравенство z<w, доказанное для пары любых допустимых решений (X, Y).

Отметим, что теорема не указывает, какая задача прямая, а какая — двойст­венная. Это очень важно при нахождении оптимальных решений обеих задач.

Из доказанной части теоремы (z < w для пары любых допустимых решений) следу­ет, что максимум функции z и минимум функции w будут достигнуты только тогда, когда обе эти функции примут одинаковое значение. Исходя из этого, можно постро­ить оценку близости полученных допустимых решений к оптимальным путем срав­нения разности 2 - w и величины (2 + и>)/2. Чем меньше отношение 2(2 - w)/(z + w), тем ближе данные решения к оптимальным. Но, конечно, из этого эмпирического правила не следует, что оптимальные значения целевых функций равны (2 + w)/2.