- •1. Задачи нелинейного программирования
- •3. Задачи с ограничениями-равенствами. Метод неопределённых множителей Лагранжа
- •2. Многомерная безусловная оптимизация
- •4. Задачи с ограничениями—неравенствами
- •5. Критерий оптимальности; теорема Куна-Таккера
- •6. Линейное программирование. Различные формы задачи линейного программирования
- •8. Симплекс—таблица и критерий оптимальности. Элементарное преобразование базиса
- •9 Прямой симплекс—метод
- •10 Лексикографический вариант прямого симплекс-метода
- •11 Метод искусственного базиса
- •12. Двойственные задачи линейного программирования. Построение двойственных задач
- •13. Теоремы двойственности
- •7. Базис и базисное решение
7. Базис и базисное решение
Далее рассматривается только задача ЛП в канонической форме (5)-(7). Предположим, что матрица А имеет ранг т (m <= п). Тогда в А имеется т линейно независимых столбцов. Система линейных уравнений (6) совместна и неизбыточна. Пусть Аj = (a1j,..., amj)T , j € J.
Определение. Любой набор Аσ(1),... ,Аσ(m)из т линейно независимых столбцов называется базисом, как и матрица В = [Аσ(1), ..., Аσ(m)], составленная из этих столбцов.
Перестановкой столбцов матрицу А можно привести к виду А = [B,N], где N-подматрица, составленная из остальных столбцов матрицы А. Поступив аналогичным образом с вектором х, получим представление х = (xB xN), где хB = {x σ(1), … ,х σ(т))T
Определение. Переменные xj, являющиеся компонентами вектора хB (соответственно xn), называются базисными (соответственно небазисными).
Определение. Решение системы (6) х = (xB xN) =(B-1 b 0) называют базисным решением (соответствующим базису В).
Утверждение 1. Вектор х — базисное решение системы (6) тогда и только тогда, когда множество столбцов {Аj | xj≠ 0, j € J} матрицы А линейно независимо.
Число базисных решений конечно и не превосходит числа Сmn. Каждому базису соответствует одно базисное решение, но базисному решению может соответствовать несколько базисов.
Определение. Базисным допустимым решением (б. д. р.) называется любой элемент множества X = {х | Ах = b, х >= 0}, являющийся базисным решением системы Ах = b.
Ясно, что решение, соответствующее базису В, является б. д. р. тогда и только тогда, когда В-1b >= 0.
Утверждение 2. Вектор х является базисным допустимым решением тогда и только тогда, когда х есть крайняя точка множества X.
Утверждение 3. Если X ≠ 0, то существует базисное допустимое решение.
Теорема 1 (критерий разрешимости). Задача (5)-(7) разрешима тогда и только тогда, когда X ≠ (пуст. Множ.) и целевая функция w(x) ограничена снизу на множестве X.
Утверждение 4. Если задача ЛП разрешима, то существует оптимальное базисное допустимое решение.