![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Базисные и опорные решения
Напомним, что допустимое решение задачи линейного программирования называется планом ( Допустимое решение Вектора линейно-зависимые, если (для трех векторов)
Пример:
· Проверим, опорное это решение или нет:
· В трехмерном пространстве максимум только 3 вектора могут быть независимыми.
·
· Так как определитель равен нулю, вектора линейно-зависимые.
· Положительные компоненты опорного решения называются базисными. Вектора условий линейных компонентов могут быть базисом в пространстве. Базис Опорное решение называется невырожденным, если количество положительных компонент равно числу линейно-независимых ограничений (k=m). Опорное решение называется вырожденным, если количество положительных компонент меньше числа линейно-независимых ограничений (k< m). Нулевые переменные невырожденного опорного решения называются свободными. Матрица, состоящая из векторов при положительных компонентах невырожденного опорного плана, называется базисной. Базисное решение – решение системы уравнений (2) Базисная матрица – матрица из Базисная матрица невырожденного решения определяется однозначно, а базисная матрица вырожденного – неоднозначно. Для определения базисного решения нужно выбрать произвольные
![]() Максимальное количество базисных решений равно Опорное решение – допустимое базисное решение. Для поиска опорных решений можно перебрать все базисные решения и выбрать из них допустимые (с неотрицательными компонентами).
Теорема 3: опорные решения задачи ЛП совпадают с угловыми точками области допустимых решений. Доказательство теоремы смотри в [8].
|