Рассмотрим задачу ЛП в канонической форме
или в матричном виде
Где
Введем предположения.
1. Система уравнений (15) линейно независимая. В противном случае необходимо привести уравнения (15) к линейной независимости.
2.Если число уравнений в (15) меньше числа неизвестных, т.е. m<n, то система (15) может иметь только единственное решение, которое в случае допустимости (выполнение условий (16)) будет и оптимальным. Это тривиальный случай.
Обозначим
- столбцы матрицы А,
допустимая область задачи ЛП.
Вектор 
называется допустимым
базисным решением (опорным планом)
канонической задачи ЛП (14), (15), (16), если система
вектор-столбцов 
,
соответствующих ненулевым компонентам
вектора х, является линейно независимой.
Наряду с введенными предположениями
предположим еще, что
Это предположение не ограничивает
общности, поскольку, если
то, умножая соответствующее
уравнение на -1, получим в правой части
При сделанных предположениях можно выбрать m неизвестных (к примеру x1,...,xm)
таких, чтобы определитель, составленный из коэффициентов при этих неизвестных, не обращался в нуль, и задача (14)-(16) может быть приведена к виду
Одно из допустимых решений этой задачи можно найти, если переменные
положить равными нулю. Тогда решение
очевидно будет допустимым базисным решением, поскольку система векторов-столбцов
линейно-независимая. Переменные
- называют базисными,
набор переменных
- называют базисом, а
переменные
- называют небазисными или
свободными.
Число возможных базисов в задаче размерности
n с m ограничениями не превосходит
величину 
(число
различных
базисов по m переменных из n переменных).
Рассмотрим задачу ЛП.
Вектор х=(0, 0, 1, 3)
1) допустим, так как при подстановке в ограничения задачи получаются тождества ;
2) базисный, так как система векторов
линейно независимая (определитель матрицы, составленной из этих векторов, не равен нулю).
Теорема о базисных решениях и
крайних точках
Множество допустимых решений Мв задачи ЛП совпадает с множеством крайних точек Мк многогранной допустимой области.
Доказательство.
Доказательство состоит из двух частей :
Часть1 Пусть х- произвольное допустимое базисное решение, необходимо доказать, что х является крайней точкой.
Предположим противное, т.е. х- не крайняя
точка. Тогда существует отрезок из допустимой
области, на котором находится точка х. Пусть 
допустимые
точки, являющиеся концами отрезка.
Тогда
Пусть базисное решение х определяется системой
Тогда
допустимое базисное
решение и
Но тогда из системы (*) следует, что
Это означает, что не существует
отрезка, на котором лежала бы базисная точка.
Поэтому предположение было неверным, и
допустимое базисное решение является крайней
точкой, т.е. 
.
Часть 2 Пусть х - произвольная крайняя точка. Необходимо доказать, что х является допустимым базисным решением.
Предположим противное, т.е. х -
недопустимое базисное решение. Тогда для
ненулевых компонент вектора х система
вектор-столбцов 
линейно зависима. Пусть 
Линейная зависимость 
означает, что
существуют
для которых выполняется равенство
С другой стороны,
из допустимости вектора х имеем равенство
Это означает, что точка
является пересечением тех же
гиперплоскостей, что и у
точки х (совпадение ненулевых компонент означает
совпадение гиперплоскостей, проходящих через
точку). Но точка х - крайняя точка, это означает,
что соответствующие ей гиперплоскости имеют
только одну точку пересечения. Поэтому должно
выполняться х'=х, а значит все
Получили противоречие. Следовательно, предположение было неверным, и крайняя точка является допустимым базисным решением.
Теорема доказана.
Данная теорема позволяет уточнить путь решения задачи ЛП : перебор крайних точек есть перебор базисных допустимых решений и оптимальное решение должно находиться среди допустимых базисных решений, число которых конечно (не превосходит величину
).Можно
найти все допустимые базисные решения и для
каждого вычислить значение целевой функции L .
Оптимальным решением будет то из найденных
решений, для которого значение L будет
минимально.
Такой путь решения задачи хотя и возможен, но весьма трудоемок, так как число допустимых базисных решений может быть весьма большим. Однако существуют рациональные способы последовательного перебора базисных решений, которые позволяет рассматривать не все допустимые базисные решения, а их минимальное число. К таким методам и относится симплекс-метод[1, 2, 3].
Замечание
Поскольку оптимальное решение задачи ЛП является базисным допустимым решением, то число ненулевых переменных в оптимальном решении совпадает с числом ограничений задачи ЛП. Так, если задача ЛП имеет одно ограничение, то в оптимальном решении будет только одна ненулевая переменная. Увеличение числа независимых ограничений влечет увеличение числа ненулевых переменных в оптимальном решении, что в свою очередь может привести к ухудшению значения целевой функции.