Решение задачи линейного программирования графическим методом

Для решения ЗЛП графическим методом необходимо:

1. Построить множество планов, пометив прямые номерами соответствующих ограничений.

2. Построить вектор-градиент.

3. Перпендикулярно вектору-градиенту отобразить несколько линий уровня, двигаясь в направлении градиента в случае, если решаем задачу на максимум, или в направлении антиградиента в случае, если решаем задачу на минимум.

4. Определить вершину как точку последнего касания.

5. Определяем уравнения, которые являются причиной образования вершины. Решения системы этих уравнений и образует координаты искомой точки.

Пример восстановления математической модели ЗЛП

Пример 3. Решим ЗЛП, поставленную в примере 2, графическим методом.

,

Решение. Для нахождения решения ЗЛП графическим методом необходимо построить множество планов задачи. Для этого построим полуплоскости, удовлетворяющие неравенствам ограничений. Для построения полуплоскости каждого из неравенств строится прямая, которая разделяет плоскость Ох₁х₂ на две части, полуплоскость определяется с помощью подстановки какой-либо точки из полуплоскости (например, (0;0)) – если при подстановке неравенство выполняется, значит полуплоскость, в которой находится точка – искомая, иначе – вторая полуплоскость искомая. Для построения полуплоскости и построения каждой прямой определим 2 точки, принадлежащие прямой, а затем определим знак неравенства, который соответствует каждой полуплоскости.

1) для прямой : , точки, удовлетворяющие уравнению: (0;2) и (3;6). Подставим в неравенство точку (0;0): 0≥-6 – выполняется, т.е. искомая полуплоскость та, что содержит точку (0;0).

2) для прямой : , точки, удовлетворяющие уравнению: (3;6) и (12;11). Подставим в неравенство точку (0;0): 0≥-39 – выполняется, т.е. искомая полуплоскость та, что содержит точку (0;0).

3) для прямой : , точки, удовлетворяющие уравнению: (12;11) и (13;8). Подставим в неравенство точку (0;0): 0≥-47 – выполняется, т.е. искомая полуплоскость та, что содержит точку (0;0);

4) для прямой : , точки, удовлетворяющие уравнению: (13;8) и (14;0). Подставим в неравенство точку (0;0): 0≥-112 – выполняется, т.е. искомая полуплоскость та, что содержит точку (0;0);

5) неравенства определяют первую полуплоскость.

Отобразим найденные множества и отобразим их пересечения, указав номер каждого из уравнения:

Ур-ние 1

Ур-ние 2

Ур-ние 3

Ур-ние 4

grad f(x₁,x₂)

Рис.3. Множество планов ЗЛП

Найдем множество допустимых значений как пересечение найденных полуплоскостей. На рисунке пересечение изображено более темным цветом.

Для нахождения оптимального решения необходимо построить градиент = =7, = =7.

Для нахождения наибольшего значения перпендикулярно построенному градиенту будем строить последовательность линий уровня, двигаясь в области допустимых решений в направлении градиента (если задача поставлена на минимум, то движение осуществляется в направлении, противоположенном градиенту). Линия уровня, которая будет последней в области допустимых решений (т.е. будет иметь общие точки с областью допустимых значений, но следующая линия уровня, проведенная с произвольным шагом, уже не будет иметь общих точек с областью допустимых значений) в пересечении с ОДЗ и дает решение задачи. В данном случае наибольшее значение достигается в точке A₂. Координаты этой вершины найдем, решив системы уравнений прямых, образующих эту точку пересечения (это уравнения 2 и 3):

, ,

т.е. в точке А₂(11;12) достигается наименьшее значение функции, равное 7∙11+7∙12= =77+84=161.

Ответ: f_max(11,12)=161.