505. Побудова опорного плану задачі лінійного програмування, перехід до іншого опорного плану.

Розглянемо задачу лінійного програмування, записану в канонічній формі:

.

Не порушуючи загальності, допустимо, що система рівнянь містить перші m одиничних векторів. Отримаємо:

(2.37)

Система обмежень (2.37) у векторній формі матиме вигляд:

де

, ,..., ,

, …, , ,

— лінійно незалежні одиничні вектори m-вимірного простору, що утворюють одиничну матрицю і становлять базис цього простору. Тому в розкладі (2.39) базисними змінними будуть , а інші змінні — вільні. Прирівняємо всі вільні змінні до нуля, тобто . Оскільки , а вектори — одиничні, то отримаємо один із розв’язків системи обмежень (2.37):

тобто допустимий план.