Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

4.9. Канонический вид задачи линейного программирования

Задачу

(4.22)

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

Эта задача представляет собой частный случай (когда I1=∅ и J2 = ∅) задачи со смешанными ограничениями (4.18), и, следовательно, все доказанные теоремы и утверждения остаются в силе и для канонической задачи.

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

для основной задачи

min <с, х>,
Ax≥b
x≥0

эквивалентной ей канонической задачей будет

min<c, x>
Ax-u=b
x≥0, u≥0

(эквивалентность здесь понимается так же, как и в задачах со смешанными ограничениями).

Если заметить, что двойственной к обеим задачам будет задача

max<b, y>
ATy≤c
y≥0

то есть задача (4.19), то доказательство эквивалентности становится тривиальным.

В дальнейшем относительно канонической задачи будем всегда предполагать m < n. Это предположение несколько упрощает изложение. С другой стороны, в реальных ситуациях всегда вводят дополнительные переменные - так называемый искусственный базис, - увеличивая тем самым число переменных задачи с n до n+m.

Для дальнейших рассмотрений понадобится ввести понятие невырожденной угловой точки множества R0.

Определение. Угловую точку множества R0 будем называть невырожденной, если матрица ее базиса имеет размерность m×m. Таким образом, у невырожденной угловой точки х число положительных компонент равно m. Если для простоты будем считать, что для угловой точки х положительными будут первые m компонент, то матрицей базиса этой невырожденной угловой точки будет


Если, как и прежде, мы запишем угловую точку х в следующем виде:


где


то


Пример. Пусть множество R0 задается в виде

x1+x2+x3=1
x1-x2=0
x1≥0, x2≥0, x3≥0

Таким образом, R0 есть отрезок, соединяющий точки


и


Обе они будут угловыми, но невырожденной из них является лишь первая, то есть x1.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"