Постановка и геометрическая интерпретация задачи параметрического программирования

Задачи параметрического программирования являются обобщением задач линейного программирования. Это обобщение состоит в том, что данные задач параметрического программирования считают не постоянными величинами, а функциями, определенным образом зависящими от некоторых параметров. Если предположить, например, что произведенная предприятием продукция подлежит хранению, то ее стоимость будет складываться из двух частей: 1) постоянной — стоимости продукции на момент изготовления; 2) переменной, зависящей от срока хранения продукции. Целевую функцию задачи оптимального планирования такого производства можно выразить через коэффициенты, линейно зависящие от одного параметра, в частности от времени .

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

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

максимизирующий

(1.1)

при условиях

(1.2)

В выражении (1.1) числа известны и постоянны.

Остановимся на геометрической интерпретации задачи.

Пусть система ограничений (1.2) совместна и определяет выпуклый многогранник . Уравнению соответствует семейство гиперплоскостей, проходящих через начало координат. Если параметру придать некоторое значение , то гиперплоскость займет вполне определенное положение. Отодвигая ее от начала координат, в направлении возрастания функции, получим решение в точке (рис. 2.1).

Рисунок 2.1

Придадим параметру другое значение и снова найдем на графике точку оптимума. Гиперплоскость вследствие изменения параметра повернется вокруг начала координат на некоторый угол. Отодвигая эту гиперплоскость от начала координат, получим оптимальное решение в той же вершине . Однако значение функции при изменится, так как оно равно взвешенному отклонению точки от исходной гиперплоскости. При гиперплоскость будет параллельна ребру . Оптимальное решение в этом случае будет достигаться в любой точке отрезка . Увеличивая дальше (при ), получим оптимальное решение только в вершине . Для этой вершины будет свой интервал изменения параметра .

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

Если многогранник неограничен, то гиперплоскость при некоторых значениях параметра может занять такое положение, что окажется неограниченным. Положение гиперплоскости (рис. 2.2) соответствует неограниченному значению функции, а положение гиперплоскости максимальному.

Рисунок 2.2