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. Основная теорема лп. Принципиальная схема решения злп, вытекающая из этой теоремы.

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

БП	1	СП -Xm+1 -Xm+2 -Xn
х1	b1o	b11 b12 b1n-m
х2	b2o	b21 b22 b2n-m
хm	bm	bm1 bm2 bmn-m
f	boo	bo1 bo2 bon-m

7. Симплексный метод решения злп. Общая идея симплекс-метода.

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

f=(n; j=1)ΣCj*Xj (max)

(n;j=1)Σaij*xj=aio (i=1,m)

Xj>=0 (j=1,n)

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

Общая идея симпл.метода состоит в том что симпл. м-д разбивается на 2 этапа:

1. нахождение начального опорного плана;

2. последовательное улучшение вплоть до нахождения оптимального, в котором целевая функция достигает максим.значения.