<< Содержание < Предыдущая Следующая >
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) план є кутовою точкою багатогранника розв’язків, а отже, може бути початковим опорним планом.
|