3.2. Графоаналитический метод

Графоаналитический метод – это один из простейших методов линейного программирования. Он наглядно раскрывает сущность линейного программирования, его геометрическую интерпретацию. Его недостаток в том, что он позволяет решать задачи с 2 или 3 неизвестными, т. е. применим для узкого круга задач. Метод основан на правилах аналитической геометрии.

Решение задачи с двумя переменными х₁ и х₂, которые по смыслу задачи не должны быть отрицательными, выполняется в системе декартовых координат. Уравнения х₁=0 и х₂ = 0 являются осями системы координат первого квадранта

(рис. 3.1).

Метод решения рассмотрим на конкретном примере.

Пример 3.1. На складе имеются 300 т изделий из пенобетона и 200 т из стали. Автопредприятию необходимо доставить эти изделия на строящийся объект. На автопредприятии имеются грузовые автомобили КамАЗ - 5320 и

ЗИЛ-4314. За одну поездку КамАЗ-5320 может доставить 6 т пенобетона и 2 т стали, а прибыль от ездки составит 4 тыс. руб. ЗИЛ-4314 за одну поездку доставляет 2 т пенобетона и 4 т стали, прибыль от ездки составляет 6 тыс. руб. Необходимо организовать перевозку так, чтобы обеспечить автопредприятию наибольшую прибыль.

Построим математическую модель задачи. Обозначим через х₁ искомое количество ездок КамАЗ-5320 и через х₂ искомое количество ездок ЗИЛ-4314.

Общая перевозка в т изделий из пенобетона составляет 6х₁ + 2х₂, а из стали 2х₁ +4х₂. Ограничения по перевозке, исходя из имеющегося количества изделий, составляют 6х₁ + 2х₂ ≤ 300 т по пенобетону и 2х₁ + 4 х₂ ≤ 200 т по стали.

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

L = 4х₁ + 6х₂ → mах при условиях: 6х₁ + 2х₂ ≤ 300; 2х₁ + 4х₂ ≤ 200; х₁≥0; х₂≥0.

Рассмотрим уравнение 6х₁ + 2х₂ = 300. Чтобы построить прямую, описываемую этим уравнением, найдем две точки, лежащие на этой прямой. При х₁ = 0 из уравнения прямой найдем 2х₂ = 300, откуда х₂ = 150. Следовательно, точка А с координатами (0,150) лежит на искомой прямой. При х₂ = 0 имеем 6х₁ = 300, откуда х₁ = 50, а точка D с координатами (50,0) также находится на искомой прямой. Через эти две точки проводим прямую AD (рис. 3.1).

Линейное неравенство 6х₁ + 2х₂ ≤ 300 представляет собой полуплоскость, расположенную с одной из сторон от построенной прямой 6х₁ + 2х₂ = 300. Чтобы выяснить, с какой стороны от этой прямой расположены точки искомой полуплоскости, подставим в неравенство 6х₁ + 2х₂ ≤ 300 координаты какой-либо точки, не лежащей на граничной прямой. Например, начало координат 0-(0,0). Для него справедливо неравенство 6∙0 + 2∙0 = 0 < 300. Это значит, что начало координат лежит в области допустимых значений, которая находится слева от прямой AD и на рис. 3.1 заштрихована.

Уравнение 2х₁ + 4х₂ = 200 построим по двум точкам. При х₁=0 4х₂ =200, откуда х₂ =50. Тогда точка Е имеет координаты (0,50) и принадлежит искомой прямой. При х₂ = 0, 2х₂ =200, точка с находится на данной прямой с координатами (100,0). Подставив в неравенство координаты точки с (0,0), получим 2∙0 + 4∙0 = 0 < 200. Значит, начало координат находится в области допустимых значений от прямой 2х₁ + 4х₂ = 200.

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

Вершинами многоугольника допустимых решений являются точки O, E, K, D, отрезки прямых OE, EK, KD, OD – его ребра. Любая точка многоугольника OEKD является планом задачи, удовлетворяя все ее условия. Вершины многоугольника образованы пересечением двух прямых и соответствуют опорным планам задачи, среди которых находится и наилучший (оптимальный) план. Таким образом, опорных планов будет столько, сколько вершин у многоугольника допустимых решений.

Наглядное геометрическое представление можно получить и для целевой функции L = 4х₁ + 6х₂. Зафиксируем какое-либо значение целевой функции, например L = 120. уравнение 4х₁ + 6х₂ = 120 определяет прямую, проходящую через точку В с координатами (х₁ = 0; х₂ = 20) и точку L с координатами ((х₁ = 30; х₂ = 0). Отрезок ВL лежит внутри многоугольника OEKD. Следовательно, для всех планов (точек) этого отрезка значение целевой функции одинаково и равно 120. Придавая другие значения целевой функции, получим параллельные прямые, которые называют линиями уровня целевой функции.

Перемещая прямую L параллельно самой себе в одном направлении, получим возрастание целевой функции, а в противоположном направлении – ее убывание. В рассматриваемом примере передвижение прямой ВL вправо определяет возрастание целевой функции, которую мы максимизируем. Так поступаем до тех пор, пока прямая ВL будет иметь хотя бы одну общую точку с многоугольником допустимых решений OEKD. Из рис. 3.1 следует, что последней точкой, которую пересечет прямая уровня целевой функции, будет точка К. Это значит, что точка К определяет оптимальный план задачи.

Н аправление возрастания, перпендикулярное к линии уровня, называется направлением наибольшего возрастания целевой функции и определяет ее максимальный прирост. Это направление можно установить без построения линий уровня. Для этого необходимо на осях х₁ и х₂ отложить отрезки, равные коэффициентам целевой функции, и по ним, как по координатам, построить вектор наибольшего возрастания целевой функции. В математике его называют градиентом и обозначают знаком grad. Градиентом для функции L = 4х₁ + 6х₂ будет вектор n | 4; 6 | . Для удобства его построения увеличим координаты, например, в 10 раз, т.е. n | 40; 60 | . Построим градиент целевой функции L, для чего соединим точку с координатами (40; 60) с началом координат. Линии уровня целевой функции строят перпендикулярно к направлению градиента.

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

6х₁ + 2х₂ = 300;

2х₁ + 4х₂ = 200.

Уравняем коэффициенты при х₁, умножив второе уравнение на 3, и вычтем из второго уравнения первое. Получим 10х₂ = 300, х₂ = 30. Подставив значение х₂ = 30 в любое из уравнений, например в первое, определим значение х₁:

6х₁ + 2х · 30 = 300,

откуда 6х₁ = 300 – 60 = 240, следовательно, х₁ = 40.

Таким образом, чтобы получить наибольшую прибыль автопредприятию, необходимо выполнить 40 ездок на КамАЗ-5320 и 30 ездок на ЗИЛ-4314. Максимальная прибыль при этом составит

L = 4х₁ + 6х₂ = 4 · 40 + 6 · 30 = 340 тыс. руб.

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

1) в двухмерном пространстве область допустимых решений представляет собой многоугольник;

2) каждой стороне многоугольника соответствует значение одной переменной, равной нулю;

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

4) каждому значению целевой функции соответствует прямая;

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

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

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

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

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