Алгебраический метод решения задач

Использование графического метода удобно при решении задач ЛП с двумя переменными.

При большем их числе необходимо применение алгебраического аппарата.

Процесс решения задачи ЛП симплекс-методом носит итерационный характер: однотипные вычислительные процедуры в определённой последовательности выполняются до тех пор, пока не будет получено оптимальное решение.

Стандартная форма линейных оптимизационных моделей

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

Например, Введём остаточную переменную s1>0, тогда.

Правую часть равенства можно сделать неотрицательной, умножив обе части на — 1.

• 2. Значения всех переменных модели неотрицательны.
• 3. Любую переменную yi, не имеющую ограничения в знаке, можно представить как разность двух неотрицательных переменных:

При любом допустимом решении только одна из этих переменных может принимать положительное значение, т.к. если, то, и наоборот. Это позволяет рассматривать как остаточную переменную, а — как избыточную.

• 4. Целевая функция подлежит максимизации или минимизации.
• 5. Максимизация некоторой функции эквивалентна минимизации той же функции, взятой с противоположным знаком, и наоборот.
• 6. Эквивалентность означает, что при одной и той же совокупности ограничений оптимальные значения переменных в обоих случаях будут одинаковы.