12.1. Постановка задачи и геометрический метод ее решения
постоянной - стоимости продукции на момент изготовления; переменной — зависящей от срока хранения продукции. Целевая функция, если она отражает стоимость, будет выражена через коэффициенты, линейно зависящие от параметра t (время).
Часто на практике встречаются задачи, в которых значение коэффициентов целевой функции известны лишь приближенно. Представив их в виде линейных функций параметра /, можно проанализировать решения задач при различных значениях этих коэффициентов. Аналогично можно провести исследования для случая, когда изменяются коэффициенты системы ограничений. Остановимся только на целевой функции. Итак, задача заключается в следующем. Дана система ограничений:
аХХХХ+аХ2Х2+... + аХпХп<С1Х
а1ххх+а11х1+..ла1пхп<а1
(12.1)
атххх +ат2х 2 +... + атпхп<ат
xj>0; j = l,n. Задана целевая функция Z:
п
= l (Cj+djt)Xj-^max, (12.2)
в которой коэффициенты при переменных являются линейными функциями параметра t є [а, |3].
В данном случае определить просто оптимальный план нельзя, так как он может изменяться при различных значениях /. Поэтому задача формулируется следующим образом: требуется разбить отре-зок [а, Р]. на конечное число интервалов, в которых целевая функция Zt достигает максимума (минимума) в одной и той же вершине многогранника решений.
ч
При / = а' изменяются коэффициенты целевой функции, геометрически это значит, что прямая, соответствующая Za, повернулась на некоторый угол. Из рис.
12.1 следует, что Za тах достигается в точке А\, а Za'max — в точке А2. Естественно предположить, что при некотором значении Ґ максимальное значение достигается одновременно в точках Ах и А2. В этом случае прямая, соответствующая целевой-функции, параллельна стороне А\А2 многоугольника решений. Фиксированное значение /' является граничной точкой между двумя соседними интервалами отрезка [а, Р]. Исходя из изложенного, задачу параметрического программирования с двумя переменными можно решить графически.Пример 12.1. Разбить отрезок t є [0; 8] на такие интервалы, в которых целевая функция Zt = 4xj + (2 + t)x2 достигает максимума в одной и той же вершине многогранника решений, и найти соот-ветствующее значение переменных:
Проведем геометрическую интерпретацию задачи параметрического программирования. Полагая t = а и ограничиваясь только двумя переменными, получаем обычную задачу линейного программирования (рис. 12.1).
2х{ - 5х2 < 10; х{ + х2> 5; -х{ -х2< 4; 4х\ + 5Х2 < 40; х{ > 0; х2 > 0.
Положив t = 0 (наименьшее значение t из заданного промежутка), находим геометрически Z0max (рис. 12.2) в точке С.
Далее приравняем Zt к нулю и находим уравнение разрешающей прямой при любом t\
Выпишем угловой коэффициент Kz этой прямой и исследуем его поведение при изменении параметра /: Kz = —4/(2 + t) при
Найдем производную углового коэффициента по параметру t\
(KZY = -4/(2 + t)\
Так как производная при любом t положительна, угловой коэффициент при увеличении t возрастает. Найдем предел его возрастания
?imKz = tim(-4 / (2 + /)) = -0.
/->00
При t -> +00 угловой коэффициент Kz приближается к нулю со стороны отрицательных значений, следовательно, разрешающая прямая поворачивается против часовой стрелки до предельного горизонтального положения. В процессе указанного анализа необходимо понять, что при вертикальном положении прямой угловой коэффициент как функция терпит разрыв. При вращении прямой против часовой стрелки от оси абсцисс до вертикального положения угловой коэффициент возрастает от 0 до +°о5 при дальнейшем вращении прямой он возрастает от —оо до 0.
В рассматриваемом примере при изменении параметра t от нуля до некоторого значения максимальное значение целевой функции будет в вершине С, затем в некоторый фиксированный момент времени оптимум будет достигаться на отрезке ВС, а затем он перейдет в точку В и останется в ней для всех значений / отрезка [0; 8]. Определим значение параметра при котором Zmax будет соответствовать всем точкам отрезка ВС.
Поскольку в этот момент прямая ВС и разрешающая прямая должны быть параллельны, приравняем их угловые коэффициенты. Угловой коэффициент прямой ВС, Квс = -4/5, следовательно, —4/(2 + 0 = -4/5, откуда / = 3. Итак, при 0 < t < 3 оптимальное решение будет в вершине С (8,3; 1,3), при t = 3 оно достигается на всем отрезке ВС, а при 3 < t < 8 - в точке В (2,2; 6,2).