Анализ ограничений по ресурсам

Симплексные преобразования

4 . 4 Симплекс-таблица

Решение ЗЛП с искусственным базисом

Понятие двойственности

Правила построения симметричных и несимметричных двойственных задач

Экономическая интерпретация двойственной задачи

Устойчивость решения ЗЛП

Анализ коэффициентов целевой функции

Анализ ограничений по ресурсам

4.1 Построение опорного плана

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

Число перебираемых допустимых базисных решений можно сократить, если производить перебор не беспорядочно, а с учетом изменений линейной функции, т.е. добиваясь того, чтобы каждое следующее решение было "лучше" (или, по крайней мере, "не хуже"), чем предыдущее, по значениям линейной функции (увеличение ее при отыскании максимума F → max, уменьшение — при отыскании минимума F → min).

Такой перебор позволяет сократить число шагов при отыска­нии оптимума. Поясним это на графическом примере.

Идея последовательного улучшения решения легла в основу универсального метода решения задач линейного программирова­ния — симплексного  метода.

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

Симплекс (лат. simplex — простой) — простейший выпуклый много­гранник в n-мерном пространстве с n+1 вершиной (например, тетраэдр в 3-мерном пространстве); симплексом является также область допустимых решений неравенства вида ∑ ^xj ≤1.

Для реализации симплексного метода — последовательного улучшения решения — необходимо освоить три основных элемента:

· способ определения какого-либо первоначального допустимого базисного решения задачи;

· правило перехода к лучшему (точнее, не худшему) решению;

· критерий проверки оптимальности найденного решения.

Для использования симплексного метода задача линейного программирования должна быть приведена к каноническому виду, т.е. система ограничений должна быть представлена в виде урав­нений.

Решим симплексным методом задачу:

F = 2х₁+ 3х₂ -> max

при ограничениях^-

С помощью дополнительных неотрицательных переменных перейдем к системе уравнений. В данном случае все дополнительные переменные вводятся со знаком "плюс", так как все неравенства имеют вид ≤.

Получим систему ограничений в виде:

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

4.2 Признак оптимальности опорного плана

Теперь можно в общем виде сформулировать критерий опти мальности решения при отыскании максимума линейной функции:

если в выражении линейной функции через неосновные переменные отсутствуют положительные коэффициенты при неосновных переменных, то решение оптимально.

При определении минимума линейной функции Z возможны два пути:

1) отыскать максимум функции F , полагая F = — Z учитывая, что Z_min = -Fmax.

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

Сформулируем критерий оптимальности при отыскании минимума линейной функции:

 если в выражении линейной функции через неосновные переменные отсутствуют отрицательные коэффициенты при неосновных переменных, то решение оптимально.