Анализ решения задачи о планировании производства мороженого на основе теории двойственности

БЕЛАРУССКИЙ РЕСПУБЛИКАНСКИЙ СОЮЗ ПОТРЕБИТЕЛЬСКИХ ОБЩЕСТВ

УЧРЕЖДЕНИЕ  ОБРАЗОВАНИЯ

«Белорусский  торгово-экономический 
университет потребительской кооперации»

 

Кафедра информационно-вычислительных систем

 

 

 

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

по дисциплине «Экономико-математические методы и модели

принятия решений»

на тему «Анализ  решения задачи о планировании производства мороженого на основе теории двойственности»

Вариант  7

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Гомель 2013

 

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ

Экономико-математическое моделирование является в настоящее время основным способом исследования сложных экономических систем.

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

Родоначальником экономико-математического моделирования считается лейб-медик короля Людовика XIV Ф. Кене. В 1758 г. он опубликовал свой труд «Экономические таблицы». В нем Ф.Кене сделал попытку описать процесс общественного воспроизводства с применением математических методов исследования. Затем простейшие модели были предложены в работах Адама Смитта (классическая макроэкономическая модель), Давида Риккардо (модель международной торговли) и другими. Начиная с XIX в., развитие экономико-математического моделирования шло ускоренными темпами. Свой вклад в этот процесс внесли такие известные учение, как О. Курно, В.Парето, Л.Вальрас, В.Леонтьев, Д. Хикс, Р. Слоу, Е.Е. Слуцкий, Л.В. Кантрович и другие.

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

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

Начало линейной оптимизации было положено в  1983 г., когда вышла в свет работа профессора Ленинградского университета Л.В. Канторовича «Математические методы организации и планирования производства». Академик Л.В. Канторович за разработку методов решения оптимизационных задач был удостоен звания лауреата Ленинской (1986 г.) и Нобелевской (1975 г.) премий.

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

Задачи курсовой работы:

1) изучить литературу  по линейному программированию и теории двойственности;

2) составить  математическую модель планирования производства мороженого, исходя из условия максимизации прибыли;

3) решить задачу  с помощью надстройки ”Поиск решения” и получить отчеты Excel;

4) провести анализ  отчетов и ответить на вопросы задания.

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

Курсовая работа состоит из 3 таблиц, 9 рисунков и 7 литературных источников.

 

1 ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ ПО ЗАДАЧАМ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ТЕОРИИ ДВОЙСТВЕННОСТИ

1.1 Задачи математического программирования

 Задачи математического  программирования – это задачи оптимизации, т.е., определения наилучшего решения из множества допустимых решений.

В общем виде постановка задачи математического  программирования состоит в определении  значений переменных х₁, х₂, …, х_n, при которых достигается максимум или минимум функции

 

                                                                         (1.1)

 

при условиях:

 

 

                                                                                                                (1.2)

 

 

где n – количество переменных;

      m – количество ограничений.  

Функция (1.1) называется целевой функцией, а условия (1.2) – ограничениями данной задачи. Запись в ограничениях означает, что возможен один из знаков , = или _{[1, c 8].}

Переменные  задачи х₁, х₂, …, х_n могут иметь различный экономический смысл. Например, если предприятие выпускает три вида продукции, и нужно найти оптимальный план производства, то х₁, х₂, х₃ – количество продукции каждого вида, которое необходимо производить. Если в задаче необходимо найти наилучший состав рациона, в которую могут входить несколько составных компонентов (например, сено и силос в рационе коров), то х₁ и х₂ – количество каждого продукта, которое нужно включить в рацион (в данном случае, сена и силоса).

Критерием оптимальности называется экономический показатель, который служит для выбора наилучшего решения. Целевая функция (1.1) выражает критерий оптимальности в математическом виде. Например, если критерием оптимальности является прибыль от производства продукции, то целевая функция стремится к максимуму. Когда же в качестве критерия оптимальности выступают затраты (например, на кормление коров), то целевая функция стремится к минимуму [2, c 12].

Система ограничений (1.2) вытекает из ограниченности материальных, трудовых ресурсов, технологических требований или же из здравого смысла. Например, в задаче планирования производства продукции ограничены материальные и трудовые ресурсы предприятия, а также сырье или материалы, используемые для производства этой продукции. Для задачи составления рациона ограничения заключаются в необходимости того, чтобы рацион был полноценным (содержал питательные вещества, витамины и микроэлементы, необходимые для жизнедеятельности коров) _{[1, c 11]}.

В зависимости от характера  целевой функции F  и функций ограничений _, говорят о различных видах задач математического программирования:

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

5х₁+6х₂.

• если целевая функция и/или ограничения содержат нелинейные функции, то это задача нелинейного программирования. Пример нелинейных функций:

, х², , sin x, 1/x и т.д.

• если содержательный смысл требует получения решения в целых числах, то такая задача является задачей целочисленного программирования. Пример: выпуск штучной продукции, назначение работников на работы (нельзя назначить на работу не целое число работников).
• если в задаче математического программирования необходимо учитывать фактор времени, то такая задача является задачей динамического программирования. Обычно решение задач динамического программирования может быть представлено как процесс пошагового принятия решений. На каждом шаге выбирается такое решение, которое не обязательно дает оптимальный результат на этом шаге, но обеспечивает наилучший исход всей операции в целом _{[3, c 20]}.

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

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

В общем виде задача линейного программирования заключается следующем: найти значения переменных х₁, х₂, …, х_n, доставляющие оптимальное значение целевой функции:

 

                                                                            (1.3)

при ограничениях

                                                                   (1.4)

и граничных  условиях

.                                                                   (1.5)

Часто граничные  условия сводятся к требованиям  неотрицательности переменных:

 

                                                                             (1.6)

Здесь параметры  задачи - это некоторые константы, известные для каждой конкретной задачи.

Ограничения (1.4) называют функциональными, а ограничения (1.5) – прямыми.

Условия неотрицательности переменных (1.6) с математической точки зрения являются необязательными, но в моделях экономических задач они, как правило, всегда присутствуют. Это связано с экономическим смыслом переменных х₁, х₂, …, х_n. Например, если под x_j понимается количество продукции вида j, которое необходимо выпускать на предприятии, то очевидно, что оно не может быть отрицательным _{[4, c 15]}.

Набор значений переменных х_1, х_2,…,х_n, при котором выполняются все ограничения, называется допустимым решением или планом. Совокупность всех допустимых решений составляет область допустимых решений.

Допустимое  решение, при котором функция F принимает максимальное или минимальное значение, называется оптимальным.

Существует  универсальный метод решения  задач линейного программирования – симплекс-метод. Автоматизировать решение этим методом можно с помощью надстройки Поиск решения пакета MS Excel.

1.3 Постановка задачи планирования производства продукции

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

 Для производства продукции n типов требуются ресурсы m видов. Нормы расхода ресурсов на производство единицы продукции каждого типа заданы матрицей , где – количество ресурса i–го вида, необходимое для производства единицы продукции j-го типа. Известно количество ресурсов  ( ) каждого вида, которое имеется в наличии у предприятия. Известны также величины прибыли С_j ( ), которую получит предприятие при реализации единицы продукции j-го типа. Требуется найти оптимальный план производства продукции, т.е. количество продукции каждого типа, которое нужно произвести, чтобы получить наибольшую прибыль _{[5, c 25]}. Условие задачи представлено в виде  таблицы 1.

 

Таблица 1- Исходные данные для задачи планирования выпуска продукции

Ресурсы	Расход ресурсов на единицу продукции				Наличие ресурсов
	Тип 1	Тип 2	…	Тип n
Ресурс 1	a11	a12	…	a1n	b1
Ресурс 2	a21	a22	…	a2n	b2
…	…	…	…	…	…
Ресурс m	am1	am2	…	amn	bm
Прибыль	C1	C2	…	Cn

Обозначим через x_j – количество продукции j-го типа, которое планируется выпустить ( ). Тогда математическая модель задачи будет выглядеть следующим образом:

                                                                 (1.7)

                                                                   (1.8)

                                                                    (1.9)

 

Целевая функция (1.7) этой задачи представляет собой общую прибыль от производства всей продукции. Ограничения (1.8) выражают условие того, что потребление ресурса i-го вида не должно превышать запаса этого ресурса. Условия неотрицательности переменных (1.9) вытекают из смысла переменной x_j ( ): количество продукции не может быть отрицательным.

1.4  Каноническая форма записи ЗЛП

Канонической называется форма записи ЗЛП, в которой целевая функция стремится к максимуму, все ограничении имеют вид равенства и на все переменные наложено условие неотрицательности.

Чтобы привести к каноническому  виду задачу с ограничениями-неравенствами, вводят дополнительные переменные. Причем если неравенство имеет вид “меньше или равно”( ), то дополнительную переменную прибавляют к левой части ограничения, а если вид “больше или равно”( ), то дополнительную переменную вычитают  из его левой части. В целевую функцию дополнительные переменные вводят с коэффициентами, равными 0 _{[2, c 28]}.