Линейное программирование. Геометрическая интерпретация и графический метод решения задачи линейного программирования, страница 3

  a_i1x₁+ a_i2x₂+…+ a_inx_n = b_i    (i=1, …, m)

                                                        x_j = 0    (j=1, …, n)

Если эта система ограничений совместна, то она образует общую часть n-мерного пространства. Такая область представляет собой пересечение множеств, являющихся полупространствами n-мерного пространств.

З а м е ч а н и е 2.6. Рассматриваемое пересечение полупространств  может быть как ограниченным, так и неограниченным множеством. В связи с этим используются следующие терминологии. Ряд авторов считает [4,7], что в случае неограниченности множества его следует называть (выпуклым) многогранным множеством, а при  ограниченности – многогранником. Другие авторы, например [6], называют такую область во всех случаях  многогранником, но считают, что она может быть как ограниченной, так и неограниченной. Мы будем придерживаться второй точки зрения.

З а м е ч а н и е 2.7. Ограниченность и неограниченность множеств не следует путать с их замкнутостью (закрытостью) и открытостью. Второй вид деления обусловлен характером неравенств, задающих множества  (видами  “ £  “ ,   “ ³ ”  и  “< ” ,  “ > ” соответственно ).

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

Таким образом, в задаче ЛП область допустимых решений представляет собой  многогранник решений (для n=2 - многоугольник решений).

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

Графический метод решения задачи ЛП основан на ее геометрической интерпретации и применяется при решении задач в стандартной форме при n=2.

З а м е ч а н и е 2.8. Графический метод применим также и для решения задач ЛП в канонической форме при n>2 при выполнении соотношения  m = n-2 [6,13].

Рассмотрим целевую функцию двух переменных.

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

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

Рассмотрим следующий пример. Пусть ограничение задачи ЛП заданы соотношениями (2.6), а максимизируемая целевая функция  имеет вид z = x₁+ x₂.

Воспользуемся многогранником решений, приведенным на рисунке 2.1. Положив z=0, построим соответствующую этому значению прямую (рисунок 2.2). Построим затем прямую, соответствующую значению z=3. Эти две прямые позволяют определить требуемое направление перемещения линий, обеспечивающее возрастание функции z.

Для определения угла наклона прямой и направления ее перемещения можно воспользоваться также вектором нормали  Nпрямой (см. рис. 2.2). Его координаты соответствуют значениям коэффициентов целевой функции z - (c₁, c₂) (в рассматриваемом примере – (1;1)). Прямые равного уровня z перпендикулярны этому вектору, а направление вектора указывает направление возрастанияz.