Параметрический анализ коэффициентов линейной формы

Рассмотрим 3 варианта параметрирования, отличающ. своими возможностями.

1. Коэффициенты критерия изменяются линейно от параметра:

C(l)=C+ l V, а вектор V задается аналогично случаю изменения ресурсов.

Задача параметрирования: (С+lV)^TX®max AX £ B X ³ 0.

ДЗ: B^TU®min A^TU ³ C+lV U ³ 0

Она представляет собой задачу параметрирования вектора ограничений, решение которой может быть получено с помощью параметрического анализа вектора ограничений. В результате найдем диапазон изменения параметра l (0 £ l < ), в котором базис двойственной задачи остается неизменным. В строке Z оптимальной таблицы двойственной задачи находятся переменные прямой задачи. Но значения z_j зависят только от базиса, поэтому в найденном диапазоне l оптимальное решение также не меняется. Изменяться будет только критерий. При достижении критического значения l произойдет смена базиса (оптимальной вершины), а значит, и оптимального решения прямой задачи. Проследить дальнейшее изменение решения можно после повторного решения двойственной задачи с вектором

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

2. Для небазисных переменных можно определить диапазон изменения C_j, в котором оптимальное решение остается неизменным. Пока при изменения C_j все Δ_j ³0 оптимальное решение исходной задачи сохраняет свой статус. Так как Δ _j = Z_j-C_j,

то уменьшение C_j не может изменить знак оценки. Поэтому интерес представляет увеличение C_j. Пусть + e_j, e_j ³.0. Тогда Δ ^’_j = Z_j – C_j - e_j = Δ _j - e_j ³ 0.

Отсюда следует, что при e_j £ Δ_j исходное решение остается оптимальным.

3. Этот вариант основан на формуле вычисления относительных оценок в модифицированном симплекс-методе: .

Она позволяет исследовать влияние изменения любых коэффициентов С_j. В общем случае эти коэффициенты являются некоторыми функциями параметра l: C_j (l). Тогда условия оптимальности запишутся в виде

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

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