Схема табличного симплекс-метода.

Шаг 0. Начальный шаг.

Пусть задано ДБР х° исходной задачи. Построим соответствующую этому ДБР х° симплекс-таблицу.

Шаг 1. Проверка условия оптимальности.

Если коэффициенты z-строки d_0J, j = 1, mнеотрицательные, то прекратить вычисления: текущей симплекс-таблице соответствует оптимальное ДБР.

Шаг 2. Выбор ведущего столбца.

Среди коэффициентов d ₀ j, j = 1, n выбрать отрицательный. Пусть мы выбрали d _{0 p}. Тогда р-й столбец будет ведущим. Переменная х_р будет вводиться во множество базисных переменных.

Шаг 3. Выбор ведущей строки.

Если коэффициенты a_ip, i = 1, m неположительные, то прекратить вычисления:

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

Элемент таблицы a_qp на пересечении ведущих строки и столбца называется ведущим элементом.

Шаг 4. Переход к новой симплекс-таблице.

Используя преобразования Жордана-Гаусса над СЛАУ, в симплекс-таблице сделать ведущий элемент равным единице, а все остальные коэффициенты ведущего столбца равными нулю. Слева от таблицы в q-ой строке запишем переменную х_р.

Перейти на шаг 1.

Постоптимальный анализ

Постоптимальный анализ (анализ моделей на чувствительность) – это процесс, реализуемый после того, как оптимальное решение задачи получено. В рамках такого анализа выявляется чувствительность оптимального решения к определенным изменениям исходной модели. Иными словами, анализируется влияние возможных изменений исходных условий на полученное ранее оптимальное решение. Важность этого анализа ЗЛП объясняется также ещё и тем, что большая часть параметров ЗЛП точно не известна, и на практике обычно берутся приближенные значения параметров.

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

В постоптимальном анализе исследуются три класса параметров:

1. Компоненты вектора ограничений b_t

После нахождения оптимального решения.представляется вполне логичным выяснить, как отразится на оптимальном решении изменение запасов ресурсов. Отметим, что неравенства модели типа " < " обычно могут быть интерпретированы, как ограничения на использование лимитированного ресурса. А ограничения типа " > " могут быть интерпретированы, как некоторые требования к моделируемому процессу.

При анализе изменений запасов ресурсов особенно важны два следующих аспекта:

> На сколько можно увеличить (уменьшить) запас некоторого ресурса для улучшения полученного оптимального значения целевой функции z?

> На сколько можно снизить (увеличить) запас некоторого ресурса при сохранении полученного оптимального значения целевой функции z?

2. Коэффициенты ЦФ Cj

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

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

> Насколько следует изменить тот или иной коэффициент целевой функции, чтобы сделать некоторый недефицитный ресурс дефицитным и, наоборот, дефицитный ресурс сделать недефицитным?

1. Существует диапазон изменения А коэффициентов ЦФ как базисных, так и небазисных переменных, в которых текущее оптимальное решение остается оптимальным.

- для небазисных переменных существует только нижняя или верхняя граница;

- для базисных - обычно существуют и нижняя и верхняя границы.

2. Изменение коэффициента ЦФ базисной переменной всегда приводит к изменению значения ЦФ.

3. Эффект от изменения коэффициентов ЦФ может рассматриваться с двух позиций:

- с точки зрения сбыта нас интересуют равновесные цены;

- с точки зрения производства нас интересует диапазон изменения коэффициента ЦФ, ' в пределах которого текущий план производства остается оптимальным.

Нахождение диапазонов изменения запасов ресурсов

Недефицитные ресурсы

Если в оптимальном решении дополнительная переменная S i-ro ограничения базисная, то это ограничение является не связывающим (не активным в точке оптимума), а ресурс - недефицитный. В этом случае значение дополнительной базисной переменной дает диапазон изменения, в котором соответствующая компонента d _i может:

• Уменьшатся (в случае знака ограничения " < " )

• Увеличивается (в случае знака ограничения " > " ).

Пусть S⁰ - значение соответствующей дополнительной переменной в точке оптимума. Тогда решение остаётся допустимым и оптимальным в диапазоне bi+ ∆ , где

Дефицитные ресурсы

Если в оптимальном решении некоторая дополнительная переменная небазисная, то существующее ' ей ограничение является связывающим (активным в точке оптимума), а ресурс - дефицитным.

Для ограничения типа " < ":

Для ограничения типа " > ":

Изменение коэффициентов Ц.Ф.

Существует диапазон изменения коэффициентов ' целевой функции как базисных так и не базисных переменных, в которых полученное решение остаётся оптимальным. Изменение коэффициента базисной переменной в пределах этого диапазона приводит к изменению значения целевой функции, так как Z = С^т_в*β, а одна из компонент вектора Св изменяется. Изменение коэффициента небазисной переменной не меняет значения задачи.

Для задачи на m ах:

Базисные переменные:

Для базисной переменной диапазон устойчивости, в котором может изменяться коэффициент Ci, оставляя текущее решение оптимальным, задаётся выражением: Ci + ∆

где dj - относительная оценка переменной xj в текущем оптимальном решении.

Eсли отсутствуют  соответственно.

Не базисные переменные:

Для не базисной переменной диапазон устойчивости, в котором может изменятся коэффициент Сi оставляя текущее решение оптимальным, задаётся выражением:

Для задачи на min: Базисные переменные:

Для базисной переменной диапазон устойчивости, в котором может изменяться коэффициент Сi, оставляя текущее решение оптимальным, задаётся выражением: Сi + ∆

He базисные переменные:

Для не базисной переменной диапазон устойчивости, в котором может изменятся коэффициент С; оставляя текущее решение оптимальным, задаётся выражением:

( d_N ) < ∆ < ∞

⇐ Предыдущая123Следующая ⇒

Поделиться: