1.2. Графический метод решения задачи лп

Графический метод применим для решения задач ЛП в сопряженной канонической форме, если число переменных n=2, т.е. задач вида

f(x) = c₁x₁+c₂x₂  max, (1.12)

p_i(x) = a_i1x₁+a_i2x₂ ≤ b_i, (1.13)

x₁≥0, x₂≥0. (1.14)

Каждое из неравенств (1.13) системы ограничений задачи геометрически определяет полуплоскость, лежащую по одну сторону от прямой a_i1x₁+a_i2x₂=b_i (прямая тоже принадлежит этой плоскости). Если b_i≥0, то ограничение выполняется для точки (x₁=0, x₂=0), т.е. допустимой является полуплоскость, включающая начало координат; если b_i<0, то допустимой является полуплоскость, не включающая начало координат. Для условий (1.14) неотрицательности переменных допустимыми являются полуплоскости над осью абсцисс (x₂≥0) и слева от оси ординат (x₁≥0). Часть плоскости [x₁0x₂], принадлежащая одновременно всем допустимым полуплоскостям, образует область X допустимых решений (если система ограничений является несовместной, то область X является пустой).

Для нахождения решения задачи ЛП строятся градиент f′(x) целевой функции и основная прямая f(x)=0 (вектор f′(x) перпендикулярен основной прямой). Основная прямая перемещается в направлении градиента до тех пор, пока она не выйдет на границу области X.

При этом возможен один из следующих случаев:

– прямая f(x)=const и область X допустимых решений имеют одну общую точку (вершину X). Эта точка определяет единственное оптимальное решение;

– прямая f(x)=const и область X допустимых решений имеют множество общих точек (вектор f'(x) перпендикулярен к одной из сторон многоугольника X). Данное множество общих точек представляет собой множество оптимальных решений;

– прямая f(x)=const не выходит на границу области X допустимых решений, сколько бы ее не перемещали (это возможно, если область X неограниченная). При этом целевая функция f(x) оказывается также неограниченной.

Таким образом, алгоритм решения задачи ЛП графическим методом заключается в следующем:

1. Строятся прямые, задаваемые уравнениями a_i1x₁+a_i2x₂=b_i, , и находят полуплоскости, определяемые каждым из ограничений задачи.

2. Находят область допустимых решений X.

3. Строят градиент f′(x)=(c₁, c₂) и основную прямую f(x)=0.

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

5. Определяют координаты точки максимума x^* функции и вычисляют значение целевой функции f^*≡ f(x^*)в этой точке.

Задачи

1.4. Решить графическим методом задачу ЛП

f(x) = 2x₁+3x₂  max,

3x₁+2x₂≤15,

x₁+x₂≤6,

x₂≤4,

x₁, x₂≥0.

1.5. Решить графическим методом задачу ЛП

f(x)=2x₁−3x₂  min,

x₁−x₂≤2,

2x₁+x₂≤6,

x₁, x₂≥0.

1.6. Решить графическим методом задачу ЛП

f(x) = −3x₁+4x₂  min,

x₁+2x₂≤3,

3x₁+3x₂≥4,

3x₁−x₂≤2,

x₁, x₂≥0.