ПЗ 9. Симплекс-метод решения задач линейного программирования

1. В системе ограничений (уравнений или неравенств) переносят свободные члены в правые части. Если среди этих свободных членов окажутся отрицательные, то соответствующее уравнение или неравенство умножают на - 1.

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

3. В данной или полученной после выполнения п. 2 этого алгоритма системе m уравнений с n переменными (m < n) m переменных принимают за основные. Основными могут быть любые m переменных, коэффициенты при которых образуют отличный от нуля определитель. Проще всего в качестве основных взять добавочные переменные (в этом случае отпадает необходимость вычислять определитель, который заведомо отличен от нуля, так как каждая добавочная переменная входит только в одно из уравнений системы ограничений).

После этого выражают основные переменные через неосновные и находят соответствующее базисное решение.

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

4. От полученного недопустимого базисного решения переходят к допустимому базисному решению или устанавливают, что система ограничений данной задачи противоречива. В отдельной статье разобран случай, когда система не имеет ни одного решения.

5. Получив допустимое базисное решение, выражают через неосновные переменные этого решения линейную форму. Если отыскивается максимум (минимум) линейной формы и в её выражении нет неосновных переменных с положительными (отрицательными) коэффициентами, то критерий оптимальности выполнен и полученное базисное решение служит оптимальным, т. е. решение окончено. В отдельных статьях разобраны случаи, когда максимум целевой функции - бесконечность и когда оптимальное решение - не единственное.

6. Если при нахождении максимума (минимума) линейной формы в её выражении имеется одна или несколько неосновных переменных с положительными (отрицательными) коэффициентами, то переходят к новому базисному решению.

Из неосновных переменных, входящих в линейную форму с положительными (отрицательными) коэффициентами, выбирают ту, которой соответствует наибольший (наибольший по абсолютной величине, то есть по модулю, отрицательный) коэффициент, и переводят её в основные.

7. Чтобы решить, какую из основных переменных следует перевести в неосновные, находят абсолютные величины отношений свободных членов уравнений к коэффициентам при переменной, переводимой в основные, причём только из тех уравнений, в которых эти коэффициенты отрицательны. Для уравнений, в которых указанные коэффициенты положительны или равны нулю (переменная, переводимая в основные, в них отсутствует), эти отношения считают равными бесконечности. Из найденных отношений выбирают наименьшее и тем самым решают, какая из основных переменных перейдёт в неосновные. Соответствующее уравнение выделяют.

8. Выражают новые основные переменные и линейную форму через неосновные переменные (это начинают делать с выделенного уравнения).

9. Повторяют пункты 6-8 этого алгоритма до тех пор, пока не будет достигунт критерий оптимальности (см. п. 5 этого алгоритма). После этого выписывают компоненты оптимального решения и находят оптимум (максимум или минимум) линейной формы.

10. Если допустимое базисное решение даёт оптимум линейной формы (критерий оптимальности выполнен), а в выражении линейной формы через неосновные переменные отсутствует хотя бы одна из них, то полученное оптимальное решение - не единственное.

11. Если в выражении линейной формы имеется неосновная переменная с положительным коэффициентом в случае её максимизации (с отрицательным - в случае минимизации), а во все уравнения системы ограничений этого шага указанная переменная входит с положительными коэффициентами или отсутствует, то линейная форма не ограничена при данной системе ограничений. В этом случае её максимальное (минимальное) значение записывают в виде .