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

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

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

Пояснительная записка к курсовому проекту

по дисциплине «Программирование»

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

Выполнил:

студент ТМЦДО

Студент гр. з-430-а

Ихиянов Наиль Фанузович

«___»________2014 г.

2014

Содержание

• Введение
• 1. Постановка задачи
• 2. Построение математической модели
• 3. Решение задачи симплекс-методом
• 4. Графическое решение задачи
• 5. Решение задачи с помощью надстройки SOLVER
• 6. Основы анализа на чувствительность
• 6.1 Анализ изменений запасов ресурсов
• 6.2 Определение наиболее выгодного ресурса
• 6.3 Определение пределов изменения коэффициентов целевой функции
• Выводы
• Литература

Введение

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

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

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

· построение экономических и математических моделей для задач принятия решения в сложных ситуациях или в условиях неопределенности;

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

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

Ш задачи об использовании ресурсов (планирование производства)

Ш задачи о смесях

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

Ш задачи о раскрое материалов

Ш транспортные задачи и др.

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

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

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

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

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

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

Модель операции- это достаточно точное описание операции с помощью математического аппарата (различного рода функций, равнений, систем уравнений и неравенств и т.п.).

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

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

Одной из таких задач является «задача производственного планирования» или «распределительная задача», которая и будет рассмотрена далее.

1. Постановка задачи

Предприятие электронной промышленности выпускает две модели радиоприемников, причем каждая модель производится на отдельной технологической линии. Суточный объем первой линии A=80 изделий, второй линии B=45 изделий. На радиоприемник первой модели расходуется C=18 однотипных элементов электронных схем, на радиоприемник второй моделиD=14 таких же элементов. Максимальный суточный запас используемых элементов равен E=900 единиц. Прибыли от реализации одного радиоприемника первой и второй моделей равны Q=30 и P=20 ед. соответственно. Определите оптимальные суточные объемы производства первой и второй моделей на основе графического решения задачи.

№ варианта	A	B	E	C	D	Q	P
7	80	45	900	18	14	30	20

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

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

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

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

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

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

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

2. Построение математической модели

Для построения математической модели необходимом определить:

· Переменные

· Целевую функцию

· ограничения

1. Переменные

Х1- суточное количество произведенных приемников модели №1

Х2- суточное количество произведенных приемников модели №2

2. Целевая функция (ЦФ)

Цель предприятия получение максимальной прибыли

3. Ограничения:

· На производство приемников двух моделей расходуются элементы электронных схем, суточный запас которых ограничен и составляет 900 ед., так как на производство 1 модели приемника первого типа необходимо затратить 18 ед. элементов электронных схем, а на производство одного радиоприемника второго типа необходимо 14 ед., то при производстве х1 и х2, расход элементов электронных схем составит:

· Мощность первой линии позволяет производить не более 80 радиоприемников первой модели в сутки:

· Мощность второй линии позволяет производить не более 45 радиоприемников второй модели в сутки:

· Неотрицательность переменных:

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

3.Решение задачи симплекс-методом

От неравенств ограничений переходим к ограничениям равенствам.

Переменные х3,х4,х5 - базисные, а x1, x2 -свободные.

Заполним 1-ую симплекс таблицу

				C1=30	C2=20	C3=0	C4=0	C5=0
№	БП	Сб	bi	A1	A2	A3	A4	A5
1	A3	0	900	18	14	1	0	0
2	A4	0	80	1	0	0	1	0
3	A5	0	45	0	1	0	0	1
	0	-30	-20	0	0	0

Находим базисное решение, для этого все свободные переменные приравниваем к 0, а базисные к bi:

Х0=(0; 0; 900; 80; 45)

L0=30*0+20*0=0

Решение базисное, так как все переменные не отрицательны.

Находим оценки плана и помещаем в строку :

Так как 2 вектора А1, А2 имеют отрицательную оценку плана, то решение не оптимальное.

Решаем какой из двух векторов выгоднее ввести в базис.

Функция цели меняется по формуле:

Если вводим вектор А1:

Функция цели при вводе вектора А1 изменится на:

=50*(-30)=-1500

увеличится на 1500 единиц

Если вводим вектор А2:

Функция цели при вводе вектора А2 изменится на:

=45*(-20)=-900 увеличится на 900 единиц

Из рассмотренных случаев видно, что при вводе в базис вектора А1 значение ЦФ увеличится больше всего на 1500 единиц. Поэтому в качестве разрешающего столбца берем А1. Разрешающая строка будет та которая отвечает И для этого столбца

№ 1 и вектор А3

Меняем А1--А3 и переходим к новой таблице по правилу:

- все элементы ведущей строки делим на разрешающий элемент

- заполняем базисные столбцы

- все остальные элементы симплекс таблицы находим по формуле:

				C1=30	C2=20	C3=0	C4=0	C5=0
№	БП	Сб	bi	A1	A2	A3	A4	A5
1	A1	30	50	1	0,778	0,056	0	0
2	A4	0	30	0	-0,778	-0,056	1	0
3	A5	0	45	0	1	0	0	1
	1500	0	3,333	1,667	0	0

Новое базисное решение

X2=( 50; 0; 0; 30; 45)

L2(x) = 30*50+20*0=1500

В строке оценок плана все коэффициенты не отрицательны, найденное решение является оптимальным.

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

.

Вывод: для получения оптимальной суточной прибыли необходимо производить 50 радиоприемников первой модели (х1=50) , а радиоприемники второй модели не производить (х2=0), так как это приведет к снижению максимальной прибыли. В случае оптимального производства, максимальная суточная прибыль составит 1500 усл.ед.

4. Графическое решение задачи

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

. (I)

(II)

(III)

Так как переменные неотрицательны, то рассматриваем только первую четверть.

Строим соответствующие прямые и определяем полуплоскости соответствующие неравенствам.

Для этого возьмем точку M(10;10).

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

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

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



Рис. 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.

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

Координаты точки F (х1=80; х2=45) так как точка F находится на пересечении прямых (II) и (III)

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

ед.

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



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

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

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

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

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

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



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

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

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

Таблица 1

Ресурс	Тип ресурса	Максимальное изменении запаса ресурса	Максимальное изменении прибыли от реализации
I	дефицитный
II	недефицитный
III	недефицитный

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

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

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

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

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

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

Таблица 5

Ресурс	Тип ресурса	Значение Yi
I	дефицитный	1,538
II	недефицитный	0
III	недефицитный	0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

Таким образом увеличивать С2 можно до величины Сmax=23,33

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

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

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

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

Выводы

Для получения максимальной суточной прибыли в размере 1500 ден. ед. рекомендуется производить 50 радиоприемников первой модели, а радиоприемников второй модели не производить. При этом суточный запас элементов электронных схем расходуется полностью. Мощности первой и второй технологических линий используются не полностью и их можно сократить: первой технологической линии до 50 ед./сутки, а вторую технологическую линии вообще не рекомендуется использовать, ее можно настроить на другое производство или продать. Теневая цена ресурса соответствующего суточному запасу элементов электронных схем составляет 1,538 ед, это значит, что при увеличении запасов элементов на 1 единицу прибыль увеличится на 1,538 ден. ед.

Литература

1. Ашманов С.А. Линейное программирование.- М.: Высшая школа, 1961.

2. Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем. - М.: «Финансы и статистика», 2003г.

3. Гольштейн Е.Г. Линейное программирование /Е.Г. Гольштейн, Д.Б. Юдин. - М.: Наука, 1969.

4. Дегтярев Ю.И. Исследование операций. - М.: Высшая школа, 1986.

5. Исследование операций в экономике. /Под редакцией профессора Н.Ш. Кремера. - М.: «Финансы и статистика», 2004г.

6. Каплан А.В., Каплан В.Е., Мащенко М.В., Овечкина Е.В. Решение экономических задач. Москва, 2004г.

7. Ларионов А.И., Юрченко Т.И. Экономико-математические методы в планировании: Учебник - М.: Высшая школа, 1984.

8. Математические методы анализа экономики /под ред. А.Я. Боярского. М., Изд-во Моск. Ун-та, 1983.

9. Минюк С.А., Ровба Е.А., Кузьмич К.К. Математические методы и модели в экономике. Минск, Тетра Системс, 2002г.

10. Орлова И.В. Экономико-математическое моделирование. Москва, Вузовский учебник ВЗФЭИ, 2004г.

11. Практикум по информатике. /Под ред. Е.К. Хеннера, Москва , 2001г.

12. Сборник задач по высшей математике для экономистов. Учебное пособие под редакцией проф. В.И. Ермакова. Москва, Инфра-М, 2001г.

13. Смородинский С.С., Батин Н.В. Методы и алгоритмы для решения оптимизационных задач линейного программирования. - Мн.: БГУИР, 1995.

14. Смородинский С.С., Батин Н.В. Анализ и оптимизация систем на основе аналитических моделей. - Мн.: БГУИР, 1997.

15. Фомин Г.П. Математические методы в коммерческой деятельности. Москва «Финансы и статистика» 2001 г.

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