Тогда проверка заключается в проверке истинности неравенства

Введение нового ограничения в ЗЛП в общем случае может привести к деформации (уменьшению) области ее допустимых решений. Эта деформация будет существенной лишь тогда, когда она приводит к отсечению оптимального решения. Например, так как показано на рио.3.6.

ЗЛП к введению нового ограничения.

Анализ чувствительности оптимального решения

Для поиска нового решения скорректированной ЗЛП, начиная с сопряженного базиса, необходимо применить алгоритм двойственного симплекс-метода. В результате его работы либо будет найдено новое оптимальное решение, либо установлено, что сделанная вариация привела к пустоте допустимого множества ЗЛП.

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

Старое оптимальное решение

Grad Z

X[2]

Новое ограничение

Определение нового оптимального решения, если новое ограничение не приво­дит к пустоте допустимого множества, находится графическим способом, как и первоначальное.

Рис. 3.6 Геометрическая интерпретация введения нового ограничения

X[1]

Новое оптимальное решение

Формальный анализ чувствительности оптимального решения к введению нового ограничения может быть проведен следующим образом. Проверка того, отсекает или нет новое ограничение найденное оптимальное решение от допус­тимой области, делается подстановкой оптимального базисного решения в новое ограничение. Будем предполагать, что вводится новое ограничение в виде неравенства вида:

(3.14)

где - число переменных исходной ЗЛП.

(3.15)

Если неравенство 3.15 не выполняется, то необходимо осуществить поиск нового оптимального решения или убедиться в пустоте допустимого множества задачи с учетом вновь введенного ограничения. Это может быть сделано путем введения нового ограничения в заключительную симплекс-таблицу и осуществления поиска нового решения задачи, начиная с этой скорректированной симплекс-таблицы. Обоснование такой возможности сос­тоит в том, что коэффициенты действительной части симплекс-таблиц и представляют собой многократно преобразованные по Гауссу-Жордану коэффициенты исходных ограничений. Для симплекс-таблицы , в этом просто убедиться на основе анализа следующих соотношений:

(3.16)

, (3.17)

где

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

(3.18)

Рис. 3.7 Соответствие с-т и преобразованных ограничений

Из 3.18 видно, что в левой части преобразованного ограничения при базисной переменной, соответствующей данной строке, коэффициент равен единице, при остальных же базисных переменных коэффициенты равны нулю, т.е. все базисные переменные из нового ограничения должны быть выведены. К такому же виду должно быть преобразовано и новое ограничение. Алгоритм преобразования будет следующим:

I. Привести ограничение 3.14 к каноническому виду:

(3.19)

где - количество переменных в канонической форме исходной ЗЛП;

- новая базисная переменная.

2. Исключить из ограничения (3.19) все переменные, являющиеся базисными в оптимальном решении ЗЛП, полученном без ограничения (3.14). Выполнение 2-го пункта алгоритма может быть очень просто осуществлено с помощью той же заключительной симплекс-таблицы. Чтобы, например, исключить переменную из ограничения 3.19 нужно вычесть из него ограничение 3.18, умноженное на . Ра­бочий алгоритм расширения заключительной симплекс-таблицы будет следующим:

1. Расширить базисное множество, поставив на последнее место номер (n+1).

Дата добавления: 2014-12-27