Определение диапазонов допустимых изменений коэффициентов при переменных в целевой функции f.

Под допустимыми знают такие трансформации этих коэффициентов, при которых оптимальный базис разглядываемой ЗЛП (т.е. базис при последней итерации симплекс – способа, соответствующий оптимальному ответу) остается оптимальным.

Пускай трансформациям

Определение диапазонов допустимых изменений коэффициентов при переменных в целевой функции f.

подвергнется коэффициент

Определение диапазонов допустимых изменений коэффициентов при переменных в целевой функции f.

. Обозначим через Jб, Jнеб множество индексов базовых и небазисных векторов в оптимальном замысле x0 соответственно.

Определим значения оценок

Определение диапазонов допустимых изменений коэффициентов при переменных в целевой функции f.

по окончании трансформации cr для двух случаев:

1) rI Jнеб , тогда

Определение диапазонов допустимых изменений коэффициентов при переменных в целевой функции f.

для всех j?r ;

Определение диапазонов допустимых изменений коэффициентов при переменных в целевой функции f.

для j=r ; (5)

2) rI Jб,

Определение диапазонов допустимых изменений коэффициентов при переменных в целевой функции f.

jIJнеб (6)

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

Определение диапазонов допустимых изменений коэффициентов при переменных в целевой функции f.

для всех небазисных переменных. Исходя из этого из условий

Определение диапазонов допустимых изменений коэффициентов при переменных в целевой функции f.

?0 в соответствии с формулами (5) и (6) возможно выяснить допустимые трансформации коэффициента

Определение диапазонов допустимых изменений коэффициентов при переменных в целевой функции f.

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

возьмём соотношения, подобные (6), в которых оценки

Определение диапазонов допустимых изменений коэффициентов при переменных в целевой функции f.

будут функциями уже нескольких параметров (?1, ?2,., ?r). Решая совместно совокупность неравенств вида

Определение диапазонов допустимых изменений коэффициентов при переменных в целевой функции f.

(c1, c2,.,cr)?0, jIJнеб, находим условия для

Определение диапазонов допустимых изменений коэффициентов при переменных в целевой функции f.

, при которых прошлый оптимальный базис сохраняется.

1.2.2 Определение диапазонов допустимых трансформаций параметров

Определение диапазонов допустимых изменений коэффициентов при переменных в целевой функции f.

, i=1,…,n.

В задачах распределительного типа величина

Определение диапазонов допустимых изменений коэффициентов при переменных в целевой функции f.

характеризует предельно вероятный количество потребления i-го ресурса. Изменение значений свободных участников

Определение диапазонов допустимых изменений коэффициентов при переменных в целевой функции f.

ведет к повышению либо уменьшению Fmax . Это изменение Fmax определяется величиной ответа двойственной задачи½y*½ и возможно оценено так лишь тогда, в то время, когда при трансформации размеров b оптимальный замысел исходной задачи остается неизменным.

Обозначим через Ax матрицу оптимального базиса задачи ЛП при векторе ресурсов b. Разумеется соответствующее оптимальное ответ

xопт= A-1x b.

Предположим, что мы поменяли вектор ресурсов b=|| bi || на направляться=b+ ?b и желаем выяснить, как это повлияет на оптимальное ответ. Для этого отыщем новое соответствующее базовое ответ

xн = А-1хbн = А-1х(b+?b).

В случае если все компоненты xiн ? 0, то это решение xн = [xiн] оптимально (т.е. оптимальный базис не изменился).

Анализ перемещения коэффициентов. Падающие коэффициенты


Похожие статьи:

Понравилась статья? Поделиться с друзьями: