Графический (геометрический) метод решения задач ЛП

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

.

Решение:

Задача линейного программирования задана в стандартной форме и имеет два проектных параметра, следовательно, возможно ее решение геометрическим методом.

1 этап: построение прямых, ограничивающих область допустимых решений (ОДР).

Рассмотрим систему ограничений задачи линейного программирования (для удобства пронумеруем неравенства):

Рассмотрим первое ограничение, заменим знак неравенства знаком равенства и выразим переменную х₂ через х₁:

.

Для построения прямой по данному уравнению зададим две произвольные точки, к примеру:

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

2 этап: определение решения каждого из неравенств системы ограничений.

Определим полуплоскости – решения каждого из неравенств.

Рассмотрим первое неравенство системы ограничений задачи. Возьмем какую-либо точку (контрольную точку), не принадлежащую соответствующей данному неравенству прямой, например, точку (0; 0). Подставим ее в рассматриваемое неравенство:

.

При подстановке координат контрольной точки неравенство остается справедливым. Следовательно, множество точек, принадлежащих данной прямой (т.к. неравенство не строгое), а также расположенных ниже ее, будут являться решениями рассматриваемого неравенства (пометим на графике (рис. 1) найденную полуплоскость двумя стрелками направленными вниз рядом с прямой I)[1].

Аналогично определяем решения других неравенств и соответственно помечаем их графике. В результате график примет следующий вид:

3 этап: определение ОДР задачи линейного программирования.

Найденные полуплоскости (решения каждого из неравенств системы ограничений) при пересечении образуют многоугольник ABCDEO, который и является ОДР рассматриваемой задачи.

Рис. 1. Область допустимых решений задачи

4 этап: построение вектора-градиента.

Вектор-градиент показывает направление максимизации целевой функции[2]. Определим его координаты: координаты начальной его точки (точки приложения) – (0; 0), координаты второй точки:

Построим данный вектор на графике (рис. 2).

5 этап: построение прямой целевой функции.

Рассмотрим целевую функцию данной задачи:

.

Зададим ей какое-либо значение, к примеру, . Выразим переменную х₂ через х₁:

.

Для построения прямой по данному уравнению зададим две произвольные точки, к примеру:

Построим прямую соответствующую целевой функции (рис. 2).

 

Рис. 2. Построение целевой функции F(X) и вектора-градиента С

 

6 этап: определение максимума целевой функции.

Перемещая прямую F(X) параллельно самой себе по направлению вектора-градиента, определяем крайнюю точку (точки) ОДР. Согласно графику (рис. 3), такой точкой является точка С ­– точка пересечения прямых I и II.

 

 

Рис. 3. Определение точки максимума целевой функции F(X)

 

Определим координаты точки С, с этой целью, решим следующую систему линейных уравнений:

Подставим найденные координаты в целевую функцию и найдем ее оптимальное (максимальное) значение:

Ответ: при заданных ограничениях максимальное значение целевой функции F (Х)=24, которое достигается в точке С, координаты которой х₁ =6, х₂ =4.

 

Пример 6.2. Решить задачу линейного программирования геометрическим методом:

Решение:

Этапы 1-3 аналогичны соответствующим этапам предыдущей задачи.

4 этап: построение вектора-градиента.

Построение вектора-градиента осуществляется аналогично, как и в предыдущей задаче. Построим данный вектор на графике (рис. 4). Отметим также на данном графике стрелкой направление, обратное вектору-градиенту, – направление минимизации целевой функции F (X).

5 этап: построение прямой целевой функции.

Построение прямой целевой функции F (X) осуществляется аналогично, как и в предыдущей задаче (результат построения приведен на рис. 4).

 

Рис. 4. Построение целевой функции F(x) и вектора-градиента С

 

6 этап: определение оптимума целевой функции.

Перемещая прямую F(x) параллельно самой себе в направлении, обратном вектору-градиенту, определяем крайнюю точку (точки) ОДР. Согласно графику (рис. 5), такой точкой является точка О с координатами (0; 0).

 

 

Рис. 5. Определение точки минимума целевой функции

 

Подставляя координаты точки минимума в целевую функцию, определяем ее оптимальное (минимальное) значение, которое равно 0.

Ответ: при заданных ограничениях минимальное значение целевой функции F (Х)=0, которое достигается в точке О (0; 0).

 

[1] Если после подстановки координат контрольной точки в неравенство его смысл нарушается, то решением данного неравенства является полуплоскость не содержащая данную точку (т.е. расположенная по другую сторону прямой).

[2] Направление, обратное вектору-градиенту, соответствует направлению минимизации целевой функции.