Теорема. Якщо В>0, задача (2.4) - (2.6) завжди має розв’язок; він може бути отриманий за кінцеве число кроків.
3. Запишемо (2.5) в іншій формі:
x1 • A1 + x2 • A2 +...+ xn • An = B, (2.7)
де ; ; .... - стовпці матриці А.
Припустимо, що матриця А містить у собі одиничну матрицю порядку m, розташовану в перших m стовпцях А1, А2,...АМ.
Тоді початковий план Х0 має вигляд:
або у вигляді вектора . (2.8)
Перехід від одного плану до іншого здійснюється заміною одного вектора базису на інший, що раніше не входив у базис.
Розв’язок (план) системи (2.5) за умови (2.6) назвемо припустимим.
Ненульовий припустимий розв’язок задачі називається опорним розв’язком (планом), якщо вектори Аj, щовідповідають додатним координатам плану утворюють незалежну лінійну систему. Якщо число векторів у цій системі дорівнює m, план називається не виродженим, якщо менше - виродженим.
План (вектор) X тоді і тільки тоді є опорним розв’язком задачі, коли точка М(х1, х2,...хn) є вершиною припустимого багатогранника.