§ 3. Выпуклые многогранные множества и линейное программирование

3.1. Множество задаваемое конечной системой линейных уравнений и неравенств, будем называть выпуклым многогранным множеством.

Это определение (охватывающее и область определения задачи линейного программирования) оправдывается следующей теоремой.

Теорема 3.1. Множество является выпуклым замкнутым множеством.

3.2. Выпуклым многогранником называется ограниченное выпуклое многогранное множество. Область определения задачи линейного программирования часто будем называть также многогранным множеством (или многогранником) планов, опуская слово выпуклое (выпуклый)

3.3. Подмножество выпуклого многогранного множества «называется -мерной гранью если:

а) размерность равна

б) из условий следует, что

При это определение превращается в определен ние крайней точки множества

Крайняя точка выпуклого многогранного множества называется вершиной (опорным планом). Ребро выпуклого многогранного множества — это одномерная грань.

3.4. Теорема 3.2 (теорема о представлении выпуклого многогранника). Произвольный выпуклый многогранник совпадает с совокупностью точек X вида

где вершины многогранника,

Другими словами, содержание теоремы 3.2 можно выразить следующим образом: если -выпуклый многогранник и множество его вершин (опорных планов), то

Теорема 3.2 (теорема о представлении выпуклого многогранного множества). Произвольное многогранное множество совпадает с совокупностью точек X вида

где вершины направляющие векторы неограниченных ребер

Теорема 3.3. Множество состоящее из точек, представимых в виде (3.1) (где произвольная конечная система точек), является выпуклым многогранником.

Теорема 3.3. Множество состоящее из точек, представимых в виде (где произвольная

конечная система точек), является выпуклым многогранным множеством.

3.5. Теорема 3.4. Если множество планов задачи (1.1) -(1.4) не пусто, то среди ее планов имеется хотя бы один опорный план.

Теорема 3.5. Всякая разрешимая задача линейного программирования имеет хотя бы одно опорное решение (опорный оптимальный план).

Теорема 3.6. Если множество планов задачи линейного программирования не пусто и линейная форма задачи ограничена сверху на рассматриваемая задача разрешима, т. е. обладает хотя бы одним решением.

Множество вершин (опорных планов) многогранного множества будем обозначать через

3.6. Определение опорного плана для канонической задачи можно записать следующим образом: план задачи называется опорным, если векторы условий, отвечающие его положительным составляющим, линейно независимы.

Систему линейно независимых векторов условий, включающую все те для которых принято называть базисом опорного плана Компоненты опорного плана, связанные с векторами базиса, иногда называют базисными компонентами (а соответствующие переменные — базисными переменными), а остальные компоненты небазисными компонентами (а соответствующие переменные небазисными переменными).

Если

— опорный план задачи линейного программирования (заданной в каноническом виде), базис опорного плана X,

и

то целевую функцию и все переменные можно линейно выразить через небазисные переменные

(взятые со знаком минус)

Здесь

Введем следующие обозначения:

Таблицу

будем называть симплексной таблицей (полной). Слово «симплексная» часто будем опускать, но это не вызовет каких-либо недоразумений. Таблицу

будем называть сокращенной симплексной таблицей. Следует отметить, что полная симплексная таблица иногда более удобна в теоретических вопросах, сокращенная же симплексная таблица занимает меньше места и поэтому более удобна при практических расчетах.

3.7. Опорный план задачи линейного программирования (1.9) -(1.11) называется невырожденным, если число соотношений системы (1.10) -(1.11), которым он удовлетворяет как равенствам, равно (естественно, эти соотношения должны быть линейно независимыми). В противном случае опорный план называется вырожденным (вырожденный опорный план обращает в равенство более чем соотношений (1.10) — (1.11)).

Задача линейного программирования называется невырожденной, если все ее опорные планы не вырождены. В противном случае задача линейного программирования называется вырожденной.

Определение невырожденного опорного плана задачи линейного программирования, записанной в канонической форме, можно сформулировать следующим образом.

Опорный план X задачи (1.9)-(1.11) называется невырожденным, если все его базисные компоненты положительны. Базис невырожденного опорного плана определяется однозначно. Вырожденному опорному плану может соответствовать несколько базисов.

3.8. Теорема 3.7. Для того чтобы расширенный опорный план был оптимальным, необходимо и достаточно, чтобы нашелся такой базис что

3.9. Пусть линейные ограничения (1.10) задачи (1.9) — (1.11) записаны в виде

соответствующая симплексная таблица,

и

Если

то симплексная таблица называется допустимой, а вектор является опорным планом задачи Если

то симплексная таблица называется нормальной, вектор X называется псевдопланом задачи а вектор X — расширенным псевдопланом задачи