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

Этап 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. Неограниченность системы ЦФ ограничений