1.2. Основные определения

Рассмотрим ЗЛП в стандартной форме (1.14) и ЗЛП в канонической форме (1.15).

(1.14.) (1.15)

Определение 1. Множество векторов называется множеством допустимых планов задачи (1.14) или допустимым множеством.

Определение 2. Множество векторов называется множеством допустимых планов задачи (1.15) или допустимым множеством.

В дальнейшем элемент допустимого множества мы иногда будем называть просто планом.

Определение 3. Вектор (из множества допустимых планов) называется оптимальным планом задачи (1.14), или задачи (1.15), если для любого вектора x из допустимого множества выполняется неравенство C(x)  C (x^*).

Определение 4. Пусть – допустимый план ЗЛП (1.14) или (1.15). Носителем плана x называется множество индексов

Замечание. Неотрицательные переменные в допустимом плане могут быть расположены в произвольном порядке.

Определение 5. Число положительных компонент плана x будем называть мощностью носителя плана и обозначать или .

Определение 6. Если векторы , а m – число уравнений ЗЛП (1.15), являются линейно независимыми векторами, то будем говорить, что данные векторы образуют базис ЗЛП.

Обозначим множество индексов через , тогда базис будем обозначать таким образом или просто А_ . Через А_ будем обозначать также квадратную матрицу, составленную из множества линейно независимых векторов . Векторы A_k называются базисными векторами, а сама матрица А_ называется базисной матрицей.

Напомним определение линейно независимых векторов.

Определение 7. Рассмотрим векторы , где k некоторое целое число. Если равенство возможно только в том случае, когда числа , то векторы A₁, A₂, …, A_k называются линейно независимыми. Векторы A₁, A₂, …, A_k могут быть линейно независимыми только, если k  m.

Рассмотрим теперь каноническую форму записи ЗЛП (1.16).

(1.16)

где вектор .

Определение 8. Пусть – допустимый план ЗЛП (1.16) и  – его носитель. Если векторы A_i , i, линейно независимые, то план x называется базисным допустимым планом (БДП) или базисным допустимым решением (БДР).

Базисный план называется невырожденным, если =m. Базисный план называется вырожденным, если < m.

П р и м е р. Рассмотрим ЗЛП следующего вида:

Приведем ее к канонической форме записи:

В данной задаче имеются следующие векторы:

; ; ; .

Их анализ показывает, что A₃, A₄ – единичные векторы, которые являются линейно независимыми, следовательно, они образуют базис ЗЛП. Вектор x = (0, 0, 18, 2) является допустимым планом, поскольку выполняются все ограничения задачи. К тому же он базисный, так как его ненулевые компоненты (координаты) соответствуют базисным векторам. Итак, вектор x = (0, 0, 18, 2) – это БДП.