Постоптимальный анализ чувствительности

Постоптимальный анализ чувствительности

Когда основное решение оптимальная задачи PL анализируется, чтобы ответить на вопросы об изменениях в ее постановке, исследование называется постоптимальным анализом чувствительности.

Мы называем пост-оптимизацией набор приемов, позволяющих получить оптимум задачи PL, когда определенные данные подверглись модификации.

Мы рассматриваем проблему линейное программирование вообще в своем стенд-арте:

анализ чувствительности симплексным методом постоптимальный первичный анализ чувствительности

Это исследование может быть мотивировано несколькими причинами:

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

Предельные затраты

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

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

Таким образом, предельные издержки y* представляют собой чистый эффект, связанный с переменными дисперсии, поскольку именно эти переменные определяют излишки (или дефицит) товаров. Это значения переменных в строке Z.

Если переменная дисперсии не равна нулю, в оптимальном решении соответствующий товар уже является избыточным. Следовательно, наличие дополнительной единицы этого товара не повлияет на доход. резервная переменная имеет нулевую предельную стоимость.

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

анализ чувствительности симплексным методом первичный анализ чувствительности

с вектором решения x* = (2,6). Будьте осторожны, здесь линия показывает значение Z, а не -Z (отсюда и положительные значения).

Можно измерить чувствительность оптимального решения к изменению правого члена или коэффициента цели.

Исследование 1: изменение целевой функции

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

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

анализ чувствительности симплексным методом первичный анализ чувствительности
Значение j-й переменной при оптимуме x*я измеряет увеличение целевой функции, если удельная стоимость c увеличивается на одну единицуя. Логичное и тривиальное поведение, поскольку целевая функция состоит из суммы cя*Икся.

Изменим целевую функцию на max z' =4*x1 + 5*х2. Значение целевой функции изменится на x*1 = 2, а вектор решения не изменится, как показано на рис. графическое разрешение :

анализ чувствительности симплексным методом первичный анализ чувствительности

Так же, если это1 изменится с 3 на 2, изменится только значение целевой функции. Для расчета интервала, на котором коэффициент x*1 верно, нам нужно масштабировать целевую функцию до тех пор, пока она не станет параллельной другим ограничениям.

То есть, когда наклон целевой функции равен наклону насыщенных ограничений для вектора решения s*:

  • г=с1*Икс1 + 5*х2 и 2*х2 = 12 так -с1/5 = 0, с1 = 0;
  • г=с1*Икс1 + 5*х2 и 3*х1 + 2*х2 = 18 так -с1/5 = -3/2, с1 =15/2.

Коэффициент х*1 поэтому справедливо для c1 от 0 до 15/2.

Когда проблема большая, можно рассчитать изменение стоимости с помощью симплекса, добавив дельту к изменению стоимости, как в следующем примере:

анализ чувствительности симплексным методом первичный анализ чувствительности

Решение остается оптимальным до тех пор, пока в строке -Z есть отрицательные числа, поэтому, если:

анализ чувствительности симплексным методом первичный анализ чувствительности

Исследование 2: вариация второй конечности

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

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

  • Решение меняется, но нулевые переменные остаются нулевыми, а ненулевые переменные остаются ненулевыми: структура решения не меняется.
  • Изменение второго члена i приводит к изменению оптимального значения целевой функции, равного uя* дя, поэтому пропорциональна dя.
Коэффициент пропорциональности называется предельной вариацией или двойной стоимостью или предельной прибылью. Двойная стоимость уя равно изменению оптимального значения целевой функции при увеличении второго члена на единицу.

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

анализ чувствительности симплексным методом первичный анализ чувствительности

Рассмотрим в примере, что b1 =4 становится b'1 = 5. Выполним графическое решение новой задачи:

анализ чувствительности симплексным методом первичный анализ чувствительности
Эволюция этого второго члена не изменила оптимальное решение, значение целевой функции не изменилось. Это изменение было легко предсказать, потому что предельные издержки резервной переменной y*1 равен нулю: z'* – z* = y*1 = 0.

Когда происходит уменьшение b1 ? Как поясняется в объяснении предельных издержек, уменьшение второго члена на 1 приводит к уменьшению значения целевой функции на величину, равную предельным издержкам. Так что уменьшение на 1 не приведет к модификации.

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

анализ чувствительности симплексным методом первичный анализ чувствительности

Решение остается оптимальным до тех пор, пока симплекс не вырожден, то есть если второй член положителен:

анализ чувствительности симплексным методом первичный анализ чувствительности
Увеличение и уменьшение не меняют значения целевой функции на малом интервале, но если b1 меньше 2, то на графическом разрешении мы видим, что оптимальное решение будет изменено. Интервал действия y*1 =0 поэтому для b1 от 2 до бесконечности.

Теперь рассмотрим увеличение третьей правой части до b'3 = 19. Поскольку предельные издержки не равны нулю, оптимальное решение будет изменено, как показано в графическом разрешении.

анализ чувствительности симплексным методом первичный анализ чувствительности
Следовательно, мы можем интерпретировать предельные издержки следующим образом: уменьшение или потеря одной единицы третьего второго члена приведет к изменению y*.3 значения целевой функции на интервале b3 между 12 и 24.

Исследование 3: изменение внебазовых переменных

Приведенная стоимость небазовой переменной xя, отметил дя, измеряет увеличение целевой функции, если значение небазовой переменной увеличивается на одну единицу. Сниженная стоимостья является обратным коэффициенту переменной в линии ворот Z.
Оптимальное решение не изменится до тех пор, пока стоимость внебазовой переменной не станет лучше, чем оптимальное значение целевой функции (например, если коэффициент находится между -бесконечностью и Z для задачи максимизации).

Вернемся к предыдущему примеру с новым ограничением и новой переменной:

анализ чувствительности симплексным методом первичный анализ чувствительности

У нас есть следующая сниженная стоимость: d3 = -2. Это означает, что для построения единицы x3  уменьшит значение целевой функции на 2 (поскольку она выходит за базис x*3 = 0).

Проверить расчетом: зафиксировать x3 к 1. Получаем следующие три неравенства: x1 ≤ 3; 2*х2 ≤10; 3*х1 + 2*х2 ≤ 15. Вектор (5/3, 5) является решением системы. Итак, у нас есть эволюция x1 5/3 – 2 = -1/3 и х2 = 5 -6 = -1 в целевой функции (новое значение – старое значение). Следовательно, его стоимость изменяется на -1/3*c.1 - 1 С2 + 1*с3 = -2 (1*с3 потому что мы переходим от производства 0 к 1). Находим стоимость, уменьшенную на х3.
Так что х3 становится прибыльным, его стоимость должна увеличиваться, по крайней мере, противоположно уменьшенной стоимости.

Исследование 4: изменение производства

Если значение имеетij изменения насыщенного ограничения, то ни оптимальное решение, ни оптимальное значение не сохраняются.
Если значение имеетij изменения в ненасыщенном ограничении и базовой переменной, то значение может варьироваться от + или - бесконечности (в зависимости от минимального или максимального значения) до Sя /Икс*я. с Ся  слабая переменная.

Действительно, добавив дельта-переменную в стоимость переменной на основе целевого ограничения, достаточно ввести оптимальный вектор и решить уравнение, как в следующем примере:

анализ чувствительности симплексным методом первичный анализ чувствительности
Если значение имеетij изменения любого ограничения и внебазовой переменной, то только отрицательная вариация (в случае максимума) может сделать продукт жизнеспособным в этом ограничении. Затем необходимо решить симплекс с учетом дельты и проверить его различные критерии оптимальности.
Делиться
ru_RURU
%d такие блоггеры, как: