![]() КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Графический метод ⇐ ПредыдущаяСтр 8 из 8 Графическим методом целесообразно решать задачи линейного параметрического программирования, содержащие не более 2-х переменных. Алгоритм графического метода рассмотрим на примере задачи: Пример 1. Определить интервал изменения параметра t и найти значения переменных х1 и х2, при которых максимум линейной функции ft=4х1+(2+t)х2, t Є [0; 8], достигается в одной и той же вершине области допустимых решений системы ограничений Решение. Строим область допустимых решений - область Р, т.е. геометрическое место точек, в котором одновременно удовлетворяются все ограничения задачи. Каждое из неравенств системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми: Условия неотрицательности переменных Находим область допустимых решений системы ограничений. Это многоугольник АВСD (рис. 3.1).
Рисунок 3.1 Придадим параметру самое малое значение t=0, тогда получим функцию с постоянными коэффициентами
Максимальное значение этой функции достигается в вершине С. Далее мы приравняем ft к нулю и найдем уравнение разрешающей прямой при любом t: Запишем угловой коэффициент этой прямой и исследуем его поведение при изменении параметра t: Его начальное значение при t=0 будет kj = —2. Найдем производную углового коэффициента по параметру t: Очевидно, что при любом t производная положительна, и угловой коэффициент при увеличении е возрастает. Найдем предел его возрастания: Так как при t→ В этом примере при изменении параметра t от нуля до некоторого значения максимум функции будет в вершине С. Далее в некоторый фиксированный момент времени оптимум будет достигаться на отрезке ВС, а затем он перейдет в точку В и останется в ней для всех больших значений t. Определим значение параметра t, при котором решение задачи окажется на отрезке ВС. Поскольку в этот момент прямая ВС и разрешающая прямая должны быть параллельны, приравняем их угловые коэффициенты. Угловой коэффициент прямой ВС kBC =— 4/5, следовательно, — Итак, при Пример 2. Предприятие должно выпустить два вида продукции А и В, для изготовления которых используется 3 вида сырья. Нормы расхода сырья каждого вида на производство единицы продукции данного вида приведены в таблице 3.1. В ней же указаны запасы сырья каждого вида, которое может быть использовано на производство единицы продукции данного вида. Известно, что цена единицы продукции может изменяться для изделия А от 2 до 12 руб., а для изделия В – от 13 до 3 руб., причем эти изменения определяются соотношениями Для каждого из возможных значений цены единицы продукции каждого из видов найти такой план их производства, при котором общая стоимость продукции является максимальной.
Решение. Предположим, что предприятие изготовит х1 единиц продукции А и х2 единиц продукции В. Тогда математическая постановка задачи состоит в определении для каждого значения параметра t ( функции при условиях
Рисунок 3.2 Для решения задачи строим многоугольник решений, определяемый системой линейных неравенств и условием неотрицательности переменных (рис. 3.2). После этого, полагая t=0, строим прямую Положим теперь t=2 и построим прямую (2+2)х1+(13-2)х2=4х1+11х2=44 (число 44 взято произвольно) и вектор Как видно из рис. 3.2, данный план производства продукции будет оставаться оптимальным для всякого значения t, пока прямая (2+t)x1+(13-t)x2=h не станет параллельной прямой 2x1+2x2=22. Это произойдет тогда, когда (2+t)/2=(13-t)/2, т.е. при t=5,5. При этом значении t координаты любой точки отрезка АВ дают оптимальный план начальной задачи. Таким образом, для всякого 0≤t≤5,5 начальная задача имеет оптимальный план Возьмем теперь какое-нибудь значение параметра t, большее 5,5, например 6. Полагая t=6, найдем решение соответствующей начальной задачи. Для этого построим прямую (2+6)х1+(13-6)х2=8х1+7х2=56 (число 56 взято произвольно) и вектор Как видно на рис. 3.2, план Таким образом, для всякого 5,5≤t≤8 начальная задача имеет оптимальный план Fmax=(2+t)×1+(13-t)×10=132-9t. Используя рис. 3.2 и проводя аналогичные рассуждения, получим, что для всякого 8≤t≤10 оптимальным планом начальной задачи является Таким образом, получаем следующее решение начальной задачи: если 0≤t≤5,5, то оптимальным планом является
|