В6 Параметрическое программирование. Постановка и геометрическая интерпретация задачи. Графическое решение задачи.

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

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

при условиях:

В первом выражении числа c_j и d_j известны и постоянны. Остановимся на геометрической интерпретации задачи.

Пусть система ограничений совместна и определяет выпуклый многогранник .

Уравнению соответствует семейство гиперплоскостей, проходящих через начало координат. Если параметру придать некоторое значение t=_0, то гиперплоскость займет вполне определенное положение. Отодвигая ее от начала координат в направлении возрастания функции, получим решение в точке A. Придадим параметру другое значение t=₁ и снова найдем на графике точку оптимума. Гиперплоскость вследствие изменения параметра t повернется вокруг начала координат на некоторый угол. Отодвинув эту гиперплоскость от начала координата, получим оптимальное решение в той же вершине A. Однако значение функции при t 1изменится, так как оно равно взвешенному отклонению точки A от исходной гиперплоскости. При t 2гиперплоскость будет параллельна ребру AB. Оптимальное решение в этом случае будет достигаться в любой точке отрезка AB. Увеличивая t дальше (при t 2), получим оптимальное решение только в вершине B. Для этой вершины будет свой интервал изменения параметра t . Из постановки и геометрической интерпретации задачи следует, что при различных значениях параметра t оптимальный план может оказаться не одним и тем же. Поэтому в задаче параметрического программирования требуется не просто найти оптимальное решение, а разбить отрезок ; на конечное число интервалов, содержащих такие значения t , для которых оптимальное базисное решение задачи достигается в одной и той же вер-

шине многогранника .

Если многогранник неограничен, то гиперплоскость f t0 при некоторых значениях параметра t может занять такое положение, что

f t max окажется неограниченным. Положение гиперплоскости соответствует неограниченному значению функции, а положение гиперплоскости -

максимальному.