1. Алгоритм решения задачи

Основная идея симплекс-метода состоит в следующем:

1. принимается за базу одна из возможных программ – отправная (опорный план);

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

Решение задач симплекс-методом предусматривает выполнение следующих процедур:

1. формирование целевой функции;

2. определение ограничительных условий – функциональных ограничений, которые могут иметь вид неравенств;

3. преобразование ограничений из неравенств в систему равенств путем ввода вспомогательных, свободных переменных;

4. построение исходной симплекс-матрицы, в которой в формируемый план входят только свободные переменные;

5. ввод в исходный вариант плана реальных переменных и, прежде всего тех, которые в наибольшей степени реализуют целевую функцию, максимизируют ее;

6. определение числового значения вводимой переменной – величины программы.

При этом каждый из показателей, характеризующих ограничительное условие, делится на соответствующий коэффициент при вводимой переменной – удельный расход данного ресурса. Тогда наименьшее частное определит максимально возможное в условиях принятых ограничений использование ресурсов при заданном критерии оптимальности. Полученный результат вводится в соответствующую строку формируемого плана симплексной таблицы. По этой строке матрицы весь ресурс исчерпан, она является «узким местом» и подлежит выводу. На ее место вводится другая строка, предварительно пересчитанная. Формируется новый вариант симплексной таблицы, соответствующей k-итерации.

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

1. значения столбцов, в которых в строке генерального элемента стоит ноль, переносятся в новую матрицу без изменения;

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

Алгоритм решения задачи симплекс-методом включает следующий ряд шагов:

1. Формирование целевой функции и ограничительных условий;

2. Перевод неравенств в систему равенств;

3. Построение исходной симплекс-таблицы (таблица 2);

Таблица 2

Базис	x1	x2	...	xn	xn+1	…	xn+m	bj
xn+1 xn+2 . . xn+m	a11 a21 . . am1	a12 a22 . . am2	… … . . …	a1n a2n . . amn	1 0 . . 0	… … . . …	0 0 . . 1	b1 b2 . . bm
L	C1	C2	…	Cn	0	…	0

4. Проверка: все ли C_j0? Если имеются C_j>0, то переход к шагу 5. Если это условие выполняется, то допустимое базисное решение является оптимальным;

5. В ыбор разрешающего столбца и выбор вводимой переменной по условию:

C_r=maх {C_k}, где k=1, n+m;

6. Проверка: все ли a_ir0 (i=1, m). Если это условие выполняется, то функция считается неограниченной и оптимальное решение найти нельзя, в противоположном случае - переход к шагу 7;

7. Выбор разрешающей строки и выводимой переменной по условию:

D_s=min {b_j/a_ir, только для a_ir>0}, где i=1, m;

8. Пересчет симплекс-таблицы по формулам, и переход к шагу 4.