Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Пусть коэффициент cj целевой функции изменяется в некоторых пределах, тогда его можно заменить выражением
,
где - постоянные; - параметр, который изменяется в некоторых пределах.
В общем случае задача линейного программирования с параметром в целевой функции записывается так:
при ограничениях:
,
Для каждого значения в промежутке , где и - произвольные действительные числа, нужно найти вектор , удовлетворяющий системе ограничений и обращающий в максимум (минимум) целевую функцию.
Решая задачу на максимум симплексным методом, и исследуя её решение в зависимости от изменения параметра , применяют следующие выражения для определения нижнего и верхнего его значений:
где - оценка симплексной таблицы, содержащая параметр ; - оценка симплексной таблицы, не содержащая параметр .
Если для целевой функции отыскивается min, то границы изменения и определяются следующим образом:
Алгоритм решения
1) Задача решается симплексным методом при конкретном значении параметра до получения оптимального решения.
2) Вычисляются значения параметров , .
3) Определяется множество значений параметра , для которых полученное решение является оптимальным.
4) В случае необходимости в базис вводим переменную, соответствующую столбцу, из которого определялось значение параметра .
5) Выбирается ключевая строка и ключевой элемент.
6) Определяется новое оптимальное решение.
7) Находится новое множество значений , для которых решение остаётся оптимальным.
8) Процесс вычисления повторяется до тех пор, пока весь отрезок не будет исследован.
Геометрический смысл задачи
Пусть . ABCDEF – область допустимых решений. При строим вектор и, перемещая линию уровня MN по направлению вектора , получим в точке D оптимальное решение. Таким образом, - оптимальное решение, при котором имеем . При различных значениях линия , Параллельная линии уровня MN, будет определённым образом поворачиваться вокруг точки D. Пусть при прямая проходит через сторону CD многоугольника допустимых решений, а при - через сторону DE. Тогда значения и не изменятся до тех пор, пока . Такая картина будет повторяться до получения нового оптимального решения, соответствующего новой целевой функции, для которой существует свой диапазон изменения .
Дата публикования: 2015-03-26; Прочитано: 412 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!