Геометрия задач ЛП

Геометрические построения возможны для размерности пространства задачи k £ 3. Рассмотрим задачи на плоскости (k= 2):

Исходная модель L =7 x 1+5 x 2→max, 1) 2 x 1+3 x 2£19, 2) 2 x 1+ x 2£13, 3) 3 x 2£12, 4) 3 x 1£17, 5) x 1³0, 6) x 2³0.

Каноническая модель L =7 x 1+5 x 2→max, 2 x 1+3 x 2+ x 3=19, 2 x 1+ x 2+ x4 =13, 3 x 2+ x5 =12, 3 x 1+ x6 =17, " xj ³0.

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

Из бесконечного множества допустимых решений, принад­лежащих этому многоугольнику, необходимо найти то, которое дает максимум критерия. Построим линии уровня критерия L=Const.. Так как критерий линейный, то линии уровня – это множество параллельных прямых с постоянным градиентом (направлением возрастания значений критерия). Поэтому для определения этого направления достаточно иметь 2 линии уровня.

L*

Критерий увеличивается в направлении, показанном стрелкой. Чтобы найти оптимальное решение, не нужно строить новые линии уровня. Предельное положение критерия соответствует прохождению линии уровня через точку С (максимальное значение). Координаты точки С – оптимальные значения переменных, можно найти как решение системы 2-х уравнений границ, образующих эту точку: 2 x^* ₁+3 x^* ₂=19, 2 x^* ₁+ x^* ₂=13.

Отсюда: х^* ₁=5, х^* ₂=3. Значения остальных переменных вычисляются однозначно из канонической модели после подстановки в ее уравнения х^* ₁и х^* ₂. В результате оптимальное решение задачи: х^* ₁=5, х^* ₂=3, х^* ₃= х^*₄ =0, х^*₅ =3, х^*₆ =2 и, L^*= 50.

Таким образом, чтобы добиться максимальной прибыли в 50 единиц, необходимо производить 5 изделий первого типа и 3 изделия второго типа. При этом будут полностью использованы ресусы 1-го и 2 -го вида (х^* ₃= х^*₄ =0), а по ресурсам 3-го и 4-го вида образуются остатки в количестве 3 и 2 соответственно (х^*₅ =3, х^*₆ =2). Задача имеет единственное оптимальное решение, так как линия уровня L= 50 соприкасается с допустимым множеством только в одной точке.

При данном допустимом множестве задача всегда будет иметь решение независимо от коэффициентов целевой функции, потому что в любом случае будет существовать предельное положение линии уровня критерия. Однако оптимальное решение может быть и не единственным. Пример: L ₁=4 x ₁+6 x ₂→ max.

Так как условия не изменились, то допустимое множество остается прежним. Если повторить построение линий уровня, то они будут параллельны стороне BC. Поэтому в предельном положении линия уровня критерия совпадает с границей по 1-му ограничению; Мн-во (бесконечное) оптимальных решений, лежащее на стороне BC, каждому из которых соответствует одно и то же максимальное значение критерия L ₁.

Пример: допустимое мн-во неограниченно. Видно разное поведение критериев, приводящее к различ. результатам.

а) Значение критерия L ₁ улучшается в направлении неограничености множества и, критерий неограничен на допустимом множестве, он может улучшаться до ∞ – допустимые решения есть, а оптимального нет.

б) Улучшение критерия L ₂ ограничено на допустимом множестве, решение существует.

Пример: пересечение допустимых множеств, порождаемых тремя функциональными ограничениями задачи и условиями неотрицательности переменных, - пустое; допустимых решений нет и задача неразрешима.

Т.о, если задача ЛП разрешима, то оптимальное решение обязательно достигается в вершине допустимого множества; оптимальное решение следует искать не на всей границе, а только в вершинах доп. множества.