Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Теоретические основы линейного программирования
Рассмотрим каноническую задачу линейного программирования (КЗЛП)
(2.22) Будем в дальнейшем считать, что ранг матрицы А системы уравнений равен m, причем m< n. Запишем КЗЛП в векторной форме: (2.23) (2.24) (2.25) где - j-й столбец матрицы А. Определение 2.14. Опорным планом (ОП) задачи линейного программирования (КЗЛП) будем называть такой ее план, который является базисным решением системы линейных уравнений . Согласно определению и предположению о том, что r(A)=m, всякому опорному плану задачи линейного программирования (как и всякому базисному решению системы линейных уравнений ) соответствует базисная подматрица В порядка m матрицы А и определенный набор m базисных переменных системы линейных уравнений . Определение 2.15. m компонент базисного решения системы линейных уравнений , являющихся значениями соответствующих ему базисных переменных, будем называть базисными компонентами этого решения. Отметим, что базисные компоненты опорного плана неотрицательны; остальные (n-m) его компонент равны нулю. Очевидно, что число опорных планов задачи линейного программирования конечно и не превышает . Число строго положительных компонент опорного плана не превышает m. Определение 2.16. ОП ЗЛП, число строго положительных компонент которого равно m (), будем называть невырожденным ОП. В противном
случае ОП ЗЛП вырожденный. Определение 2.17. Опорным планом ЗЛП будем называть такой план , что векторы , входящие в разложение со строго положительными , линейно независимы.
|