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


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

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.

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






Выпущен открытый сервер навыков 0Mind для упрощения разработки ИИ

Создатель Всемирной паутины выступил против Facebook и Google

В Китае построят суперкомпьютер, способный выполнять квинтиллион вычислений в секунду

Использование нейронной сети для восстановления повреждённых изображений

В Китае робот сдал тест для поступления в университет

Россия будет защищена от внешнего отключения Рунета к 2021 году

О конференции Strata AI: будущее искусственного интеллекта

Китайский самообучающийся процессор сможет имитировать работу нервных клеток человека

Илон Маск работает над интерфейсом для подключения мозга к компьютеру

Загадка QWERTY: почему буквы на клавиатуре расположены не в алфавитном порядке

Нейронную сеть научили практически идеально копировать человеческий голос





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