Геометрия задач ЛПГеометрические построения возможны для размерности пространства задачи k £ 3. Рассмотрим задачи на плоскости (k= 2):
Надо сначала построить допустимое множество, а затем по целевой функции найти на нем точку или множество с максимальным значением критерия. Допустимое множество задачи находится как пересечение допустимых множеств, построенных по отдельным условиям задачи. Построение множества начинается с определения его границы (условия неотриц-ти). Допустимое множество задачи ЛП всегда лежит в первом квадранте. Теперь перейдем к построению допустимых множеств по функциональным условиям. Записываем уравнения границ и проводим соответствующие прямые. Находя пересечение шести построенных допустимых множеств, получаем выпуклый шестиугольник – частный случай выпуклого многогранника. Из бесконечного множества допустимых решений, принадлежащих этому многоугольнику, необходимо найти то, которое дает максимум критерия. Построим линии уровня критерия L=Const.. Так как критерий линейный, то линии уровня – это множество параллельных прямых с постоянным градиентом (направлением возрастания значений критерия). Поэтому для определения этого направления достаточно иметь 2 линии уровня.
Отсюда: х* 1=5, х* 2=3. Значения остальных переменных вычисляются однозначно из канонической модели после подстановки в ее уравнения х* 1и х* 2. В результате оптимальное решение задачи: х* 1=5, х* 2=3, х* 3= х*4 =0, х*5 =3, х*6 =2 и, L*= 50. Таким образом, чтобы добиться максимальной прибыли в 50 единиц, необходимо производить 5 изделий первого типа и 3 изделия второго типа. При этом будут полностью использованы ресусы 1-го и 2 -го вида (х* 3= х*4 =0), а по ресурсам 3-го и 4-го вида образуются остатки в количестве 3 и 2 соответственно (х*5 =3, х*6 =2). Задача имеет единственное оптимальное решение, так как линия уровня L= 50 соприкасается с допустимым множеством только в одной точке. При данном допустимом множестве задача всегда будет иметь решение независимо от коэффициентов целевой функции, потому что в любом случае будет существовать предельное положение линии уровня критерия. Однако оптимальное решение может быть и не единственным. Пример: L 1=4 x 1+6 x 2→ max. Так как условия не изменились, то допустимое множество остается прежним. Если повторить построение линий уровня, то они будут параллельны стороне BC. Поэтому в предельном положении линия уровня критерия совпадает с границей по 1-му ограничению; Мн-во (бесконечное) оптимальных решений, лежащее на стороне BC, каждому из которых соответствует одно и то же максимальное значение критерия L 1. Пример: допустимое мн-во неограниченно. Видно разное поведение критериев, приводящее к различ. результатам. а) Значение критерия L 1 улучшается в направлении неограничености множества и, критерий неограничен на допустимом множестве, он может улучшаться до ∞ – допустимые решения есть, а оптимального нет. б) Улучшение критерия L 2 ограничено на допустимом множестве, решение существует. Пример: пересечение допустимых множеств, порождаемых тремя функциональными ограничениями задачи и условиями неотрицательности переменных, - пустое; допустимых решений нет и задача неразрешима. Т.о, если задача ЛП разрешима, то оптимальное решение обязательно достигается в вершине допустимого множества; оптимальное решение следует искать не на всей границе, а только в вершинах доп. множества.
|