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

Конечно, если один из коэффициентов целевой Диапазон оптимальности функции изменен, общая прибыль (например, 88/3) -~Г Х.п°: будет изменяться, даже если оптимальные количества Xl и Х2 не изменяются.

Анализ включает вычисление ряда отношений, используя строку C-Z конечной таблицы и строку, соответствующую той переменной, диапазон оптимальности которой должен определяться. Элементы нижней строки делятся на соответствующие элементы строки переменной. Например, для переменной xi, соотношения таковы:

C-Z О О -9 -Ц

-: j = 0 - = (неопределенность) 3 = 86

тором количественные показатели решения для всех переменных останутся неиз -менными.

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

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

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

Таблица 5п-8. Задача и оптимальная таблица используются для демонстрации анализа чувствительности

Максимизировать: Z = 4х,+ SXg Ограничения: х,+ SXj < 12

Ближайшее к нулю положительное отношение показывает, насколько может быть увеличен исходный коэффициент Х] в целевой функции, без изменения значений оптимального решения. Таким образом, 4 может увеличиваться на 8/3 = 2,67 (т.е. до 6,67) и изменить при этом решения. Аналогично, 4 может быть уменьшен отрицательным отношением, самым близким к нулю (т.е. - 7/3 = 2,33) и не изменить количественных показателей решения. Следовательно, диапазон оптимальности для коэффициента Х]:

4-2,33 < С, <4+2,67

Если С] остается равным 4, то диапазон оптимальности для Х2 определяется следующим образом:

--: 7г = (неопределенность) 7 = 0 -ri- = - 2 -- - 7

Х2 I тд - (Л)

Наименьшее положительное значение равно 7; следовательно, исходный коэффициент 5 может увеличиваться на 7 (5 + 7 = 12). Отрицательное отношение, самое близкое к нулю, есть -2. Следовательно, исходный коэффициент Х2 может быть уменьшен на это значение. Следовательно, нижняя граница 5-2=3. Таким образом, диапазон оптимальности для С2 будет от 3 до12.

Этот пример содержит две переменных, обе из которых присутствуют в решении. В некоторых случаях одна или более переменных могут не присутствовать в решении. В подобной ситуации мы говорим о диапазоне незначительности, то есть о диапазоне, за которым данная переменная останется вне решения. Для того, чтобы данная переменная вошла в решение, коэффициент целевой функции должен быть увеличен на значение большее, чем значение на пересечении строки C-Z и столбца этой переменной. Например, если появилось значение -4, то коэффициенты при переменных в целевой функции должны увеличиться больше чем на 4, чтобы переменная вошла в решение. Диапазон незначительности для нее от О до 4.

Давайте рассмотрим изменения для правой стороны уравнения ограничения. Не забудьте, что изменяется только одно ограничение; все остальные сохраняют свои первоначальные значения. Некоторые ограничения не подлежат изменению; ничего полезного из увеличения их значений извлечь нельзя (при условии ограничений типа <). Это относится к ограничениям, которые являются резервными в окончательном решении; эти ограничения не являются для проблемы ограничивающими факторами. Следовательно, диапазон Диапазон выполнимости выполни.мости для резервного ограничения в нижней - диапазон значений для части равен его значению в окончательном решении. правой стороны ограниче- i -.т

ния, за которым теневое Таким образом, если Si=250 в окончательном ре-

значение остается неизмен- шении задачи, то исходное значение правой части пер-i ным. I вого ограничения можно уменьшить на это значение и

1ааж11с-,2-ж:-?-.:1..<--~жшшж11М прИ ЭТОМ НС ИЗМСНИТЬ решеНИС. В ВСрХНСЙ ЧЗСТИ, ЗНаЧС-

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

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

появившиеся в решении, будут иметь в своем столбце .-.жж-А г.-, :ы>;, . irsi отрицательное значение в строке C-Z. Эти отрицатель-I Теневые значения - вели- t ные значения известны как теневые значения. Они ука-I чины, показывающие на- зывают, насколько уменьшение на одну единицу в ис-1 SZ;:?:SHa.;: -дно- значенииограничения уменьшит конечное j ограничения изменит окон- Л значение целевой функции.

I чательноезначение целевой i; Таким образом, в таблице 5п-8, мы можем уви-

S функции. ь деть, что единичное уменьшение в первом ограниче-

Следовательно, если первое ограничение остается неизменным, второе можно увеличить на 24 единицы или уменьшить на 12. Воздействие на оптимальное значение целевой функции будет 7/9 = 0,79 на единицу.

Компьютерные решения

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

Один из наиболее широко используемых пакетов р UNDO - широко используе-линейного программирования -LINDO. ый пакет линейного про-

Этот пакет разработал Линус Шрадж из Чикаг- S граммироваиия. ского университета. Он существует в версиях для уни-

версальных ЭВМ и для персональных компьютеров.

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

Рассмотрим следующую ЛП модель: .

Максимизировать: бОХ] + 50x2 Ограничения: 4xi + 10x2 100

нии данной задачи приведет к уменьшению конечного значения целевой функции на 8/9 = 0,89. Аналогично, уменьшение на одну единицу во втором ограничении приведет к уменьшению целевой функции на 7/9= 0,78. Наоборот, увеличение на единицу одно, го из этих значений будет иметь обратный эффект: увеличение на единицу первого or-раничения увеличит оптимальное значение целевой функции на 0,89, а увеличение на единицу второго ограничения приведет к увеличению целевой функции на 0,78. Во-прос, на который может ответить анализ чувствительности: за каким диапазоном значений правой части ограничения показатели теневыхзначений останутся значимыми?

Чтобы определить диапазон выполнимости для ограничения, сначала определим значения в тексте конечной таблицы в колонке для резервной переменной данного ограничения. Например, в таблице 5п-8 значения для Sj 4/9 и -1/3. Затем разделим эти значения на соответствующие значения в столбце количества. Для Sj получим:

y-i 4

Положительное отношение, самое близкое к нулю, указывает значение, на которое можно уменьшить исходное ограничение; а отрицательное отношение, ближайшее к нулю, - насколько его можно увеличить. В данном примере, исходное значение правой стороны первого ограничения было 12. Его можно уменьшить на 6 единиц или увеличить на 12. Воздействие этого на оптимальное значение целевой функции будет 8/9 = 0,89 на единицу. Аналогично, отношения для S2:

У-\ 4