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

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

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

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

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

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

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

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

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

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

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

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

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

1) Первый столбец, содержащий положительный элемент в векторе решений.

2) Столбец, содержащий наибольший положительный элемент в строке решения.

3) Если столбец удовлетворяет условию max(C_j min b_j/a_ij) при решении на max, и min(C_j min b_j/a_ij) при решении задач на min.

C_j – коэффициент целевой функции в столбце j, a_ij – коэффициент в столбце j и строке i.