Введение в методы оптимизации

Приведем еще одну важную теорему об опорных пла­ нах. Теорема 2.2. Если множество планов М задачи (2.11) - (2.13) непусто, то соответствующая ЗЛП имеет хотя бы один опор­ ный план. Если при этом целевая функция f{x) ограничена сверху на М, то ЗЛП разрешима и среди ее оптимальных планов имеется хотя бы один опорный. Базисом опорного плана х ° называется любая система из т линейно независимых векторов ,i = 1,т , в число ко­ торых включены все векторы условий, соответствующие строго положительным компонентам данного опорного пла­ на. Матрица ^ называется базисной матри­ цей опорного плана х". Из теоремы 2.1 следует, что число строго положительных компонент любого опорного плана не превосходит т, поскольку количество линейно независимых векторов условий A j не может быть больше их размерности. Если х" - опорный план, J - его базисная матрица, то компоненты = называются базисными компонентами опорного плана, а остальные - небазисными. Небазисные компоненты всегда равны нулю, Опорный план называется невыроэюденным, если число его строго положительных компонент равно т, вырожден­ ным - если меньше т. Невырожденный опорный план имеет единственный базис, все его базисные компоненты строго положительны. Вырожденный опорный план имеет несколько базисов, некоторые из базисных компонент тшсого плана рав­ ны нулю. Задача (2.11) - (2,13) называется невырожденной, 39