Исследование чувствительности оптимального решения задачи линейного программирования к вариациям ее параметров и введению нового ограничения

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

"Исследование чувствительности оптимального решения задачи линейного программирования к вариациям ее параметров и введению нового ограничения"

по дисциплине "Теория оптимального планирования и управления"

1. Цель работы

Изучение теоретических вопросов анализа чувствительности оптимального решения ЗЛП к вариациям некоторых параметров задачи и введению нового ограничения. Получение навыков практического решения такого рода задач.

2. Основные теоретические сведения

Необходимость анализа чувствительности задачи математического программирования к вариациям ее параметров может возникнуть в следующих случаях:

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

данных, на основе которых формируются параметры ЗЛП;

при определения наилучшей вариации параметров, когда их выбор

находится в руках лица, принимающего на основе результатов оптимизации решение по реализации оптимальных значений переменных;

при внесении в задачу после получения ее решения изменений,

связанных с дополнительной информацией.

При проведении такого анализа может возникнуть потребность в ответе на следующие вопросы:

в каких пределах можно варьировать параметры задачи, чтобы

прежнее оптимальное решение оставалось неизменным;

остается ли прежнее решение допустимым, оптимальным при осуществлении определенных изменений параметров исходной задачи;

если прежнее решение задачи стало недопустимым или неоптимальным,

то каково будет новое решение задачи.

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

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

вариациям коэффициентов целевой функции.

Вариации коэффициентов целевой функции ЗЛП приводят к изменению направления вектора градиента. Так как при этом не затрагивается допустимое множество, то прежнее решение остается допустимым базисным, а оптимальное решение может измениться.

3.1 Графический способ анализа чувствительности оптимального решения к вариациям C[j

Результаты графического анализа чувствительности оптимального решения ЗЛП к вариациям коэффициентов целевой функции. Оптимальное решение достигается в крайней точке под номером 4. Определены предельные положительные и отрицательные вариации коэффициентов целевой функции , которые находятся из условия возможности изменения направления Z внутри конуса, определяемого векторами-градиентами активных ограничений 2 и 3.

При положительной вариации больше предельной оптимальное решение переместится в крайнюю точку(КТ) 3, а при отрицательной - в КТ 5. Отрицательная вариация больше предельной () приведет к перемещению оптимального решения либо в КТ 3, либо в КТ 2.

Формальный анализ чувствительности оптимального решения к вариациям коэффициентов целевой функции может быть произведен с использованием заключительной симплекс-таблицы . Структура симплекс-таблицы для ручного счета имеет следующий вид:

Рис. 3.2 Структура симплекс-таблицы

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

Формула расчета симплекс-разности для каждого j-го столбца симплекс-таблицы имеет следующий вид:

(3.1)

где -коэффициенты целевой функции при базисных переменных;

-коэффициенты матрицы , являющейся составной частью симплекс-таблицы .

Анализ этой формулы позволяет выделить два случая:

варьируется ;

- варьируется ,

где - базисное множество, соответствующее оптимальному решению

В первом случае будет меняться лишь симплекс-разность k-о столбца

(3.2)

К изменению оптимального решения при этом может привести лишь положительная вариация , которую можно определить, прировняв соотношение (3.2) к нулю:

(3.3)

Предельные отрицательные вариации по коэффициентам целевой функции небазисных переменных равны:

(3.4)

Рассмотрим второй случай

Пусть . Тогда:

(3.5)

Очевидно, что при вариациях такого будет изменяться не одна симплекс-разность, а все те из них, которым в l-ой строке матрицы соответствуют ненулевые коэффициенты.

(3.6)

При этом увеличиваться симплекс-разности будут в следующих случаях:

при положительных вариациях , если ;

при отрицательных вариациях , наоборот, если

В соответствий с этими рассуждениями формулы для определения предельных вариаций коэффициентов целевой функции для случая имеют вид:

(3.7)

(3.8)

где

это величина вариации коэффициента целевой функции , при котором симплекс-разность обратиться в ноль.

Если произведена вариация больше предельной, то, чтобы найти новое решение ЗЛП, необходимо:

- рассчитать с учетом проведенной вариации ;

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

,

а в случае и величину, определяющую значение целевой функции:

- применить к скорректированной симплекс-таблице алгоритм поиска оптимального решения,

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

3.2 Анализ чувствительности оптимального решения к вариациям правых частей ограничений

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

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

Ограничение 2 - активное. Крайнюю точку и соответственно, базисное решение определяют ограничения 2 и 3. Предельная положительная вариация находятся из условия параллельного перемещения прямой, определяющей 2-е ограничение до точки 6. При большей вариации новый оптимальный базис будет определяться ограничениями 1 и 3, т.е. изменится состав активных ограничений. Аналогично, предельная отрицательная вариация определяется параллельным перемещением этой же прямой до крайней точки 5, после чего базисное решение будет определяться только ограничением 2 и , т.е. опять изменится состав активных ограничений. Ограничение 1 - пассивное. Предельная вариация , т.к она не может привести к изменению состава систем ограничений.

Предельная отрицательная вариация определяется параллельным смещением ограничения 1 до крайний точки 4, после чего оптимальный базис будет определяться ограничениями 1 и 3.

Формальный способ анализа связан с изменением базисных компонент решения. Для его проведения наиболее удобно использовать заключительную симплекс-таблицу . Ее структура, используемая для ручного счета, показана на рис. 3.5

Рис.3.5 Структура симплекс-таблицы .

Вариация правой части любого, например,k-о ограничения, приводит к изменению вектора

Действительно, если то . (3.9)

Каждая i-я компонента вектора определяется следующим соотношением:

(3.10)

где - номер ограничения, правая часть которого варьируется,

- i -я строка матрицы ,

- элемент [i,k] матрицы .

Из формулы (3.10) видно, что изменяться при вариации величины будут лишь те элементы , которым в k-м столбце матрицы соответствует ненулевой элементов .

К неоптимальности прежнего базиса может привести лишь уменьшение . При положительной вариации () это будет в случае <0, а при отрицательной () наоборот - при >0.

Так как в общем случае при вариация b[k] могут изменяться несколько базисных элементов прежнего оптимального решения, то формулы для определения предельных вариаций и будут иметь следующий вид:

(3.11)

(3.12)

где (3.13)

Соотношение (3.13) получается из (3.10) приравниванием последнего к нулю.

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

Классифицировать ограничения на активные и неактивные можно из анализа последней строки расширенной обратной базисной матрицы .

Известно, что ,

где - оптимальные значения двойственных переменных. Известно также, что

Следовательно, если , то соответствующее i-ое ограничение является активным (т.е. любое изменение b[i] приводит к изменению оптимального значения целевой функции ЗЛП), в противном случае оно является неактивным.

После проведения вариации величины b[k] меньше предельной для получения нового оптимального решения достаточно скорректировать вектор соответствии с формулой (3.10). Если же осуществляется вариация больше предельной, то после пересчета вектора среди новых значений первых m его компонент появятся отрицательные, т.е. прежнее базисное решение станет недопустимым. При этом прежний базис станет сопряженным, т.е. таким, которому соответствуют значения двойственных переменных, определяющие допустимое базисное решение двойственности ЗЛП.

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

3.3 Анализ чувствительности оптимального решения ЗЛП к введению нового ограничения

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

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

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

(3.14)

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

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

(3.15)

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

(3.16)

, (3.17)

где

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

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

(3.18)

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

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

(3.19)

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

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

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

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

2. Сдвинуть на одну строку вниз последнюю строку симплекс-

таблицы .

На место сдвинутой строки записать в соответствующем порядке коэффициенты нового ограничения.

Добавить к симплекс-таблице новый столбец, соответствующий

n+1 -ой базисной переменной,

Из вновь образованной в п.З строки вычитать поочередно каждую i-ую строку (i=1,m) заключительной симплекс таблицы, умноженную соответственно на .

Рис. 3.8 Расширенная с-т

В результате получим расширенную симплекс-таблицу , изображенную на рис. 3,8. В ней выделена та ее часть, которая добавляется вновь, а заштрихованная часть соответствует прежней симплекс-таблице .

Расширение симплекс-таблицы может быть осуществлено аналогичным образом, если учесть, что обратная матрица получается в результате эквивалентных преобразований Гаусса-Жордана столбцов матрицы условий вспомогательной задачи при фиктивных переменных. В соответствии с этим представлением в п.3 предыдущего алгоритма во вновь образуемую m+1-ую строку расширенной обратной матрицы первоначально должны быть записаны нули. Добавление же нового столбца осуществляется вставкой его на предпоследнее место с предварительным сдвигом последнего столбца заключительной с-т на один вправо.

В результате получим расширенную симплекс-таблицу изображенную на рис. 3.9

Рис. 3.9 Расширенная симплекс-таблица .

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

Литература

Хахулин Г.Ф., Красовская М.А., Булыгин В.С. Теоретические основы автоматизированного управления (Задачи, методы, алгоритмы теории оптимального планирования и управления). М.: МАИ, 2005 г.

Хахулин Г.Ф. Методические указания для выполнения РГР «Исследование чувствительности оптимального решения ЗЛП к вариациям ее параметров и введению нового ограничения». Каф. уч. пособие (под пропуск у секретаря)

Размещено на Allbest.ru