ТОП 10:

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



 

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

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

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

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

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

 

Уравнению соответствует семейство гиперплоскостей, проходящих через начало координат. Если параметру придать некоторое значение t=a0, то гиперплоскость займет вполне определенное положение. Отодвигая ее от начала координат в направлении возрастания функции, получим решение в точке A. Придадим параметру другое значение t=a1 и снова найдем на графике точку оптимума. Гиперплоскость вследствие изменения параметра 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 и найти значения переменных x1 и x2, при которых максимум линейной функции , достигается в одной и той же вершине области допустимых решений системы ограничений

 

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

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

 

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

 

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

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

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

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

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

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







Последнее изменение этой страницы: 2016-07-14; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.236.35.159 (0.008 с.)