/span> , ... , х n ); СХ - скалярний твір; Р 1 , Р 2 , ..., Р n і Р 0 - m-мірні вектор-стовпці , складені з коефіцієнтів при невідомих і вільних членах системи рівнянь задачі.
План X = (х 1 , х 2 , ..., х n ) називається опорним планом основного завдання лінійного програмування, якщо система векторів P j , що входять до розкладання (4.6) з позитивними коефіцієнтами x j , лінійно незалежна.
Непорожнє безліч планів основного завдання лінійного програмування утворює опуклий багатогранник. Кожна вершина цього багатогранника визначає опорний план. В одній з вершин багатогранника рішень (тобто для одного з опорних планів) значення цільової функції є максимальним (за умови, що функція обмежена зверху на безлічі планів). Якщо максимальне значення функція приймає більш ніж в одній вершині, то це ж значення вона приймає в будь-якій точці, що є опуклою лінійною комбінацією даних вершин. p align="justify"> Вершину багатогранника рішень, в якій цільова функція приймає максимальне значення, знайти порівняно просто, якщо завдання, записана у формі стандартної, містить не більше двох змінних або завдання, записана у формі основної, містить не більше двох вільних змінних. Haйдем рішення задачі, що складається у визначенні максимального значення функції:
F = c 1 x 1 + з 2 х 2 (4.8)
за умов:
a i1 x 1 + a i2 x 2 ВЈ b i (i = 1, k) (4.9) j Ві 0 (i = 1,2) (4.10)
Кожне з нерівностей (4.9), (4.10) системи обмежень задачі геометрично визначає полуплоскость відповідно з граничними прямими a i1
