Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

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

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

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

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

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

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

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

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

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

Вариант 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 и т.д.

если содержательный смысл требует получения решения в целых числах, то такая задача является задачей целочисленного программирования. Пример: выпуск штучной продукции, назначение работников на работы (нельзя назначить на работу не целое число работников).
если в задаче математического программирования необходимо учитывать фактор времени, то такая задача является задачей динамического программирования. Обычно решение задач динамического программирования может быть представлено как процесс пошагового принятия решений. На каждом шаге выбирается такое решение, которое не обязательно дает оптимальный результат на этом шаге, но обеспечивает наилучший исход всей операции в целом _[₃_,_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	a₁₁	a₁₂	…	a_1n	b₁
Ресурс 2	a₂₁	a₂₂	…	a_2n	b₂
…	…	…	…	…	…
Ресурс m	a_m1	a_m2	…	a_mn	b_m
Прибыль	C₁	C₂	…	C_n

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

(1.7)

(1.8)

(1.9)

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

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

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

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

Таким образом, задача (1.7) – (1.9) может быть записана в следующей канонической форме:

(1.10)

Дополнительные переменные y_i () представляют собой остатки ресурсов каждого вида. Если в оптимальном решении какой-либо ресурс будет использован полностью, то ограничение исходной задачи (1.3.2) будет выполнено в виде равенства и y_i=0. Такое ограничение в отчетах Exсel называется связанным. Ресурс, который использован полностью, считается дефицитным.

1.5 Двойственность в линейном программировании

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

Она имеет столько переменных, сколько ограничений в исходной задаче;
Правые части ограничений исходной задачи становятся коэффициентами целевой функции в двойственной задаче;
Если исходная задача на максимум, то двойственная задача – на минимум, и наоборот;
Матрица коэффициентов при переменных в ограничениях транспонируется;
Коэффициенты целевой функции исходной задачи становятся правыми частями ограничений в двойственной задаче;
Если ограничения исходной задачи имеют вид , то двойственной - и наоборот;
На переменные двойственной задачи наложено условие неотрицательности _[₆_,_c₃₁_].

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

Таблица 2- Исходная и двойственная задачи

Исходная задача

Двойственная задача

(1.11)

(1.12)

. (1.13)

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

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

F_Д=b₁×z₁+ b₂×z₂+…+ b_m×z_m®min

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

().

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

В отчетах Excel, получаемых с помощью надстройки “Поиск решения” оптимальное значение двойственной переменной называется теневой ценой. Теневая цена - это оценка значимости ресурса, вытекающая из конкретных условий задачи, а не реальная цена на рынке _{[7, c 33]}.

1.6 Первая теорема двойственности

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

max F=min F_Д .

Это означает, что предприятию безразлично, производить ли продукцию по оптимальному плану X^* и получить максимальную прибыль, либо продать ресурсы по оптимальным ценам Z^* и получить такую же сумму. Для всех других (неоптимальных) планов X и Z прибыль от выпуска продукции всегда меньше внутренней стоимости затраченных ресурсов: F<F_Д, а величина F_Д-F характеризует производственные потери.

Следствие (теорема об оценках).

Двойственная оценка z_i^* (теневая цена) показывает, как изменится целевая функция исходной задачи при изменении ресурса b_i на единицу:

Таким образом, по теневым ценам можно судить о том, насколько целесообразно изыскивать резервы для увеличения количества i-го ресурса: если соответствующая теневая цена равна нулю, то увеличение количества этого ресурса никак не повлияет на рост прибыли. С другой стороны, чем больше теневая цена, тем больше увеличится прибыль при увеличении количества этого ресурса на одну единицу. Поэтому тот ресурс, который имеет большую теневую цену, считается более дефицитным _{[3, c 25]}.

Однако эта теорема справедлива только тогда, когда при изменении количества ресурса b_i значения переменных z_i^* в оптимальном плане двойственной задачи остаются неизменными. Это выполняется в пределах устойчивости оптимального решения, т.е. когда структура решения не изменяется. Пределы устойчивости при изменении правых частей ограничений указаны во второй таблице отчета по устойчивости (рис. 8).

1.7 Понятие нормированной стоимости

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

(1.14)

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

Таким образом, v_j – это разница между той суммой, что могли бы получить, продавая ресурсы, необходимые для производства единицы продукции типа j, и прибылью, которая будет получена, если из этих ресурсов произвести и продать продукцию _{[1, c 35]}.

v_j=0, если оценка затрат ресурсов равна прибыли, т.е. потерь при производстве нет.

v_j>0, если оценка затрат ресурсов больше прибыли от единицы продукции. В этом случае производить этот вид продукции невыгодно.

В отчетах Excel оптимальное значение дополнительной двойственной переменной называется нормированной стоимостью.

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

Пусть, например, продукция вида j не вошла в оптимальный план производства, т.е. =0. Однако существует некоторое плановое задание, предписывающее выпуск этого вида продукции в количестве T_j единиц. Тогда при выпуске этого невыгодного вида продукции на него будут оттянуты ресурсы, и выгодной продукции будет выпущено меньше. Целевая функция (общая прибыль) уменьшится, причем это уменьшение можно количественно измерить:

1.8 Вторая теорема двойственности (теорема о дополняющей

нежесткости)

Оптимальные решения исходной и двойственной задач связаны соотношениями:

Эта теорема означает, что между переменными исходной и двойственной задач существует взаимосвязь, которая заключается в том, что одна переменная из пары должна быть нулевой _{[3, c 29]}.

Рассмотрим связь (остаток ресурса i-го вида) и (теневая цена ресурса i-го вида).

Если , то имеется остаток ресурса i-го вида, т.е. ресурс не дефицитен. Увеличение количества этого ресурса не позволит нарастить объемы производства, т.е. не вызовет увеличение прибыли. Увеличится только остаток этого ресурса. Поскольку теневая цена показывает, на сколько возрастает прибыль, она должна быть равна нулю: .

Если , то i - й ресурс является дефицитным, и следовательно, использован полностью. Остаток этого ресурса равен нулю: .

Рассмотрим связь (оптимальный объем производства продукции j-го типа) и (потери при производстве единицы продукции j-го типа).

Если , то продукция типа j является невыгодной, и не должна входить в оптимальный план производства:

Если , т.е. согласно оптимальному плану этот вид продукции должен быть произведен в каком-то количестве, он является выгодным. Поэтому соответствующие потери равны нулю: _{[1, c 38].}

2 ПОСТАНОВКА ЗАДАЧИ

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

Таблица 3- Исходные данные

Ресурсы	Норма расхода ресурса на 1 т мороженого				Общее количество ресурсов
Ресурсы	сливочного I вида	сливочного II вида	пломбира I вида	пломбира II вида	Общее количество ресурсов
Молоко натуральное, кг	550	0	620	0	64100
Молоко сухое, кг	40	30	20	20	4800
Молоко сухое обезжиренное, кг	30	40	30	30	5200
Масло сливочное, кг	86	110	150	52	22360
Сахар, кг	160	92	158	128	26240
Молоко сгущенное, кг	0	0	0	50	800
Молоко сгущенное обезжиренное, кг	0	158	30	50	7910
Затраты оборудования (машино/ч)	4,5	4,5	4,5	4,5	720
Прибыль от реализации 1 т мороженого, ден. ед.	315	278	573	370

Вопросы:

Какое количество мороженого каждого вида следует производить? Какая будет получена прибыль?
Полностью ли задействовано оборудование в оптимальном плане производства? Имеются ли остатки сырья какого-либо вида?
Какое управленческое решение принесет большую прибыль: дополнительно ввести в производство 100 кг молока сгущенного, или увеличить количество молока натурального на 200 кг?
К чему приведет плановое задание по выпуску 1 т сливочного мороженого 1 вида?

3 РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Составим математическую модель этой задачи. Для этого выполним три шага:

1) Введем переменные. Нужно найти план производства, т.е. количество мороженого каждого вида, которое следует производить. Таким образом, будет 4 переменных:

x₁- количество сливочного мороженого I вида;

x₂ –количество сливочного мороженого II вида;

x₃ –количество мороженого пломбир I вида;

x₄ –количество мороженого пломбир II вида.

2) Запишем целевую функцию. Она должна выражать собой критерий оптимальности (т.е. тот показатель, который в задаче должен достигнуть максимума или минимума). В нашей задаче указано, что должна быть максимальна прибыль. Поэтому целевая функция должна представлять собой формулу расчета прибыли. Прибыль от единицы сливочного мороженого I вида составляет 315 денежных единиц, а поскольку мы собираемся выпускать x₁ мороженого данного вида, прибыль составит 315x₁ ден.ед. Аналогично прибыль от сливочного мороженого II вида равна 278x₂ , и т.д. Общая прибыль от всех видов мороженого равна сумме:

F=315x₁+178x₂+573x₃+370x₄ → max

3) Запишем систему ограничений. Очевидно, что расход каждого вида ресурса не должен превышать его запас. Расход молока натурального на производство сливочного мороженого I вида равен 550x₁, на сливочное мороженое II вида – 0x₂, и т.д. Общий расход молока натурального выражается с помощью формулы: 550х₁+0х₂+620х₃+0х₄, а запас равен 64100. Поэтому имеем неравенство:. Аналогично записываются другие ограничения.

Математическая модель задачи имеет вид:

Здесь x_j – количество выпускаемой продукции j-го типа (j=). Целевая функция представляет собой общую прибыль от производства мороженого всех видов. Ограничения отражают конечность запасов ресурсов на предприятии. Неотрицательность переменных следует из их смысла.

Анализ решения задачи о планировании производства мороженого на основе теории двойственности 📙 Курсовая → 🆔 18128