Разработка модели и решение задачи линейного программирования (на примере задачи о составлении графика работы персонала)

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

ПЕРМСКИЙ ИНСТИТУТ МУНИЦИПАЛЬНОГО УПРАВЛЕНИЯ

(ВШПП)

Дисциплина: Методы оптимальных решений

КУРСОВАЯ РАБОТА

Тема: Разработка модели и решение задачи линейного программирования (на примере задачи о составлении графика работы персонала)

Выполнил: Студент группы ЧЭ 11-3

Красноперова Юлия

Проверил: преподаватель Муратова Елена

Содержание

Введение

1. Задачи линейного программирования

1.1 Общая постановка задачи линейного программирования

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

1.3 Задача о составлении рациона (задача о диете, задача о смесях)

1.4 Задача о раскрое материалов

1.5 Транспортная задача

2. Задача о составлении графика персонала

2.1 Разработка экономико-математической модели

2.2 Решение поставленной задачи с помощью программы EXCEL

2.3 Анализ результатов расчетов и выработка управленческого решения

Заключение

Список используемой литературы

Введение

программирование линейный задача ресурсы

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

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

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

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

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

1. Задачи линейного программирования

1.1 Общая постановка задачи линейного программирования

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

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

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

Экономико-математические методы и модели применяют с целью отыскания наилучшего решения, т. е. решения, оптимального в том или ином смысле (максимума или минимума). Но задачи математического программирования применяют только тогда, когда имеется много допустимых решений (два и более).

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

1. Постановка (формулировка) задачи.

2. Разработка математической модели изучаемой системы.

3. Отыскание решения с помощью этой модели.

4. Проверка данной модели и решения.

5. Уточнение решения на практике.

В общем виде математическая постановка задачи линейного программирования состоит в определении значения целевой функции.

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

Е=F(х; y)

Где Е - мера общей эффективности, F - функция, задающая соотношение между Е, х, y.

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

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

Рассмотрим наиболее распространенные задачи линейного программирования.

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

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

Пример. Для изготовления двух видов продукции Р₁ и Р₂ используют три вида сырья: S₁, S₂, S₃. Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а так же величина прибыли, получаемая от реализации единицы продукции, приведены в таблице 1.1.

Таблица 1.1

Норма расхода сырья

Вид сырья	Запас сырья	Количество единиц сырья, идущих на изготовление единицы продукции
		Р1	Р2
S1	20	2	5
S2	40	8	5
S3	30	5	6
Прибыль от единицы продукции, руб.	50	40

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

Обозначим через х₁ количество единиц продукции Р₁, а через х₂ - количество единиц продукции Р₂. Тогда целевая функция (прибыль от реализации) будет записываться

Z = 50х₁ + 40х₂ > max

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

2х₁ + 5х₂ ? 20

8х₁ + 5х₂ ? 40

5х₁ + 6х₂ ? 30

х₁ ? 0

х₂ ? 0

1.3 Задача о составлении рациона (задача о диете, задача о смесях)

Цель задачи о смесях составить рацион, позволяющий обеспечить всеми необходимыми питательными элементами, с минимальными затратами.

Пример. При откорме каждое животное ежедневно должно получать не менее 9 ед. питательного вещества S₁, не менее 8 ед. вещества S₂ и не менее 12 ед. вещества S₃. Для составления рациона используют два вида корма. Содержание количества единиц питательных веществ в 1 кг каждого вида корма и стоимость 1 кг корма приведены в таблице 1.2.

Таблица 1.2

Содержание питательн. веществ

Питательные вещества	Количество единиц питательных веществ в 1 кг корма
	Корм 1	Корм 2
S1	3	1
S2	1	2
S3	1	6
Стоимость 1 кг корма, руб.	4	6

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

Для составления математической модели обозначим через х₁ и х₂ соответственно количество килограммов корма 1 и 2 в дневном рационе. Цель данной задачи - добиться минимальных затрат на дневной рацион, поэтому общую стоимость рациона можно выразить в виде линейной функции

Z = 4х₁ + 6х₂ > min

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

3х₁ + х₂ ? 9

х₁ + 2х₂ ? 8

х₁ + 6х₂ ? 12

х₁ ? 0

х₂ ? 0

1.4 Задача о раскрое материалов

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

Пример. Продукция бумажной фирмы выпускается в виде бумажных рулонов стандартной ширины - по 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

Обозначим переменные:

х₁ - количество рулонов раскроенных первым способом

х₂ - количество рулонов раскроенных вторым способом

х₃ - количество рулонов раскроенных третьим способом

х₄ - количество рулонов раскроенных четвертым способом

х₅ - количество рулонов раскроенных пятым способом

х₆ - количество рулонов раскроенных шестым способом

Целью нашей задачи будет минимизация отходов. Целевая функция будет рассчитываться как:

О = 0,4* х₁ + 0,3* х₂ + 0,1* х₃ + 0,1* х₅ + 0,2* х₆ > min

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

2*х₂ + 2*х₃ + 4*х₄ + х₅ ? 150

х₁ + х₂ +2* х₅ ? 200

х₁ + х₃ +2* х₆ ? 300

1.5 Транспортная задача

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

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

На товарных станциях А ₁ и А ₂ имеется по 30 комплектов мебели. Известно, что перевозка одного комплекта со станции С₁ в магазины М₁, М₂, М₃ стоит 1р., 3р., 5р., а стоимость перевозки со станции С₁ в те же магазины - 2р., 5р., 4р. необходимо доставить в каждый магазин по 20 комплектов мебели. Составить план перевозок так, чтобы затраты на транспортировку мебели были наименьшими.

Количество комплектов мебели, перевозимых со станции А₁ в магазины М₁, М₂, М₃ обозначим через х₁₁, х₁₂, х₁₃, а со станции А ₂ - через х₂₁, х₂₂, х₂₃. Тогда схема перевозок буде выглядеть следующим образом (см. таблицу 1.4.):

Таблица 1.4

Схема перевозок

	в М1	в М2	в М3	Всего отправлено
Из А1	х11	х12	х13	30
Из А 2	х21	х22	х23	30
Всего получено	20	20	20	60

Целевая функция (стоимость перевозок) будет находиться:

С = х₁₁ + 3 х₁₂ + 5 х₁₃ + 2 х₂₁ + 5 х₂₂ + 4 х₂₃

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

х₁₁ + х₁₂ + х₁₃ = 30

х₂₁ + х₂₂ + х₂₃ = 30

х₁₁ + х₂₁ = 20

х₁₂ + х₂₂ = 20

х₁₃ + х₂₃ = 20

2. Задача о составлении графика работы персонала

2.1 Разработка экономико-математической модели

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

Рассмотрим пример: Открывается новый филиал супермаркета. Необходимо рассчитать численность кассиров и подобрать оптимальные графики их работы. Количество покупателей зависит от времени суток и отличается по дням недели. Магазин работает с 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-ми часовой рабочей смены.

Для решения данной задачи определяем цель - минимизировать расходы на оплату труда кассиров. Значит, целевая функция будет вычисляться как сумма произведений числа кассиров в каждую смену на заработную плату. Переменными решения (х₁, х₂, х₃, … х₂₈) будет количество персонала, работающего в четырехчасовой отрезок времени. Ограничения:

х₁: х₂₈ ?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 с.

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