ТОП 10:

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



 

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

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

C(l)=C+lV,

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

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

(С+lV)TX®max

AX £ B

X ³ 0.

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

BTU®min

ATU ³ C+lV

U ³ 0

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

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

2. Для небазисных переменных весьма просто можно определить диапазон изменения Cj, в котором оптимальное решение остается неизменным.

Действительно, пока при изменения Cj все Δj ³0 оптимальное решение исходной задачи сохраняет свой статус. Так как

Δj = Zj-Cj,

то уменьшение Cj не может изменить знак оценки. Поэтому интерес представляет увеличение Cj. Пусть + ej, ej ³.0. Тогда

Δj = Zj – Cj - ej = Δj - ej ³ 0.

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

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

.

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

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

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

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

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

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

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

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

при линейном изменении столбца условий Aj+lVj или строки ai+lVi.

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







Последнее изменение этой страницы: 2016-08-12; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.226.243.36 (0.006 с.)