Программирования
Рассмотрим задачу линейного программирования: найти значения переменных хj (j=1, n), обеспечивающих минимальное значение линейной функции вида (3.1) при ограничениях, заданных неравенствами вида (3.7) и (3.8).
Согласно теореме 3.1 и определению 3.1 совокупность чисел х1, х2,..., хn, удовлетворяющих ограничениям (3.7) и (3.8), является допустимым решением задачи линейного программирования. Если система неравенств (3.7) при условии (3.8) имеет хотя бы одно решение, она называется совместной, а в противном случае несовместной.
Рассмотрим случай, когда r = n - m = 2 (то есть, число свободных переменных равно 2, а число базисных переменных - m). Предположим, что свободными переменными являются х 1 и х 2, а базисными - х 3,..., х n, которые выразим через свободные х 1 и х 2.
С учетом условия неотрицательности переменных получим систему ограничений вида:
a11·x1 + a12·x2 ≤ b1,
a21·x1 + a22·x2 ≤ b2 (3.11)
......
am1·x1+ am2·x2 ≤ bm,
x1 ≥ 0, x2 ≥ 0.
Каждое неравенство этой системы на плоскости х1Ох2 (рис. 3.1) геометрически определяет полуплоскость с граничной прямой ai1·x1 + ai2·x2 = bi, (i = 1,m), (условия неотрицательности переменных определяют полуплоскости, соответственно, с граничными прямыми x1= 0, x2= 0). Если система уравнений совместна, полуплоскости, пересекаясь, образуют общую часть называемую областью допустимых решений (ОДР), которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы (3.11). Совокупность этих точек (решений) называется многоугольником решений. Он может быть точкой, отрезком, лучом, многоугольником, неограниченной многоугольной областью.
Если в системе ограничений (3.7) - (3.8) r = 3, то каждое неравенство геометрически представляет полупространство трехмерного пространства с граничной плоскостью ai1·x1 + ai2·x2 + ai3·x3 = bi , (i = 1, m), а условия неотрицательности - полупространства с граничными плоскостями xi = 0, (i = 1, 2, 3).
Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений. Многогранник решений может быть точкой, отрезком, лучом, многоугольником, многогранником, многогранной неограниченной областью.
Если в системе ограничений (3.7) - (3.8) r > 3; то каждое неравенство определяет полупространство n - мерного пространства с граничной гиперплоскостью ai1·x1 + ai2·x2 +... + ain·xn= bi, (i = 1, m). Если система ограничений совместна, то по аналогии с трехмерным пространством она образует общую часть n-мерного пространства, называемую многогранником решений, так как координаты каждой его точки являются решением системы.
Таким образом, геометрически задача линейного программирования представляет собой отыскание такой точки многогранника решений, координаты которой доставляют целевой функции минимальное значение, причем допустимыми решениями являются все точки многогранника решений.
Существуют теоремы.
Теорема 3.2. Множество всех планов задачи линейного программирования выпукло. То есть, во всех случаях отрезок, соединяющий две точки этого множества, целиком относится этому множеству.
Теорема 3.3. Каждому допустимому базисному решению задачи ЛП соответствует угловая точка многогранника решений и, наоборот, каждой угловой точке многогранника решений соответствует допустимое базисное решение задачи ЛП.
Теорема 3.4. Целевая функция задачи линейного программирования достигает своего экстремального значения в угловой точке многогранника решений. Если целевая функция принимает экстремальное значение более, чем в одной угловой точке, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек, то есть, на ребре многоугольника решений, соединяющем эти угловые точки.
Из теорем 3.3 и 3.4 непосредственно вытекает важное следствие: если задача линейного программирования имеет оптимальное решение, то оно совпадает, по крайней мере, с одним из ее допустимых базисных решений, то есть, с одной из угловых точек многогранника решений.
Итак, оптимум линейной функции задачи ЛП следует искать среди конечного числа допустимых базисных решений. Геометрически это соответствует перебору всех угловых точек многогранника решений, что, в конце концов, приведет к оптимальному решению, если оно существует.
Однако, такой перебор практически связан с большими трудностями, так как количество угловых точек (число допустимых базисных решений) может оказаться, хотя и конечно, но чрезвычайно велико. Потому процедура поиска точки оптимума должна быть целенаправленной.
Таким образом, геометрически задача линейного программирования сводится к целенаправленному поиску угловой точки многогранника решений, в которой целевая функция достигает своего экстремального значения.
Для уменьшения количества перебираемых вариантов разработан ряд методов решения задачи линейного программирования.
