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

Определить интервал изменения параметра 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.

В7 Параметрическое программирование. Постановка и геометрическая интерпретация задачи. Аналитическое решение задачи.

Алгоритм решения задачи c предыдущего вопроса состоит из двух этапов.

Этап I. Параметру t дают фиксированное значение, например t= . Этим задача приводится к задаче линейного программирования. Решая эту задачу симплекс-методом, находят вершину, в которой f _t достигает максимума.

Этап II. Определяют интервал изменений параметра t , для которого максимум f_t достигается в одной и той же вершине многогранника  . Найденный интервал исключают из отрезка [;]. Для оставшейся части отрезка снова решают задачу симплекс-методом, т. е. переходят к этапу I. Решение продолжается до тех пор, пока весь отрезок [;] не будет разбит на частичные интервалы.

Подробно алгоритм решения рассмотрим на примере.

Пример 1. Найти интервалы изменения параметра t на отрезке [;] для которых достигает максимума в одной и той же вершине области допустимых решений системы ограничений

Решим задачу в два этапа.