Геометрический способ решения задачи линейного программирования

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

и удовлетворяющие условиям, которые могут быть только равенствами и неравенствами вида:

,

,

,

где .

Условие неотрицательности переменных принято выделять в отдельную группу.

Покажем применение геометрического метода решения задачи линейного программирования на следующем примере.

Найти значение переменных , которые доставляют максимум функции при условиях:

Поскольку в этой задаче только две переменные х, у (иногда их называют фазовыми переменными), то легко можно построить геометрическую интерпретацию допустимой области, в которой будем искать оптимальное решение, а именной максимум функции . Каждое неравенство, записанное в системе неравенств, геометрически представляет собой полуплоскость. Действительно, возьмем одно неравенство, например, . Если вместо знака неравенства поставить знак “=”, то получим уравнение прямой в двумерном метрическом пространстве (на плоскости), любая прямая делит плоскость на две части (полуплоскость, которая находится выше прямой, и полуплоскость, которая находится ниже прямой). Выбор полуплоскости зависит от знака неравенства. В системе неравенств четыре неравенства, каждое из которых геометрически представляет собой полуплоскость (последние два неравенства определяют первый квадрант декартовой системы координат). Наложение этих полуплоскостей представляет собой область допустимых значений (представлена на рис. 3.1).

Область изменения х, у, удовлетворяющая всем ограничениям, - выпуклый многоугольник ABCDE на рис. 3.1 (в двумерном метрическом пространстве это всегда будет многоугольник).

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

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

Рис.3.2 Линии уровня целевой функции

Задания:

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

· изобразите на графике соответствующие прямые и определите область допустимых значений переменных;

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

· если задача имеет единственное решение, найдите вершину, в которой достигается искомое экстремальное значение (максимум или минимум) целевой функции и укажите ее координаты;

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

Методические указания

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