Общий алгоритм решения задач линейного программирования

Без ограничения общности имеем следующую задачу линейного программирования:

,                    (4.1)

.

Найти среди допустимых , j = 1, 2, ..., n, такие, что:

.

Основные шаги решения сформулированной задачи следующие.

1. Находится хотя бы одно из неотрицательных решений .

2. Подставляем в систему полученное решение, в результате чего получаем новую систему, эквивалентную исходной:

.

3. Подставляем выражения основных переменных в L:

.

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

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

Возникает вопрос. Как найти хотя бы одно неотрицательное решение системы (4.1)?

Сводим исходную систему (4.1) к виду:

, i = 1, 2, ..., m.                                          (4.2)

Если в этой системе имеется переменная, входящая только в одно уравнение, и коэффициент при ней имеет знак «+», то уравнение можно разрешить относительно этой переменной.

Считаем, что в (4.2) уравнения разрешены относительно всех таких переменных, тогда, сделав перенумерацию, имеем:

       (4.3)

l = 1, 2, ..., l₀;  = 1, 2, ..., ₀;

l₀ + ₀ = m; l₀ + k = n; .

Любое уравнение в (4.3), неразрешенное относительно какой-либо переменной, будем называть 0-уравнением.

Для системы (4.3) неотрицательное решение отыскивается последовательными тождественными преобразованиями, удовлетворяющими следующим условиям:

1. Отыскиваем 0-уравнение, у которого свободный член  (если такого свободного члена нет, то значения переменных xl = bl, , l = 1, 2, ..., l0; j = 1, 2, ..., k образуют неотрицательное решение системы (4.3)). Пусть это будет i-ое уравнение.

2. Отмечаем в i-ом уравнении положительный коэффициент .

3. Находим разрешающий элемент  и производим торжествен­ное преобразование (4.3).

4. i-ое 0-уравнение используется до тех пор, пока либо разрешим его, либо придем к несовместимости системы (4.3).

5. После разрешения i-го уравнения отыскиваем следующее 0-уравнение с положительным свободным членом и производим с ним аналогичные действия.

6. Процесс продолжается до тех пор, пока не освободимся от всех 0-уравнений.

В результате можем получить:

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

б) После конечного числа тождественных преобразований обнаружится, что используемое 0-уравнение превращается в уравнение вида:

,

где , т.е. для всех j - система несовместна;

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