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

Если в одной из задач целевая функция примет бесконечное значение, что мож­но сказать о решении другой? Ответ очевиден: другая задача не должна иметь до­пустимых решений. Если это не так (т.е. обе задачи имеют допустимые решения), неравенство z < w обязательно должно выполняться, что невозможно, например,

При 2 = +оо или w = -оо.

Рассмотрим обратную ситуацию. Если одна из задач не имеет допустимых решений, то обязательно ли решение другой задачи будет неограниченным? Не

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

обязательно! В следующем примере и прямая, и двойственная задачи не имеют до­пустимых решений.

Прямая задача. Максимизировать z = {х₁ + х₂ | х₁ - х₂ <-1, ~х₁ + х₂ <-1, х„ х₂>0}.

Двойственная задача. Минимизировать w = {-y_t - у₂ \ у, - у₂> 1, -у, + у₂ > 1,

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

Y = C_SB\

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

Доказательство. Для доказательства этой теоремы надо показать, что допус­тимое решение двойственной задачи можно вычислить по формуле Y = С_ВВ, и что в соответствии с теоремой 7.5.1 z = w для оптимальных решений.

Решение прямой задачи будет оптимальным, если выполняются неравенства г_у - с_у> О для всехj (см. раздел 7.2.1), т.е.

С_ВВ 'А - С > 0.

Но решение Y допустимо, если оно удовлетворяет ограничению YA > С. Это доказы­вает равенство Y = С_ВВ^-1 для допустимого решения двойственной задачи Y.

Равенство оптимальных значений z и w доказывается непосредственным срав­нением выражений

w = Yb = C_BB 'Ь,

Переменные двойственной задачи Y= С_ВВ^-1 иногда называют симплексными мультипликаторами. Они также известны как двойственные цены — название, идущее от экономической интерпретации этих переменных (см. раздел 4.3.1).

Обозначим через Р_у у'-й столбец матрицы А. Из теоремы 7.5.2 следует, что величины

z_rc_rC_BK^lP_rc_rYP_j-c_i

равны разностям между левыми и правыми частями ограничений двойственной задачи. В начале решения прямой задачи максимизации по крайней мере для од­ного j выполняется неравенство z_t - с. < 0; это означает, что соответствующее ог­раничение YP. >с не удовлетворяется. Если достигнуто оптимальное решение прямой задачи, тогда выполняются неравенства z. - с\ > 0 для всех /; в этом случае соответствующее решение двойственной задачи Y= С_ВВ~' допустимо. Таким обра­зом, если решение прямой задачи оптимально, то решение двойственной задачи автоматически допустимо. На этом соотношении построен двойственный сим­плекс-метод (раздел 4.4), в котором вычисления начинаются с недопустимого решения, "лучшего", чем оптимальное. Выполнение метода продолжается до тех пор, пока не будет достигнуто допустимое решение. В противоположность этому в "обычном" симплекс-методе (глава 3) вычисления начинаются с допустимого, но "худшего", чем оптимальное, решения и продолжаются до тех пор, пока не будет достигнуто оптимальное решение.

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

Пример 7.5.1

В следующей задаче ЛП оптимальный базис равен В = (Р,, Р₄). Сформулируем двойственную задачу и найдем ее оптимальное решение, используя оптимальный базис прямой задачи.

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

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

х, + 2х₂ + х₃ = 5, -х, + Зх_г + x_t = 2,

^Х\1 ^Х2> ^3' ^Х4 — ^*

Двойственная задача имеет следующий вид.

Минимизировать w = Ъу, + 2у_г

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

У\~Уг - ³> 2у, + Зу₂>Ъ,

«/,.«/, по­имеем В = (х,, x₄)^r, тогда С_в = (3, 0). Оптимальный базис и его обратная матрица равны следующему.

ч: >Н%

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

(x₁,x/ = B-¹b = (5, 7f,

((_/l,y₂) = C_BB^,=(3,0).

Оба решения допустимы и 2 = w = 15 (проверьте!). Таким образом, решения оп­тимальны.

УПРАЖНЕНИЯ 7.5.2

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

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

Максимизировать z = 50х, + 30х₂ + 10х₃ при ограничениях

2х₁ + х_г ' 1, 2х_г - -5, 4x, + x₃ = 6, х„ х_г, х₃>0.

a) Сформулируйте и запишите двойственную задачу.

b) Покажите с помощью непосредственной проверки, что прямая задача не имеет допустимого решения.

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

c) Покажите, что двойственная задача не имеет ограниченного решения.

d) На основе примеров задач из предыдущих упражнений найдите соотно­шение между свойствами недопустимости и неограниченности прямой и двойственной задач ЛП.

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

Максимизировать z = Ьх_х + 12х₂ + 4х₃

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

2х, - х₂ + Зх₃ = 2, х_х + 2х₂ + х₃ + х_л = 5, Ху₇ x_2t х₃, х_А — 0.

a) Сформулируйте и запишите двойственную задачу.

b) В каждом из следующих случаев сначала проверьте, что приведенный ба­зис В является допустимым для прямой задачи. Затем, используя форму­лу Y = C_SB \ вычислите значения переменных двойственной задачи. Кро­ме того, определите, является ли данное решение прямой задачи оптимальным.

а) В = (Р₄,Р₃). в)В-(Р„Р,).

б) В = (Р₂,Р₃). г) В = (Р,, Р₄).

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

Максимизировать z = 2х_х + 4х₂ + 4х₃ - 3x_t при ограничениях

х, + 4х₂ + x_t = 8, x_v х₂, х₃, х₄>0.

a) Сформулируйте и запишите двойственную задачу.

b) Путем вычисления разностей г. - с_у для всех небазисных Р_у проверьте, что базис В = (Р₂, Р₃) соответствует оптимальному решению.

c) Найдите оптимальное решение двойственной задачи.

5. Модель ЛП содержит две переменные х_г и х₂ и три ограничения типа "<". Со­ответствующие дополнительные (остаточные) переменные обозначены как х₃, х_А и х_у Предположим, что B = (Pj, Р₂, Р₃)— оптимальный базис, а соот­ветствующая обратная матрица имеет следующий вид.

,'0 -1 О В⁴ = 0 1 о

,1 1 -.

Ниже представлены оптимальные решения прямой и двойственной задач.

Х_я*,)^г = (2,6, 2)^т, Y = (y₁,(/₂,(/₃) = (0, 3, 2). Найдите оптимальное значение целевой функции.

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

6. Докажите следующее соотношение между оптимальными решениями пря­мой и двойственной задач:

£',(B-'P,).=j>A,.

где С_в = (с„ с₂,.... cj иР, = (о₁₄, a_2t, a_m/ для = 1, 2, л, (В'РД — /-Й элемент вектора В 'Р_к.

7. Запишите задачу, двойственную к следующей.

Максимизировать z = {СХ | АХ = b, X — свободные переменные}

8. Покажите, что задача, двойственная к задаче

максимизировать z = {СХ | АХ < b, 0<L<X<U< <*>}, всегда имеет допустимое решение.

7.6. ПАРАМЕТРИЧЕСКОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Параметрическое линейное программирование — это расширение техники анализа чувствительности, которую мы рассмотрели в разделе 4.5. Здесь исследу­ются изменения в оптимальном решении задачи ЛП, являющиеся результатом предопределенных непрерывных изменений коэффициентов целевой функции и значений правых частей ограничений.

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

Максимизировать z = jcx|£V_jx_l= b, X>oj.

В параметрическом программировании задаются изменения коэффициентов це­левой функции и правых частей ограничений. Для этого используются функции С(£) и Ь(£), зависящие от параметра изменения t. Для определенности полагаем, что t > 0.

Основная идея параметрического анализа заключается в следующем. Вначале находится оптимальное решение задачи ЛП при t = 0. Затем на основании условий оптимальности и допустимости симплекс-метода определяется интервал 0 < t < t, значений параметра t, для которых решение, полученное при t = 0, остается опти­мальным и допустимым. Значение t, называется критическим. Затем определяют­ся следующие критические значения параметра t и соответствующие им оптималь­ные допустимые решения. Процесс заканчивается, когда будет найдено такое значение t_r, что при любых значениях t > t_r последнее решение остается неизмен­ным либо решения не существует.

7.6.1. Параметрическое изменение коэффициентов целевой функции

Пусть Х„, В, и С„ (0 — элементы оптимального решения, соответствующего

критическому значению t_t (вычисления начались при t₀ = 0 с оптимальным бази­сом В₀). Далее определяем следующее критическое значение и соответствую­щий ему оптимальный базис, если он существует. Поскольку изменения в векто­ре коэффициентов целевой функции влияют только на оптимальность решения, текущее решение Х_я = B~'b останется оптимальным при t > t_t до тех пор, пока бу­дет выполняться условие оптимальности

z.(f) - с jit) = С„ (ОВГ'Р, - c_y(t) > 0 для всех

7.6. Параметрическое линейное программирование

Очередное критическое значение t_M определяется как наибольшее t, t > t_t, при ко­тором выполняются все условия оптимальности.

Отметим, что приведенное неравенство не требует, чтобы вектор С(0 был линей­ной функцией от t; допустима функциональная зависимость любого вида — как ли­нейная, так и нелинейная. Трудность использования нелинейных функций заключа­ется лишь в том, что численное решение системы неравенств может быть очень трудоемким. (В упражнении 7.6.1.5 рассмотрен случай нелинейной функции.)

Пример 7.6.1

Рассмотрим задачу ЛП.

Максимизировать г = (3 - 60 х, + (2 - 2t) х₂ + (5 + 50 х. при ограничениях

х, + 2х₂ + х₃< 40, Зх, + 2х₃ < 60, х₁ + 4х₂ < 30,

Здесь С(0 = (3 - 6t, 2 - 2t, 5 + 5t), t > 0. Введем дополнительные (остаточные) пере­менные х₄, х₅ и х₆.

Оптимальное решение при t₀ = 0.

Базис	Xl	х2	Хз	Х4	Хь	х6	Решение
z
хг	-1/4			1/2	-1/4
Хз	3/2				1/2
*6				-2

Х_йо - (х₂, х₃, х/ = (5, 30, 10f С_Во(/) =(2-2t, 5 + 5t, 0),

в-' = о

-2

1 1

Условия оптимальности для текущих небазисных векторов Р,, Р₄ и Р₅ имеют вид {<:„(/)В-'Р_у - с//)}._{=| о} = (4 + Ш, 1 - t, 2 + 3t) > 0.

Таким образом, решение остается оптимальным до тех пор, пока выполняются неравенства

4 + 14t>0,

1 -t>0,

2 + 3t> 0.

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

Первое и третье неравенства выполняются при всех положительных t (напомним, что t > 0), второе — справедливо при t < 1. Отсюда имеем, что £, = 1, т.е. решение остается оптимальным (и допустимым) для всех t из интервала 0 < t < 1.

При t = 1 разность z₄(f) - c_t(t) = 1 -1 равна нулю и становится отрицательной при t > 1. Поэтому при f > 1 вектор Р₄ должен войти в базис, тогда вектор Р₂ будет исклю­чен из базиса (см. симплекс-таблицу с оптимальным решением при t = 0). Итак, при t = 1 (вследствие включения в базис вектора Р₄) получаем новое решение Х^.

Оптимальное решение при f, = 1. Имеем новый базис и новую обратную матрицу.

	'1		о4		'\.1 о4
				. ВГ =	о; о
	,0		К		0 0 1,

Отсюда получаем

Х^ = (x_t, х₃, х_в)^т = В-'Ь = (10, 30, 30)^т, С_я(0 =(0, 5 + 5i, 0).

Для небазисных векторов Р_1; Р₂ и Р₅ условия оптимальности можно записать сле­дующим образом.

_{C,(0Br-P,-c_iW}^=(^.-2 ₊ 2,.^)₂0

В соответствии с этими условиями базисное решение Х_в остается оптимальным для

всех t > 1. Это означает, что t₂ = °° и вычислительный процесс параметрического ана­лиза закончен. Отметим, что условие оптимальности -2 + 2t > 0 автоматически "запомнило", что решение Х^ оптимально в интервале, который начинается со зна­чения £, = 1. Такое "запоминание" всегда имеет место при параметрическом анализе.

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

г	X1	Хг	Хз	z
0< f< 1				160 + 140г
t> 1				150 + 150f

УПРАЖНЕНИЯ 7.6.1

1. Пусть в примере 7.6.1 параметр t может принимать как положительные, так и отрицательные значения. Определите интервал изменения значений пара­метра t, при которых решение Х_% остается оптимальным.

2. Проведите параметрический анализ задачи ЛП из примера 7.6.1, если целе­вая функция задана следующими выражениями.

a) Максимизировать z = (3 + 3i) x_t + 2дг₂ + (5 - 6t) х₃.

b) Максимизировать z = (3 - 2t) дг, + (2 +1) x₂ + (5 + 2t) x₃.

c) Максимизировать z = (3 +1) x, + (2 + 2t) x₂ + (5 - t) x₃.

7.6. Параметрическое линейное программирование

3. Проведите параметрический анализ оптимального решения следующей зада­чи ЛП, здесь t > 0.

Минимизировать z = (4 - t) x_l + (1 - 3t) x₂ + (2 - 2t) x₃ при ограничениях

3jc, +jc₂ + 2jc₃ = 3, 4x_t + Зх, + 2x₃ > 6, x, + 2x₂ + bx₃ < 4,

X j j X — 0 •

4. При выполнении параметрического анализа в этом разделе предполагалось, что оптимальное решение задачи ЛП при t = 0 получено обычным симплекс-методом. Однако в некоторых ситуациях предпочтительнее получить опти­мальное решение двойственным симплекс-методом (раздел 4.4). Разработай­те схему проведения параметрического анализа для такого случая и выпол­ните анализ задачи ЛП из примера 4.4.1, предполагая, что целевая функция задана следующим выражением.

Минимизировать z = (3 + t) х, + (2 + 4t) x₂

5. Пусть в примере 7.6.1 целевая функция нелинейная по t (t > 0) и задается следующим выражением.

Максимизировать z = (3 + 2t²) х, + (2 - 2t²) x₂ + (5 - t) x₃.

Найдите первое критическое значение t_v

7.6.2. Параметрическое изменение правых частей ограничений

Параметрическое изменение вектора правых частей ограничений Ь(£) влияет только на свойство допустимости решения. В этом случае критические значения параметра t определяются на основе условия

Х„ = В'Ь(0>0.

Пример 7.6.2

Рассмотрим задачу ЛП.

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

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

х, + 2х₂ + x₃<40~t, Зх, + 2х₃ < 60 + 2t, х, + 4х₂ < 30 - It,

Предполагается, что t > 0.

Оптимальное решение этой задачи при t = 1₀ = 0 приведено в примере 7.6.1. Имеем

Х_В(] - (х₂, х₃, х/ = (5, 30, 10)^т,

■1 о

т ⁰

1 1.

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

Чтобы найти первое критическое значение используем условие допустимости Х_я = В„'Ь(/) > 0, которое в данном случае примет вид

V		' 5-t N
	=	30 + t	>
\хь)		,10-3/,		,0,

Эти неравенства выполняются при t < 10/3. Таким образом, t, = 10/3, и базис В₀ остает­ся допустимым при изменении параметра t в интервале 0 < t < 10/3. Отметим, что здесь значения базисных переменных х_г, х₃ и х_в изменяются при изменении параметра t.

Значение базисной переменной х₆ (= 10 - 3t) равно нулю при t = t, = 10/3 и стано­вится отрицательным для t > 10/3. Следовательно, при t = 10/3 необходимо опре­делить новый базис В,. Для этого применим модифицированный симплекс-метод (см. упражнение 7.2.2.5). Исключаемой из базиса будет переменная х₆.

Новый базис при t = 10/3.

Имея переменную х_е в качестве исключаемой из базиса, определяем вводимую в ба­зис. Поскольку

то

^х«„ = (^Х2> ^хз> *_в) ^{и с}я„ С) ⁼ (²> ⁵> °)>

к-^и,={^в₀-р_у-_сл^_14а-(4,1,2).

Далее вычисляем

{(В^'РД. }_;=М], = (строка в В"¹, ассоциированная с х₆) (Р„ Р₄, Р₅) =

= (3-я строка в В₀') (Р„ Р₄, Р₅) -= (-2, 1, 1)(Р„Р₄,Р₆) = = (2,-2, 1).

Отсюда следует, что

e = min< —

соответствует переменной x_t. Следовательно, в базис вводится вектор Р₄. Вычисляем новый базис и обратную матрицу В~'.

^ХВ_; (^2' ^3> ^Х4^ '

'2 1 \\

В,=(Р₂,Р₃,Р₄) =

0 2 0 4 0 0

'0 0

7.6. Параметрическое линейное программирование

Следующее критическое значение t₂ определяем из условия Х_в = В, 'b(r) >0. Отсюда получаем следующее.

	(30-7/ ^
ХУ =	30+/	>
\X4j	-10 + 3/		,0,

i 2;

Это условие показывает, что В, остается допустимым базисом для 10/3 < t < 30/7.

При t = t₂ = 30/7 новый базис можно получить с помощью модифицированного двойственного симплекс-метода, при этом исключаемой из базиса будет пере­менная х₂.

Новый базис при t₂ = 30/7.

Определив исключаемую переменную х₂, находим вводимую переменную следую­щим образом. Поскольку

Х_Я| = (х₂, х₃, х/ и С_Я| (/) = (2, 5, 0),

то

Далее вычисляем

{(В['Р.)_Д, }_>=156 = (строка в В;', ассоциированная с x₂) (Р,, Р₅, Р₆) = = (1-я строка в В^') (P_lf Р₅, Р₆) =

-(o.O.±)(P_lfP„ Р.)-

Поскольку все элементы неотрицательны, задача не имеет допустимых решений при £>30/7. Таким образом, параметрический анализ заканчивается в точке t = *₂ = 30/7.

Оптимальные решения при различных значениях параметра t приведены в сле­дующей таблице.

	xi хг	Хз	z
0 < f S 10/3	0 5-f	30 + f	160+ 3f
10/3 S f<30/7	0 (30 - 7()/4	30 + г	165 + (3/2)f
/>30/7	Допустимых решений нет

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

УПРАЖНЕНИЯ 7.6.2

1. Для задачи из примера 7.6.2 найдите первое критическое значение t, и опре­делите векторы, составляющие матрицу В,, для следующих случаев.

a) Ь(*) = (40 + 2t, 60 - 3t, 30 + 6tf.

b) b(0 = (40 - t, 60 + 2t, 30 - 5t)^T.

2. Проведите параметрический анализ оптимального решения следующей зада­чи ЛП, предполагая, что t > 0.

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

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

Зх, + х₂ + 2х_г = 3 + 3t, 4.x, + Зх, + 2х₃ > 6 + 2f, х, + 2х₂ + 5х₃ < 4 - *,

3. При выполнении параметрического анализа в этом разделе предполагалось, что оптимальное решение задачи ЛП при £ = 0 получено обычным симплекс-методом. Однако в некоторых ситуациях предпочтительнее получать опти­мальное решение двойственным симплекс-методом (раздел 4.4). Разработай­те схему проведения параметрического анализа для такого случая и выполните анализ задачи ЛП из примера 4.4.1, предполагая, что вектор правых частей ог­раничений задачи задан следующим выражением (считаем, что t > 0).

b(0 = (3 + 2f, 6-t, 3-4г)^т

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

Ь(0 = (3 + 3t\ 6 + 2t\ 4 - t²f

Затем решите эту же задачу при условии, что параметр t может принимать как положительные, так и отрицательные значения.

7.7. МЕТОД КАРМАРКАРА

В симплекс-методе оптимальное решение находится путем продвижения вдоль граней пространства решений от одной угловой (крайней) точки к другой. Хотя на практике симплекс-метод применяется для решения очень больших задач, теоре­тически количество итераций, необходимых для достижения оптимального реше­ния, может расти по экспоненциальному закону. Можно построить задачу ЛП с л переменными, при решении которой необходимо перебрать все 2" крайних точек, пока не будет достигнуто оптимальное решение.

В 1984 году Н. Кармаркар (N. Karmarkar) разработал алгоритм с полиномиальным временем выполнения, который "пробегает" по внутренним точкам пространства ре­шений. Этот алгоритм особенно эффективен при решении очень больших задач ЛП.

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

7.7. Метод Кармаркара

7.7.1. Основная идея метода Кармаркара

Рассмотрим очень простой пример.

Максимизировать г = х_х при выполнении ограничения

0<х_х<2.

Вводим дополнительную (остаточную) переменную х₂. Задача в стандартной форме будет записана следующим образом.

Максимизировать г = х₁

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

х^ ~\~ х^ 2) х_х, х₂ > 0.

Эта задача представлена на рис. 7.6. Ее пространство решений совпадает с от­резком прямой АВ. Направление возрастания целевой функции z совпадает с по­ложительным направлением оси х_х.

х₂

Рис. 7.6. Иллюстрация основной идеи метода Кармаркара

Начнем поиск оптимального решения с произвольной внутренней (не крайней) точки С пространства допустимых решений (отрезок АВ). Градиент целевой функ­ции г = х, в точке С показывает направление скорейшего возрастания функции г. Если мы зафиксируем какую-нибудь точку вдоль градиента и опустим из нее пер­пендикуляр на пространство допустимых решений, то получим новую точку D с лучшим значением целевой функции. Такое улучшение значения целевой функ­ции получено вследствие движения по направлению проекции CD градиента. Если мы повторим описанную процедуру для точки D, получим новую точку Е, которая будет еще ближе к точке оптимума В. Таким образом, если мы будем двигаться (но осторожно) в направлении проекции градиента, то, вероятно, рано или поздно

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

"споткнемся" о точку оптимума В. Если же необходимо найти минимум целевой функции (вместо ее максимума), следует перемещаться в направлении, противопо­ложном проекции градиента, т.е. от точки В к точкеА, где х_х = 0.

Конечно, данную процедуру нельзя считать алгоритмом (в обычном смысле), но идея очень интересная! Чтобы воплотить эту идею в алгоритм, необходимо выпол­нить модификации приведенной процедуры, гарантирующие, что, во-первых, по­следовательность шагов, сделанных вдоль проекции градиента, не "перескочит" через точку оптимума, во-вторых, в общем л-мерном случае направления, указан­ные проекциями градиентов, не приведут алгоритм к неоптимальной точке (т.е. не "зациклят" алгоритм на неоптимальной точке). Если реализовать эти условия, то получим вполне работоспособный алгоритм.

7.7.2. Алгоритм Кармаркара

Существует несколько вариантов алгоритма Кармаркара. Мы рассмотрим ис­ходный вариант, предложенный его автором. Кармаркар предполагал, что задача ЛП приведена к следующему виду.

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

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

АХ = 0, IX = 1, Х>0.

Здесь все ограничения представлены в виде однородных уравнений, за ис­ключением ограничения IX = Z"_,x_/ = 1, которое определяет «-мерный пра­вильный симплекс.⁴ Обоснованность алгоритма Кармаркара "покоится" на вы­полнении двух условий.

1. Вектор Х=|—,—.....—) удовлетворяет ограничениям АХ = О.

\п п п)

2. min z = 0.

Кармаркар предложил алгебраические преобразования, приводящие общую за­дачу ЛП к виду, представленному выше. Эти преобразования показаны в следую­щем примере. Там также показано, как в результате преобразований добиться того, чтобы вектор X = (1/п, 1/п, 1/п) являлся допустимым решением системы АХ = 0 (условие 1). Преобразования, необходимые для выполнения условия 2 (min г = 0), мы не приводим из-за их громоздкости и трудоемкости.

⁴ Симплексом (n-мерным) называется выпуклая оболочка п точек X,, Х₂, Х„, не лежащих на одной (п - 2)-мерной плоскости. Точки X,, Х₂, Х_п являются вершинами симплекса, при этом любую точку симплекса можно представить как выпуклую комби­нацию (см. раздел 7.1) его вершин. Двухмерный симплекс — это отрезок, трехмерный — треугольник, четырехмерный — тетраэдр. (Здесь размерность симплекса определяется по размерности пространства, а не по размерности (п - 1)-мерной гиперплоскости, на которой он расположен.) В данном случае вершинами симплекса являются точки X, = (0, 1,...,0), i= 1, л. Такой симплекс является частным случаем правильного симплекса. —Прим. ред.

7.7. Метод Кармаркара

Пример 7.7.1

Рассмотрим следующую задачу.

Максимизировать z = у,+ у₂

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

У, + 2у₂<2, */„*/₂>0.

С помощью дополнительной переменной у₃ > О преобразуем ограничение у, + 2у₂ < 2 в равенство:

i/, + 2i/₂ + z/₃ = 2.

Теперь введем неравенство

Ух + Уг + У г ^ U,

где U — достаточно большое положительное число, но такое, которое не удаляло бы ни одной допустимой точки исходного пространства решений. В данном приме­ре, исходя из равенства у, + 2у₂ + у₃ = 2, достаточно взять U, равное 5. После введе­ния еще одной дополнительной переменной у₄ получаем

У, +У₂ + У₃ ⁺ У4 = ⁵-