Линейные неравенства. Графический метод линейного программирования.

Пусть в уравнении прямой (4) знак равенства заменен знаком неравенства ³ или £; соответствующее множество точек M(x; y) называется полуплоскостью.

Например, линейное неравенство y ³ 2 x + 3 описывает полуплоскость, состоящую

из всех точек на или выше (левее) прямой y = 2 x + 3. Аналогично, x ³ 0 - это

неравенство для полуплоскости, состоящей из точек на или правее оси O y.

Системы линейных неравенств находят применение в так называемых задачах линейного программирования. Рассмотрим конкретный (двумерный) пример.

Пример. Пусть некоторое множество состоит из всех точек на плоскости, координаты которых удовлетворяют системе линейных неравенств (10.а) – (10.д).

Все точки плоскости,удовлетворяющиеданной системе неравенств, называются планами. Кроме того, задана линейная функция z = 2 x + 3 y, называемая целевой функцией. Задача ставится так: найти наибольшее значение (максимум) целевой функции на множестве планов. Также следует указать оптимальный план M₀ (x ₀ ; y ₀), на котором целевая функция принимает максимум. (Аналогично формулируется задача на минимум целевой функции.)

Решение задачи графическим методом. Множество всех планов состоит из точек, удовлетворяющих сразу всем 5 условиям: эти точки расположены (a) на или ниже прямой y - x =2, (б) на или ниже прямой 3 y + x = 14, (в) на или выше прямой y - 3 x= -12, (г) на или правее прямой x = 0, (д) на или выше прямой y = =0. Отсюда следует, что множество планов есть выпуклый 5-угольник OA₁A₂A₃A₄. Каждая его вершинанаходится на пересечении пары прямых, ограничивающих 5-угольник. Например, на пересечении прямых y - x = 2, x = 0 находится вершина A₁; на пересечении прямых y – x = 2, 3 y + x = 14 находится вершина A₂. Аналогично определяются вершины A₃, A₄, O.

Множество точек M(x; y), на которых целевая функция принимает некоторое постоянное значение, называется линией уровня для z. Все линии уровня представляют собой параллельные прямые, задаваемые уравнениями 2 x +3 y = c.

Рассмотрим одну из этих прямых 2 x + 3 y = 0 (здесь c= 0, целеваяфункция z

также равна 0). Это прямая L_O с угловым коэффициентом k = - 2 / 3.Другие линии уровня получаются параллельным перемещением прямой L_O. Этот сдвиг прямой можно производить с помощью линейки. При сдвиге линейки вправо (или вверх) значение c целевой функции увеличивается. Например, прямая L₁ - линия уровня, проходящая через вершину A₁. Линейку можно сдвигать вправо (или вверх) до тех пор, пока на соответствующей линии уровня находятся точки 5-угольника. В итоге достигается крайняя точка, которая и будет оптимальным планом. Это - вершина 5-угольника, характеризуемая тем, что линия уровня, проходящая через нее, не имеет общих точек с внутренностью 5-угольника. В данном случае, как видно из рисунка, эта вершина есть A₃(5; 3), координаты которой x ₃ = 5, y ₃ = 3 находятся из системы уравнений 3 y + x = 14, y - 3 x = -12. Значение целевой функции для этого плана есть z = 2 x ₃+3 y ₃=2 × 5 + 3 × 3 = 19. Ответ: z _max = 19, оптимальный план M₀ (5; 3).

Правило проверки. Существует простой числовой метод, который позволяет подобрать оптимальный план или проконтролировать правильность подобранного оптимального плана. Рассмотрим более общую целевую функцию z = a ₁ x + a ₂ y, для которой нужно найти максимум. По знакам чисел a ₁ , a ₂ уже можно указать те части границы многоугольника, где следует искать оптимальный план.

a 1> 0, a 2> 0: П Ç В

a 1> 0, a 2 < 0: П Ç Н

a 1 < 0, a 2> 0: Л Ç В

a 1 < 0, a 2< 0: Л Ç Н

Здесь П,Л,В,Н – это правая, левая, верхняя, нижняя части границы многоугольника. (Например, верхняя часть границы, В, состоит из всех верхних точек сечений многоугольника вертикальными прямыми.) Остановимся подробнее на двух случаях.

1-я ситуация. Пусть коэффициент a ₂ > 0, тогда оптимальный план является вершиной на верхней части границы многоугольника планов. В рассмотренном примере верхняя часть границы – это ломаная линия A₁A₂A₃, выпуклая вверх. Угловые коэффициенты k ₁₂и k ₂₃ сторон A₁A₂ и A₁A₂ ломаной линии убывают при обходе верхней границы слева направо: k ₁₂ > k ₂₃ . Если угловой коэффициент k = - a ₁/ a ₂ линии уровня z = c расположен на полуинтервале k ³ k ₁₂, то вершина A₁ -

оптимальный план. Если k ₁₂³ k ³ k ₂₃, то вершина A₂ –оптимальный план. Если k ₂₃ ³ k, то вершина A₃ – оптимальный план.

Для 1-й ситуации «правило проверки» можно сформулировать так. Пусть

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

2-я ситуация. Пусть коэффициент в целевой функции a ₁ > 0, тогда оптимальный план является вершиной на правой части границы многоугольника планов. В рассмотренном примере правая часть границы – это ломаная линия A₁A₂A₃, выпуклая вправо. Обратные угловые коэффициенты сторон ломаной линии убывает при обходе правой границы снизу вверх. Если обратный угловой коэффициент 1/ k = - a ₂ / a ₁ таков, что 1/ k ³ 1/ k ₃₄, то вершина A₄ – оптимальный план. Если 1/ k ₃₄ ³ 1/ k ³ 1/ k ₂₃, то A₃ – оптимальный план. Если 1 / k _BC ³ 1/ k, то A₂ –оптимальный план.