Для выполнения расчетно-графической работы

Хахулин Г.Ф.

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

Для выполнения расчетно-графической работы

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

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

Москва 2010

Содержание

Цель работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Где (3.9)

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

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

где рассчитываются с учетом проведенной вариации;

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

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

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

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

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

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

таблицы .

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

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

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

Определение предельных вариаций коэффициентов целевой функции ЗЛП графическим методом

Определение предельных вариаций коэффициентов целевой функции ЗЛП формальным методом

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

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

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

Литература

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

Хахулин Г.Ф.

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

для выполнения расчетно-графической работы

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

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

Москва 2010

Содержание

Цель работы