Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ПЕРМСКИЙ ИНСТИТУТ МУНИЦИПАЛЬНОГО УПРАВЛЕНИЯ
(ВШПП)
Дисциплина: Методы оптимальных решений
КУРСОВАЯ РАБОТА
Тема: «Разработка модели и решение задачи линейного программирования (на примере задачи о составлении графика работы персонала)»
Выполнил:
Студент группы ЧЭ 11-3
Красноперова Юлия Борисовна _________________
«__» _________ 2013 г. (подпись)
Проверил:
преподаватель
Муратова Елена Андреевна _________________
«__» _________ 2013 г. (подпись)
СОДЕРЖАНИЕ
Введение 3
Заключение 19
Список используемой литературы 20
ВВЕДЕНИЕ
В своей жизни мы ежедневно сталкиваемся с необходимостью принимать решения. Менеджерам, экономистам, коммерсантам для принятия правильного решения, приходится учитывать много факторов, и сделать это без помощи компьютера порой невозможно. В настоящее время множество задач планирования и управления в отраслях народного хозяйства, а также большой объём частных прикладных задач решаются методами математического программирования. Наиболее развитыми в области решения оптимизационных задач являются методы линейного программирования. Эти методы позволяют описать с достаточной точностью широкого круга задач коммерческой деятельности, таких, как планирование товарооборота; размещение розничной торговой сети города; планирование товароснабжения города, района; прикрепление торговых предприятий к поставщикам; организация рациональных перевозок товаров; распределение работников торговли должностям; организация рациональных закупок продуктов питания; распределение ресурсов; планирование капиталовложений; оптимизация межотраслевых связей; замена торгового оборудования; определение оптимального ассортимента товаров в условиях ограниченной площади; установление рационального режима работы.
В задачах линейного программирования критерий эффективности и функции в системе ограничений линейны. Если содержательный смысл требует получения решения в целых числах, то такая задача является задачей целочисленного программирования. Если в задаче математического программирования имеется переменная времени, а критерий эффективности выражается через уравнения, описывающие течение операций во времени, то такая задача является задачей динамического программирования.
Во многих экономических моделях зависимости между постоянными и переменными факторами можно считать линейными. Использование методов математического программирования в коммерческой деятельности связано со сбором необходимой информации коммерсантом, экономистом, финансистом, затем постановкой задачи вместе с математикой. Поскольку методы математического программирования уже реализованы на компьютере в виде пакета стандартных программ, то доступ к ним обычно прост, автоматизирован и не составляет особых трудностей.
Тогда эксплуатация модели включает в себя сбор и обработку информации, ввод обработанной информации в ЭВМ, расчеты на основе разработанных программ календарных планов и, наконец, выдачу результатов вычислений (в удобном для пользователей виде) для их использования в сфере производственной деятельности.
Целью выполнения курсовой работы является изучение методов оптимальных решений, развитие навыков самостоятельной творческой работы, практическое применение полученных теоретических знаний при решении задачи о составлении графика работы персонала.
В общем виде задачу эффективного управления в любой сфере деятельности можно определить как достижение наилучших с точки зрения целей данной организации результатов при использовании доступных ресурсов и в условиях тех или иных ограничений, которые налагает на ее деятельность внешняя среда.
Для применения количественных методов исследования требуется построить математическую модель операции.
Экономико-математическая модель — это математическое описание исследуемого экономического процесса или объекта. Эта модель выражает закономерности экономического процесса в абстрактном виде с помощью математических соотношений. Использование математического моделирования в экономике позволяет углубить количественный экономический анализ, расширить область экономической информации, интенсифицировать экономические расчеты.
Экономико-математические методы и модели применяют с целью отыскания наилучшего решения, т. е. решения, оптимального в том или ином смысле (максимума или минимума). Но задачи математического программирования применяют только тогда, когда имеется много допустимых решений (два и более).
Разработку любой модели оптимизации можно приблизительно разбить на 5 стадий, частично перекрывающих друг друга и не имеющих четких границ:
1. Постановка (формулировка) задачи.
2. Разработка математической модели изучаемой системы.
3. Отыскание решения с помощью этой модели.
4. Проверка данной модели и решения.
5. Уточнение решения на практике.
В общем виде математическая постановка задачи линейного программирования состоит в определении значения целевой функции.
Целевой функцией называют величину, значение которой количественно характеризует цель, которую мы хотим достичь. Это может быть прибыль от производства, тогда наша цель сделать ее максимальной, или затраты, тогда цель – их минимизировать. Математически это записывается так:
Е=F(х ; y)
Где Е – мера общей эффективности, F – функция, задающая соотношение между Е, х, y.
х – величины, которые мы можем изменять, и от которых зависит целевая функция, называются переменными решения. По-другому эти величины можно назвать неизвестными, поскольку мы стремимся найти такие их значения, при которых целевая функция достигает максимума (или минимума).
y – некоторые действительные числа, или параметры модели. В ходе решения они остаются неизменными, постоянными. Параметры модели определяют вид и значения целевой функции.
Рассмотрим наиболее распространенные задачи линейного программирования.
Смысл задачи об использовании ресурсов заключается в составлении такого плана продаж, исходя из имеющихся запасов, при котором прибыль будет максимальной.
Пример. Для изготовления двух видов продукции Р1 и Р2 используют три вида сырья: S1, S2, S3. Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а так же величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 1.1.
|
Норма расхода сырья |
Таблица 1.1. |
||
|
Вид сырья |
Запас сырья |
Количество единиц сырья, идущих на изготовление единицы продукции |
|
|
Р1 |
Р2 |
||
|
S1 |
20 |
2 |
5 |
|
S2 |
40 |
8 |
5 |
|
S3 |
30 |
5 |
6 |
|
Прибыль от единицы продукции, руб. |
50 |
40 |
Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль.
Обозначим через х1 количество единиц продукции Р1, а через х2 – количество единиц продукции Р2. Тогда целевая функция (прибыль от реализации) будет записываться Z = 50х1 + 40х2 → max
Поскольку количество сырья, расходуемого на изготовление продукции, не может превышать имеющихся запасов, получим систему ограничений:
2х1 + 5х2 ≤ 20
8х1 + 5х2 ≤ 40
5х1 + 6х2 ≤ 30
х1 ≥ 0
х2 ≥ 0
Цель задачи о смесях составить рацион, позволяющий обеспечить всеми необходимыми питательными элементами, с минимальными затратами.
Пример. При откорме каждое животное ежедневно должно получать не менее 9 ед. питательного вещества S1, не менее 8 ед. вещества S2 и не менее 12 ед. вещества S3. Для составления рациона используют два вида корма. Содержание количества единиц питательных веществ в 1 кг каждого вида корма и стоимость 1 кг корма приведены в таблице 1.2.
|
Содержание питательн. |
веществ |
Таблица 1.2. |
|
Питательные вещества |
Количество единиц питательных веществ в 1 кг корма |
|
|
Корм 1 |
Корм 2 |
|
|
S1 |
3 |
1 |
|
S2 |
1 |
2 |
|
S3 |
1 |
6 |
|
Стоимость 1 кг корма, руб. |
4 |
6 |
Необходимо составить дневной рацион нужной питательности, причем затраты на него должны быть минимальными.
Для составления математической модели обозначим через х1 и х2 соответственно количество килограммов корма 1 и 2 в дневном рационе. Цель данной задачи – добиться минимальных затрат на дневной рацион, поэтому общую стоимость рациона можно выразить в виде линейной функции Z = 4х1 + 6х2 → min
Принимая во внимание значения, приведенные в таблице 1.2, и условие, что дневной рацион удовлетворяет требуемой питательности только в случае, если количество единиц питательных веществ не меньше предусмотренного, получаем систему ограничений:
3х1 + х2 ≥ 9
х1 + 2х2 ≥ 8
х1 + 6х2 ≥ 12
х1 ≥ 0
х2 ≥ 0
Задача оптимального раскроя материалов заключается в определении наиболее рационального способа раскроя имеющихся материалов (стальной лист, полоса, круг, швеллер, стекло, бревно и т.д.)
Пример. Продукция бумажной фирмы выпускается в виде бумажных рулонов стандартной ширины – по 2 метра. Фирма имеет заказы на бумажные рулоны разной ширины: 150 шт – шириной 0,5 м, 200 шт – шириной 0,7 м, 300 шт – шириной 0,9 м. Существует 6 вариантов, известно количество отходов в результате раскроя каждым из шести способов, данные приведены в таблице 1.3.:
|
Варианты раскроя |
Таблица 1.3. |
||||||
|
ширина рулона |
варианты раскроя |
заказанное кол-во рулонов |
|||||
|
1 |
2 |
3 |
4 |
5 |
6 |
||
|
0,5 |
0 |
2 |
2 |
4 |
1 |
0 |
150 |
|
0,7 |
1 |
1 |
0 |
0 |
2 |
0 |
200 |
|
0,9 |
1 |
0 |
1 |
0 |
0 |
2 |
300 |
|
Отходы (м) |
0,4 |
0,3 |
0,1 |
0 |
0,1 |
0,2 |
|
Обозначим переменные:
х1 – количество рулонов раскроенных первым способом
х2 – количество рулонов раскроенных вторым способом
х3 – количество рулонов раскроенных третьим способом
х4 – количество рулонов раскроенных четвертым способом
х5 – количество рулонов раскроенных пятым способом
х6 – количество рулонов раскроенных шестым способом
Целью нашей задачи будет минимизация отходов. Целевая функция будет рассчитываться как:
О = 0,4* х1 + 0,3* х2 + 0,1* х3 + 0,1* х5 + 0,2* х6 → min
Поскольку при раскрое рулона четвертым способом отходы не образуются, то значение величины х4 не будет влиять на целевую функцию. Исходя из имеющихся заказов, пропишем ограничения:
2*х2 + 2*х3 + 4*х4 + х5 ≥ 150
х1 + х2 +2* х5 ≥ 200
х1 + х3 +2* х6 ≥ 300
1.5 Транспортная задача
Транспортная задача заключается в отыскании оптимального плана перевозок с минимальными транспортными расходами, она бывает открытая и закрытая. В открытой задаче количество продукции, находящейся на складе, больше (либо меньше) количества, требующегося потребителям. В закрытой задаче количество продукции, находящейся на складе, равно количеству, требующемуся потребителям.
Пример закрытой транспортной задачи.
На товарных станциях А 1 и А 2 имеется по 30 комплектов мебели. Известно, что перевозка одного комплекта со станции С1 в магазины М1, М2, М3 стоит 1р., 3р., 5р., а стоимость перевозки со станции С1 в те же магазины – 2р., 5р., 4р. необходимо доставить в каждый магазин по 20 комплектов мебели. Составить план перевозок так, чтобы затраты на транспортировку мебели были наименьшими.
Количество комплектов мебели, перевозимых со станции А1 в магазины М1, М2, М3 обозначим через х11, х12, х13, а со станции А 2 – через х21, х22, х23. Тогда схема перевозок буде выглядеть следующим образом (см. таблицу 1.4.):
Схема перевозок Таблица 1.4.
|
в М1 |
в М2 |
в М3 |
Всего отправлено |
|
|
Из А1 |
х11 |
х12 |
х13 |
30 |
|
Из А 2 |
х21 |
х22 |
х23 |
30 |
|
Всего получено |
20 |
20 |
20 |
60 |
Целевая функция (стоимость перевозок) будет находиться:
С = х11 + 3 х12 + 5 х13 + 2 х21 + 5 х22 + 4 х23
Ограничения:
х11 + х12 + х13 = 30
х21 + х22 + х23 = 30
х11 + х21 = 20
х12 + х22 = 20
х13 + х23 = 20
Очень важно правильно организовать работу предприятия для получения качественной продукции с минимальными затратами. Для этого необходимо подобрать оптимальный график работы персонала.
Рассмотрим пример: Открывается новый филиал супермаркета. Необходимо рассчитать численность кассиров и подобрать оптимальные графики их работы. Количество покупателей зависит от времени суток и отличается по дням недели. Магазин работает с 8-00 до 24-00 ч. Известно количество касс, необходимое для эффективного обслуживания покупателей, данные сведены в таблицу (таб. 2.1.).
Потребность в кассирах таблица 2.1.
|
Часы работы |
8-12 |
12-16 |
16-20 |
20-24 |
|
пн |
3 |
5 |
8 |
3 |
|
вт |
3 |
5 |
8 |
3 |
|
ср |
3 |
5 |
8 |
3 |
|
чт |
3 |
5 |
8 |
3 |
|
пт |
3 |
5 |
8 |
5 |
|
сб |
3 |
8 |
5 |
5 |
|
вс |
3 |
8 |
5 |
3 |
По условиям задачи кассир получает заработную плату 40 у.е. в день, из расчета 8-ми часовой рабочей смены.
Для решения данной задачи определяем цель – минимизировать расходы на оплату труда кассиров. Значит, целевая функция будет вычисляться как сумма произведений числа кассиров в каждую смену на заработную плату. Переменными решения (х1, х2, х3, … х28) будет количество персонала, работающего в четырехчасовой отрезок времени. Ограничения:
х1 : х28 ≥0, целые числа
Чтобы обеспечить наиболее комфортную для покупателей атмосферу, количество кассиров должно быть больше или равно данным, приведенным в таблице 2.1.
2.2. Решение поставленной задачи с помощью программы EXCEL
Вначале создаем форму для ввода условий задачи (см. рис.1)
Рисунок 1. Форма для ввода условий
В нашей задаче оптимальные решения будут помещены в ячейках АD3: АD23. Оптимальное значение целевой функции поместим в ячейку В27.
Затем вводим исходные данные в форму. В ячейки В26:АС26 переносим данные из таблицы 2.1. Составляем 21 вариант графиков работы. Причем цифра 1 – будет обозначать работу, а 0 – отдых. (см. рис.2)
Рисунок 2. Ввод исходных данных
Введем формулу расчета количества персонала в ячейку В24:
=СУММПРОИЗВ(B3:B23;$AD3:$AD23)
Затем копируем эту формулу на диапазон ячеек С24:АС24. (см. рис.3)
Рисунок 3. Ввод формулы расчета количества персонала
Поскольку мы разделили каждый день недели на 4 отрезка времени, равных 4 часам, а зарплата кассира в смену ( 8 часов) составляет 40 у.е., то половинка смены будет стоить 20 у.е. Сумма в диапазоне B24:AC24 будет равняться количеству отработанных всеми работниками половинок смен. Соответственно целевая функция будет представлять собой недельный фонд оплаты труда всего персонала.
В ячейку В27 вводим формулу расчета целевой функции:
=СУММ(B24:AC24)*20
Далее запуск Поиска решения.
Устанавливаем целевую ячейку (вводим адрес ячейки целевой функции В27). Направление целевой функции «минимальному значению».
Вводим адреса искомых переменных - АD3: АD23
Далее – ограничения:
АD3: АD23 – целые, АD3: АD23 ≥ 0
Поскольку число кассиров не должно быть меньше числу, заданному условиями задачи, в соответствующий отрезок времени, то вводим ограничение: В24:АС24 ≥ В26:АС26 (см. рис. 4)
Рисунок 4. Ввод условий для поиска решений
Нажимаем «Выполнить», а затем «сохранить найденное решение».
В итоге компьютер подобрал 11 графиков работы, вычислил оптимальное количество работников (16 человек), а так же рассчитал недельный фонд оплаты труда (3200 у.е.). (см. рис.5)
Рисунок 5. Итоговая таблица
2.3. Анализ результатов расчетов и выработка управленческого решения.
Одним из важных этапов решения задач оптимизации является анализ полученных данных с последующей выработкой управленческого решения. Поскольку компьютер может лишь рассчитать и предложить оптимальные варианты решения, но именно принятие решения целиком и полностью лежит на человеке, а точнее руководителе.
По условиям задачи недельный фонд оплаты труда, исходя из потребности в кассирах, должен быть:
Требуемый ФОТ = СУММ(B26:AC26)*20 у.е .= 2740 у.е.
То есть, по результатам решения нашей задачи, перерасход ФОТ составит 460 у.е. Сравнивая данные полученные компьютером и потребность гипермаркета в кассирах по условиям задачи, видно, что в понедельник 1 кассир будет не загружен работой целую смену с 8-00 до 16-00. А в остальные дни недели некоторые работники будут загружены не полностью. Соответственно гипермаркет понесет лишние затраты, связанные с оплатой труда в момент простоя.
С целью минимизации расходов на оплату труда, кого-то из сотрудников можно привлекать на неполный рабочий день, либо предоставлять дополнительный выходной день (например, в понедельник). Так же можно предложить использование совмещения профессий. То есть в момент полной загрузки работник выполняет функции кассира, а во время вынужденного перерыва функции (например) фасовщика.
ЗАКЛЮЧЕНИЕ
В процессе выполнения курсовой работы, мною изучены задачи линейного программировании, методы оптимальных решений. Так же мною получены практические навыки составления и решения задач линейного программирования на примере составления графика работы кассиров в гипермаркете, используя программу EXCEL (надстройку «Поиск решений»).
Актуальность задач линейного программирования в настоящее время сомнений, как правило, ни у кого не вызывает, так как проблема оптимального планирования и организации производства, является важнейшей составляющей поиска скрытых ресурсов предприятия, помогает снизить затраты, повысить производительность труда и прибыль предприятия.
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ
1. Глухов В. В., Медников М. Д., Коробко С. Б. Математические методы и модели для менеджмента. 2-е изд., испр. и доп. — СПб.: Издательство «Лань», 2005. — 528 с. — (Учебники для вузов. Специальная литература).
2. Зайцев М.Г. Методы оптимизации управления для менеджеров. – М: Дело, 2002.
3. Н.Ш. Кремер, Б А Путко, И.М. Тришин, М.Н. Фридман; Под рея- проф. НЖ Кремера. Исследование операций в экономике – М: ЮНИТИ, 2002. - 407 с.