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

 

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

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

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

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

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

 

Уравнению соответствует семейство гиперплоскостей, проходящих через начало координат. Если параметру придать некоторое значение t=a_0, то гиперплоскость займет вполне определенное положение. Отодвигая ее от начала координат в направлении возрастания функции, получим решение в точке A. Придадим параметру другое значение t=a₁ и снова найдем на графике точку оптимума. Гиперплоскость вследствие изменения параметра t повернется вокруг начала координат на некоторый угол. Отодвинув эту гиперплоскость от начала координата, получим оптимальное решение в той же вершине A. Однако значение функции при t =a1 изменится, так как оно равно взвешенному отклонению точки A от исходной гиперплоскости. При t =a2 гиперплоскость будет параллельна ребру AB. Оптимальное решение в этом случае будет достигаться в любой точке отрезка AB. Увеличивая t дальше (при t >a2), получим оптимальное решение только в вершине B. Для этой вершины будет свой интервал изменения параметра t. Из постановки и геометрической интерпретации задачи следует, что при различных значениях параметра t оптимальный план может оказаться не одним и тем же. Поэтому в задаче параметрического программирования требуется не просто найти оптимальное решение, а разбить отрезок [ a;b ] на конечное число интервалов, содержащих такие значения t, для которых оптимальное базисное решение задачи достигается в одной и той же вер-

шине многогранника W.

 

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

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

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

 

Графическое решение задачи

 

Определить интервал изменения параметра t и найти значения переменных x₁ и x₂, при которых максимум линейной функции , достигается в одной и той же вершине области допустимых решений системы ограничений

 

Находим область допустимых решений системы ограничений. Это многоугольник ABCD. Придадим параметру самое малое значение t=0, тогда получим функцию с постоянными коэффициентами

Максимальное значение этой функции достигается в вершине C.

 

Область допустимых решений задачи

 

Далее приравняем f_t к нулю и найдем уравнение разрешающей прямой при любом t:

Запишем угловой коэффициент k_f этой прямой и исследуем его поведение при изменении параметра t:

При t=0 его начальное значение  k_f = -2

Найдем производную углового коэффициента по параметру t:

Очевидно, что при любом t производная положительна, а угловой коэффициент при увеличении t возрастает. Найдем предел его возрастания:

Так как при t®+¥ угловой коэффициент k_f приближается к нулю со стороны отрицательных значений, то разрешающая прямая поворачивается против часовой стрелки до предельного горизонтального положения. (На- помним, что при вертикальном положении прямой угловой коэффициент как функция терпит разрыв. При вращении прямой против часовой стрелки от оси абсцисс до вертикального положения угловой коэффициент возрастает от 0 до +¥, при дальнейшем вращении прямой он возрастает от -¥ до 0.)

В рассматриваемом примере при изменении параметра t от нуля до некоторого значения максимум функции будет в вершине C. Далее в некоторый фиксированный момент времени оптимум будет достигаться на отрезке BC, а затем он перейдет в точку B и останется в ней для всех больших значений t.

Определим значение параметра t, при котором решение задачи окажется на отрезке BC. Поскольку в этот момент прямая BC и разрешающая прямая должны быть параллельны, приравняем их угловые коэффициенты. Угловой коэффициент прямой BC kBC = -4/5, следовательно,

Итак, при 0 £ t < 3 оптимальное решение задачи будет в вершине C (8,3;1,3), при t = 3 оно достигается на всем отрезке BC, а при 3< t £ 8 – в точке B (2,2; 6,2).