Моделирование максимальной прибыли мебельным цехом от производства шкафов и тумб
Построение базовой аналитической модели. Обоснование и описание вычислительной процедуры. Методы определения оптимального целочисленного решения. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".
| Рубрика | Экономико-математическое моделирование |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 28.03.2012 |
| Размер файла | 555,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Введение
Математическое программирование в применении к анализу и управлению экономикой представляет собой теорию эффективного использования ресурсов. Она применяется для определения оптимальных планов, решения проблемы наилучшего сочетания желаемого и возможного.
Математическое программирование как экономическая теория было востребовано логикой научно-технического развития на протяжении по крайней мере последних 50 лет. Как самостоятельная научная дисциплина эта теория сформировалась в течение десятилетия, начиная с первой публикации советского математика Л.В. Канторовича и кончая работами американца Дж. Данцига, относящимися к 1948 г. В дальнейшем математическое программирование развивалось под мощным воздействием успехов в создании средств обработки информации.
Без вычислительной техники прикладное значение математического программирования было бы небольшим. Но и сама вычислительная техника развивалась благодаря массовому появлению таких прикладных оптимизационных задач, решение которых было абсолютно немыслимым при отсутствии возможности выполнять гигантский объем вычислений. Именно чудовищное быстродействие, по выражению Н.Н. Моисеева, электронных вычислительных машин позволяет ставить прикладные оптимизационные задачи и получать их решение. Эта характеристика была дана в начале 70-х гг. XX в., когда быстродействие доступных для широкого применения ЭВМ измерялось десятками тысяч, в лучшем случае сотнями тысяч операций в секунду. Именно в это время на волне поразительных достижений вычислительной техники и прикладной математики дух оптимизации проник и в экономическую науку.
Быстродействие современных компьютеров увеличилось не менее чем в десятки тысяч раз по сравнению с быстродействием ЭВМ 70-х гг. Кроме того, если «ретро-ЭВМ» занимала помещение, сравнимое с большим спортзалом, а от системы ее охлаждения могла работать баня, то даже больший по вычислительной мощности программируемый калькулятор помещается на ладони и работает от миниатюрной батарейки.
Современные компьютеры в миллионы раз превосходят «ретро-ЭВМ» как по быстродействию, так и по емкости памяти, работая без сбоев годами. Их включение и выключение по сложности не превышают аналогичные манипуляции с настольной лампой. Все более совершенное программное обеспечение делает работу на современном компьютере доступной широкому кругу пользователей, не имеющих глубокой специальной подготовки или даже вовсе без таковой.
На фоне возросших технических возможностей решения оптимизационных задач не может не измениться подход к их применению в управлении экономикой, как впрочем и в любых других сферах.
Уходят в прошлое времена, когда все исходные данные задачи линейного программирования вводились вручную. В лучшем случае применение подобной «информационной технологии» позволяет решать задачи, содержащие до нескольких сот переменных, да и это является рекордом. Сегодня уже очевидно, что такой путь годится только для изолированных от практики упражнений. Причин этому множество: трудоемкость ввода данных, неизбежность большого числа ошибок ввода, дальнейшее обнаружение которых проблематично, информационная непротиворечивость другим задачам системы управления, трудности актуализации данных и т.п. Все это приводит к тому, что к моменту получения решения задачи оно уже никому не нужно, во всяком случае для практического применения.
Постоянное увеличение мощности компьютеров делает возможным решение оптимизационных задач все большей размерности, что приводит к усложнению информационного обеспечения соответствующих экономико-математических моделей. На данном этапе становится реальным решение задачи линейного программирования до 10 тысяч переменных с примерно таким же числом ограничений. Надо сказать, что необходимость решения задач такой размерности ощущается уже сегодня, особенно в связи с применением в экономике теории графов и постановкой оптимизационных задач на сетях. Матрица ограничений такой задачи содержит 100 миллионов элементов. Достаточно представить, сколько времени занял бы только визуальный контроль исходных данных, не говоря уже о их первичном вводе, чтобы стала очевидной бессмысленность подобного подхода.
Учитывая вышесказанное, приходим к логическому выводу, что в курсе математического программирования целесообразно уделить больше внимания алгоритмическим методам формирования исходных данных для оптимизационных задач с целью сведения к минимуму первичного ввода и даже полного его исключения. Можно указать ряд путей достижения этой цели.
Для моделирования и оптимизации решений широко используется аппарат математического программирования, который позволяет решать сложные системные задачи «с хорошей структурой». Хорошо структурированные задачи поддаются математической формализации и решаются с помощью тех или иных математических методов, методик, моделей, алгоритмов и процедур. Математическое программирование изучает задачи оптимизации, включая теорию и алгоритмы решения задач при наличии ограничений с ориентацией на перспективные средства компьютерной техники. В настоящее время в математическом программировании развиваются следующие направления: линейное, нелинейное, динамическое, дискретное (целочисленное), стохастическое, эвристическое и др. Среди направлений математического программирования наиболее развитым и законченным является линейное программирование, когда в задачах оптимизации находится экстремум линейной целевой функции при линейных ограничениях.
1. Постановка задачи операционного исследования
Мебельный цех выпускает два вида изделий (шкафы и тумбы), используя при этом материалы трех видов: древесные плиты, пластмассу и лак. Затраты материалов на одно изделие, имеющиеся запасы материалов (на сутки) и прибыль от продажи одного изделия каждого вида приведены в таблице 1:
модель вычислительный программный надстройка
Таблица 1. Данные задачи
|
Материал |
Запас сырья |
Расход на одно изделие |
||
|
Шкаф |
Тумба |
|||
|
Древесные плиты (кв. м) Пластмасса (кг) Лак (кг) |
1000 300 140 |
20 2 2 |
10 5 1 |
|
|
Прибыль (д.е.) |
15 |
12 |
Определить план производства изделий каждого вида, при котором прибыль предприятия будет максимальной.
2. Построение базовой аналитической модели
Обозначим через число шкафов, через число тумб, через Z - суммарную прибыль от реализации произведенных изделий.
Так как каждое шкаф дает прибыль 15 ден. ед., а таких изделий изготавливается ед., то все шкафы дадут прибыль ; аналогично тумбы обеспечат прибыль . Суммарную прибыль можно записать в виде
(1)
Древесной плита на шкаф требуется 20 кв. м., на тумбу - 10 кв. м. Тогда для изготовления шкафов и х2 тумб потребуется кв. м. Так как запас древесной плиты не может превышать 1000 кв. м., то должно выполняться неравенство .
Аналогично можно записать условия, налагаемые пластмассы и лак .
Итак, искомый план задачи х = (х1; х2) должен удовлетворять следующей системе ограничений:
(2)
Переменные х1 и х2 не могут быть выражены отрицательными числами, поэтому
(3)
План х = (х1; х2), удовлетворяющий системе ограничений (2) и условию неотрицательности (3), называется допустимым. Допустимый план, для которого целевая Функция (1) принимает максимальное значение, называется оптимальным.
3. Обоснование и описание вычислительной процедуры
Линейная функция (1), максимум которой надо определить, вместе с системой ограничений (2) и условием неотрицательности (3) образуют математическую модель задачи. Так как функция (1) линейная, а система (2) содержит только линейные ограничения, то задача (1) - (3) является задачей линейного программирования.
4. Решение задачи оптимизации на основе технологии симплекс-метода
Решим полученную задачу линейного программирования симплексным методом.
Перейдем к канонической форме задачи линейного программирования, введя дополнительные (балансовые) переменные, означающие возможные остатки ресурсов сырья.
.
Составим начальную таблицу по данным модели.
Таблица 2. Первая симплекс таблица
|
БП |
Сб |
А0 |
|||||||
|
15 |
12 |
0 |
0 |
0 |
|||||
|
0 |
1000 |
20 |
10 |
1 |
0 |
0 |
|||
|
0 |
300 |
2 |
5 |
0 |
1 |
0 |
|||
|
0 |
140 |
2 |
1 |
0 |
0 |
1 |
|||
|
0 |
-15 |
-12 |
0 |
0 |
0 |
Полученный план х = (0, 0, 1000, 300, 140) является опорным но не является оптимальным, т.к. в индексной строке есть отрицательные элементы. Наибольший по модулю отрицательный элемент (-15) индексной строки указывает, что в новый базис следует ввести переменную . Чтобы определить переменную, выводимую из базиса, составим симплексные отношения и выберем наименьшее из них
Введем в базис переменную вместо переменной .
Выполним симплексные преобразования, получим новую таблицу.
1) в разрешающем столбце все элементы будут разны 0, кроме разрешающего;
2) поделим разрешающею строку на 5;
3) все остальные элементы таблицы вычислим по формуле:
,
где - разрешающий элемент.
Таблица 3. Вторая симплекс таблица
|
БП |
Сб |
А0 |
|||||||
|
15 |
12 |
0 |
0 |
0 |
|||||
|
0 |
400 |
16 |
0 |
1 |
-2 |
0 |
|||
|
12 |
60 |
1 |
0 |
0 |
|||||
|
0 |
80 |
0 |
0 |
- |
1 |
||||
|
720 |
0 |
0 |
0 |
Полученный план х = (0, 60, 400, 0, 80) является опорным но не является оптимальным, т.к. в индексной строке есть отрицательные элементы. Наибольший по модулю отрицательный элемент () индексной строки указывает, что в новый базис следует ввести переменную . Чтобы определить переменную, выводимую из базиса, составим симплексные отношения и выберем наименьшее из них
Введем в базис переменную вместо переменной .
Выполним симплексные преобразования, получим новую таблицу.
Таблица 4. Третья симплекс таблица
|
БП |
Сб |
А0 |
|||||||
|
15 |
12 |
0 |
0 |
0 |
|||||
|
15 |
25 |
1 |
0 |
- |
0 |
||||
|
12 |
50 |
0 |
1 |
- |
0 |
||||
|
0 |
40 |
0 |
0 |
- |
0 |
1 |
|||
|
975 |
0 |
0 |
0 |
Так как в полученной таблице в индексной строке нет отрицательных оценок, то план x = (25; 50; 0; 0; 40) является оптимальным. Максимальная прибыль предприятия составит 975 денежных единиц, если оно выпустит 25 шкафов, 50 тумбочек. При этом ресурс 3-го вида (лак) будет израсходован не полностью .
5. Анализ базовой аналитической модели на чувствительность
Для решения задач анализа чувствительности ограничения линейной модели классифицируются следующим образом. Связывающие ограничения проходят через оптимальную точку. Несвязывающие ограничения не проходят через оптимальную точку. Аналогично ресурс, представляемый связывающим ограничением, называют дефицитным, а ресурс, представляемый несвязывающим ограничением - недефицитным. Ограничение называют избыточным в том случае, если его исключение не влияет на ОДР и, следовательно, на оптимальное решение. Выделяют следующие три задачи анализа на чувствительность [1, ст. 40].
1. Анализ сокращения или увеличения ресурсов:
· на сколько можно увеличить (ограничения типа ) запас дефицитного ресурса для улучшения оптимального значения ЦФ?
· на сколько можно уменьшить (ограничения типа ) запас недефицитного ресурса при сохранении оптимального значения ЦФ?
2. Увеличение (ограничения типа ) запаса какого из ресурсов наиболее выгодно?
3. Анализ изменения коэффициентов ЦФ: каков диапазон изменения коэффициентов ЦФ, при котором не меняется оптимальное решение?
Составим модель двойственной задачи.
Напишем матрицу исходной задачи
и транспонируем её .
По теореме двойственности получим. Преобразуем ограничения - неравенства:
По теореме двойственности получим.
Функция общая оценка сырья. Каждое ограничение системы, представляет неравенство, где левая часть - оценка всех видов ресурсов, а правая часть - стоимость единицы продукции.
Из первой теоремы двойственности следует, что если найдено решение одной задачи, то одновременно найдено и решение двойственной задачи. Запишем каноническую форму математической модели двойственной задачи, введя дополнительные (балансовые переменные) , .
Переменные являются базисными, а - свободными. Переменные являются свободными, а - базисными. Сопоставим базисные переменные прямой задачи, свободным переменным двойственной задачи, и наоборот.
Соответствие между переменными двойственной задачи имеет вид:
.
Оптимальный план двойственной задачи имеет вид
Установим степень дефицитности используемых ресурсов. Дефицитный ресурс имеет положительную оценку, а ресурс избыточный имеет нулевую оценку. Степень дефицитности используемых ресурсов производим в ограничениях-неравенствах прямой задачи, путем подстановки оптимального плана производства =(25; 50; 0; 0; 40).
Произведем оценку ресурсов Р1 и Р2:
;
.
Первое и второе ограничения прямой задачи выполняется как строгие равенства. Это свидетельствует о дефицитности ресурсов Р1 и Р2.
Именно поэтому в оптимальном плане двойственной задачи , .
Произведем оценку ресурса Р3:
;
Третье ограничение прямой задачи выполняются как строгое неравенство. Это означает, что расход ресурса Р3 меньше его запаса, т.е. ресурс является избыточными.
Именно поэтому в оптимальном плане двойственной задачи , т.е. имеет нулевую оценку.
Оценку продукции производим в ограничениях-неравенствах двойственной задачи, путем подстановки оптимального плана .
Произведем анализ продукции:
;
.
Ограничения двойственной задачи выполняются как строгие неравенства. Это свидетельствует о том, что выпуск продукции нецелесообразен, поскольку оценка израсходованных ресурсов превышает суммарную оценку продукции.
Произведем анализ дополнительных переменных прямой и двойственной задач. Дополнительные переменные прямой задачи указывают количество неиспользованного ресурса соответственно. Так как х3 = 0, х4 = 0, то ресурс дерево и пластмасса используется полностью, а, х6 = 10 говорит о количестве неиспользованного ресурса лак.
Дополнительные переменные двойственной задачи являются мерой убыточности выпускаемой продукции. По оптимальному плану следует выпускать продукцию. Оценка , этого вида продукции равны нулю. Оценка убыточной продукции показывает, насколько будет снижать каждая изготовленная единица такой продукции достигнутый максимальный уровень выручки.
6. Определение оптимального целочисленного решения
Задача имеет целочисленное решение.
7. Анализ результатов базовой аналитической модели и предложения по модификации
Базовая аналитически модель
Позволяет найти решение данной оптимальное задачи. Произвести оценку ресурсов. Найти максимальное значение целевой функции. А также найти решение задачи с помощью ЭВМ.
8. Проверка оптимального решения в среде MS Excel с использованием программной надстройки «Поиск решения»
На рабочем листе среде MS Excel введем исходные данные задачи (рис 1.).
Рисунок 1 - Решение в Excel
Введем формулы для расчета значений целевой функции (рис 2).
Рисунок 2 - режим формул
Выполним поиск решения задачи «Сервис / Поиск решения» (рис. 3).
Рисунок 3 - Поиск решения
Рисунок 4 - Дополнительные параметры поиска
Рисунок 5 - Решение задачи
Делаем выводы.
Суммарная прибыль составит 975 ден. ед.
При этом будет произведено изделия первого вида (шкафы) - 25 ед., изделия второго вида (тумбы) - 50 ед.
Заключение
В результате выполнения курсового проекта были рассмотрены следующие задачи:
рассмотрены основные понятия линейного программирования;
рассмотрены основные понятия целочисленного программирования;
решение задач симплекс - методом;
решение задач линейного программирования в пакете Excel.
Список использованных источников
модель вычислительный программный надстройка
1. Алесинская Т.В. Учебное пособие по решению задач по курсу «Экономико-математические методы и модели». Таганрог: Изд-во ТРТУ, 2002, 153 с.
2. Алесинская Т.В., Сербин В.Д., Катаев А.В. Учебно-методическое пособие по курсу «Экономико-математические методы и модели. Линейное программирование». Таганрог: Изд-во ТРТУ, 2001. 79 с.
3. Кузнецов А.В. Сборник задач по высшей математике. Математическое программирование. - Мн.: Выш. шк., 2002.
4. Орлов, А.И. Прикладная статистика. М.: Издательство «Экзамен», 2004.
5. Орлов, А.И. Эконометрика Учебник. М.: Издательство «Экзамен», 2002.
6. Колемаев, В.А. Теория вероятностей и математическая статистика: учебник для вузов / В.А. Колемаев, В.Н. Калинина - 2-е изд., перераб. и доп. - М.: ЮНИТИ-ДАНА, 2003. - 362 с.
Размещено на Allbest.ru
Подобные документы
Построение экономико-математической модели оптимизации производства с учетом условия целочисленности. Расчет с помощью надстроек "Поиск решения" в Microsoft Excel оптимального распределения поставок угля. Экономическая интерпретация полученного решения.
контрольная работа [2,5 M], добавлен 23.04.2015Моделирование задачи определения оптимального плана выпуска продукции, вывод ее в канонической форме. Решение задания с помощью надстройки MS Excel "Поиск решения", составление отчетов по устойчивости и результатам. Оптимальная прибыль при заданной цене.
курсовая работа [635,6 K], добавлен 07.09.2011Технология решения задачи с помощью Поиска решения Excel. Отбор наиболее эффективной с точки зрения прибыли производственной программы. Задачи на поиск максимума или минимума целевой функции при ограничениях, накладываемых на независимые переменные.
лабораторная работа [70,0 K], добавлен 09.03.2014Типы транспортных задач и методы их решения. Поиск оптимального плана перевозок методом потенциалов. Решение задачи с использованием средств MS Excel. Распределительный метод поиска оптимального плана перевозок. Математическая модель, описание программы.
курсовая работа [808,7 K], добавлен 27.01.2011Построение и обоснование математической модели решения задачи по составлению оптимального графика ремонта инструмента. Использование табличного симплекс-метода, метода искусственных переменных и проверка достоверности результата. Алгоритм решения задачи.
курсовая работа [693,1 K], добавлен 04.05.2011Симплекс метод решения задач линейного программирования. Построение модели и решение задачи определения оптимального плана производства симплексным методом. Построение двойственной задачи. Решение задачи оптимизации в табличном процессоре MS Excel.
курсовая работа [458,6 K], добавлен 10.12.2013Построение экономико-математической модели. Решение задачи с помощью надстройки MS Excel "Поиск решения". Целевая функция задачи. Формульный вид таблицы с исходными данными. Результат применения надстройки. Организация полива различных участков сада.
контрольная работа [1,3 M], добавлен 28.11.2012Графический метод решения и построение экономико-математической модели производства. Определение выручки от реализации готовой продукции и расчет оптимального плана выпуска продукции. Баланс производства проверка продуктивность технологической матрицы.
задача [203,4 K], добавлен 03.05.2009Построение модели планирования производства. Использование инструментального средства "Поиск решения" для решения задачи линейного программирования. Решение оптимальной задачи, с использованием методов математического анализа и возможностей MathCad.
лабораторная работа [517,1 K], добавлен 05.02.2014Пример решения задачи симплексным методом, приведение ее к каноническому виду. Составление экономико-математической модели задачи. Расчеты оптимального объёма производства предприятия при достижении максимальной прибыли. Построение симплексной таблицы.
практическая работа [58,0 K], добавлен 08.01.2011
