Лекция: Дайте определение К-матрицы КЗЛП.

К-матрицей КЗЛП будем называть расширенную матрицу системы линейных уравнений, равносильной системе, содержащую единичную подматрицу на месте первых n своих столбцов и все элементы ( n+1 )-го столбца которой неотрицательны.

Число К-матриц конечно и не превышает. Каждая К-матрица определяет ОП КЗЛП и наоборот.

Сформулируйте связь между опорным планом и К-матрицей.

Каждая К-матрица определяет ОП КЗЛП и наоборот.

23 Число опорных планов конечно или нет?

Число опорных планов задачи линейного программирования конечно и не превышает. Число строго положительных компонент опорного плана не превышает m.

24 Какого числа не превышает количество опорных планов КЗЛП?

Число опорных планов задачи линейного программирования конечно и не превышает. Число строго положительных компонент опорного плана не превышает m.

m -ранг матрицы А системы уравнений, причем m < n.

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

Отметим, что базисные компоненты опорного плана неотрицательны; остальные n-m его компонент равны нулю.

Сформулируйте связь между опорным планом и крайней точкой.

Теорема (о крайней точке). Опорный план ЗЛП является крайней точкой множества P’ и наоборот.

Следствие 1. Крайняя точка множества P’ может иметь не более m строго положительных компонент.

Следствие 2. Число крайних точек множества P’ конечно и не превышает .

Следствие 3. Если множество P’ ограниченное, то оно является выпуклым многогранником.

Сформулируйте утверждение о существовании оптимального опорного плана.

Теорема 3.3 (о существовании опорного плана или решения ЗЛП). Если линейная форма ограничена сверху на непустом множестве P’, то ЗЛП разрешима, то есть существует такая точка, что .

Теорема 3.4. Если множество P’ не пусто, то оно имеет опорный план (или крайнюю точку).