Пример графического метода решения задачи линейного программирования. Поиск оптимального решения графического метода lpm
Первая задача анализа чувствительности: анализ чувствительности к изменениям в правых частях ограничений
жүктеу/скачать 74,92 Kb.
|
Пример графического метода решения задачи линейного программирования
| 3. Первая задача анализа чувствительности: анализ чувствительности к изменениям в правых частях ограничений.
Эта задача позволяет ответить на вопрос: насколько целесообразно увеличивать или уменьшать ресурсные запасы? Особенно важно проанализировать эти два аспекта. 1. На какое значение можно увеличить запас какого-либо ресурса для повышения оптимального значения целевой функции? 2. На какое значение можно уменьшить запас какого-либо ресурса при сохранении оптимального значения целевой функции? Поскольку объем запаса каждого из ресурсов фиксируется в нужных частях ограничений, этот вид анализа часто называют анализом назойливости нужных частей (ограничений). Прежде чем ответить на поставленные вопросы, мы классифицируем ограничения линейной модели на связующие (активные) и несвязывающие (неактивные). Линия, соответствующая пределу привязки, должна проходить через оптимальную точку. На рисунке 2. 2.1 Привязками являются только ограничения (1) и (2), то есть те, которые ограничивают запасы ресурсов А и В. Если какое-то ограничение является обязательным, то ресурс, который ему соответствует, следует отнести к разрядке дефицитных ресурсов, так как он расходуется полностью. Ресурс, с которым связан необязательный лимит, следует отнести к категории недефицитных ресурсов (то есть имеющихся в некотором избытке). Таким образом, в ходе анализа модели на чувствительность к правым частям ограничений определяются следующие значения: 1) предельно допустимое увеличение запаса дефицитного ресурса, позволяющего улучшить ранее найденное оптимальное решение; 2) предельно допустимое уменьшение запаса недефицитного ресурса, не изменяющего ранее найденного значения целевой функции. Информация, полученная в последнем случае, особенно полезна в ситуациях, когда избыточные недефицитные ресурсы могут быть использованы для других целей. Может возникнуть вопрос: не стоит ли анализировать, как увеличение количества ресурсов, которые находятся в избытке, и уменьшение количества дефицитных ресурсов повлияет на оптимум. Ответ на первую часть вопроса очевиден, ведь в этом случае мы постараемся сделать и без того избыточный ресурс еще более избыточным, что не повлияет на ранее полученное решение. Вторая часть вопроса заслуживает особого внимания, так как при возможных недопоставках дефицитного ресурса важно знать, как это отразится на результатах решения проблемы. Вернемся к конкретному примеру. В проблеме «на красках» продукты А и В (ограничения (1) и (2)) являются дефицитными ресурсами. Рассмотрим сначала ресурс А. На рис. 1. 2.3 Видно, что при увеличении запаса этого ресурса линия (1) (или отрезок D) движется вверх параллельно себе, постепенно «подтягивая» треугольник СD к точке. Стороны CK и DK этого треугольника представляют собой продолжение линий, соответствующих границам (2) и (4). В точке K ограничения (2) и (4) становятся обязательными; оптимальное решение соответствует точке К, а пространственным (допустимым) решением является многоугольник AVKEF. В точке K предел (1) (для ресурса A) становится избыточным, так как любое дальнейшее увеличение запаса соответствующего ресурса не повлияет ни на пространство решения, ни на оптимальное решение. Таким образом, объем ресурса А не следует увеличивать до высоты предела, соответствующего точке, в которой предел (1) становится избыточным. Рис. 2.3. Определение предельно допустимого прироста запаса ресурса А. Этот предельный уровень определяется следующим образом. Во-первых, устанавливаются координаты точки, в которой пересекаются прямые (2) и (4), то есть происходит решение системы уравнений: В результате получается x1=3 и x2=2. Подставляя координаты точки К в левую сторону ограничения (1), определяем максимально допустимый запас ресурса А: x1+2 x2=2=3+2× 2=7 t. Рис. 2.4 иллюстрирует ситуацию, когда рассматривается вопрос о целесообразности увеличения запаса дефицитного ресурса (2) (исходный продукт В). Новой оптимальной точкой является точка J, где пересекаются линии (6) и (1), то есть x2 = 0, x1 + 2x2 = 6. Отсюда следует, что x1=6,x2=0, а запас продукта B может быть увеличен до значения, равного 2x1+x2=2×6+1×0=12 t. Рис. 2.4. Визначення максимально допустимого збільшення запасу ресурсу В. Розглянемо тепер питання про зменшення правої частини незв’язуючих обмежень. Обмеження (4), x2 2 фіксує граничний рівень попиту на фарбу другого виду. На рис. 2.2. видно, що, не змінюючи оптимального розв’язку, пряму (4) (ЕD) можна опускати донизу до перетину з оптимальною точкою С. Оскільки точка С має координати x1 = і x2= то, зниження попиту на фарбу 2 до величини x2= ніяк не вплине на оптимальність раніше отриманого розв’язку. Розглянемо обмеження (3), -x1+ x2 1, що описує співвідношення між попитом на фарбу 2 і попитом на фарбу 1. У цьому випадку праву частину обмеження можна зменшувати доти, поки пряма (3) (ЕF) не досягне точки С, При цьому права частина обмеження (3) стане рівною -x1+ x2=(- )+( )= -2, що дозволяє записати це обмеження у вигляді: -x1+ x2 -2, або в еквівалентній формі: x1- x2 . Цей результат показує, що раніше отриманий оптимальний розв’язок не зміниться, якщо попит на фарбу 1 перевищить попит на фарбу 2 не більше, ніж на 2 т. Результати проведеного аналізу можна звести в таку таблицю. Таблиця 2.1
жүктеу/скачать 74,92 Kb. Достарыңызбен бөлісу:
|