Главная | Обратная связь

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

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

Пусть задача ЛП задана в двумерном пространстве, т.е. ограничения содержат две переменные.

Найти минимальное значение функции

F = С₁Х₁ + С₂Х₂ (3.9)

при

(3.10)

x₁ >= 0, x₂ >=0 (3.11)

Допустим, что система при условии совместна и ее многоугольник решений ограничен. Каждое из неравенств (3.9)-(3.11), как отмечалось выше, определяет полуплоскость с граничной прямой;

а_i1x₁ + а_i2x₂=b_i, (i=1.m), х₁=0, х₂=0

Линейная функция (2.28) при фиксированных значениях F является уравнением прямой линии: С₁Х₁ + С₂Х₂ = соnst.Построим многоугольник решений системы ограничений (3.10) и график линейной функции (3.9) при F=0(рис.3.1). Тогда поставленной задаче ЛП можно дать следующую интерпретацию. Найти точку многоугольника решений, в которой прямая

С₁Х₁ + С₂Х₂= соnst.является опорной и функция F при этом достигает минимума.

Значения F=С₁Х₁ + С₂Х₂возрастают в направлении вектора N=(C₁, C₂),поэтому прямую F=0 передвигаем параллельно самой себе в направлении вектора N.Из рисунка 3.1 следует, что прямая дважды становится опорной по отношению к многоугольнику решений в точках А и С), причем минимальное значение принимает в точке А. Координаты точки А(х₁;х₂) находим, решая систему уравнений прямых АВ и АЕ.

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

Случай 1.Прямая С₁х₁+С₂х₂ = соnst, передвигаясь в направлении вектора N или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу (рис. 3.2).

Рис. 3.1 Рис. 3.2

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

 

 

а) б) в)

Рис. 3.3

Итак, нахождение решения ЗЛП на основе ее геометрической интерпретации включает следующие этапы:

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

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

3) Находят многоугольник решений.

4) Строят вектор С=(с₁;с₂).

5) Строят прямую с₁х₁+с₂х₂=к, проходящую через многоугольник решений

6) Передвигают прямую с₁х₁+с₂х₂=к в направлении вектора С,в результате чего либо находят точку (точки), в которой целевая функция принимает максимальное значение, либо устанавливают неограниченность сверху функции на множестве планов.

7) Определяют координаты точки максимума функции и вычисляют значение целевой функции в этой точке.

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

Задача. Найти минимальное значение линейной функции

F=4x₁+6x₂ min

при ограничениях

3х₁+х₂ 9,

x₁+2x₂ 8,

x₁+6x₂ 12,

x₁ 0, x₂ 0

Решение. Построим многоугольник решений (рис. 3.4). Для этого в системе координат х₁Ох₂ на плоскости изобразим граничные прямые

3х₁+х₂=9 (L₁);

x₁+2x₂=8, (L₂); x₁ 0, x₂ 0

x₁+6x₂=12 (L₃);

Построим прямую, соответствующую уравнению L₁. Координаты любой точки прямой L₁ удовлетворяют ее уравнению. Прямая разделяет плоскость на две полуплоскости. Если от прямой отступить в одну из плоскостей, то координаты любой точки удовлетворять уравнению не будут. Чтобы установить какой полуплоскости соответствует неравенство надо подставить в него координаты произвольной точки. Удобнее всего использовать начало координат (х₁ и х₂).

3*0 + 0 - 9 < 0

Следовательно, полуплоскость, содержащая начало координат, соответствует неравенству 3х₁+х₂ <9, а вторая полуплоскость неравенству 3х₁+х₂ > 9. Координаты любой точки полуплоскости являются решением соответствующего неравенства, а вся полуплоскость - областью его решений. Отметим, что для нестрогого неравенства (>=, <=), в область решения включается и прямая линия.

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

Причем значение целевой функции F=0. Получим 4х₁+6х₂=0. Геометрическим образом этого уравнения является прямая, проходящая через начало координат. При F=1 уравнение будет 4х₁+6х₂=1 и соответствующая прямая сдвинется от начало координат, но останется параллельна первоначальной прямой. При F=3 прямая отодвинется еще дальше и т.д. Таким образом целевой функции F= 4х₁+6х₂ геометрически соответствует семейство параллельных прямых с разными значениями F. При движении в одну сторону целевая функция увеличивается, в другую уменьшается.

Построим вектор N= (4;6) и прямую 4х₁+6х₂=0 (F). Перемещаем прямую F параллельно самой себе в направлении вектора N. Из рис. 3.5 следует, что она впервые коснется многогранника решений и станет опорной по отношению к нему в угловой точке B; если прямую перемещать далее в направлении вектора N, то значения линейной функции на многограннике решений возрастут, значит, в точке B линейная функция принимает минимальное значение.

Точка B лежит на пересечении прямых L₁иL₂; для определения её координат решим систему уравнений

3х₁+х₂=9,

х₁+2х₂=8.

Имеем: х₁=2; х₂=3. Подставляя найденные значения в линейную функцию, получаем Z_min=4 · 2+6 · 3=8+18=26.