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

Министерство образования Российской Федерации

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

Томский межвузовский центр дистанционного образования Кафедра автоматизированных систем управления (АСУ) Курсовой проект по дисциплине:

«Исследование операций»

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

Студент гр. z-439-a

М. А. Шелепов

Задание

Предприятие электронной промышленности выпускает две модели радиоприемников, причем каждая модель производится на отдельной технологической линии. Суточный объем первой линии A = 50 изделий, второй линии B = 35 изделий. На радиоприемник первой модели расходуется C = 16 однотипных элементов электронных схем, на радиоприемник второй модели D = 12 таких же элементов. Максимальный суточный запас используемых элементов равен E = 825 единиц. Прибыли от реализации одного радиоприемника первой и второй моделей равны Q = 20 и P = 15 ед. соответственно. Определите оптимальные суточные объемы производства первой и второй моделей на основе графического решения задачи.

Рассмотрите три задачи анализа полученного решения на чувствительность к принятой модели и на основании полученных результатов:

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

2. Определите предел уменьшения производительности второй линии, при котором полученное оптимальное решение останется неизменным;

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

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

5. Определите интервал изменения прибыли от продажи радиоприемника первой модели, в котором оптимальное решение остается неизменным;

6. Определите аналогичный интервал для приемника второй модели;

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

Математическая модель задачи

Математическая модель задачи. Приведем следующие обозначения:

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

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

Функция прибыли (целевая функция) примет вид:

Ограничения на суточный запас элементов (деталей):

Ограничение на объем производства первой линии:, где:

Ограничение на объем производства второй линии:, где:

Определить максимум функции при ограничениях

.

Графический метод решения

электронный предел интервал прибыль

На основание данных изобразим график

Рисунок — 1. Графики на основание данных

Уравнения:

— ограничения на суточный запас деталей;

— прямой целевой функции;

Поскольку коэффициенты при равны, отсюда, прямая (z) и прямая (3) параллельны.

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

Рисунок — 2. Графики целевой функции. При увлечении (z).

Получим оптимальное решение, когда прямая (z) совпадает с прямой (3). При этом оптимальным решением является множество точек прямой BD.

Найдем значение целевой функции для точки D.

Анализ задачи на чувствительность

Первая задача на чувствительность

Выясним, как отразится на оптимальном решении изменения запасов ресурсов. Проанализируем следующие два аспекта:

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

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

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

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

Связывающими являются ограничения:

· запас деталей — прямая (3);

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

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

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

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

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

Дефицитными ресурсами в задаче являются максимальный суточный запас деталей и объем производства первой линии — эти ресурсы исчерпаны полностью.

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

Прямая (3) перемещается вверх параллельно самой себе, стягивая в итоге треугольник ВCD в точку С.

В точке С ограничения (1) и (2) становятся связывающими; оптимальному решению при этом соответствует точка С, а пространством (допустимых) решений становится прямоугольник ОАСЕ. В точке С ограничение (2) становится избыточным, так как любой дальнейший рост запаса соответствующего ресурса не влияет ни на пространство решений, ни на оптимальное решение.

Таким образом, максимальный суточный запас деталей не следует увеличивать сверх того предела, когда соответствующее ему ограничение (3) становится избыточным. Предельный уровень определяется координатами точки С, в которой пересекаются прямые (1) и (2). Координаты и. При этом значение суточного запаса деталей равно. Значение целевой функции равно .

Вторым дефицитным ресурсом является объем производства 1-й линии. Его значение можно увеличивать до пересечения прямой (2) точки Е, в которой связывающим становится ограничение на суточный запас деталей — прямая (3).

Координаты точки:

Значение целевой функции:

К несвязывающему ограничению относится объем производства 2-й линии Из рисунка 2 видно, что, не изменяя оптимального решения, прямую (1) можно двигать вниз до пересечения с оптимальной точкой. Уменьшение объема производства 2-й линии до значения 25/12, никак не изменит значение целевой функции.

Таблица — 1. Результаты проведенного анализа.

Вторая задача на чувствительность

Наиболее выгодное увеличение объема из ресурсов.

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

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

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

Таблица — 2. Ценность единицы каждого из ресурсов.

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

Третья задача на чувствительность

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

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

Рассмотрим прямую (3) при изменении коэффициента .

Рисунок — 3. прямую (3) при изменении коэффициентов .

При уменьшении коэффициента прямая целевой функции будет вращаться против часовой стрелки вокруг точки В. Эта точка будет единственной точкой оптимального решения. Так прямая целевой функции будет вращаться, пока не совпадет с прямой (1). При этом.

При увеличении коэффициента прямая целевой функции будет вращаться по часовой стрелке вокруг точки D. Эта точка будет единственной точкой оптимального решения. Так прямая целевой функции будет вращаться, пока не совпадет с прямой (2). При этом стремится в бесконечность.

Таким образом, интервал изменения коэффициента :

При увеличении коэффициента прямая целевой функции будет вращаться против часовой стрелки вокруг точки В. Эта точка будет единственной точкой оптимального решения. Так прямая целевой функции будет вращаться, пока не совпадет с прямой (1). При этом стремится в бесконечность.

При уменьшении коэффициента прямая целевой функции будет вращаться по часовой стрелке вокруг точки D. Эта точка будет единственной точкой оптимального решения. Так прямая целевой функции будет вращаться, пока не совпадет с прямой (2). При этом .

Таким образом, интервал изменения коэффициента :

Выводы

По завершению выполнения данной работы, а это — разбор задач на чувствительность, выяснили что: Дефицитными ресурсами в задаче являются максимальный суточный запас деталей и объем производства первой линии — эти ресурсы исчерпаны полностью. Рассмотрели увеличение максимального суточного запаса деталей. Таким образом, максимальный суточный запас деталей не следует увеличивать сверх того предела, когда соответствующее ему ограничение (3) становится избыточным. Изменение коэффициентов целевой функции, которые определяются ценами на готовую продукцию, оказывает влияние на наклон прямой, которая представляет эту функцию в принятой системе координат. Очевидно, что идентификация конкретной угловой точки в качестве оптимума зависит, прежде всего, от наклона этой прямой. Это означает, что вариация коэффициентов целевой функции может привести к изменению совокупности связывающих ограничений и, следовательно, статуса того или иного ресурса (т. е. сделать недефицитный ресурс дефицитным, и наоборот).

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

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

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

Снизить запас можно до 825 единиц.

Астафуров В. Г. Исследование операций, Томск 2002 г.

Р. М. Ларин А. В. Плясунов А. В. Пяткин Методы оптимизации. Примеры и задачи. учебное пособие. Новосибирск: Новосибирский государственный университет, 2003.