Алгоритм симплекс метода

При решении ЗЛП симплекс-метод реализуется в виде так называемой симплекс таблицы. Алгоритм симплекс метода состоит из следующих этапов:

1. Заготавливается исходная симплекс таблица в первом столбце которой располагаются обозначения векторов входящих в базис, во втором столбце коэффициенты C_i ЦФ соответствующие векторам, входящим в базис, а в третьем столбце пишется величина Z₀, где Z₀=∑^m_i=1C_iX_i. Далее идут столбцы соответствующие всем векторам A_j, в этих столбцах записываются координаты этих векторов в рассматриваемом базисе, при этои для векторов входящих в базис эти координаты имеют вид (0,0,0,…,0,1,0,…,0). Здесь: единица стоит в той строке, где находится сам базисный вектор. В дополнительной строке сверху выписывают коэффициенты C_i соответствующие этим векторам. В дополнительной строке снизу пишутся величины Z_j-C_j=∑^m_i=1C_iX_ij-C_{j .} Далее идут этапы которые связаны с преобразованием заготовленной таблицы.

2. рассматривается дополнительная строка снизу:

· если все разности Z_j-C_j<=0, то полученный план является оптимальным (теор. 2)

· если Z_j-C_j>0 для некоторого j, то выбирается столбец с максимальным значением этой разницы. Индекс j определяе вектор вводимый в базис. Пусть max(Z_j-C_j)= Z_i-C_i значитвектор A_i необходимо ввести в базис. Этот вектор называется направляющим, ему соответствует направляющий столбец, который помечают символом «↑»

3. просматриваем направляющий столбец если в нем все x_il<0, то значит ЦФ не ограничена снизу, если есть x_il>0, то находим величину Ө₀=min_i x_i/x_il просматриваются только те дроби для которых x_il>0. Пусть этот минимум достигается для вектора A_k, тогда именно этот вектор подлежит выводу из базиса. Строка соответствующая этому вектору называется направляющей и обозначается «à».

4. После определения направляющих столбца и строки заполняют новую симплекс таблицу. В такой таблице на месте направляющей строки будет стоять A_i . Заполнение новой таблицы начинается с направляющей строки. В качестве компоненты опорного плана туда пишется величина Ө₀ X^’_l=Ө₀=X_k/X_kl, остальные элементы этой строки определяются по формуле X^’_lj X^’_lj=X_kj/X_kl где X_kl элемент находящийся на пересечении направляющих строки и столбца, именно на него делятся все бывшие элементы направляющей строки, а на месте бывшего элемента X_kl автоматически появляется единица. Общее правило для пересчета направляющей строки можно записать так: A_k (новый эл-т направляющей строки)=(старый Эл-т направл. строки)/(эл-т стоящий на пересечении направл. столбца и строки)

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

_· для компонент опорного плана X^’_i=X_i-Ө₀X_il=X_i-(X_k/X_kl)*X_il

_· для компонент разложенных по базису X^’_ij=X_ij-(X_kj/X_kl)*X_il

· для дополнительной строки Z^’_j-C_j=(Z_j-C_j)-(X_kj/X_kl)*(Z_l-C_l)

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

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

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

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

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

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

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

F: C₁X₁=C₂X₂+…+C_nX_nàmin

a₁₁x₁+a₂₁x₂+…+a_n1x_n=b₁

a₁₂x₁+a₂₂x₂+…+a_n2x_n=b₂

…………………………

a_1mx₁+a_2mx₂+…+a_nmx_n=b_m

x_i>=0 V_i=1,n

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

F: C₁X₁+C₂X₂+…+C_nX_n+MX_n=1+MX_n+2+…+MX_n+màmin

a₁₁x₁+a₂₁x₂+…+a_n1x_n+x_n+1=b₁

a₁₂x₁+a₂₂x₂+…+a_n2x_n+x_n+2=b₂

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

a_1mx₁+a_2mx₂+…+a_nmx_n+x_n+m=b_m

X_i>=0 V_i=1,n+m

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

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

Определяем эл-ты дополнительной строки по формулам Z₀=Mb₁+Mb₂+…+Mb_m=∑^m_i=1Mb_i=M∑ⁿ_i=1b_i

Для определения разностей Z_j=a₁₁M+Ma₁₂+…+Ma_1m=M∑^m_j=1a_ij V i=1,n

Z_j-C_j=M∑^m_j=1a_ij-C_j

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

Поскольку М очень большое число, то среди разностей Z_j-C_j будет много положительных чисел. Т. е. будет множество претендентов на введение в базис среди векторов A₁,A₂,…,An

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

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

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

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

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