Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Анализ чувствительности задачи линейного программирования
Задача ЛП имеет статическое оптимальное решение, по- этому, как только изменяются исходные условия, полученное решение теряет свою актуальность. Анализ чувствительнос- ти задачи ЛП как раз и связан с исследованием возможных изменений полученного оптимального решения в результате изменений исходных данных задачи. Анализ чувствительнос- ти — это процесс, который реализуется после того, как получе- но оптимальное решение. Для проведения такого анализа используется итоговая симплекс-таблица, из которой либо непосредственно, либо при помощи простых вычислений получают важную и существен- ную информацию относительно 1) оптимального решения, 2) статуса ресурсов, 3) ценности каждого ресурса, 4) чувствительности оптимального решения к изменению запасов ресурсов, 5) чувствительности к вариациям коэффициентов ЦФ. Оптимальное решение. С точки зрения практического при- менения результатов решения задачи ЛП классификация пере- менных на базисные и небазисные не имеет значения, поэтому ее можно не учитывать. Переменные, которые отсутствуют в столб- це “Базис”, имеют нулевые значения, значения же остальных переменных и значение ЦФ приводятся в столбце “Решение”. Определение статуса ресурсов. Определение статуса ресурсов предусматривает отнесение ресурсов задачи ЛП к разряду дефицитных или недефицитных. К дефицитным относятся ресурсы, если в оптимальном решении предусмат- ривается их полное использование; если же ресурс использу- ется неполностью, то такой ресурс следует отнести к недефи- цитным. Статус ресурсов любой задачи ЛП определяется на основании значений остаточных переменных. Если остаточная переменная равна нулю, то это свидетельствует о полном ис- пользовании ресурса, т. е. ресурс является дефицитным. Если же остаточная переменная не равна нулю, то это означает, что ресурс использован неполностью и относится, таким образом, к недефицитным. Ценность ресурсов. Ценность ресурса характеризуется величиной улучшения оптимального значения ЦФ, приходя- щегося на единицу прироста объема рассматриваемого ре- сурса. В итоговой симплекс-таблице ценность ресурсов можно определить по значениям коэффициентов при остаточных пе- ременных si, i = 1, …, m, начального базиса, фигурирующих в z-уравнении оптимальной симплекс-таблицы. Поскольку пере- менная si всегда связана только с ресурсом i, то идентификация ресурса происходит однозначно. Столбцы итоговой симплекс- таблицы, связанные с искусственными переменными, при ана- лизе чувствительности могут быть удалены как не содержащие полезной информации.
Пример 9.10. Рассмотрим задачу ЛП, придав ей экономи- ческое содержание: найти max W(x) = 4x1 + 3x2 при ограничениях: 3x1 + 8x2 ≤ 24 (ресурс 1); 2x1 + x2 ≤ 8 (ресурс 2); - x1 + x2 ≤ 2 (ресурс 3); x1, x2 ≥ 0. Предположим, что речь идет об определении объемов про- изводства продукции двух типов: x1 (прод. 1) и x2 (прод. 2). Для их производства используются три вида ресурсов, запасы ко- торых ограничены и представлены правыми частями ограни- чений. Коэффициенты при переменных в ограничениях харак- теризуют интенсивность расходования ресурсов на единицу каждого вида продукции. Коэффициенты ЦФ имеют смысл сто- имости продукции каждого вида (например, тыс. руб./прод. j), а ЦФ в этом случае — прибыль от реализации изготавливаемой продукции (тыс. руб.). Итоговая симплекс-таблица задачи ЛП представлена в табл. 9.9. Таблица 9.9
Из таблицы видно, что переменная s3 = 2, а переменные s1, s2, будучи небазисными, равны нулю. Это означает, что ресурс 3 является недефицитным, а ресурсы 1 и 2 — дефицитными, т. е. расходуемыми полностью без остатка. Ценность ресурсов определяется только для дефицит- ных ресурсов. В данном случае эта информация содержится в Z-строке для переменных s1 и s2. Размерность каждого элемен- та итоговой симплекс-таблицы устанавливается отношением единиц измерения элементов столбца “Решение” к единицам измерения каждой из переменных, сопоставленных со столбца- ми. Поэтому, элемент в столбце для s1 имеет размерность [тыс. руб./ресурс 1] и характеризует интенсивность улучшения оп- тимального значения ЦФ при увеличении на единицу запасов ресурса 1. Величины, характеризующие ценность ресурсов, на- зывают еще теневыми ценами или издержками производства. Учитывая, что значения двойственных переменных опреде- ляются с помощью коэффициентов в Z-строке, можно сделать следующий вывод: двойственные переменные характеризуют издержки производства. Любое ограничение ДЗЛП ≥ (или ≤) cj отражает суммарные издержки на производство j-го вида про- дукции.
Анализ чувствительности оптимального решения к из- менению запасов ресурсов. Для проведения такого анализа ис- пользуется следующий прием: вводится некоторая величина Δi в правую часть для ресурса bi. Допустим, что такая величина введена для ресурса 2 в исходную задачу ЛП. Если провести вновь все алгебраические преобразования и выполнить все ите- рации, то в итоговой симплекс-таблице величина Δ2 будет фи- гурировать только в столбце “Решение”, так как этот столбец не может быть ведущим. Коэффициенты при Δ2 равны коэффи- циентам столбца для переменной s2, соответствующей ресурсу 2. Эти результаты представлены в табл. 9.10.
Таблица 9.10
Решения |
|||||||||||||||||||||||||||||||||||||||||||||||
Z | 0 | 0 | 1/6 | 4/7 | 0 | 18 + | 4/7Δ2 | |||||||||||||||||||||||||||||||||||||||||
x 1 | 1 | 0 | 1/6 | -1/4 | 0 | 2 − | 1/4Δ2 | |||||||||||||||||||||||||||||||||||||||||
x 2 | 0 | 1 | -1/12 | 5/8 | 0 | 3 + | 5/8Δ2 | |||||||||||||||||||||||||||||||||||||||||
s 3 | 0 | 0 | -1/4 | 7/8 | 1 | 2 + | 7/8Δ2 |
Так как введение Δ2 сказывается только на правой части симплекс-таблицы, то изменение запасов ресурса может пов- лиять только на допустимость решения. Поэтому Δ2 не может быть отрицательной и должна быть ограничена таким интер- валом значений, при которых выполняется условие неотрица-
тельности правых частей ограничений (или неотрицательности переменных), т. е.
x1 = 2 − 1/4Δ2 ≥ 0, x2 = 3 + 5/8Δ2 ≥ 0, s3 = 2 + 7/8Δ2 ≥ 0.
Решение этой системы неравенств приводит к результа- ту: -16/7 ≤ Δ2 ≤ 8. Любое значение Δ2, выходящее за пределы указанного интервала (т. е. уменьшение запаса ресурса 2 на 16/7 единиц или увеличение его на 8 единиц), приведет к недо- пустимости решения и новой совокупности базисных перемен- ных. При известных границах изменения Δ2 устанавливаются реальные границы изменения запасов ресурса 2:
24 + Δ2min ≤ b2 ≤ 24 + Δ2 max.
Аналогичная процедура выполняется для всех остальных ресурсов, являющихся дефицитными.
Анализ чувствительности к вариациям коэффициентов ЦФ. Существо анализа сводится к установлению допустимых границ изменения коэффициентов ЦФ, при которых оптималь- ные значения переменных задачи ЛП остаются неизменными (хотя значение ЦФ при этом меняется).
Для установления таких границ, например, коэффициета c1, вводится величина изменения δ1 этого коэффициента в урав- нение ЦФ. Поскольку уравнение ЦФ не может быть в процес- се преобразований ведущей строкой, то приращение δ1 будет фигурировать только в Z-строке итоговой симплекс-таблицы. ЦФ в этом случае принимает вид: W(x) = (4 + δ1)x1 + 3x2. Если провести вновь все преобразования, то получим следующие из- менения в симплекс-таблице (табл. 9.11).
Таблица 9.11
Базис | x 1 | x 2 | s 1 | s 2 | s 3 | Решение |
Z | 0 | 0 | 1/6 + 1/6δ1 | 4/7 − 1/4δ1 | 0 | 18 + 2δ1 |
x 1 | 1 | 0 | 1/6 | -1/4 | 0 | 2 |
Коэффициенты при δ1 в Z-строке равны коэффициентам при соответствующих переменных в строке для x1, поскольку
именно для этой переменной была введена величина δ1 в исход- ное уравнение ЦФ.
По условиям оптимальности для задачи максимизации ЦФ все элементы Z-строки должны быть неотрицательными, поэ- тому составляется система неравенств:
|
1/6 + 1/6δ1 ≥ 0;
4/7 − 1/4δ1 ≥ 0.
Решая систему неравенств, получим: -1 ≤ δ1 ≤ 16/7. Эти ре- зультаты определяют пределы изменения коэффициента c1 в ЦФ: 4 + δ1min ≤ c1 ≤ 4 + δ1max. Таким образом, при уменьшении ко- эффициента ЦФ до значения 4 + (-1) = 3 и при увеличении его до значения 4 + 16/7 = 44/7 оптимальные значения базисных переменных остаются неизменными, хотя значение ЦФ изме- няется в соответствии с выражением 18 + 2δ1.
Аналогичным образом определяются границы изменения
остальных коэффициентов ЦФ при переменных задачи ЛП.
| Поделиться: |
Читайте также:
Последнее изменение этой страницы: 2021-01-14; просмотров: 191; Нарушение авторского права страницы; Мы поможем в написании вашей работы!
infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.144.105.59 (0.01 с.)