Линейное программирование с параметром в целевой функции
Пусть коэффициент cj целевой функции изменяется в пределах (cj — c'j,cj + с''j), тогда для удобства решения задачи его можно заменить выражением
где c'j, с''j — постоянные; λ — параметр, который изменяется в некоторых пределах (в общем случае от -до ).
В общем виде задача линейного программирования с параметром в целевой функции записывается так:
при ограничениях:
Для каждого значения λ в промежутке δ ≤ λ ≤ φ, где δ и φ — произвольные действительные числа, найти вектор (x1, x2,..., xп), удовлетворяющий системе ограничений и обращающий в максимум (минимум) целевую функцию.
Решая задачу на максимум симплексным методом и исследуя ее решение в зависимости от изменения параметра λ, получим выражения для определения нижнего (λ1) и верхнего (λ2) его значений:
где Δ"j, — оценка симплексной таблицы, содержащая параметр λ; Δ'j — оценка симплексной таблицы, не содержащая параметр λ.
Если для целевой функции отыскивается min, то границы изменения λ (λ1 и λ2) определяются следующим образом:
Приведем алгоритм решения.
1) Задачу решаем симплекс-методом при конкретном значении параметра λ до получения оптимального решения.
2) Вычисляем значения параметров λ1, λ2.
3) Определяем множество значений параметра λ, для которых полученное решение является оптимальным.
4) В случае необходимости в базис вводим вектор, соответствующий столбцу, из которого определялось значение параметра λ2.
5) Выбираем ключевую строку и ключевой элемент.
6) Определяем новое оптимальное решение.
7) Находим новое множество значений λ, для которых решение останется оптимальным.
8) Процесс вычисления повторяем до тех пор, пока весь отрезок [δ, φ] не будет исследован.
Выясним геометрический смысл задачи.
Пусть L() = (c'j + λc''jxj) → max. ABCDEF — область допустимых решений (рис. 25.1). При λ = 0 строим вектор и, перемещая линию уровня MN по направлению вектора , получим в точке D оптимальное решение. Итак, (D) — оптимальное решение, при котором имеем L((D))max. При различных значениях λ линия M'N', параллельная линии уровня MN, будет определенным образом поворачиваться вокруг точки D. Пусть при λ = λ1 прямая M'N' проходит через сторону CD многоугольника допустимых решений, а при λ = λ2 — через сторону DE. Тогда значения (D)опт и L((D))max не изменятся до тех пор, пока λ1 ≤ λ ≤ λ2. Такая картина будет повторяться до получения нового оптимального решения, соответствующего новой целевой функции, для которой существует свой диапазон изменения λ.