Симплекс-метод. Основная идея, этапы поиска решений, алгоритм метода.

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

Основная идея симплекс-метода заключается в том, чтобы так переходить от одной вершины ОДР к другой, чтобы при каждом переходе значение ЦФ уменьшалось. Именно так из любой вершины можно добраться до оптимальной и получить оптимальный план.

Например: пусть известен опорный план X =(x1,x2,…,xm,0,0,…,0) и связанная с ним система линейно независимых векторов: А1,А2,…,Аm , тогда для этого опорного плана можно подсчитать значение ЦФ Z=(c1x1+c2x2+…+cmxm) и записать условия ограничения в следующем виде x1A1+x2A2+…+xmAm=b

Поскольку векторы А1,А2,…,Аm линейно независимые любой вектор Aj можно разложить по этим векторам: Aj=x1jA1+x2jA2+…+xmjAm (*) Введем величины Zj Zj=x1jc1+x2jc2+…+xmjcm, где xij коэффициент соответствующий Ai в разложении вектора Aj по базисным векторам

Теорема1: улучшение опорного плана

Если для некоторого индекса j выполняется условие Zj-Cj>0, то можно уменьшить значение ЦФ причем:

· если ЦФ ограничена снизу, то можно построить опорный план с меньшим значением ЦФ, сем предыдущий

· если ЦФ не ограничена снизу, то можно построить план соответствующий сколь угодно малому значению ЦФ

Теорема2: критерий оптимальности опорного плана

Если для некоторого индекса j в опорном плане неравенство Zj-Cj0.

Пусть этот минимум достигается для вектора Ak, тогда именно этот вектор подлежит выводу из базиса. Строка соответствующая этому вектору называется направляющей и обозначается «à».

4. После определения направляющих столбца и строки заполняют новую симплекс таблицу. В такой таблице на месте направляющей строки будет стоять Ai . Заполнение новой таблицы начинается с направляющей строки. В качестве компоненты опорного плана туда пишется величина Ө0 X’l=Ө0=Xk/Xkl, остальные элементы этой строки определяются по формуле X’lj X’lj=Xkj/Xkl где Xkl элемент находящийся на пересечении направляющих строки и столбца, именно на него делятся все бывшие элементы направляющей строки, а на месте бывшего элемента Xkl автоматически появляется единица. Общее правило для пересчета направляющей строки можно записать так: Ak (новый эл-т направляющей строки)=(старый Эл-т направл. строки)/(эл-т стоящий на пересечении направл. столбца и строки)

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

· для компонент опорного плана X’i=Xi-Ө0Xil=Xi-(Xk/Xkl)*Xil

· для компонент разложенных по базису X’ij=Xij-(Xkj/Xkl)*Xil

· для дополнительной строки Z’j-Cj=(Zj-Cj)-(Xkj/Xkl)*(Zl-Cl)

Все эти формулы строятся по одному правилу:

(новый эл-т)=(старый эл-т)-(эл-т новой направл. строки)*(эл-т направл. столбца стоящего в соотв. строке)

После заполнения новой симплекс таблицы осуществляется переход ко второму этапу алгоритма.

Методы природного и искусственного базиса. Основные понятия, алгоритмы методов.

Для большинства задач линейного программирования возникают трудности при их решении связанные с определением исходного опорного плана и исходной симплекс таблицы, с которой начинаются все итерации. Обусловлено это тем, что в реальных задачах среди векторов Ai нет векторов, содержащих только одну не нулевую компоненту, т. е. векторов вида (0,0,0,…,0,1,0,…,0) или их количество не достаточно для формирования базиса.

Т. е. не возможно сформировать природный базис.

Метод искусственного базиса основан на искусственном введении в математическую модель задачи таких векторов.

Пусть задана ЗЛП канонической формы

F: C1X1=C2X2+…+CnXnàmin

a11x1+a21x2+…+an1xn=b1

a12x1+a22x2+…+an2xn=b2

…………………………

a1mx1+a2mx2+…+anmxn=bm

xi>=0 Vi=1,n

Тогда ее преобразовывают к виду

F: C1X1+C2X2+…+CnXn+MXn=1+MXn+2+…+MXn+màmin

a11x1+a21x2+…+an1xn+xn+1=b1

a12x1+a22x2+…+an2xn+xn+2=b2

……………………………….

a1mx1+a2mx2+…+anmxn+xn+m=bm

Xi>=0 Vi=1,n+m

Где М – бесконечно большие числа. В полученной задаче сразу виден исходный базис, в качестве него следует взять вектора при искусственно введенных переменных xn+1, xn+2,…, xn+m. Поскольку именно эти вектора будут иметь вид: (1,0,0,…,0),(0,1,0,…,0),(0,0,…,1). Затем преобразованную задачу решают, используя алгоритм симплекс метода. Исходный опорный план преобразованной задачи имеет вид (0,0,…,0,xn+1,xn+2,…,xn+m)=(0,0,…,0,b1,b2,…,bm). Исходная симплекс таблица выглядит следующим образом

Базис Ai	коэф. ЦФ Ci	План Xi	C1	C2	…	Cn	M	M	…	M
Базис Ai	коэф. ЦФ Ci	План Xi	A1	A2	…	An	An+1	An+2	…	An+m
An+1	M	b1	a11	a21	…	an1	1	0	…	0
An+2	M	b2	a12	a22	…	an2	0	1	…	0
…	…	…	…	…	…	…	…	…	…	…
An+m	M	bm	a1m	a2m	…	anm	0	0	…	1
			Z0

Определяем эл-ты дополнительной строки по формулам Z0=Mb1+Mb2+…+Mbm=∑mi=1Mbi=M∑ni=1bi

Для определения разностей Zj=a11M+Ma12+…+Ma1m=M∑mj=1aij V i=1,n

Zj-Cj=M∑mj=1aij-Cj

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

Поскольку М очень большое число, то среди разностей Zj-Cj будет много положительных чисел. Т. е. будет множество претендентов на введение в базис среди векторов A1,A2,…,An

Если какой-то вектор соответствует искусственно введенным переменным xn+1,xn+2,…,xn+m, то соответствующий вектор выводится из базиса, а столбец симплекс таблицы при этом векторе вычеркивается и больше к нему не возвращаются. В конце преобразования симплекс таблицы возможны два варианта:

· все векторы соответствующие искусственным переменным были выведены из базиса, в этом случае все столбцы симплекс таблицы соответствующие дополнительным переменным исчезнут, и будет решаться исходная задача

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

Двойственные задачи линейного программирования. Постановка задач, их свойства.

Симметричные двойственные задачи:

Первая стандартная форма

f(x)=c1x1+c2x2+…+cnxnàmin