На начальном шаге алгоритма симплекс-метода должно быть выбрано базисное допустимое решение(X₁ , ..., X_m ) >= 0 при X_j = 0 (j = m+1, ..., n) , следовательно, все свободные члены ограничений A_i,0 >= 0 (i = 1, ..., m) . Когда это условие выполнено, симплекс-таблица называется прямо-допустимой , так как в этом случае базисные переменные, равные A_i,0 , определяют допустимое решение прямой задачи линейного программирования. Если все коэффициенты целевой функции A_0,j >= 0 (j = 1, ..., m) , то симплекс-таблица называется двойственно-допустимой , поскольку соответствующее решение является допустимым для двойственной задачи линейного программирования.

Если симплекс-таблица является одновременно прямо и двойственно допустимой, т.е. одновременно все A_i,0 >= 0 и A_0,j >= 0 , то решение оптимально.

Действительно, поскольку допустимыми являются лишь неотрицательные значения управляемых параметров, то изменение целевой функции за счет вариации свободных переменных, через которые она выражена, возможно только в сторону увеличения, т.e. будет ухудшаться. Если среди ее коэффициентов имеются A_0,j < 0 , то значение целевой функции еще можно уменьшить (т.e. улучшить), увеличивая значение любой свободной переменнойX_j с отрицательным коэффициентом A_0,j при побочном уменьшении базисных переменных, чтобы оставались справедливы ограничения задачи. Теоретически можно использовать любую свободную переменнуюX_j с A_0,j < 0 , но на практике обычно действуют в соответствии со стратегией наискорейшего спуска, выбирая минимальный элемент A_0,p < 0 из всех отрицательных A_0,j <&nbsp0 :

A_0,p = min A_0,j < 0.^j

Столбец p симплекс-таблицы, соответствующий выбранному коэффициенту A_0,p < 0 , называется ведущим столбцом . Свободная переменная ведущего столбца должна быть введена в базис вместо одной из текущих базисных переменных. Очевидно, из базиса следует исключить такую переменную X_q , которая раньше других обращается в нуль при увеличении переменной X_p ведущего столбца.

Её индекс легко определить, если среди положительных элементов ведущего столбца p найти элемент, минимизирующий отношение (A_i,0 / A_i,p ) :

A_q,0 A_i,0 ------ = min ------ , i = 1,...,m.A_{q , p} iA_{i , p}

Элемент A_{q , p} называется ведущим элементом , cтрока q симплекс-таблицы, содержащая ведущий элемент, называется, соответственно, ведущей строкой . Переменная ведущей строки X_q заменяется в базисе переменной ведущего столбца X_p и становится свободной переменной с значением 0, в то время как новая базисная переменнаяX_p достигнет максимально возможного значения, равного: max X_p = ( A_{q ,0} / A_{q , p} ).

После указанного взаимообразного обмена переменными X_p и X_q между наборами свободных и базисных переменных нужно модифицировать исходную каноническую модель задачи путем приведения ее к диагональной форме относительно нового множества базисных переменных. Для указанного преобразования можно формально использовать процедуру исключения Гаусса , которая, как известно, состоит из двух элементарных операций, применяемых к системе алгебраических уравнений ( в данном случае ограничений - равенств):

· умножение уравнения E₁ (X) = 0 на константу K₁ и замена уравнения E₁ (X) = 0 уравнением K₁ *E₁ (X) = 0;

· сложение уравнений E₁ (X) = 0 и E₂ (X) = 0 c последующей заменой уравнения E₂ (X) = 0 уравнением E₁ (X) + E₂ (X) = 0 .

Исключения Гаусса позволяют привести систему уравнений к диагональной форме относительно желаемого множества переменных. В данном случае исключение Гаусса применяется так, чтобы все элементы симплекс-таблицы в ведущем столбце, кроме ведущего элемента A_q,p , стали нулевыми, а ведущий элемент стал равным единице:

A_i,p = 0, если i не равно q

и

A_i,p = 1, если i = q.

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

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

Постановка задачи

На звероферме могут выращиваться норки, выдры и нутрии. Для обеспечения нормальных условий их выращивания используется 3 вида кормов. Количество корма каждого вида, которое должны получать зверьки в среднем приведено в таблице:

Количество единиц корма, которое ежедневно должны получать
Вид корма	Норка	Выдра	Нутрия	Общее количество корма
I	4	2	5	190
II	5	3	4	320
III	7	9	5	454
Прибыль от реализации одной шкурки, руб.	150	320	350

В таблице указано общее количество корма каждого вида, которое может быть использовано зверофермой, и прибыль от реализации одной шкурки зверька.

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

Алгоритм решения задач симплекс – методом

1) Поставленная описательная задача переводится в математическую форму (целевая функция и ограничения).

2) Полученное математическое описание приводят к канонической форме.

3) Каноническую форму приводят к матричному виду.

4) Ищут первое допустимое решение. Для этого матрица должна быть правильной. Матрица в ЗЛП называется правильной, если она содержит минимум m правильных (базисных) столбцов, где m – число строк в матрице. Столбец в канонической ЗЛП называется правильным (базисным), если все его элементы равны нулю, кроме единственного равного единице.

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

6) Строят последовательность матриц. Нужно определить ведущий столбец, ведущую строку и ведущий элемент. Элемент, соответствующий ведущей строке, удаляется из базиса, а на его место ставят элемент, соответствующий ведущему столбцу. Составляют уравнение пересчета матрицы, выполняют пересчет, а затем проверяют его результаты на оптимальность. Если решение не оптимально, то заново ограничивают ведущий элемент, ведущую строку и ведущий столбец.

Признаком оптимальности решения является наличие в векторе решений только отрицательных или нулевых коэффициентов при всех ограничениях.

Ответ записывается следующим образом:

- Каждому отрицательному коэффициенту в векторе решения ставится в соответствие нулевой коэффициент для соответствующей переменной в ответе.

- Для каждого нулевого коэффициента в векторе решения ставится в соответствие значение свободного члена из строки, содержащей единицу в столбце данной переменной.

- Фиктивные переменные в ответе не учитываются.

Ведущим может быть назначен любой столбец, удовлетворяющий одному из условий: