Курсовая работа (т): Анализ решения задачи линейного программирования на чувствительность к параметрам модели

Второе неравенство , так же соответствует неравенству.

Третье неравенство , так же соответствует неравенству.

Рис. 1 границы неравенств

Рис. 2. Область допустимых решений (ОДР) задачи.

Строим линию 0-го уровня для ЦФ: L0: 30x1+20x2=0.

Рис. 3. Линии уровня ЦФ.

Параллельно перемещаем линию уровня ЦФ до последнего пересечения с ОДР. В точке последнего касания ЦФ и ОДР будет максимальное значение на заданном множестве допустимых решений.

Таким образом оптимальное решение, когда прямая L пройдет через точку C. Координаты точки C:

L* =L(50; 0)=30*50+20*0= 1500

Максимальное значение целевой функции равно L(50; 0)=1500.

При производстве 50 ед. радиоприемников первой модели и 0 радиоприёмников второй модели будет получена максимальная суточная прибыль в размере 1500 ед.

5. Решение задачи с помощью надстройки SOLVER

Создание электронной формы для решения задачи:

Рис. 4. Электронная форма для решения поставленной задачи

Вызываем надстройку «Поиск решений»/ SOLVER

Рис. 5. Заполненное окно надстройки «Поиск решений»

Оптимальное решение будет:

Рис. 6. Оптимальное решение задачи.

ВЫВОД: При производстве 50 ед. радиоприемников первой модели и 0 радиоприёмников второй модели будет получена максимальная суточная прибыль в размере 1500 ед.

Как видно из расчетов решения полученные тремя разными способами полностью совпадают.

Проведем анализ полученных результатов.

математический модель графический программирование

6. Основы анализа на чувствительность

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

В рамках такого анализа выявляется чувствительность оптимального решения к определенным изменениям исходной модели. В наше задаче, например, может представить интерес вопрос о том, как повлияет на оптимальное решение увеличение и уменьшение суточной производительности каждой из технологических линий или изменения запасов используемых элементов. Можно проанализировать влияние на оптимальное решение изменения прибыли от реализаций той и другой моделей радиоприемников.

При таком анализе рассматривается некоторая совокупность оптимизационных моделей. Это придает модели определенную динамичность, позволяющую провести анализ влияния возможных изменений исходных условий на полученное оптимальное решение.

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

Для проведения анализа модели на чувствительность будем использовать графический метод.

6.1 Анализ изменений запасов ресурсов

На сколько можно сократить или увеличить запасы ресурсов?

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

1.      На сколько можно увеличить запас некоторого ресурса для улучшения полученного оптимального значения целевой функции L?

2.      На сколько можно снизить запас некоторого ресурса при сохранении полученного оптимального значения целевой функции?

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

Ограничения линейной модели бывают:

·        связывающие (активные)

·        несвязывающие (неактивные)

Прямые проходящие через оптимальную точку, соответствуют активным ограничениям. Если прямые-ограничения не проходят через оптимальную точку, то они не являются активными.

Так как через оптимальную точку проходит только прямая (I), то ограничение , которые лимитирует запас используемых элементов является активным.

Активные ограничения соответствуют дефицитным ресурсам.

Если ограничение не активно, то данный ресурс не является дефицитным.

Таким образом, при анализе модели на чувствительность к правым частям ограничений определяются:

1.      предельно допустимое увеличение запаса дефицитного ресурса, позволяющее улучшить найденное оптимальное решение;

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

Информация, полученная в последнем случае, особенно полезна в тех ситуациях, когда излишки недефицитного ресурса могут быть использованы для других целей.

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

Активным является только ограничение по суточному запасу элементов электронных схем. Поэтому рассмотрим изменение оптимального решения при увеличении этого ресурса.

·        Увеличение суточного запаса элементов электронных схем. Из рис. 4 видно, что при увеличении запаса этого ресурса прямая (I) (или отрезок ВС) перемещается вверх параллельно самой себе, постепенно «стягивая» в точку F четырехугольник ВCEF. (Стороны CF и ЕF этого треугольника представляют собой продолжения прямых, соответствующих ограничениям (II) и (III).

В точке FЕ ограничения (II) и (III) становятся активными.

Оптимальному решению в этом случае соответствует точка F, а ОДР становится прямоугольник AFED. В точке F ограничение (I) (запас элементов) становится избыточным, потому что любой дальнейший рост запаса элементов электронных схем не влияет ни на ОДР, ни на оптимальное решение. Поэтому объем элементов электронных схем следует увеличивать только до того момента пока соответствующее ему ограничение (I) не станет избыточным, т.е. до уровня пока прямая не пройдет через точку F.

Находим максимальный уровень запасов.

При таком производстве необходимо иметь запас элементов в размере:

 ед.

При этом прибыль составит L(80;45)= ден. единиц.

Рис. 7. Увеличение суточного запаса элементов электронных схем

Так как ограничения (I) и (II) являются не активными, то рассмотрим до какого уровня можно сократить эти ресурсы:

·        Уменьшение производительности технологической линии №1

Из рис.8 видно, что если прямую (II) переместить до точки С, то это не повлечет за собой изменение оптимального решения. Координаты точки С(50;0), таким образом производительность 1-ой технологической линии можно сократить на 30 радиоприемников в сутки, до значения 50.

·        Находим уровень, до которого можно сократить производительность второй технологической линии.

Из рис. 9 следует, что, не изменяя оптимального решения, прямую (III) можно опускать вниз до пересечения с оптимальной точкой С, которая имеет координаты (50; 0).

Рис. 8. Сокращение производительности I-ой технологической линии

Таким образом, использование второй линии не рентабельно и поэтому эту линию можно либо задействовать на другое производство, либо продать, так как при оптимальном производстве она не задействована.

Рис. 9. Сокращение производительности второй технологической линии

Таблица 1

6.2 Определение наиболее выгодного ресурса

Увеличение объема какого из ресурсов наиболее выгодно?

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

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

Для каждого дефицитного ресурса получаем: .

Аналогичным образом можно определить ценность единицы каждого из ресурсов и представить результаты в следующей таблице:

Таблица 5

Полученные результаты указывают на то, что при увеличении суточного запаса элементов электронных схем на 1 единицу прибыль увеличится на 1,538 ден. ед. Увеличение недефицитных ресурсов не увеличит прибыль.

6.3 Определение пределов изменения коэффициентов целевой функции

В каких пределах допустимо изменение коэффициентов целевой функции?

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

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

·        Каков диапазон изменения (увеличения или уменьшения) того или иного коэффициента целевой функции, при котором не происходит изменения оптимального решения?

·        Насколько следует изменить тот или иной коэффициент целевой функции, чтобы сделать некоторый недефицитный ресурс дефицитным и, наоборот, дефицитный ресурс сделать недефицитным?

Обсудим эти вопросы на нашем примере.

Рассматривая первый вопрос, обозначим через с1 и c2 доходы предприятия от продажи одного радиоприемника первой и второй модели соответственно. Тогда целевую функцию можно представить в следующем виде: . Коэффициент наклона ЦФ можно записать в виде ( тангенс угла наклона )

Если увеличить С1 - то коэффициент увеличивается и прямая соответствующая ЦФ начинает вращаться по часовой стрелке. Тоже самое происходит если уменьшить С2. (рис,10)

Рис. 10. Вращение ЦФ по часовой стрелке.

Как только угол наклона ЦФ совпадет с углом наклона прямой (III) (это произойдет, когда прямая ЦФ совпадет с прямой параллельной оси Ох), оптимальное решение изменится и в качестве оптимального решения будет множество принадлежащее отрезку AB.

Если уменьшить С1 - то коэффициент уменьшается и прямая соответствующая ЦФ начинает вращаться против часовой стрелке. Тоже самое происходит если увеличить С2. (рис.11)

Рис. 10. Вращение ЦФ против часовой стрелке.

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

Тангенс угла наклона ЦФ

.

Находим интервал изменения коэффициента С1, для этого фиксируем С2=20. Угол наклона ЦФ:

Вращаем ЦФ до совпадения с прямой (I), тангенс угла наклона которой:

Таким образом уменьшать С1 можно до величины Сmin=25,714

Вращаем ЦФ до совпадения с прямой (II), тангенс угла наклона которой:

Прямая ЦФ и (II) совпадут если

Таким образом увеличивать С1 можно до величины Сmax=∞

Интервал изменения С1:

Аналогично находим интервал изменения коэффициента С2. Фиксируем С1=30, В этом случае угол наклона ЦФ:

Вращаем ЦФ до совпадения с прямой (I), тангенс угла наклона которой: