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

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

(ВШПП)

 

 

 

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

 

 

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

 

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

 

 

 

 

 

Выполнил:

Студент группы ЧЭ 11-3

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

«__» _________ 2013 г.                                                       (подпись)

 

 

Проверил:

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

Муратова Елена Андреевна                                        _________________

«__» _________ 2013 г.                                                       (подпись)

СОДЕРЖАНИЕ

 

Введение                                                                                                                       3

1. Задачи линейного программирования                                                              5
1. Общая постановка задачи линейного программирования                              5
2. Задача об использовании ресурсов (задача планирования производства).   6 
3. Задача о составлении рациона (задача о диете, задача о смесях)                 7
4. Задача о раскрое материалов                                                                             9
5. Транспортная задача                                                                                         10
2. Задача о составлении графика персонала                                                       12   
1. Разработка экономико-математической модели.                                        12
2. Решение поставленной задачи с помощью программы EXCEL                   13
3. Анализ результатов расчетов и выработка управленческого решения.      17

Заключение                                                                                                                 19

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

 

 

ВВЕДЕНИЕ

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

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

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

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

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

 

 

1. ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
1. Общая постановка задачи линейного программирования.

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

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

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

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

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

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

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

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

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

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

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

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

Е=F(х ; y)

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

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

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

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

 

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

 

 

 

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

 

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

Пример. При откорме каждое животное ежедневно должно получать не менее 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

 

 

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

 

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

Пример. Продукция бумажной фирмы выпускается в виде бумажных рулонов стандартной ширины – по 2 метра. Фирма имеет заказы на бумажные рулоны разной ширины: 150 шт – шириной 0,5 м, 200 шт – шириной 0,7 м, 300 шт – шириной 0,9 м. Существует 6 вариантов, известно количество отходов в результате раскроя каждым из шести способов, данные приведены в таблице 1.3.: