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

[Введите текст]

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение задачи 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 6 — Отчет по устойчивости задачи 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 можно уменьшить до 29 000 часов.

Постановка задачи 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 килограмм. Определить ежедневный план работы цеха, приносящий максимальный доход.

Решение задачи Пусть — количество килограмм выпущенных тортов «Нижегородский», «Киевский», «Ежик», «Полет» соответственно.

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

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

В результате имеем следующее решение:

Рис. 8 — Решение для задачи 2

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

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

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

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

Рис. 9 — Поиск решения для двойственной задачи 2

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

Рис. 10 — Решение для двойственной задачи 2

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

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

Рис. 11 — Отчет по устойчивости задачи 2

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

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

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

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

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

Относительно дефицитных ресурсов можно поставить вопрос о том, какой из них наиболее ценен, то есть приносит наибольшую прибыль и вопрос о предельном наращивании каждого из ресурсов. Ответ на первый вопрос дает сопоставление величины теневых цен. Один дополнительный кг масла приносит прибыль в размере 39 единиц, один дополнительный кг сахара- 112 единиц, а один дополнительный кг торта «Ежик» дает прибыль в 25 единиц согласно двойственным оценкам. Если теперь сопоставить 1 дополнительный кг масла и один кг сахара можно выбрать наиболее ценный ресурс. Например, кг масла на рынке стоит 200 рублей, а кг сахара 30 рублей, тогда 200 рублей, вложенных в оплату дополнительного кг масла принесет 39 единиц прибыли, а 200 рублей, потраченных на дополнительный кг сахара, принесет 746 единиц прибыли. Получается, что сахар более ценный ресурс.

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

Так ресурс масло можно увеличить на 130 единиц, ресурс сахар на 50 единиц, ресурс торт «Ежик» на 200 кг.

Можно так же поставить вопрос о влиянии уменьшения дефицитного ресурса на принимаемый план производства. Ответ на него дает графа Допустимое уменьшение. Ресурс масло можно уменьшить на 62 кг, ресурс сахар на 32 кг, ресурс торт «Ежик» на 371 кг. Данное уменьшение не влияет на оптимальный план выпуска продукции. Двойственные оценки при этих изменениях остаются такими же.

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

Заключение

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

Применение математики в экономической науке дало толчок в развитии как самой экономической науки, так и прикладной математики в части методов экономико-математического моделирования. Пословица говорит: «Семь раз отмерь — один отрежь». Использование моделей и есть своеобразный математический способ «примерить» вырабатываемое решение, позволяющий экономить время, силы, материальные средства. Кроме того, расчеты по моделям противостоят «волевым» решениям, поскольку позволяют заранее оценить последствия каждого решения, отбросить недопустимые варианты и рекомендовать наиболее удачные.

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

1. Акулич И. Л. Математическое программирование в примерах и задачах: Учебное пособие для студентов экономических специальностей вызов. — М.: Высш. шк., 1986. — 319 с.

2. Некрасова Н. В., Жарикова М. И. Экономико-математическое моделирование: Учебное пособие. — Й-Ола: МарГТУ, 2002. — 144 с.