Анализ чувствительности задачи линейного программирования

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

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

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

Базис	x 1	x 2	s 1	s 2	s 3	Решение
Z	0	0	1/6	4/7	0	18
x 1	1	0	1/6	-1/4	0	2
x 2	0	1	-1/12	5/8	0	3
s 3	0	0	-1/4	7/8	1	2

Из таблицы видно, что переменная 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

Базис

x 1

x 2

s 1

s 2

s 3

Решения