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

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

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

График целевой функции имеет одну единственную точку прикосновения с ОДР, причем в этой точке ЦФ имеет оптимальное значение. Оптимальное решение задачи ЛПР всегда достигается в одной из вершин многоугольника допустимых решений. Именно к такой ситуации следует стремиться при графическом решении задачи ЛПР. В показанном на рисунке случае число ограничений равно 6. Стороны изображенного многоугольника описываются прямыми, уравнения которых берутся из ограничений (2). При построении многоугольника допустимых решений знаки неравенств в ограничениях заменяются знаками равенств. Таким образом, точки внутри многоугольника допустимых решений удовлетворяют сразу всем неравенствам.

Построение многоугольника допустимых решений и графика целевой функции

Пусть нужно максимизировать ЦФ вида z=d₁x₁+d₂x₂ при имеющихся ограничениях: 

a₁₁x₁+a₁₂x₂<=b₁

a₂₁x₁+a₂₂x₂<=b₂…

a_m1x₁+a_m2x₂<=b_m

x₁>=0, x₂>=0

Для построения многоугольника допустимых решений вначале строится прямая a₁₁x₁+a₁₂x₂=b₁. При построении целесообразно расположить точки прямой на осях системы координат. Взяв x₁=0, x₂=b₁/a₁₂, при x₂=0, x₁=b₁/a₁₁.

x₂

 

A

 

      

 

 

   0                          B              x₁

 

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

На график с изображением многоугольника допустимых решений наносится прямая линия, которая описывает ЦФ в соответствии с формулой (1).

   x₂

 

 

 

 

                                      

                                       ЦФ

      

      0                                                x₁

 

Первоначально прямую линию графика ЦФ проводят так, чтобы она пересекала многоугольник допустимых решений. Затем эту прямую перемещают в сторону увеличения целевой функции до тех пор, пока прямая линия имеет хотя бы одну точку с ОДР. Для ЦФ вида z= d₁ x₁+ d₂ x₂ прямую линию следует перемещать параллельно самой себе в направлении вектора d с координатами (d₁; d₂). При минимизации ЦФ прямую линию смещают в направлении вектора (- d₁;- d₂).

При графическом решении задач ЛПР:

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

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

3. На основании уравнения, которое описывает ЦФ, строится вектор-градиент d с координатами (d1;d2), определяющие вектор возрастания ЦФ.

4. Выбрав некоторое постоянное значение h, строится график ЦФ d1x1+d2x2=h, который должен пересекать многоугольник допустимых решений. График ЦФ будет обязательно перпендикулярен вектору d.

5. Увеличивается значение h до тех пор, пока график ЦФ имеет хотя бы одну общую точку с ОДР. При увеличении h график ЦФ смещается параллельно самому себе в направлении возрастания вектора d.

6. Определяет точка или отрезок, где ЦФ принимает максимальное значение в этой точке или на этом отрезке переменные x_i имеет оптимальное значение.

Пример. Для производства двух видов изделий А и В предприятие использует три вида сырья. Норма расхода сырья каждого вида на изготовление единицы продукции данного вида приведено в таблице. В ней же указаны прибыль от реализации одного изделия каждого вида и общее количество сырья данного вида, которое может быть использовано предприятием.

Вид сырья	Нормы расхода сырья (кг) на одно изделие		Общее количество сырья (кг)
	A	B
I II III	12 4 3	4 4 12	300 120 252
Прибыль от реализации одного изделия (руб.)	30	40

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

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

Общая прибыль от реализации   изделий вида  А и   изделий вида В составит F=30 + 40 .

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

Решим сформулированную задачу геометрическим способом. Сначала определим многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств и найдём соответствующие прямые:

Эти прямые изображены на рисунке. Каждая из построенных прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству, а другой – нет. Чтобы определить искомую полуплоскость, нужно взять какую-нибудь точку, принадлежащую одной из полуплоскостей, и проверить, удовлетворяют ли её координаты данному неравенству. Если координаты взятой точки удовлетворяют данному неравенству, то искомой является та полуплоскость, которой принадлежит эта точка, в противном случае – другая полуплоскость.

Найдем, например, полуплоскость, определяемую неравенством 12 +4 <300. Для этого, построив прямую 12 +4 =300 (пр. I), возьмем какую-нибудь точку, принадлежащую одной из полученных полуплоскостей, например, точку O(0;0). Координаты этой точки удовлетворяют неравенству: , значит, полуплоскость, которой принадлежит точка O(0;0), определится неравенством . Это и показано стрелками на рисунке.

 

 

 

 

Пересечение полученных полуплоскостей и определяет многоугольник решений данной задачи.

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

Поэтому сформулированная задача будет решена, если мы сможем найти точку, принадлежащую пятиугольнику OABCD, в которой функция F принимает максимальное значение. Чтобы найти указанную точку, построим вектор и прямую  где h – некоторая постоянная такая, что прямая    имеет общие точки с многоугольником решений. Положим, например, h=480 и построим прямую  (см. рис.). Точки пересечения с осями .

Если теперь взять какую-нибудь точку, принадлежащую построенной прямой и многоугольнику решений, то её координаты определяют такой план производства изделий А и В, при котором прибыль от их реализации равна 480 руб. Далее, полагая h равным некоторому числу, большему чем 480, мы будем получать различные параллельные прямые. Если они имеют общие точки с многоугольником решений, то эти точки определяют план производства изделий А и В, при которых прибыль от их реализации превзойдет 480 руб.

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

Найдем координаты точки В, как точки пересечения прямых II  и III. Следовательно, ее координаты удовлетворяют уравнениям этих прямых:

Решив эту систему уравнений, получим =12, =18. Следовательно, если предприятие изготовит 12 изделий вида А и 18 изделий вида В, то оно получит максимальную прибыль, равную =  руб.