Для выполнения курсовой работы

Хахулин Г.Ф.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

Для выполнения курсовой работы

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

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

Москва 2010

Содержание

Цель работы

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

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

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

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

Содержание отчета

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

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

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

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

- при анализе влияния на результат оптимизации ошибок в исходных
данных, на основе которых формируются параметры ЗЛП;

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

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

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

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

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

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

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

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

Где

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

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

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

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

,

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

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

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

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

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

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

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

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

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

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

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

СОДЕРЖАНИЕ РГР ПО КУРСУ ТОПУ

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

1. Формализованная постановка ЗЛП
2. Решение ЗЛП

ТРЕБОВАНИЯ К ФОРМИРОВАНИЮ ЗЛП ДЛЯ ВЫПОЛНЕНИЯ РГР

Число ограничений - 3

3. Все ограничения типа неравенства вида «≤» с положительными правыми частями (т.е. нулевая точка не отсечена от области допустимых решений)

Литература

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

Хахулин Г.Ф.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

для выполнения курсовой работы

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

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

Москва 2010

Содержание

Цель работы