Теорема 1: (основная теорема линейного программирования):

1)     Линейная форма  достигает своего минимума в угловой точке многогранника решений.

2)     Если она принимает минимальное решение более чем в одной угловой точке, то она достигает того же самого значения в любой точке, являющейся выпуклой комбинацией этих угловых точек.

Доказательство: Доказательство теоремы основано на следующей лемме.

Лемма: Если  - замкнутое, ограни­ченное, выпуклое множество, имеющее конечное число крайних (угловых) точек, то любая точка  может быть представлена в виде выпуклой комбинации крайних точек .

1) Пусть - некоторая внутренняя точка. Многогранник ограниченный замкнутый, имеет конечное число угловых точек.  - допустимое множество.

Предположим, что точка  является опти­мальной точкой, то есть  ,  . Предположим, что точка  не является угловой. Тогда на основании леммы точку  можно выразить через угловые точки многогранника , т.е. ,  ,  .

Так как функция  линейна, то

.                                                   (*)

Выберем среди точек  ту, в которой линейная форма  принимает наименьшее значение. Пусть это будет точка . Обозначим минимальное значение функции в угловой точке через : .

Подставим данное значение функции в линейную форму (*) вместо и получим:  .

Так как  - оптимальная точка, то получили противоречие:  (!). Следовательно, ,  - угловая точка.

2) Предположим, что линейная форма  принимает минимальное значение более чем в одной угловой точке, например, в угловых точках  . Тогда если  является выпуклой комбинацией этих точек, то есть  ,    и   , то .

То есть, если минимальное значение достигается более чем в одной угловой точке, то того же самого значения линейная форма достигает в любой точке, являющейся выпуклой комбинацией этих угловых точек