5. Опорные планы задачи линейного программирования. Соответствие между опорными планами и вершинами многогранника планов.

Рассмотрим задачу: F=c1x1+c2x2+cnxn-max (1) a11x1+…a1nxn<=b1}am1x1+…+amnxn<=bm }(2) xj>=0, ( j=1,n) (3). Чтобы задача 1-3 имела решение (2) должна быть совместной и иметь неотрицательное решение. Это возможно если число линейно-независимых уравнений с-мы ( r ) не больше числа переменных (r<=n). При r=n –с-ма имеет единст. решение; r<n с-ма имеет бесконечное множество решений. Множество векторов а1 и …an будет содержать линейно-независимую подсистему векторов (базис), состоящую из n-векторов. Предположим, что вектор a1..am линейно-независимы, тогда общее решение с-мы (2) может быть получено путем размещения ее относительно переменных х1…хm (базисных переменных). Хi=Bi0-(n-m;J=1)ΣBij*Xj+m ( i=1,m ) (4). Подставим Xi в целевую функцию, получим F= Boo-(n-m; j=1)ΣBoj*Xj+m (5). Базисное решение получается путем подстановки вместо переменных Xj+m (j=1,n-m) нулей. Переменные, которые стоят в правой части (4) называется свободными. Если в базисном решении значение всех базисных переменных неотрицательное, решение называется опорным. Каждому опорному плану (1-3) соответствует вершина многогранника плана и наоборот, каждой вершине многогранника плана соответствует опорный план задачи 1-3. Опорных планов задачи 1-3 не более, чем число сочетаний из m по n , поэтому выбирая все опорные планы можно определить тот, для которого целевая функция принимает экстремальные значения.

6. Основная теорема линейного программирования. Принципиальная схема решения задачи линейного программирования, вытекающая из этой теоремы.

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

7. Общая идея симплексного метода решения задачи линейного программирования. Геометрическая иллюстрация.

Одним из универсальных методов является симплексный (симплекс-метод), называемый так же методом последовательного улучшения плана. Из геометрической интерпретации видно, что экстремум достигается в крайней точки, то есть в ОДР. В основу симплекс – метода положена идея рассмотрения только крайних точек (вершин), а не всё бесконечное множество. Суть метода в том, что в начале получают допустимый план удовлетворяющий всем ограничениям, но не обязательно оптимальный (Начальное опорное решение). Оптимальность достигается последовательным улучшением исходного варианта за определенное число этапов.