Геометрическая интерпретация задачи

Рассмотрим задачу ЛП в стандартной форме записи:

(2.18).

при ограничениях.

(2.19).

(2.20).

Рассмотрим эту задачу на плоскости, т. е. при п = 2. Пусть система неравенств (2.19), (2.20) совместна (имеет хотя бы одно решение):

Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой Условия неотрицательности определяют полуплоскости, соответственно, с граничными прямыми x_i = 0, х₂ = 0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы. Совокупность этих точек называют многоугольником решений Он может быть точкой, отрезком, лучом, многоугольником, неограниченной многоугольной областью.

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

Пусть в системе ограничений (2.19)-(2.20) п > 3, тогда каждое неравенство определяет полупространство n-мерного пространства с граничной гиперплоскостью , а условия неотрицательности — полупространства с граничными гиперплоскостями .

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

Таким образом, геометрически задача линейного программирования (2.18)-(2.20) представляет собой отыскание такой точки многогранника решений, координаты которой доставляют линейной функции цели максимальное (минимальное) значение, причем допустимыми решениями являются все точки многогранника решений.

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

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

(2.21).

Этап 2. Прямая , называемая линией уровня и перпендикулярная вектору-градиенту, передвигается в направлении этого вектора в случае максимизации до тех пор, пока не покинет пределов области допустимых решений (ОДР). Предельная точка (или точки) области при этом движении и является точкой максимума .

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

В случае минимизации прямую надо перемещать в направлении, противоположном вектору-градиенту. Ясно, что если прямая при своем движении не покидает ОДР, то соответствующий максимум или минимум не существует (область определения задачи — незамкнутый многоугольник).

Пример 2.6. Решить графическим методом следующую ЗЛП:

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

Этап 1. Определим множество решений первого неравенства. Оно состоит из решения уравнения и строгого неравенства. Решением уравнения служат точки прямой . Построим прямую по двум точкам (0; 7) и (21; 0), которые легко получить в результате последовательного обнуления одной из переменных. На рис. 2.4 обозначим ее цифрой I.

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

Рис. 2.4. Решение ЗЛП графическим методом.

Аналогичным образом построим области решения двух других неравенств.

(на рис. 2.4 прямая II);

при выполняется, берется нижняя полуплоскость.

(на рисунке прямая III);

при выполняется, берется нижняя полуплоскость.

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

Вычислим значение целевой функции в этой точке:

Аналогично поступим для других точек, являющихся вершинами замкнутого выпуклого многоугольника OABCD, представляющего собой область допустимых решений рассматриваемой ЗЛП. Координаты этих вершин имеют следующие значения:

Этап 2. Приравняем целевую функцию постоянной величине а:

Это уравнение является множеством точек, в котором целевая функция принимает значение, равное а. Меняя значение а, получим семейство параллельных прямых, каждая из которых называется линией уровня. Пусть, а = 0, вычислим координаты двух точек, удовлетворяющих соответствующему уравнению . В качестве одной из этих точек удобно взять точку О (0; 0), а так как при будет , то в качестве второй точки возьмем точку G (2; -1).

Через эти две точки проведем линию уровня (пунктирная прямая на рис. 2.4).

Следует отметить, что во многих случаях удобно брать значение, а равным не нулю, а целому числу, делящемуся без остатка на коэффициенты при неизвестных в целевой функции задачи. Например, в рассматриваемой задаче можно было бы брать уравнение линии уровня в виде ; тогда легко бы определялись две точки пересечения линии уровня с координатными осями.

Этап 3. Для определения направления движения к оптимуму построим вектор-градиент , координаты которого (в соответствии с (2.21)) являются частными производными функции , т. е. . Чтобы построить этот вектор, нужно соединить точку (30; 60) с началом координат. При максимизации целевой функции необходимо двигаться в направлении вектора-градиента, а при минимизации — в противоположном направлении. Для удобства можно строить вектор, пропорциональный вектору . Так, на рис. 2.4 изображен вектор

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

Если поставить задачу минимизации функции при тех же ограничениях, линию уровня необходимо смещать параллельно самой себе в направлении, противоположном вектору-градиенту . Как это видно на рис. 2.4, минимум целевой функции достигается в точке О(0; 0), следовательно, можно записать и достигается при .

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

Этот особый случай решения ЗЛП (случай неединственности решения) иллюстрируется, например, следующей задачей:

Графическое решение этой задачи показано на рис. 2.5. Линия уровня параллельна одной из линий по границе области допустимых решений .

Это означает, что задача имеет бесконечное множество оптимальных решений (его задают координаты точек отрезка ВС), среди которых два оптимальных решения — в угловых точках и .

Точки отрезка ВС задаются уравнением , где . При этом максимальное значение целевой функции равно 80.

Рис. 2.5. Случай неединственности решения ЗЛП.

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

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

Указанные выше два случая отсутствия решений в ЗЛП иллюстрируются рис. 2.6 и 2.7, на которых графически представлены, соответственно, задачи:

Как видно из рисунков, первая из приведенных ЗЛП не имеет решения, поскольку ее множество допустимых решений — пустое множество, вторая — поскольку не существует конечного максимума на неограниченном множестве допустимых решений.

Рис. 2.6. Противоречивость.

Рис. 2.7. Неограниченность системы ЦФ ограничений.