Область применения. Графический метод
основан на геометрической интерпретации задачи линейного программирования и
применяется в основном при решении задач двумерного пространства и только
некоторых задач трехмерного пространства, так как довольно трудно построить
многогранник решений, который образуется в результате пересечения
полупространств. Задачу пространства размерности больше трех изобразить
графически вообще невозможно.
Пусть задача линейного программирования задана в двумерном пространстве, т.е. ограничения содержат две переменные.
Найти минимальное значение функции
Z = C1x1 + C2 x2 (2.3.1)
при
a11x1 + a12x2 £ b1,
a21x1 + a22x2 £ b2,
..................................
(2.3.2)
am1x1 + am2x2 £ bm,
x1 ³ 0, x2 ³ 0.
(2.3.3)
Допустим, что система (2.3.2) при условии (2.3.3) совместна и ее многоугольник решений ограничен. Каждое из неравенств (2.3.2) и (2.3.3), как отмечалось выше, определяет полуплоскость с граничной прямой: ai1x1 + ai2x2 = bi (i = 1, 2, ..., m), x1 = 0, x2 = 0. Линейная функция (2.3.1) при фиксированных значениях Z является уравнением прямой линии: C1x1 + C2 x2 = =const. Построим многоугольник решений системы ограничений (2.3.2) и график линейной функции (2.3.1) при Z = 0 (рис.2.2).

Рис. 2.2
Тогда поставленной задаче линейного программирования можно дать следующую интерпретацию. Найти точку многоугольника решений, в которой прямая C1x1 + C2x2 = const является опорной и функция Z при этом достигает минимума.
Значения Z = C1x1 + C2x2 возрастают в направлении вектора N = (C1, C2), поэтому прямую Z = 0 передвигаем параллельно самой себе в направлении вектора N.
Из рис.2.2 следует, что прямая дважды становится опорной по отношению к многоугольнику решений (в точках А, С), причем минимальное значение принимает в точке А. Координаты точки А (x1; x2) находим, решая систему уравнений прямых АВ и АЕ.
Если многоугольник решений представляет собой неограниченную многоугольную область, то возможны два случая.
Случай 1. Прямая C1x1 + C2x2 = const, передвигаясь в направлении вектора N или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу (рис. 2.3).

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


а) б)
в)
Рис. 2.4
Пример 1. (Решить графически). Найти minZ = 2x1 – 10x2 при следующих ограничениях:
x1 - x2 ³ 0,
x1 - 5x2 ³ -5,
x1 ³ 0,
x2 ³ 0.
Решение. Заменив знаки неравенств на знаки равенств, получим
уравнения четырех прямых:
x1 - x2 = 0, (1)
x1 - 5x2 = -5, (2)
x1 =
0, (3)
x2 =
0. (4)
Областью решений данной системы
неравенств является неограниченная фигура
(рис.2.9).
Точки О(0;0), А(х1;х2) являются
вершинами полученной области решений. Так как точка А(х1;х2)
– точка
пересечения двух прямых, то, чтобы найти ее координаты, решаем систему:
x1 - x2 = 0,
x1 - 5x2 =
-5, х1 = х2
= 5/4, А(5/4;5/4).
Рис.2.9
Вычислим значения функции Z в точках О(0;0),
А(5/4;5/4):
ZA = -10; ZO = 0, Zmin = -10.
Решение задач линейного программирования графическим методом,
если n и m связаны соотношением n – m = 2
Вообще, с помощью графического метода может быть решена задача линейного программирования, система ограничений которой содержит n неизвестных и m линейно независимых уравнений, если n и m связаны соотношением n – m = 2. Действительно, пусть поставлена задача линейного программирования.
Найти минимальное значение линейной функции Z = C1x1 + C2 x2 + ... + +Cnxn при ограничениях
a11x1 + a12x2 + ... + a1nxn = b1,
a21x1 + a22x2 + ... + a2nxn = b2,
................................................. (2.3.8)
am1x1 + am2x2
+ ... + amnxn = bm,
xj
³ 0 (j = 1, 2, ... , n),
где все
уравнения линейно независимы
и выполняется соотношение n – m =2.
Используя метод
Жордана – Гаусса, производим m исключений, в
результате которых базисными неизвестными оказались, например, m первых неизвестных x1, x2, ..., xm, а
свободными – два последних: xm+1 и xn, т.е. система
ограничений приняла вид:
x1 + a¢1, m+1 xm+1 + a¢1nxn = b¢1,
x2 + a¢2, m+1 xm+1 + a¢2nxn = b¢2,
............................................... (2.3.9)
xm + a¢m, m+1 xm+1 + a¢mnxn = b¢m
xj
³ 0 (j = 1, 2, ... , n).
С помощью уравнений
преобразованной системы выражаем линейную функцию только через свободные
неизвестные и, учитывая, что все базисные неизвестные – неотрицательные: xj
³ 0 (j =
1, 2, ... , m), отбрасываем их, переходя к системе ограничений, выраженных в
виде неравенств. Таким образом, окончательно получаем следующую задачу.
Найти минимальное значение
линейной функции Z = C¢m+1xm+1 + C¢nxn при ограничениях
a¢1, m+1 xm+1 + a¢1nxn £ b¢1,
a¢2, m+1 xm+1 + a¢2nxn £ b¢2,
.................................................
a¢m, m+1 xm+1 + a¢mnxn £ b¢m,
х m+1 ³ 0,
xn ³ 0.
Преобразованная
задача содержит два неизвестных; решая ее графическим методом, находим
оптимальные значения х m+1, и xn, а затем, подставляя их в (2.3.9), находим
оптимальные значения х1, x2, ..., х m.