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

 

Здесь рассмотрим три варианта параметрирования, отличающихся своими возможностями.

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

C (l)= C + l V,

а вектор V задается аналогично случаю изменения ресурсов.

Тогда задача параметрирования имеет вид:

(С +l V)^T X ®max

AX £ B

X ³ 0.

Запишем соответствующую двойственную задачу:

B ^T U ®min

A ^T U ³ C +l V

U ³ 0

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

Такое поведение следует и из геометрических представлений (рис. 4.14). Изменение коэффициентов линейной формы изменяет наклон линии уровня критерия, но не влияет на допустимое множество. При наличии критических значений 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, при котором хотя бы одно из условий становится равенством, и будет критическим. Практически оно находится так: каждое условие записывается как равенство и определяются его корни; из всех корней выбирается наименьшее положительное. Это и будет

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

Пример 4.8. Пусть ожидается изменение коэффициентов критерия в примере 4.2 (разд. 4.9.7) по закону: C ₁(l)=7 - 2 l, C ₂(l)=5 + l. Необходимо определить критическое значение l, если таковое имеется.

В оптимальной симплекс-таблице базисные индесы расположены в следующем порядке: 6, 2, 5, 1. Значит, Вычисляем:

Из условий оптимальности Δ₃³0, Δ₄ ³0 записываем уравнения

Первое уравнение имеет отрицательный корень, корень второго равен 11/8. Таким образом, До этого значения l оптимальное решение не изменяется, при l =11/8 имеем альтернативные оптимальные решения (линии уровня L()=34/8 x ₁+ 51/8 x ₂= Const параллельны границе 2 x ₁+ 3 x ₂=19), а при l >11/8 оптимальное решение переместится в вершину В (рис. 4.3).▲

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

при линейном изменении столбца условий A_j + l V_j или строки a _i+ l V _i.

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