Вычислительная схема симплекс-метода для задачи в базисной форме

Канонической наз-ся задача, где все ограничения с/с имеют форму равенств и все переменные неотрицательны. Частным случаем канонической задачи является задача в базисном виде, которая отличается тем, что все bi>0 (i=1;m) и в каждом уравнении имеются переменные с коэффициентом +1, которые не входят ни в один из других уравнений. Такие переменные называются базисными.

F(X)=C1*X1+C2*X2+…+Cn*Xn+Cn+1*Xn+1+Cn+2*Xn+2+…+Cn+m*Xn+m à max (1)

A11*X1+A12*X2+…A1n*Xn+X(n+1)=B1

A21*X1+A22*X2+…A2n*Xn+X(n+2)=B2 (2)

……………………………………………

Am1*X1+Am2*X2+…Amn*Xn+X(n+m)=Bm

X1>0;X2>0;…Xn>0;X(n+1)>0;X(n+2)>0;…X(n+m)>0 (3)

АЛГОРИТМ:

1. Нажодят первое опрное решение: свободные переменные приравниваются к 0, соответственно базисные пер-е равны правым частям с/с ограничений.

2. Составляют симплекс-таблицу: первые m строк заполняют используя запись задачи в базисной форме и найденный опорный план; в столбце i указываются номера строк; в столбце Б – перечисляются базисные переменные. Соответствующие им коэф-ты целев.ф-ии заносят в столбец Сi, а значение баз.перем-х при рассматриваемом опорном плане, заносят в столбец bi.

В столбцах переменных записывают коэф-ты aij из системы уравнений. Показат-ей (m+1)-й строки вычисляют

F(X)=Sci*bi

Dj=Sci*aij-cj

3.Опорный план проверяют на оптимальность: если все Dj>0, то получен оптимальный план задачи, решаемый на максимум, а если Dj<0, то план для задачи на минимум. Если не все Dj>0 (Dj<0), то переходят к шагу 4.

4.Среди Dj>0 (Dj<0) находим наибольшее по абсолютной величине. Соответствующий столбец называется ключевым, он указывает на переменную, которую необходимо ввести в базис.

Если в ключевом столбце все элементы aij<0, то целевая ф-я задачи не ограничена, решение окончено. Если не все aij<0, то переходят к шагу 5.

5. Для каждого положительного элемента aij ключевого столбца находят qi=bi/aij, записывают полученное значение в столбец и выбирают наим. значение, соответствующая строка называется ключевой, она указывает на переменную, которая из базиса выйдет. На пересечении ключевого столбца и ключевой строки находится ключевой элемент.

6.Составляют новую симплекс-таблицу: в столбце Б на месте ключевой строки предыд. таблицы записывают переменную, соотв-ю ключев.столбцу предыд. таблицы.

Заполняем столбцы Б и Ci: элементы ключ. строки предыд. таблицы делят на ключ. элемент и записывают в новую таблицу на то же самое место.

На месте ключевого элемента получается единица, остальные элементы столбца равны 0.

Далее остальные элементы пересчитываются по правилу прямоугольника.

Для определения показателей оценочной строки можно использовать формулы или правило прямоугольника

Затем переходим к шагу 3 и идем вплоть до того пока не получим необходимый ответ.