Экономико-математическое моделирование в химии и экологии. Бутырская Е.В - 14 стр.

                                              14
� n
�   ∑ aij x j ≤bi   (i =1,2,..., k )
� j =1
� n
 �
�   ∑ aij x j =bi   (i =k +1, k +2,..., m )
� j
 x j ≥0 ( j =1,2,..., l; l ≤n).
и линейная функция
F =c1 x1 +c2 x2 + +cn x n
Алгоритм пошагового симплекс-метода в общем случае заключается в
следующем:
1. Систему ограничений записывают в каноническом виде, т.е. введением
дополнительных      неотрицательных     переменных     неравенства    системы
ограничений превращают в равенства.
2. В полученной системе ограничений выбирают m переменных за основные
переменные и оставшиеся n – m за неосновные переменные. Основными могут
быть переменные, если определитель, составленный из коэффициентов при
этих переменных, отличен от 0.
3. Выражают основные переменные через неосновные переменные, такая
запись называется общим решением системы ограничений в базисе основных
переменных.
4. Проверяют, является ли выбранное решение допустимым. Для этого в общем
решении, полученном на предыдущем шаге, полагают неосновные переменные
равными нулю и вычисляют получившиеся при этом значения основных
переменных. Решение, при котором неосновные переменные равны нулю, а
основные переменные неотрицательны, называется допустимым базисным
решением. Решение, при котором неосновные переменные равны нулю, а среди
основных переменных имеются отрицательные, называется недопустимым
базисным решением.
5. Если полученное в п.4 решение является недопустимым базисным решением,
то от полученного недопустимого базисного решения переходят к допустимому
базисному решению или устанавливают, что система ограничений
противоречива, т.е. задача не имеет решения.
6. Если в п.4 получено допустимое базисное решение, то функцию цели
выражают через неосновные переменные и проверяют, выполнен ли критерий
оптимальности решения. А именно: критерий оптимальности решения при
отыскании максимума линейной функции: если в выражении функции цели
через неосновные переменные отсутствуют положительные коэффициенты при
неосновных переменных, то решение оптимально. Критерий оптимальности
решения при отыскании минимума линейной функции: если в выражении
функции цели через неосновные переменные отсутствуют отрицательные
коэффициенты при неосновных переменных, то решение оптимально.
7. Если критерий оптимальности не выполнен, то переходят к новому
допустимому базисному решению до тех пор, пока критерий оптимальности не
будет выполнен или не будет установлено, что задача не имеет решения.