4.8. Изменение правых частей ограничений

Теперь от изменения коэффициентов целевой функции перейдем к рассмотрению изменений правых частей ограничений. Начнем обсуждение с общих наблюдений, ка­сающихся влияния изменений правых частей ограничений в виде неравенств. Чтобы продемонстрировать воздействие изменений этих параметров, вновь обратимся к графи­ческому анализу. Предлагаем поэкспериментировать, перемещая линии ограничений модели Oak Products на рис. 4.3 путем присвоения различных значений правым частям ограничений, чтобы увидеть разнообразие допустимых областей, получаемых в результа­те этих простых манипуляций. В программе GLP это можно делать, вводя различные значения правых частей неравенств, перетаскивая линии ограничений или щелкая на кнопках со значками + и —, находящихся справа от каждого поля ограничения в окне GLP. В результате экспериментов с перемещением ограничений модели Oak Products на рис. 4.3 можно сделать вывод, что увеличение правой части ограничения вида >= усилива­ет ограничение, т.е. такое ограничение становится сложнее удовлетворить. Аналогично, если правая часть ограничения вида < уменьшается, такое ограничение также становится сложнее удовлетворить, следовательно, оно усиливается.

Усиление ограничения-неравенства означает, что такое ограничение становится слож­нее удовлетворить. Для ограничения вида > это происходит при увеличении правой час- \ ти. Для ограничения вида < это происходит при уменьшении правой части.

Процесс уменьшения правой части ограничения вида >=, напротив, называется ослаб­лением ограничения. Как показано на рис. 4.3, с уменьшением правой части ограничения вида > появляется все больше комбинаций значений С и М, удовлетворяющих данному ограничению. Таким образом, данное ограничение становится проще удовлетворить. Аналогично при увеличении правой части ограничения вида < его становится проще удовлетворить, следовательно, происходит ослабление данного ограничения.

Ослабление ограничения -неравенства означает, что данное ограничение становится легче удовлетворить. Для ограничения вида > это происходит при уменьшении правой части, а для ограничения вида < — при ее увеличении.

Подытожим наши наблюдения геометрических последствий усиления и ослабления ограничений-неравенств.

Усиление ограничения-неравенства приводит к уменьшению допустимой области тли оставляет ее неизменной. Ослабление ограничения-неравенства приводит к расшире­нию допустимой области или оставляет ее неизменной.

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

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

Устойчивость к изменениям правых частей ограничений и теневые цены

Рассмотрим сначала ситуацию, при которой все числа в модели Oak Products остаются фиксированными, за исключением запаса длинных штифтов. Что если вместо 1280 штук их запас составит 1281? Как это отразится на оптимальном значении целевой функции? Поскольку данное ограничение имеет вид <. можно заключить, что увеличение правой части приведет к ослаблению ограничения, т.е. его будет проще удовлетворить. Следова­тельно, данное изменение определенно не уменьшит значения целевой функции. Однако произойдет ли его увеличение, и если да, то насколько?

Чтобы ответить на эти вопросы, воспользуемся испытанным средством — графиче­ским анализом, а затем свяжем результаты анализа с данными отчета по устойчивости, генерируемого средством Поиск решения. Обозначим через L значение правой части ог­раничения для длинных штифтов. Тогда первоначально L = 1280. В ходе экспериментов

с представленной на рис. 4.4 моделью будем менять ограничение для длинных штифтов, подставляя значения L— 1281, L =1320 и L= 1350. Как мы показали в разделе 4.2, эти новые значения L геометрически соответствуют параллельному переносу (в направлении от начала координат) линии ограничения.

Поскольку увеличение L означает ослабление данного ограничения, в геометриче­ском представлении допустимая область может измениться только в сторону расширения (если она вообще будет меняться). Новые множества ограничений совместно с опреде­ленными программой GLP оптимальными решениями, соответствующими значениям запаса длинных штифтов 1281, 1320 и 1350, представлены на рис. 4.13, 4.14 и 4.16 соот­ветственно. Эти рисунки позволяют обнаружить некоторые интересные факты, которые можно проверить, непосредственно изменяя модель Oak Products в программе GLP.

При L = 1281 (рис. 4.13) ограничения для ножек и длинных штифтов продолжают ос­таваться лимитирующими, новое решение: С= 130,25, М = 59,75, оптимальное значение целевой функции равно $9684. Заметим, что последнее значение увеличилось на $4 по сравнению с исходной моделью (было $9680).

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

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

На рис. 4.14 показано, что при L = 1320 оптимальным решением является С= 140, М — 50, лимитирующими становятся три ограничения — для длинных штифтов, для но­жек и прочных сидений, а оптимальное значение целевой функции равно $9840.

Решение, предложенное средством Поиск решения, и отчет по устойчивости для дан­ной модели показаны на рис. 4.15. Мы видим нулевые значения конечного запаса для трех лимитируюших ограничений. В предыдущих случаях (при L = 1280 и 1281) в точке оптимальности обе переменные решения были положительными и только два ограниче­ния были лимитирующими. В данном случае в точке оптимальности обе переменные ре­шения положительны, но связывающих лимитируюших ограничения — три. Нестрого говоря, решение задачи ЛП, для которого лимитирующих ограничений больше, чем по­ложительных переменных, называется вырожденным, что может приводить к определен­ным аномалиям при интерпретации отчета по устойчивости. Так, например, на рис. 4.15 показано, что допустимое увеличение и допустимое уменьшение для некоторых теневых цен равны нулю.⁵

Совет. Отчет по устойчивости — это обычный рабочий лист с отключенной сеткой. Мож­но изменить форматирование его содержимого, чтобы придать ему более удобную форму. Важно отметить, что теневая цена по умолчанию имеет тот же числовой формат, что и ячейка левой части соответствующего ограничения в исходной таблице Excel. Если в фор­мате этой ячейки десятичные знаки после запятой отсутствуют или их недостаточно, это может привести к тому, что будет указано нулевое значение теневой цены, в то время как фактически оно равно небольшому дробному числу, скажем, 0,023. Поэтому нужно взять за правило просматривать нулевые элементы в отчете по устойчивости, чтобы про­верить, действительно ли данный элемент равен 0, или же это небольшое число, требующее числового формата с большим количеством знаков после запятой.

Вырожденность — просто обозначение особенности модели (указывает на то, что некоторые ограничения избыточны — Прим. ред.) однако она требует более тщательной интерпретации содержащейся в отчете по устойчивости информации. Подробнее тема избыточности рассмотрена в разделе 4.13.

При L = 1320 значение правой части ограничения для длинных штифтов увеличилось на 40 единиц по сравнению с исходным значением 1280. В соответствии с определенной ранее теневой ценой (которая равна 4) значение целевой функции увеличилось на 9840 - 9680 == = 160 = 4x40.

Если значение L превышает 1320, то, как показано на рис. 4.14 и рис. 4.16, ограничение для длинных штифтов перестает быть лимитирующим, более того, оно становится избы­точным, поскольку теперь его удаление никак не отражается на решении. Оптимальное ре­шение остается точно таким же, как на рис. 4.14 и 4.15. Решение, предложенное средством Поиск решения, и отчет по устойчивости для значения L = 1350 представлены на рис. 4.17.

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

Таким образом, из отчетов по устойчивости, приведенных на рис. 4.11, 4.15 и 4.17, можно извлечь следующую информацию.

a. При L— 1280 (см. рис. 4.11) теневая цена равна 4, допустимое увеличение вели­ чины L для ограничения длинных штифтов составляет 40 штук, а допустимое уменьшение — 180. Как можно убедиться, для значений L, находящихся в диа­ пазоне 1100-1320, при каждом увеличении запаса (правой части ограничения) на единицу при условии, что остальные данные остаются неизменными, прирост оп­ тимального значения целевой функции составит $4.

b. При L= 1320 (см. рис. 4.15) теневая цена остается равной 4, но допустимое увеличение становится равным 0, а это означает, что для данных правой части ограничения, превышающих 1320. значение 4 уже не будет верным. Геометри­ ческий анализ свидетельствует, что при L > 1320 данное ограничение становит­ ся нелимитируюшим и, более того, избыточным. Незначительные изменения правой части нелимитирующего ограничения не могут повлиять на оптимальное значение целевой функции, следовательно, для нелимитирующего ограничения те­ невая цена всегда равна 0.

c. При L =1350 (см. рис. 4.17) данное ограничение является нелимитируюшим, те­ невая цена равна нулю, а допустимое увеличение — бесконечности.⁶ Таким обра­ зом, при дальнейшем увеличении L данное ограничение останется нелимити­ руюшим, а теневая цена — равной 0. Допустимое уменьшение имеет значение 30, при этом правая часть ограничения вновь примет значение 1320. Для значений L, меньше 1320, как показано на рис. 4.15, теневая цена составляет $4, а не 0.

Подведем итог.

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

2. Теневая цена нелимитирующего ограничения всегда равна 0. ("Нелимитируюшее" означает, что в точке оптимальности данное ограничение имеет ненулевой резерв или излишек.)

3. Таблица Ограничения отчета по устойчивости не содержит информации о том, как меняются оптимальные значения переменных С и М. В ней только показано, как будет меняться оптимальное значение целевой функции при изменении пра­вой части ограничения.

Наибольшее число, которое можно представить в Excel, равно 1E+30, т.е. 1 и 30 нулей. Это чист можно считать бесконечно большим по сравнению с другими числами, фигурирующими в модели.

Линейное программирование помогает

компании экономить материалы

Компания Welborn Cabinet занимается производством шкафов в штате Алабама. Производство состоит из лесопилки, четырех сушильных камер и сборочного завода с фабрикой, производящей компоненты шкафов. Компания получает пиломатериа­лы для производства шкафов; 1) приобретая бревна, которые обрабатываются на ле­сопилке, чтобы получить доски, используемые затем на сборочном заводе; 2) приоб­ретая доски у внешних поставщиков. В настоящее время около 73% досок поступает с собственной лесопилки компании.

Бревна и доски относятся к первому или второму сорту, пиломатериалы первого сорта более качественные и дорогие. В настоящее время около двух третей общего объема закупленных компанией Wellborn бревен составляют бревна 1-го сорта. Заку­пленные доски, составляющие около 27% общего объема используемых досок, были двух видов: сырые (18%), которые необходимо сушить в сушильных камерах компа­нии, и сухие (9%). Практически все сухие доски также были 1 -го сорта.

Стоимость пиломатериалов составляет около 45% всех материальных затрат на изготовление шкафов. Поэтому руководство компании хотело узнать, является ли используемый компанией подход к покупке древесины наиболее экономичным. Чтобы ответить на данный вопрос, Центр технической помощи при университете Оборна в содружестве с Лесотехническим институтом проанализировали деятель­ность компании. Была создана линейная оптимизационная модель производства заготовок, ограничения которой учитывали производственные мощности лесопилки и сушильных камер, требуемый объем производства заготовок и возможный объем поставок сырья.

В результате оптимизации обнаружилось, что компания может минимизировать затраты на производство заготовок, покупая только два вида древесины: бревна 2- о сорта с диаметром тонкого конца 9—15 дюймов (88% объема закупок) и сырые доски 2-го сорта (12%). Такая политика закупок может почти на треть снизить затраты компании Wellborn на сырье, что позволит сэкономить около $412 000 в год. Модель также предоставила менеджерам множество дополнительной информации.

• Теневые цены показывают возможность сделать более выгодную закупку бревен различных размеров.

• Анализ чувствительности позволяет узнать диапазоны цен, для которых решение, предлагаемое моделью, будет оставаться оптимальным. В частности, он свиде­тельствует, что снижение цен на сухие доски или бревна 1-го сорта вплоть до 20% не повлияет на оптимальную политику закупок.

• Нулевое значение резерва для процесса работы сушильных камер показывает, что данный процесс является узким местом, т.е. производственная мощность сушиль­ ных камер — единственный фактор, сдерживающий увеличение производства. По­ вышение производственной мощности сушильных камер на 22% позволит увели­ чить выпуск заготовок на 29% безо всяких дополнительных изменений. [51