При условиях:

a₁₁x₁ + a₁₂x₂  () b₁

……………………

a_m1x₁ + a_m2x₂  () b_m

x₁, x₂  0

Каждое из неравенств системы ограничений задачи геометрически определяет полуплоскость с граничными прямыми a_i1x₁ + a_i2x₂ = b_i (i = 1,…,m), x₁, x₂  0. В случае, если данная система неравенств совместна, область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям. Выпуклое множество, образованное в результате пересечения рассматриваемых полуплоскостей, называется многоугольником решений (при n  3 многогранником решений). Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки точных равенств (рис.1). Так как линейная целевая функция достигает своего оптимального (максимального или минимального) значения в угловой точке многоугольника решений, то решение необходимо искать только среди вершин многоугольника.

Построим линию уровня целевой функции, c₁x₁ + c₂x₂ = h, где h – некоторая постоянная. Значение целевой функции возрастает в направлении градиента целевой функции, т.е. в направлении вектора и убывает в противоположном направлении. Перемещая линию уровня в направлении вектора до тех пор, пока она не пройдет через последнюю ее общую точку с многоугольником решений, получим точку, координаты которой определяют максимальное значение целевой функции (на рис.1 это точка D). Перемещая линию уровня в противоположном направлении, до касания с допустимой областью, получим точку, определяющую минимальное значение целевой функции (на рис.1 это точка A).

Рис.1

Координаты точек А и D можно получить, решая системы уравнений, задающих граничные прямые АВ и АР, ВD и DЕ.

Таким образом, решение задачи линейного программирования на основе ее геометрической интерпретации включает следующие этапы:

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

2. Определение полуплоскостей, задаваемых каждым из ограничений задачи.

3. Нахождение многоугольника решений, образующегося в результате пересечения всех полуплоскостей.

4. Построение вектора

5. Построение прямой, c₁x₁ + c₂x₂ = h , проходящей через прямоугольник решений.

6. Перемещение прямой c₁x₁ + c₂x₂ в направлении вектора для определения точки, в которой целевая функция принимает максимальное значение, или в противоположном направлении для определения точки, в которой она принимает максимальное значение.

7. Определение координат точки максимума (минимума) функции в результате решения соответствующей системы уравнений и вычисление значения целевой функции в этой точке.

При решении возможны ситуации, изображенные на рис 2-5.

Рис.2 Рис.3

Рис.4 Рис.5

Рис.2 характеризует случай, когда целевая функция принимает единственное максимальное значение в точке D и единственное минимальное значение в точке А. Из рис. 3 видно, что максимальное значение целевая функция принимает в любой точке отрезка СD. На рис. 4 изображен случай, когда целевая функция не ограничена сверху на множестве допустимых решений, а на рис. 5 – случай, когда система ограничений задачи несовместна.

Пример Найти максимум и минимум функции F = x₁ + x₂ при условиях:

Решение. Построим многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных заменим знаки неравенств на знаки точных равенств:

Построив полученные прямые, найдем соответствующие полуплоскости и их пересечение (рис. 6).

Рис. 6

Как видно из рис. 6 многоугольником решений задачи является треугольник АВС. Координаты точек этого треугольника удовлетворяют условию неотрицательности и неравенствам системы ограничений задачи. Построим прямую x₁ + x₂ = 4 (число 4 взято произвольно) и вектор = (1,1).

Передвигая данную прямую параллельно самой себе в направлении вектора видим, что ее последней общей точкой с многоугольником решений задачи является точка С. Следовательно, в этой точке функция F принимает максимальное значение. Так как С – точка пересечения прямых I и II, то ее координаты удовлетворяют уравнениям этих прямых:

Решив эту систему уравнений, получим . Таким образом, максимальное значение функции F_max = 7.

Для нахождения минимального значения целевой функции задачи передвигаем прямую x₁ + x₂ = 4 в направлении, противоположном направлению вектора = (1;1). В этом случае, как видно из рис. 6, последней общей точкой прямой с многоугольником решений задачи является точка А. Следовательно, в этой точке функция F принимает минимальное значение. Для определения координат точки А решаем систему уравнений:

Откуда . Подставляя найденные значения в целевую функцию, получим F_min = 3.