Нахождение оптимального плана производства двух типов ремонтных работ с помощью симплексного метода
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
ВВЕДЕНИЕ
Оптимальной производственной программой предприятия считается такая программа выпуска продукции, при которой достигается максимальный экономический эффект. Такая производственная программа может быть определена только путем решения задачи по размещению и концентрации производства по отрасли или народному хозяйству в целом.
Под оптимальной производственной программой следует понимать такой выпуск изделий за определенный промежуток времени, при котором достигается максимальная экономическая эффективность для данного предприятия.
Применение экономико-математических методов в планировании производства позволяет рационально использовать сырьевые ресурсы, а, следовательно, снижать себестоимость выпускаемой продукции, а прибыль приносить максимальную. Наибольшее значение и наиболее широкое применение при решении экономических задач в настоящее время приобрели методы линейного программирования.
Методы линейного программирования позволяют обеспечивать рациональный раскрой материалов, рациональное смешивание взаимозаменяемых компонентов, помогают разрабатывать технически обоснованные нормы расхода материалов.
Экономические задачи в большинстве случаев относятся к экстремальным задачам, для решения которых необходимо из большого количества возможных решений найти одно, оптимальное, т.е. максимизирующее или минимизирующее соответствующую числовую функцию. Задачи такого типа решаются методами линейного программирования.
В частности:
-симплексный метод,
-метод искусственного базиса,
-двойственный симплексный метод,
-графический метод.
В данной курсовой работе используется симплексный метод, задача линейного программирования реализуется на ЭВМ, используя средства ЯП Pascal для решения задач оптимизации.
1 ПОСТАНОВКА ЗАДАЧИ
Небольшая фирма производит два тина подшипников А и В, каждый из которых должен быть использован на трех станках, а именно на токарном, шлифовальном и сверлильном.
Время, требуемое для каждой из стадий производственного процесса, приведена в табл.1.
Таблица1
Тип подшипникаВремя обработки (час)Прибыль от продажи 1 подшипника (доллары)Токарный станокШлифовальный станокСверлильный станокА0.010.020.0480В0.020.010.01125Полное время работы В неделю (час)160120150
Фирма хотела бы производить подшипники в количествах, максимизирующих ее прибыль. Задачу решить симплексным методом. Программу составить на языке программирования С и реализовать на ПЭВМ.
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ
Математическая модель в общем виде:
Вводятся обозначения:- тип подшибников;- виды станков;ij - норма расхода , i-го вида сырья на j вид ремонтных работi - общее количество сырья i-го вида;j - прибыль от одного ремонта j - го вида;j - выпуск ремонтных работ j-го вида;- максимальная прибыль от выпуска ремонтных работ.
Математическая модель данной ЗЛП:
при ограничениях:
Модель необходимо привести к каноническому виду, введем дополнительные переменные:x3,x4,x5,x6, а в целевую функцию они войдут с нулевыми коэффициентами.
Тогда модель примет вид
при ограничениях
3 МЕТОД РЕАЛИЗАЦИИ МОДЕЛИ
Поставлена задача линейного программирования. Найти максимальное значение функции
при ограничениях
Алгоритм симплексного метода представляет собой способ целенаправленного перебора планов. Через конечное число шагов линейная форма достигает max или min.
Заполняется исходная таблица. После чего производится вычисления в последовательности:
Подсчитывается и определяется, не является ли рассматриваемый план оптимальным, т.е. не выполняется ли для всех x условие: 0
Если для некоторого j значение >0, то выбирается вектор, который может быть введен в базис. Для этого разыскивается какое-нибудь j, для которого max()=>0, тогда P- вводится в базис.
; : j=1,2,…,n
Выбирается вектор, который подлежит исключению из базиса. Это вектор для которого: q = min= для всех X>0 , тогда P- исключается из базиса.
Если все X< 0, то линейная форма неограниченна снизу.
После выделения направляющей строки и направляющего столбца, таблица преобразуется по формуле полного исключения.
В результате каждой итерации образуется новый опорный план. В конце концов, либо придем к оптимальному плану, либо убедимся в неограниченности линейной формы задачи. Вычисления сводятся в табл.2:
Таблица №2
iБазисCP0C1C2……Cl……CmCm+1……Cj……Ck……CnP1P1……P1……PmPm+1……Pj……Pk……Pn1P1C1X110……0……0X1,m+1……X1j……X1k……X1n2P2C2X201……0……0X2,m+1……X2j……X2k……X2n...………………………………………v……………lPlClXl00……1……0Xl,m+1……Xljv…Xlk……Xln……………………………………………………mPmCmXm00……0……1Xm,m+1……Xmj……Xmk……Xmnm+1Z000……0……0Zm+1-Cm+1……Zj-Cjv…v…
АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ
4.1 Вводятся коэффициенты a,b,c
.2 Заполняется симплексная таблица
.3 Находится базис
.4 Находится опорный план
.5 Вычисляется Z-C в m+1 строке
.6 Проверяется условие Z-C?0 в m+1 строке, если выполняется, то переход на 4.11
.7 Вводится P по max (Z-C)=(Z-C)>0 в m+1 строке
.8 Выводится P по q = min=, Xik, lk ?0
.9 Производится преобразование таблицы
.10 Переход на 4.4
.11 Выводится на печать Xопт и Zопт.
ВЫЧИСЛИТЕЛЬНАЯ СХЕМА
Таблица №380125000iБазисC БазисP0C1C2C3C4C5P1P2P3P4P51P301600.010.021002P401200.020.010103P501500.040.01001m+1zj - cj0-80-1250001P312580000.5150002P40400.020-0,5103P20700.