Решение задач линейного программирования в программной среде MS Excel

 

 

Кафедра «Информационных  систем в экономике»

 

 

 

Курсовая  работа по курсу

«Экономико-математическое моделирование»

на тему:

«Решение задач линейного программирования в программной среде MS Excel»

Вариант 12

 

                                                                        

 

 

 

                                                                        Выполнила: студентка гр. ММЭ-41

 

 

 

 

                                                           

 

 

 

 

 

 

Содержание:

1. Введение                    3

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

3. Решение задачи 1                  5

4. Решение двойственной задачи 1                                                      8

5. Анализ отчета по устойчивости                10

6. Постановка задачи 2                 13

7. Решение задачи 2                 14

8. Решение двойственной задачи 2               17

9. Анализ отчета по устойчивости                19

10. Заключение                  22

11. Список использованной литературы              23

 

 

 

 

 

 

 

 

 

 

 

1. Введение

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

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

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

 

 

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

Производственный  участок изготавливает изделия  И-1,И-2,И-3 для сборочного конвейера  предприятия-заказчика. Потребность  в них 300, 500, 400 шт. соответственно. Запасы металла на изделие И-1 ограничены, поэтому их можно производить не более 350 шт.

Все изделия  последовательно обрабатываются на станках С-1, С-2, С-3. Технология изготовления первого изделия допускает три  способа обработки, второго изделия  – два способа. Нормы времени  на обработку, плановая себестоимость и оптовые цены изделий приведены в таблице:

Таблица 1. Исходные данные

	Изделия и способы  обработки
Показатели	И-1			И-2		И-3
	1	2	3	1	2
Норма времени  на обработку, часов:
на С-1	3	7	0	8	4	3
на С-2	2	3	6	3	2	3
на С-3	7	5	6	0	3	6
Плановая себестоимость руб.	13	15	11	20	24	10
Оптовая цена руб.		16		25		20

 

Плановый фонд времени  работы станков составляет для станков  С-1 и С-2 по 6000 часов, для С-2 – 40000 часов.

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

3. Решение задачи 1

Пусть - количество изделий вида И-1, изготовленных 1, 2 и 3 способами обработки соответственно,  - количество изделий вида И-2, изготовленных 1 и 2 способами обработки соответственно, - количество изделий вида И-3.

По условию  задачи потребность в изделиях И-1, И-2, И-3составляет соответственно 300, 500, 400. А запасы металла на изделие И-1 ограничены, поэтому их можно производить не более 350 шт. Поэтому

В соответствии с таблицей задачи составим ограничения:

 

Составим функцию  прибыли:

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

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

Рис.1- Ввод данных задачи 1 в  MS Excel

После ввода  данных, воспользуемся функцией «Поиск решения», установив в роли целевой  ячейку H10, равную максимальному значению. Требуем изменения ячеек B12:G12 и добавляем ограничения: B12:G12=целое и ≥ 0; I2≤J2; I3≤J3; I4≤J4; I5≤J5. Во вкладке «Параметры» ставим галочку напротив параметров «Линейная модель» и «Неотрицательные значения». Поиск решения выглядит следующим образом:

Рис.2- Поиск решения задачи 1

Далее нажимаем кнопку «Выполнить», предлагаем вывести  отчет по устойчивости и нажимаем ОК.

В итоге мы получили следующее решение:

,

Выглядит оно  следующим образом:

Рис. 4- Полученное решение задачи 1

 

 

 

 

 

 

 

 

 

 

4. Решение двойственной задачи 1

Двойственная  к прямой задаче линейного программирования имеет следующий вид:

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

Рис.5- Поиск решения для  двойственной задачи 1

В итоге мы получаем следующее решение:

Рис.6- Решение двойственной задачи 1

То есть мы получили следующее оптимальное решение:

,

 

 

 

 

 

 

 

 

 

 

 

 

 

5. Анализ отчета по устойчивости

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

Отчет по устойчивости задачи 1 выглядит следующим образом:

Рис. 7- Отчет по устойчивости задачи 1

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

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

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

Проведем анализ оптимального решения нашей задачи. Правые части  ограничений- это объемы ресурсов. Ресурсами являются потребность в изделиях, запасы металла и плановый фонд времени работы станков. Ресурсы «Потребность в изделии И1», «Потребность в изделии И2», «Плановый фонд времени работы станка С1» и «Плановый фонд времени работы станка С2» являются дефицитными, так как они используются полностью. На это указывают ненулевые значения Теневой цены. Эти ресурсы следует наращивать, если возникает необходимость увеличить прибыль.

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

Относительно дефицитных ресурсов можно поставить вопрос о том, какой из них наиболее ценен, то есть приносит наибольшую прибыль и вопрос о предельном наращивании каждого из ресурсов. Ответ на первый вопрос дает сопоставление величины теневых цен. Одно дополнительное изделие И1 принесет фирме 5 единиц прибыли, одно дополнительное изделие И3 принесет 9 единиц прибыли, 1 дополнительный час работы станка С1 принесет 2 единицы прибыли и один дополнительный час работы станка С2 принесет так же 2 единицы прибыли согласно двойственным оценкам. Если теперь сопоставить 1 дополнительный час работы станка и одно дополнительное изделие, например, И3, можно выбрать наиболее ценный ресурс. Например, час рабочего времени стоит 20 рублей, а изделие И3 10 рублей, тогда 20 рублей, вложенных в оплату дополнительного времени работы станка принесет 2 единицы прибыли, а 20 рублей, потраченных на изготовление изделия И3, принесет 18 единиц прибыль. Получается, что потребность в изделии И3 более ценный ресурс.

Если же час рабочего времени  стоит 2 рубля, а изделие И3 20 рублей, то ситуация меняется, в таком случае, более ценным ресурсом будет являться время работы станка.

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

Так ресурс «Потребность в изделии И1» можно увеличить на 133 единицы, ресурс «Потребность в изделии И3» на 500 единиц, ресурс «Плановый фонд рабочего времени станка С1» на 1300 часов, а ресурс «Плановый фонд рабочего времени станка С2» на 800 часов.

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

Увеличение  недефицитных ресурсов не имеет никакого смысла, так как не приводит к изменению значения целевой функции и двойственных оценок. Поэтому его можно только уменьшать. Ресурс 2 можно уменьшать до 50 единиц. Дальнейшее уменьшение приведет к тому, что этот ресурс станет дефицитным. Ресурс 4 можно уменьшить до 819 единиц, а ресурс 7 можно уменьшить до 29000 часов.

 

 

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

Кондитерский  цех выпускает торты "Нижегородский", "Киевский", "Ежик", "Полет". Для выпечки торта "Нижегородский" следует взять 6 частей муки, 4 части масла, 3 части яиц, 3 части сахара, 1 часть шоколада, 1 часть орехов. Для "Киевского" торта эти продукты берутся в частях: 3, 4, 5, 1, 2, 2. Для торта "Ежик": 7, 5, 4, 3, 1, 0. Для торта "Полет": 3, 5, 7, 4, 0, 2. Продукты покупаются по цене соответственно: 7, 40, 12, 10, 50, 30 рублей за килограмм. Торты реализуются по цене: 30, 40, 20, 50 рублей за килограмм. Ежедневные поставки в цех муки, масла и сахара не могут превосходить 300, 200, 100 килограмм. Тортов "Ежик" должно быть произведено не менее 200 килограмм. Определить ежедневный план работы цеха, приносящий максимальный доход.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

7. Решение задачи 2

Пусть - количество килограмм выпущенных тортов "Нижегородский", "Киевский", "Ежик", "Полет"соответственно.

По условию  задачи составим систему ограничений

 

 

Стоимость продуктов  при этом составит

Средства, полученные от продажи тортов

Прибыль кондитерского  цеха

Таким образом, получаем задачу линейного программирования

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

Рис.8- Поиск решения для задачи 2