Построение области допустимых решений задачи

Для этого:

- отобразить в прямоугольной системе координат условия неотрицательности переменных (3). В двумерном пространстве уравнению соответствует прямая, а неравенству – полуплоскость, лежащая по одну сторону от прямой. Построим прямые Х₁ = 0, Х₂ = 0, которые лежаи на границах полуплоскостей и совпадают с осями координат. Полуплоскости Х₁ > 0, X₂ > 0 лежат соответственно справа от оси ОХ₂ и выше оси ОХ_1. Множество точек, удовлетворяющих одновременно неравенствам Х₁ > 0 и X₂ > 0, представляет собой пересечение построенных полуплоскостей вместе с граничными прямыми и совпадают с точками первой четверти;

- построить ограничения задачи (2). Для этого построить по порядку прямые (рис.1):

10X₁ + 3X₂ = 30 (1)

-X₁ + X₂ = 3 (2)

X₁ - X₂ = 4 (3)

X₁ + X₂ = 10 (4)

Рис.1. Графическое решение задачи

- установить, с какой стороны от этих прямых лежат полуплоскости, точки которых удовлетворяют строгим неравенствам:

10X₁ + 3X₂ > 30 (1)

-X₁ + X₂ < 3 (2)

X₁ - X₂ < 4 (3)

X₁ + X₂ < 10 (4)

Сторона, в которой располагается полуплоскость от прямой, указывается стрелкой. Убедиться в том, с какой стороны от прямой лежит полуплоскость, точки которой удовлетворяют заданному неравенству, можно путем подстановки координат точек одной или другой полуплоскости в неравенство. Когда прямая, ограничивающая полуплоскость, не проходит через начало координат, удобнее всего подставлять точку с координатами (0, 0). Если координаты точки удовлетворяют неравенству, то эта точка лежит в полуплоскости, соответствующей данному неравенству. В противном случае неравенству будет соответствовать другая полуплоскость;

- определить область определения задачи. Она будет представлять собой пересечение всех построенных полуплоскостей. В данном случае – это пятиугольник АВСDЕ. Каждая точка этого многоугольника, включая и точки, лежащие на его границах, будет удовлетворять ограничениям задачи.

2. 2 Построение целевой функции

Для этого присвоить целевой функции Z значение нуль и построить прямую

Z = Х₁ - 3Х₂ = 0.

Эта прямая, проходящая через начало координат, строится следующим образом. Легко заметить, что в левой части данного уравнения стоит скалярное произведение двух векторов:

N = (с₁, с₂) = (1, -3) и Х = (х₁, х₂).

Скалярное произведение равно нулю когда векторы перпендикулярны.

Построим вектор N – вектор нормали. Он проходит через начало координат и точку (1, -3). Перпендикулярно ему через начало координат проведем прямую. Это и будет прямая целевой функции Z = 0.

Вектор N всегда показывает направление возрастания (максимизации) значения целевой функции, а противоположный ему вектор (- N) – направление убывания (минимизации) значения целевой функции.

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

Передвижение на графике прямой Z = 0 равносильно изменению значения b в уравнении Х₁ - 3Х₂ = b. Каждому значению b соответствует прямая. Полученные прямые параллельны между собой и называются линиями уровня. Особенность линии уровня состоит в том, что целевая функция принимает на ней одинаковые значения, т.е. подставив координаты любой точки линии уровня в целевую функцию, ее значение изменяться не будет.