2.8.1. Початковий опорний план

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

.

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

(2.36)

(2.37)

(2.38)

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

, (2.39)

де

, ,..., ,

, …, , ,

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

(2.40)

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

Такому плану відповідає розклад

(2.41)

де — лінійно незалежні вектори і за властивістю 3 розв’язків задачі лінійного програмування (§ 2.5) план є кутовою точкою багатогранника розв’язків, а отже, може бути початковим опорним планом.