Правило решения слау

Для отыскания опорного решения СЛАУ необходимо:

- представить СЛАУ в виде жордановой таблицы так, чтобы все свободные члены были неотрицательными. Если в каком - либо уравнении есть отрицательный свободный член, то это уравнение надо умножить на (-1).

- разрешающие элементы надо выбирать по правилу: а) положительные числа основной части таблицы, лучше равные 1;

б) если таких элементов несколько, то вычислить минимальное симплексное отношение: отношение свободных членов к соответствующим положительным элементам столбца, выбранного разрешающим и выбрать наименьшее отношение;

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

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

- проанализировать полученное решение:

• если появится в ходе исключений строка, все элементы которой равны 0, а свободный член нет, то система несовместна;

• в противном случае система совместна;

• если в верхней строке (заглавной) последней таблицы останется хотя бы одна переменная, то система имеет бесчисленное множество решений;

• если все переменные окажутся в левом заглавном столбце, то решение единственное.

Анализ решения

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

• Если в базисном решении, есть отрицательная переменная, то это решение для задачи ЛП является недопустимым.

Решение любой задачи ЛП можно найти:

а) симплексным методом;

б) методом искусственного базиса.

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

Для нахождения оптимального плана симплекс - методом нобходимо:

1) найти опорный план;

2) составить симплекс - таблицу;

3) выяснить, является ли найденный опорный план оптимальным. Если да, то решение заканчивают. Если нет, то переходят к новому опорному плану.