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

К-матрицей КЗЛП будем называть расширенную матрицу системы линейных уравнений, равносильной системе , содержащую единичную подматрицу на месте первых 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’ не пусто, то оно имеет опорный план (или крайнюю точку).