Решение задач с помощью оптимизационного моделирования

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

«Казанский национальный исследовательский технический университет им.А.Н.Туполева-КАИ»

Кафедра компьютерных систем

 

 

 

 

Курсовой проект

по дисциплине: «Информационные технологии в управлении персоналом»

на тему: «Решение задач  с помощью оптимизационного моделирования»

 

 

Выполнила:

студентка гр.8403

Уразаева Альбина

Провериил:

преподаватель

Захаров В.А.

Казань 2012

Содержание

Введение…………………………………………………………………………..3

Практическая часть……………………………………………………………….4

Задача 1…………………………………………………………………….4

Задача 2……………………………………………………………………..

Задача 3……………………………………………………………………..

Выводы………………...…………………………………………………………29

Заключение……………………………………………………………………….30

Список литературы………………………………………………………………31 

Введение

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

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

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

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

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

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

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

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

Наиболее известны следующие  оптимизационные модели:

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

Для решения оптимизационных  задач в Excel используется надстройка Поиск решения.

В курсовом проекте необходимо решить три задачи:

1. определить оптимальную производственную программу;
2. определить штатное расписание организации;
3. решить транспортную задачу;
4. с помощью PowerPoint подготовить презентацию курсового проекта.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Практическая  часть.

Задача 1.

Выполнение первого  задания предполагает следующие  действия:

1. построение математической модели задачи;
2. получение решения задачи;
3. выполнение анализа отчетов по результатам и устойчивости
4. ответы на вопросы задания;
5. с помощью возможностей Excel построить отчет, в котором привести оптимальную программу и суммарные затраты ресурсов на ее выполнение. Отчет должен быть выполнен таким образом, чтобы любое изменение в решении задачи автоматически отображалось в отчете.

Условие ЗАДАЧИ 1:

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

Тип сырья	Нормы расхода сырья на одно изделие				Запасы  сырья
	А	Б	В	Г
I	1	4	1	3	1120
II	2	3	0	8	950
III	8	6	7	5	1230
Цена изделия	12	9	14	20

 

1) Как изменится общая  стоимость продукции и план  ее выпуска при увеличении  запасов сырья I и Ш видов  на 180 и 170 единиц соответственно  и одновременном уменьшении на 40 единиц запасов сырья первого  вида?

2) Целесообразно ли включать  в план изделие Д ценой 18 единиц, на изготовление которого  расходуется по 3 единицы каждого  вида сырья?

Решение:

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

Введем следующие обозначения:

x₁  - количество продукции A

x₂ – количество продукции Б

х_{3 –} количество продукции В

х₄ – количество продукции Г

Прибыль от реализации продуктов  вида А составляет 12 Х₁, вида Б – 9 X₂, вида В – 14 X₃, вида Г – 20 X₄. Запишем критерий оптимальности:

F(x)=12*х₁+9*x₂+14*x₃+20*x₄          max

Ограничения имеют вид:

1*х₁+4*х₂+1*х₃+3*х₄<=1120 ограничение по I типу сырья

2*х₁+3*х₂+0*х₃+8*х₄<=950   ограничение по II типу сырья

8*х₁+6*х₂+7*х₃+5*х₄<=1230 ограничение по  III типу сырья

Ввод исходных данных.

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

В нашей задаче х1, х2, х3, х4 обозначают нормы расходов сырья на изделие каждого типа. Для оптимального значения вектора Х=( х1, х2, х3, х4) зарезервируем ячейки B2:Е2, а для оптимального значения целевой функции (максимальная прибыль) – ячейку F4.

Ввод зависимости для  целевой функции.

Поместите курсор в ячейку F4. С помощью мастера функций  введите функцию СУММПРОИЗВ. В окне функции в строку Массив1 введите В2:Е2 (ячейки искомых переменных. Этот массив будет использоваться при вводе зависимостей для ограничений, сделайте на него абсолютную ссылку с помощью клавиши F4. 

В строку Массив2 введите B4:E4. На экране до нажатия кнопки ОК будем иметь:

После нажатия кнопки ОК, то есть после выполнения функции СУММПРОИЗВ вид экрана показан на рисунке:

В режиме просмотра формул, это выглядит следующим образом:

 В диалоговом окне Поиск решения нажмите кнопку Параметры. На экране появится диалоговое окно Параметры поиска решения. Устанавливаем флажки в окнах Линейная модель (это обеспечит применение симплекс-метода¹) и Неотрицательные значения².· Нажмите на кнопку ОК. На экране появится диалоговое окно Поиск решения.· Нажмите на кнопку Выполнить. Через короткий промежуток времени появится окно Результаты поиска решения и исходная таблица с заполненными ячейками В2:Е2 для значений хi, и ячейка F4 с максимальным значением целевой функции:

Укажите тип отчетов Результаты и Устойчивость. В результате получим на отдельных листах Отчет по результатам и Отчет по устойчивости. Отчетом по результатам и Отчетом по устойчивости будут иметь вид:

 

 

Структура отчета по результатам.

В разделе Целевая ячейка указана максимальная суммарная прибыль – 3647,5 денежных единиц.

В разделе Изменяемые ячейки показан оптимальный план:

Х1 (количество продукции А) –0;

Х2 (количество продукции Б) – 0;

Х3 (количество продукции В) – 90,89;

Х4 (количество продукции Г) – 118,75.

В разделе Ограничения показано, что при оптимальном плане тип сырья II и III используются полностью (Статус –связанное), а I тип сырья недоиспользуется, о чем сообщает Статус – несвязанное.

Структура отчета по устойчивости.

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

У недефицитных ресурсов (I) теневая цена равна нулю.

Например, подсчитаем, как  изменится суммарная прибыль (целевая  функция), если запасы сырья I вида увеличить на 180 единиц и запасы сырья вида III увеличить на 170 единиц, запасы сырья вида II уменьшить на 40 единиц. Для этого вычислим выражение:

180*0+170*2-40*1,25=290

То есть, в данном случае суммарная прибыль увеличится на 290 единиц.

Двумя правыми колонками  задается допустимый диапазон изменения  запаса ресурсов. При изменении запаса ресурсов в указанном диапазоне значение теневой цены сохраняется.

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

Запасы сырья II вида: 1,25*2=3 денежных единиц

Запасы сырья III 2*2=4 денежных единиц.

Следует заметить, что  значение 1Е+30 в допустимом увеличении для запасов сырья I свидетельствует о том, что данный параметр не влияет на целевую функцию.

Отсюда делаем вывод, что  выгоднее всего вкладывать средства в закупку Запасов сырья вида III.

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

По тем видам изделий, где нормированная стоимость  больше или равна нулю, делается вывод, что выпуск этих изделий предприятию выгоден (в данном случае изделия видов В и Г).

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

Затраты ресурсов на производство единицы продукции вычисляются  путем умножения теневой цены каждого ресурса на нормы его расхода на единицу изделия и последующего суммирования их.

Например, для изделия  х1 (изделия вида А) затраты ресурсов на производство единицы продукции будут равны:

1*0+1,25*2+8´2=19

Прибыль от реализации изделия вида А составляет 12 денежных единиц, тогда нормированная стоимость будет равна разности прибыли и затрат на одно изделие:

Прибыль-затраты=12-19 =-7.

Это означает, что производство продукции вида А предприятию не выгодно.

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