Графический метод. Графическим методом целесообразно решать задачи линейного параметрического программирования, содержащие не более 2-х переменных

Графическим методом целесообразно решать задачи линейного параметрического программирования, содержащие не более 2-х переменных.

Алгоритм графического метода рассмотрим на примере задачи:

Пример 1.

Определить интервал изменения параметра и найти значения переменных и , при которых максимум линейной функции

, , достигается в одной и той же вершине области допустимых решений системы ограничений

Решение. Строим область допустимых решений - область P, то есть геометриче­ское место точек, в котором одновременно удовлетворяются все ограничения задачи. Каж­дое из неравенств системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми:

Условия неотрицательности переменных ограничивают область допустимых решений в I квадрате.

Находим область допустимых решений системы ограничений. Это многоугольник ABCD (рис. 3.1).

Рисунок 3.1

Придадим параметру самое малое значение , тогда получим функцию с постоянными коэффициентами

.

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

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

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

Его начальное значение при будет .

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

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

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

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

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

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

Пример 2.

Предприятие должно выпустить два вида продукции A и B, для изготовления которых используется 3 вида сырья. Нормы расхода сырья каждого вида на производство единицы продукции данного вида приведены в таблице 3.1. В ней же указаны запасы сырья каждого вида, которое может быть использовано на производство единицы продукции данного вида.

Известно, что цена единицы продукции может изменяться для изделия А от 2 до 12 руб., а для изделия B – от 13 до 3 руб., причем эти изменения определяются соотношениями

Для каждого из возможных значений цены единицы продукции каждого из видов найти такой план их производства, при котором общая стоимость продукции является максимальной.

Решение. Предположим, что предприятие изготовит х₁ единиц продукции А и единиц продукции В. Тогда математическая постановка задачи состоит в определении для каждого значения параметра ( максимального значения

функции

при условиях

Рисунок 3.2

Для решения задачи строим многоугольник решений, определяемый системой линейных неравенств и условием неотрицательности переменных (рис. 3.2). После этого, полагая , строим прямую

(число взято произвольно) и вектор . Передвигая построенную прямую в направлении вектора видим, что последней общей точкой ее с многоугольником решений ОАВСD является точка А (0;11). Следовательно, задача, полученная из изначального условия при t=0, имеет оптимальный план Это означает, что если цена единицы продукции А равна 2+0=2 руб., а цена единицы продукции В равна 13-0=13 руб., то оптимальным планом производства является план, согласно которому производится 11 изделий В и не производятся изделия А. При таком плане производства продукции ее стоимость максимальна и равна .

Положим теперь и построим прямую

(число 44 взято произвольно) и вектор Передвигая построенную прямую в направлении вектора , видим, что последней ее общей точкой с многоугольником решений является точка А (0;11). Следовательно, задача полученная из исходной задачи при t=2, имеет оптимальный план Это означает, что если цена единицы продукции А равна 2+2=4 руб., а цена единицы продукции В равна 13-2=11 руб., то предприятию также наиболее целесообразно производить 11 ед. продукции вида В и совсем не производить продукцию вида А. При таком плане производства продукции общая стоимость является максимальной и составляет F_max =(2+2)×0+(13-2)×11=121 руб.

Как видно из рис. 3.2, данный план производства продукции будет оставаться оптимальным для всякого значения t, пока прямая (2+ t) x₁ +(13- t) x₂ = h не станет параллельной прямой 2 x₁ +2 x₂ =22. Это произойдет тогда, когда (2+ t)/2=(13- t)/2, т.е. при t =5,5. При этом значении t координаты любой точки отрезка АВ дают оптимальный план начальной задачи.

Таким образом, для всякого 0≤ t ≤5,5 начальная задача имеет оптимальный план при котором значение целевой функции есть

Возьмем теперь какое-нибудь значение параметра t, большее 5,5, например 6. Полагая t =6, найдем решение соответствующей начальной задачи. Для этого построим прямую (2+6) х₁ +(13-6) х₂ =8 х₁ +7 х₂ =56 (число 56 взято произвольно) и вектор =(8;7). Передвигая построенную прямую в направлении вектора , видим, что последней ее общей точкой с многоугольником решений является точка В (1;10). Следовательно, задача, полученная из начальной задачи при t =6, имеет оптимальный план Это означает, что если цена единицы продукции А равна 2+6=8 руб., а цена единицы продукции В равна 13-6=7 руб., то оптимальным планом ее изготовления является план, согласно которому производится одно изделие вида А и десять изделий вида В. При этом плане общая стоимость производимой продукции максимальна: Fmax =8×1+7×10=78 руб.

Как видно на рис. 3.2, план является оптимальным планом начальной задачи для всякого t >5,5 до тех пор, пока прямая (2+ t)x₁ +(13- t)x₂ = h не станет параллельной прямой 6 х₁ +3 х₂ =36. Это произойдет тогда, когда (2+ t)/6=(13 -t)/3, т.е. при t =8. При этом значении t координаты любой точки отрезка ВС дают оптимальный план начальной задачи.

Таким образом, для всякого 5,5≤ t ≤8 начальная задача имеет оптимальный план , при котором значение линейной функции составляет

F max =(2+ t)×1+(13- t)×10=132-9 t.

Используя рис. 3.2 и проводя аналогичные рассуждения, получим, что для всякого 8≤ t ≤10 оптимальным планом начальной задачи является Это означает, что если цена ед. продукции вида А заключена между (или равна) 10 и 12 руб., а ед. продукции В – между (или равна) 3 и 5 руб., то оптимальным планом ее производства является такой план, согласно которому изготовляется 2 ед. продукции вида А и 12 ед. продукции вида В. При этом плане производства продукции ее общая стоимость для каждого значения параметра 8≤ t ≤10 составляет Fmax =108-6 t.

Таким образом, получаем следующее решение начальной задачи: если 0≤t≤5,5, то оптимальным планом является , при чем Fmax=143-11t; если 5,5≤t≤8, то оптимальным планом является , причем Fmax=132-9t; наконец, если 8≤t≤10, то оптимальный план , причем Fmax=108-6t.

Поиск по сайту: