4.5. Геометрический метод решения задачи линейного программирования
Рассмотрим
задачу линейного программирования с
двумя переменными
.
Пусть геометрическим изображением системы ограничений является многоугольник (рис.4.1). Чтобы решить задачу необходимо среди вершин этого многоугольника найти вершину, в которой функция цели принимает минимальное значение.
Рис. 4.1. |
Рассмотрим линию уровня линейной функции Q(x), то есть линию вдоль которой эта функция принимает одно и то же фиксированное значение a. График этой линии задается уравнением
|
Для различных значений величины a линии уровня линейной функции параллельны. Одно из свойств линий уровня линейной функции состоит в том, что при параллельном смещении линии в одну сторону значение функции только возрастает, а при смещении в другую сторону – только убывает. Направление, в котором следует осуществлять сдвиг, чтобы достичь меньших значений целевой функции, можно найти построением другой линии уровня. Путем параллельного переноса прямой Q(x)=a в направлении меньших значений целевой функции достигают того, что эта прямая будет пересекать допустимую область решений (многоугольник) по части ее границы – множеству точек Р. (В общем случае параллельная прямая может пересекать допустимую область в одной точке, по отрезку, лучу или прямой.) Все другие допустимые точки лежат на линиях уровня, принадлежащих большим значениям целевой функции. Все точки, лежащие на линиях уровня с меньшими значениями, являются не допустимыми. Таким образом, множество точек Р является множеством оптимальных решений.
Пример. Решить геометрическим методом следующую задачу линейного программирования:
Решение.
На первом этапе построим область допустимых решений – многогранник решений.
Для каждого их заданных неравенств на плоскости строим полуплоскости, то есть множество точек, удовлетворяющих неравенству.
Для
этого, например, построим сначала прямую
.
Эта прямая проходит через точки (0;6) и
(12;0) – точки ее пересечения с осями
координат. Затем возьмем произвольную
точку, не лежащую на этой прямой точка,
например точку (0;0), и проверим, удовлетворяют
ли ее координаты соответствующему
неравенству или нет. Если координаты
точки удовлетворяют неравенству, то
вся полуплоскость, в которой находится
эта точка, является допустимой (по
отношению к этому условию). В противном
случае, полуплоскость является
недопустимой и на рисунке заштриховывается.
Таким же образом поступаем со всеми
неравенствами, заданными в задаче.
В следующей таблице приведены результаты вычисления координат точек, через которые проходят прямые, определяемые неравенствами исходной системы. Получим искомый многогранник решений. На рис. 4.2 многогранник решений изображен в виде заштрихованной области.
Уравнение |
Х1 |
Х2 |
Х1 |
Х2 |
Точка (0,0) |
1 |
0 |
6 |
12 |
0 |
Удовлетворяет неравенству |
2 |
8 |
2 |
8 |
4 |
Удовлетворяет неравенству |
3 |
0 |
3 |
3 |
0 |
Не удовлетворяет неравенству |
Рис. 4.2. |
На втором этапе построим прямые – линии уровня целевой функции, то есть линии, во всех точках которых значение целевой функции постоянно. Для этого выбираем произвольные значения целевой функции, например, Q=10. |
Тогда
точки, в которых целевая функция принимает
значение 10, лежат на прямой
-
линии уровня Q=10.(на
рисунке эта линия обозначена точками).
Все линии уровня, принадлежащие другим
значениям, являются прямыми, параллельными
прямой Q=10.
Направление, в котором следует параллельно
смещать линию уровня, чтобы достичь
меньших значений, определим, построив
линию уровня Q=15.
В следующей таблице приведены результаты вычисления координат точек, через которые проходят выбранные линии.
Уравнение |
Х1 |
Х2 |
Х1 |
Х2 |
Q=10 |
0 |
4 |
10 |
0 |
Q=15 |
0 |
7,5 |
15 |
0 |
Построим по координатам найденных точек линии уровня.
Укажем с помощью линии со стрелкой, перпендикулярной линии уровня, направление уменьшения значений целевой функции.
Путем параллельного переноса линий уровня в направлении меньших значений целевой функции получаем, что множеству P принадлежит одна точка, которая является точкой пересечения прямой, заданной неравенством 3, и прямой х2=0.
Для нахождения координат точки P необходимо решить систему уравнений, содержащую уравнения прямых, на пересечении которых лежит точка P.
Решением этой системы является точка х1=3, х2=0: P = { (3;0) }.
Решением задачи является точка (3;0), в которой целевая функция принимает минимальное значение:
Qmin=3+2,5*0=3.
Все задачи линейного программирования с двумя переменными можно решить при помощи графического метода, объясненного на этом примере.