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

Геометрическая интерпретация задачи ЛП

Рассмотрим задачу ЛП, система ограничений которой задана в виде неравенств:

F = с₁х₁ + с₂х₂ + . . . + с_nх_n (3. 4)

(3.5)

x_j>=0 (j=1,2,...,n) (3.6)

Совокупность чисел х₁, х₂, . . . х_п,удовлетворяющих ограничениям (3.5) и (3.6), называется решением. Если система неравенств (3.5) при условии (3.6) имеет хотя бы одно решение, она называется совместной, в противном случае - несовместной.

Рассмотрим на плоскости х₁ох₂совместную систему линейных неравенств:

(3,7)

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

Это все равно, что в системе (3.4) - (3.6) положить п=2. Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой а_i1x₁+а_i2x₂=b_i ( i=1, 2, ... m).Условия неотрицательности определяют полуплоскости соответственно с граничными прямыми х₁ =0, х₂=0. Система совместна, поэтому полуплоскости как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы. Совокупность этих точек (решений) будем называть многоугольником решений. Он может быть точкой, отрезком, лучом, многоугольником, неограниченной многоугольной областью.

Если в системе ограничений п=3, то каждое неравенство геометрически представляет полупространство трехмерного пространства, граничная плоскость которого а_i1x₁+а_i2x₂+а_i3x₃=b_i (i=1,2,...m), а условия неотрицательности - полупространства с граничными плоскостями соответственно х_j =0, (j=1,2,...,n). Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений. Многогранник решений может быть точкой, отрезком, лучом, многогранником, многогранной неограниченной областью.

Пусть в системе ограничений п>3; тогда каждое неравенство определяет полупространство п-мерного пространства с граничной гиперплоскостью

а_i1x₁ + а_i2x₂ + ... + а_inx_n = b_i, (i=1,2, ... m), а условия неотрицательности - полупространства с граничными гиперплоскостями х_j =0, (j=1,2,...,n).

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

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

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

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

Теорема 1.Множество всех планов ЗЛП выпукло.

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

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

Однако при больших значениях m ип затруднительно также исследование всех угловых точек. Для этой цели разработаны специальные вычислительные методы.