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

ром ограничений. Произвольный вектор-столбец х = = , удовлетворяющий условиям (2.12) и (2.13), назьюается таном (допустимым планом) ЗЛП. Множество всех планов задачи называется допустимым множеством. Если задача (2.11) - (2.13) имеет хотя бы одно решение, то она называется разрешимой, иначе - неразрешимой. Пусть М = [х&Е^: Ах = Ь,х> о] - множество планов ЗЛП. План, геометрически являющийся угловой точкой мно­ жества М, называется опорным таном ЗЛП. План, достав­ ляющий максимум целевой функции, называется оптималь­ ным таном ЗЛП. Поскольку матрица В задаче (2.14) содержит т строк и п столбцов, ее ранг г не превосходит Полагая, что из системы (2.12) исключены линейно зависимые уравне­ ния, будем считать, что г = т. Если г = п, то система (2.12) имеет единственное решение х = , а множество планов М состоит из одной точки (если все компоненты Зс неотрицательны) или пусто (если хотя бы одна из компонент отрицательна). Поэтому будем считать, что г <п . Приведем без доказательства условие спорности плана ЗЛП. Теорема 2.1. План х" задачи (2.11) - (2.13) является опорным в том и только в том случае, если векторы усло­ вий , соответствующие строго положительным ком­ понентам , линейно независимы. 38