Из эквивалентности алгебраического понятия опорного плана геометрическому понятию вершины многогранника вытекает очевидное следствие.
С л е д с т в и е 2.1. Каждая вершина многогранника X имеет не более m положительных координат.
Итак, если целевая функция задачи ЛП ограничена на выпуклом многогранном множестве, заданном условиями задачи, то существует крайняя точка (опорный план) этого множества, в котором целевая функция достигает максимума. Поэтому для решения задачи линейного программирования необходимо исследовать только вершины многогранного множества – опорные планы задачи линейного программирования. В этом и состоит основная идея симплекс-метода решения задач линейного программирования.
З а м е ч а н и е 2.11. Поскольку в задаче ЛП наибольшее или наименьшее значение целевой функции достигается границах областей изменения переменных оптимизации, то, следовательно, в такой задаче находится не экстремум, а оптимум.
2.5. Симплекс-метод
2.5.1. Предварительные сведения
Основным методом решения задач ЛП до настоящего времени остается симплекс-метод. Он разработан для задачи в канонической форме записи (2.4) или (2.8) – (2.10) (точнее, для задачи в канонической базисной форме).
З а м е ч а н и е 2.12. Симплексом называется многогранник в n-мерном пространстве, имеющий n +1 вершину [2,25,26]. Именно ОДР такого вида была в одной из первых задач, для которой был применен этот метод. Впоследствии это название сохранилось за методом независимо от формы линейных ограничений.
В канонических задачах ограничения задаются системой линейных алгебраических уравнений (вида AX=B или вида (2.9), в которых число уравнений меньше числа неизвестных т.е. m < n). Поскольку преобразования таких систем лежат в основе симплекс-метода, то приведем сначала необходимые сведения о методе решения таких систем уравнений.
Будем полагать далее для определенности, что ранг матрицы системы уравнений равен количеству уравнений m. Тогда если такая система совместна, то у нее существует бесчисленное множество решений.
Эти решения получаются следующим образом: n-m переменным придаются произвольные значения (они называются свободнымипеременными), а остальные m переменных выражаются через них (они называются базисными переменными).
Множество решений системы AX=B в рассматриваемом случае может быть представлено в виде
x1 = y1(xm+1, …, xn)
x2 = y2(xm+1, …, xn)
. . . . . . . . . . . . . . . . (2.11)
xm = ym(xm+1, …, xn) , где x1, x2, …, xm – базисные переменные, а y1, …, ym – линейные комбинации свободных переменных xm+1, xm+2, …, xn.
З а м е ч а н и е 2.13. В (2.11) базисными являются первые m переменных в их последовательной нумерации x1, x2, …,xm,…,xn. В общем случае базисные переменные могут иметь любые номера.
Выражение (2.11) задает общий вид решения системы уравнений при n < m.
Пример 2.1. Система линейных уравнений
2x1 – x2 + 2x3 + x4 = 1
x1 + x2 - x3 + 3x4 = 5
3x1 – x2 + 3x3 - x4 = 5
c помощью специальных эквивалентных преобразований может быть представлена в виде (2.11), описывающем множество ее решений:
x1 = 1 - x4
x2 = 7 - 5x4
x3 = 3 - 5x4 .
Здесь переменные x1, x2 , x3 – базисные, а x 4 – свободная.
При решении системы свободным переменным придают любые значения, а затем по соотношениям (2.11) находят соответствующие значения базисных переменных. Каждый полученный таким образом набор значений переменных (x1, x2, … , xm , xm+1 ,…, xn ) определяет отдельное частное решение системы уравнений AX=B.
Определение 2.3. Частное решение системы уравнений, в котором свободные неизвестные равны нулю, называется базисным.
В примере 2.1 базисное решение системы имеет следующие компоненты: x1 = 1, x2 = 7, x3 = 3, x4 = 0.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.