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


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

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

Пусть найдены оптимальные угловые точки х* и y* задач (5.1) и (5.6) соответственно. Предположим, что к системе условий, определяющих допустимое множество R0, добавлено еще одно неравенство


Если


то х* будет оптимальным и для новой задачи, поскольку добавление условий может только увеличить величину минимума целевой функции. В случае


выясним, как, зная оптимальные угловые точки x* и y*, получить решение новой задачи.

Запишем новую задачу в каноническом виде, введя дополнительную переменную хn+1. Обозначим



em+1 - (m+1)-й единичный координатный вектор. Новая задача примет вид

(5.22)

Согласно правилам (4.18)-(4.19) двойственной к (5.22) будет задача

(5.23)

Так как точка y*- угловая для задачи (5.6), то


будет угловой точкой для задачи (5.23), поскольку из линейной независимости системы векторов a1, а2, ... ..., аm-базиса угловой точки y* - следует линейная независимость системы векторов


Теперь естественно, принимая y* за исходную угловую точку, решать задачу (5.22) двойственным симплексным методом. Как правило, для получения решения задачи (5.22) требуется небольшое число итераций.

Очевидно, что все, сказанное в этом пункте, остается в силе, если к неравенствам, определяющим множество R0, добавляется не одно, а несколько новых.

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





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


Диски от INNOBI.RU




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