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

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

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 17.12.2014
Размер файла 289,5 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

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

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

Томский межвузовский центр дистанционного образования

Кафедра автоматизированных систем управления (АСУ)

Курсовой проект по дисциплине:

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

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

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

М. А. Шелепов

2014

Задание

Предприятие электронной промышленности выпускает две модели радиоприемников, причем каждая модель производится на отдельной технологической линии. Суточный объем первой линии 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. Результаты проведенного анализа.

Ресурс

Тип ресурса

Максимальное изменение запаса ресурса

Максимальное изменение дохода

Суточный запас деталей

Дефицитный

1220 - 825 = 395

1525 - 1031= 494

Объем производства 1-й линии

Дефицитный

51.5625 - 50 = 1.5625

1031- 1031= 0

Объем производства 2-й линии

Недефицитный

25/12 - 35 = -32.917

0

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

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

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

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

Обозначим ценность дополнительной единицы ресурса через . Величина определяется из соотношения

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

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

Ресурс

Тип ресурса

Изменение дохода / изменение ресурса

Объем производства 1-й линии

Дефицитный

0 / 1.5625 = 0

Объем производства 2-й линии

Недефицитный

0

Суточный запас деталей

Дефицитный

494 / 395 = 1.25

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

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

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

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

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

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

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

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

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

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

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

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

Выводы

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

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

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

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

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

Литература

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

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

Размещено на Allbest.ru


Подобные документы

  • Построения математической модели с целью получения максимальной прибыли предприятия, графическое решение задачи. Решение задачи с помощью надстройки SOLVER. Анализ изменений запасов ресурсов. Определение пределов изменения коэффициентов целевой функции.

    курсовая работа [2,4 M], добавлен 17.12.2014

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

    курсовая работа [223,0 K], добавлен 23.01.2014

  • Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.

    курсовая работа [132,0 K], добавлен 09.12.2008

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

    курсовая работа [511,9 K], добавлен 20.07.2012

  • Графическое решение задач. Составление математической модели. Определение максимального значения целевой функции. Решение симплексным методом с искусственным базисом канонической задачи линейного программирования. Проверка оптимальности решения.

    контрольная работа [191,1 K], добавлен 05.04.2016

  • Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.

    курсовая работа [1,1 M], добавлен 21.03.2012

  • Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.

    контрольная работа [118,5 K], добавлен 11.04.2012

  • Математическая модель задачи. Построение области допустимых планов. Построение линии уровня целевой функции. Оптимизация целевой функции. Точка контакта линии уровня с областью допустимых планов. Максимальное значение и вектор-градиент целевой функции.

    презентация [534,8 K], добавлен 11.05.2013

  • Построение математической модели. Выбор, обоснование и описание метода решений прямой задачи линейного программирования симплекс-методом, с использованием симплексной таблицы. Составление и решение двойственной задачи. Анализ модели на чувствительность.

    курсовая работа [100,0 K], добавлен 31.10.2014

  • Определение варианта организации функционирования экономического объекта. Каноническая форма задачи линейного программирования. Ввод данных в таблицу Excel. Анализ коэффициентов целевой функции. Пределы изменения дефицитных и недефицитных ресурсов.

    дипломная работа [4,2 M], добавлен 05.07.2013

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.