Содержание к диссертации
Введение
Глава 1. Модель планирования производства, ориентированная на учет эффекта масштаба производства 12
1.1 Эффект масштаба производства 12
1.2 Линейная модель планирования производства 14
1.3 Нелинейная экономико-математическая модель, ориентированная на учет эффекта масштаба и выпуск неизбежного брака продукции 18
Глава 2. Прикладное использование выпуклого программирования 23
2.1. Предпосылки к возникновению 23
2.2 Основные определения 24
2.3 Метод штрафных функций 29
2.4 Алгоритмы метода штрафных функций с неполной минимизацией вспомогательных функций 37
2.5 тестовые задачи. Сравнительный анализ 47
Глава 3. Cистема поддержки принятия решений и поиска оптимального плана производства и реализации продукции при ограниченных ресурсах, ориентированная на учет эффекта масштаба и выпуск бракованной продукции 60
3.1 Описание программного комплекса 60
3.1.1. Поле задания количества переменных 64
3.1.2. Поле для ввода целевой функций 64
3.1.3.Элементы управления для ввода начальной точки, ограничений 65
3.2 Задача планирования производства, ориентированная на учет эффекта масштаба Производства и неизбежного выпуска брака 67
Заключение 74
Список источников 76
- Линейная модель планирования производства
- Нелинейная экономико-математическая модель, ориентированная на учет эффекта масштаба и выпуск неизбежного брака продукции
- Метод штрафных функций 29
- Поле для ввода целевой функций
Линейная модель планирования производства
В данном разделе рассматривается теория эффекта масштаба производства, история и развитие данной теории. Определяется понятие эффекта масштаба производства.
Теория эффекта масштаба производства зародилась в 80-ые годы, в трудах А.Маршалла, который определил ряд преимуществ объединенных предприятий с отдельной взятой крупной компанией [69,70]. При этом малые предприятия, которые находятся вблизи друг от друга, получают возможность успешно конкурировать с крупными промышленными предприятиями, в том числе за доступ к местным ресурсам. У такой совокупности малых предприятий возникает эффект экономии на масштабе производства (внешняя экономия), также как и в крупных предприятиях (внутренняя экономия). Современный вклад в понимание термина «эффекта масштаба» внесли американские экономисты М. Кэмп и П. Кругман, которые отказались от стандартной модели Хэкшера-Олина (об отсутсвии зависимости прибыли от масштабов деятельности предприятия, как производственно-экономической системы). Они определили, что с ростом масштабов производства, себестоимость продукции дешевеет и цена на товар, соотвественно, падает [62]. Для увеличения масштабов производства необходимо максимально расширить рынок, что может обеспечить только механизм внешней торговли. П.Кругман определил этапы развития мирового рыночного механизма, которые обуславлены действием крупных производителей на рыночный сегмент. Проанализировав автомобильный рынок в Западной Европе, он определил, что данный сегмент растет благодаря продукции 10 крупных поставщиков. В этом случае возникает эффект масштаба, когда крупные производители доминируют за счет: . качества товара (высокие затраты на научные исследования); за счёт более низких затрат на единицу продукции. Влияние фактора эффекта масштаба приводит к тому, что предприятия разных стран, которые относятся к одной и той же отрасли начинают специализироваться на более узкой товарной категории и вести торговлю друг с другом продукцией одной и той же отрасли [59,62].
Все больше экономистов сходятся во мнении, что классические теории уже не в состоянии объяснить современную международную торговлю, поскольку в России, как и в других странах, в первую очередь выделяют владение каким-либо важным естественным или производственным ресурсом, совершенно игнорируя главную причину - эффект масштаба, который в свою очередь оказывает существенное влияние на прибыль предприятия. С другой стороны, вторым фактором, способствующим увеличению объема реализации продукции и прибыли, является качество продукции. Качество продукции, в свою очередь, характеризуется наличием или отсутствием неизбежного брака. Для того, чтобы управлять браком, предприятия должны не просто учитывать их в составе затрат, а определять величину затрат от допущенного брака. В связи с чем, возникает необходимость построения модели планирования производства, ориентированного на учет эффекта масштаба и выпуск бракованной продукции [114].
В данном разделе рассматривается линейная модель планирования производства без учета эффекта масштаба и выпуска бракованной продукций. В задачах, объединенных этим названием, рассматривается производство нескольких видов различной продукции, на изготовление которых затрачиваются материальные ресурсы (сырье, комплектующие, полуфабрикаты), человеческий труд, время, энергетические ресурсы, финансы, причем наличие всех ресурсов ограничено [19, 46]. Изготовленная продукция затем направляется в продажу или на реализацию в другие производства. Требуется определить оптимальный план производства, т. е. найти, какую продукцию и в каком количестве следует выпускать, чтобы суммарная прибыль (выручка, доход) от продажи всех видов продукции была максимальной [46,61].
Для составления математической модели необходимо, прежде всего, структурировать операцию, другими словами, выделить в ней цель, критерий сравнения возможных решений, управляемые и неуправляемые факторы, ограничения, множество возможных решений.
Целью рассматриваемой операции является получение большей суммарной прибыли, и соответствующий этой цели критерий представляет собой величину прибыли. По величине суммарной прибыли будут оцениваться различные решения по выпуску продукции, и наилучшим решением будет то, которое соответствует наибольшему значению прибыли. Ограничения определяются совокупностью неуправляемых факторов и выражают ограниченные объемы запасов ресурсов, имеющихся на фирме. Рассмотрим общую постановку задачи о планировании производства [19]. Предприятие планирует выпуск n видов продукции A1, А2,…,Аn на производство которых затрачивается m видов ресурсов S1 ,S2,…,Sm — сырье различных видов, энергоносители, финансы, трудозатраты. Предприятие располагает предельным количеством ресурсов в объемах b1, b2, b3,…, bm , усл. ед. Количество каждого вида ресурса Si, i = 1, 2, ..., m, затрачиваемого на производство единицы продукции Aj, j = 1, 2, ..., п, известно и равно аij усл. ед/ед. прод. После изготовления продукции А1, А2, ..., Аn она поступает в продажу. Ожидаемая прибыль от реализации единицы каждого вида продукции известна и составляет c1,c2,…,cn ден. ед./ед. прод.
Требуется составить план производства, то есть определить, какую продукцию и в каком объеме следует производить предприятию, чтобы получаемая от реализации продукции суммарная прибыль была максимальной [61].
Нелинейная экономико-математическая модель, ориентированная на учет эффекта масштаба и выпуск неизбежного брака продукции
Все алгоритмы сходятся и имеют приближенное решение. Следует отметить, что алгоритмы 3 и 6 решают такого типа задачу за меньшее число итераций, чем другие. Алгоритм 1 и 2 оказались самыми трудоемкими по общему числу итераций, это, видимо, связно с трудоемкостью вычислений этапов для вспомогательных функций.
Задача решалась в программе, разработанном в среде программирования Delphi 7.0 на компьютере с процессором Intel Core i3, с частотой 3,2 Ггц и 4 Гб оперативной памяти. Пример 1 решался алгоритмом 1 за 0.4 секунды, алгоритмом 2 - за 0.4 секунды, алгоритмом 3 - за 0.2 секунды, алгоритмом 4 и 5 - за 0.3 секунды, алгоритмом 6 - за 0.1 секунды. Пример 2. Задача выпуклого программирования, начальная точка выбирается какх0 = (0,0,0,0).
Оптимальное приближенное решение задачи 2 приведено в таблице 2.2. Здесь можно сделать вывод, что самым трудоемким алгоритмом является алгоритм 1. В примере 2 алгоритм 3 немного превосходил по числу итераций алгоритм 6, значит, надлежащий выбор параметра p лучшим оказался именно у алгоритма 3. При выборе параметра a 1 трудоемкость вычисления снижается и, соответственно, уменьшается число этапов минимизаций вспомогательной функции. Как отмечалось в работе [87], существует произвол выбора расчета коэффициента штрафа, однако лучшим является именно мультипликативный закон изменения коэффициента штрафа. В примере 1, как и в примере 2 , в алгоритмах метода штрафных функций с неполной минимизацией вспомогательных функций на первом шаге задавалось начальное значение 10 и увеличивалось по мультипликативному способу изменения роста коэффициента штрафа Ск=ак, однако в работе И.А.Фукина [87] использовался иной способ роста коэффициента штрафа Ск= , который зависит от параметра //, который рекомендуется брать больше 1, чтобы гарантировать решение задачи. Для нашего коэффициента мы не всегда можем гарантировать включение итерационной точки в допустимую область. Также следует учесть тот факт, что увеличение значения параметра С ведет к большей овражности функций. Следовательно, мы не всегда можем получить даже приближенное решение, доказательство тому пример 3. Пример 3. Задача [68] выпуклого программирования.
Таблица 2.3. Решение примера 12 3 4 5 Точкаминимумаx Числоитераций приN=2 и а =2(значения),гдеСк=ак Числоитераций при7У=2 иа =2(значения),гдеСк = uN к Оптимальноеприближенное решениеF(x ), где Ск=ак Оптимальноеприближенное решениеF(x ), гдеСк = N к
С теоретической точки зрения мультипликативный закон изменения параметра штрафа Ск = должен был выглядеть лучше, так при N=k вкючение точки в заданную область выполняется. Однако на практике мы не всегда видим, что данный способ выглядит лучше.
В работе [68] найдено приближенное решение JC = (0,268191;-0,028947), F(JC )=1,06874. По полученным результатам можно сказать, что оптимальным и приближенным решением для примера 3 является решение задачи алгоритмом 5. Следует отметить, что алгоритмы 3 и 5 решают такую задачу за меньшее число итераций. Оцениваемый параметр у не сильно влияет на исход решения данных задач. Однако точность решения таких задач в большей степени зависит от параметра р, который может использоваться в промежуточных этапах вычислений.
В работе [92] получено решение х = (1,75;0,25), F(x )= - 4,125. Теперь получим решение алгоритмами метода штрафных функций с неполной минимизацией вспомогательных функций. При этом выбирается начальная точка х0 = (0;0), как и в работе [92].
Таблица 2.4. Решение примера 4 6 Точкаминимумаx Числоитераций приN=5 и а =10,гдеСк=ак Число итерацийпри N=5 и а =10, гдеС С к = uN к ОптимальноеприближенноерешениеF(x ), где Ск =ак ОптимальноеприближенноерешениеF(x ), где (1,76; 0,25) 66 69 -4,15 -4,12 (1,75; 0,25) 34 34 -4,14 -4,14 Алгоритмы 1 и 6 привели к приближенному решению примера 5. Из таблицы 2.4 видно, что общее число итераций с использованием мультипликативного способа Ск = ак заметно ниже, чем при использовании закона Ск = , что заметно снижает вычислительные затраты на решение примера 4. Пример 4 есть задача квадратичного программирования. Как отмечено в работе [77], лучшим оказался способ сведения задачи к форме равенств, чем использование внешнеквадратичного штрафа. Также можно отметить, что алгоритмы 1 и 6 по общему числу итераций и скорости сходимости превосходили как сам метод штрафных функций без использования внешнеквадратичного штрафа (общее число итераций составило 95), так и с использованием внешнеквадратичного штрафа (общее число итераций составило 216), см. работу [77]. Причем, наблюдалась большая трудоемкость вычисления градиента штрафной функций при решении задачи с использованием внешнеквадратичного штрафа.
На графике приведены результаты счета по общему числу итераций по трем методам, где АМШФ с НМВФ обозначает алгоритм метода штрафных функций с неполной минимизацией вспомогательных функций; МШФ - метод штрафных функций; МШФ с ВШ - метод штрафных функций с использованием внешнеквадратичного штрафа. задачи в работе [92]: х = (5; 1,25), F(x )= 7,5625.
Решаем задачу со смешанными ограничениями алгоритмами метода штрафных функций с неполной минимизацией вспомогательных функций. Построим таблицу приближенных решений: Таблица 2.5. Решение примера Алгоритмы Точкаминимумаx Числоитераций приN=5 и а =10,гдеСк=ак ОптимальноеприближенноерешениеF(x ), где Ск =ак Парамет р p
Точка минимума находится на границе первого ограничения. Из таблицы 2.5 видим, что алгоритмы 6 и 3 решают эту задачу за меньшее число итераций, чем другие. Самым трудоемким оказался алгоритм 1.
Использование мультипликативного закона Ск = позволило решить эту задачу алгоритмом 1 (при N =5 и а =10) за 112 итераций, алгоритмом 6(при N =5 и а =10) за 42 итерации. Остальные алгоритмы оказались более трудоемкими и имели другие результаты. Пример 5 решался в разработанном программном комплексе алгоритмом 1 за 0,4 секунды, алгоритмом 2 - за 0,4 секунды, алгоритмом 3 - за 0,2 секунды, алгоритмами 4 и 5 - за 0,3 секунды, алгоритмом 6 - за 0,1 секунды.
Метод штрафных функций 29
Для выполнения условия (b) необходимо и достаточно, чтобы множество X было ограничено.
Доказательство. Достаточность. По определению X = {х: х є Д0), f(x) f j = D(0) C\Q(f )- В постановке задачи (1.20) предполагается, что минимум функции f(x) на множестве D(0) достигается. Поэтому множество X непусто, а по условию (Ь) еще и ограничено. Тогда по теореме 1.4, в силу выпуклости функции f(x) и выпуклости и замкнутости D(0), множество D(p )nQ(f) также ограничено. Так как р 0, то D(p ) D(0). Отсюда следует неравенство f f и включение Q(f ) Q(f). Тогда множество D(0) п Q(f) не пусто. Далее снова по теореме 1.4 в силу выпуклости функции g(x) и выпуклости и замкнутости множества Q(f) получим ограниченность множества D(p ) n Q(f). Необходимость доказывается аналогично в обратную сторону. Следуя схеме доказательства теоремы 2.4 также несложно показать, что условие (Ь) выполняется тогда и только тогда, когда множество X ограничено.
В силу [18, стр. 207] при выполнении условия (а) множество D(0) выпукло, замкнуто и ограничено. Поэтому несложно заметить, что при выполнении условия (а) или (Ъ) будет выполняться и условие (с). Необходимость явного введения этого условия состоит в том, что многие оценки используют константу Липшица L.
Алгоритмы метода штрафных функций с неполной минимизацией вспомогательных функций В данном разделе рассмотрены алгоритмы метода штрафных функций с неполной минимизацией вспомогательных функций.
В диссертационной работе представлены алгоритмы метода штрафов, которые допускают приближенное решение вспомогательных задач за конечное число итераций с точностью, которая задается. Эти алгоритмы имеют критерии остановки, при выполнении условий которых гарантируется точность и допустимость полученного решения [43]. Основным фундаментом для построения этих алгоритмов является аппроксимация допустимого множества [38].
Разберем подробно алгоритмы, которые допускают приближенное решение вспомогательных задач. Надлежащий выбор параметра р, который зависит от точности решения вспомогательных задач, позволяет обеспечить требуемую точность решения задачи (2.20) [38, стр. 46]. Алгоритм 1.
Программная реализация 3-го алгоритма принимается в качестве є - решения задачи (2.8) - (2.20). Алгоритм 4. Задается требуемая точность решения є О, х0 є Rn, числа 8 є (0, є), у є (О1), натуральное число N. Выбирается 0 р rmn{8 yas(s-S) возрастающая функция p(t) такая, что L(sV(x )-ya(s-\ + y) s(\-ry- a т Функция штрафа выбирается вида: F(x) = (max{y:(x),0}) при s 1 (в данном случае s=2). Полагается к= 1. 1. Вычисляется Ск=ср{к). 2. Если к N, то находится приближенное решение задачи rmnF(x,Ck). Переход к шагу 1 при к, измененном на к+\. 3. Если к = N, то находится точка хп є А{а), являющаяся 8 оптимальным по функционалу решением задачи min F(x, CN). Точка xN принимается в качестве є - решения задачи (2.8) - (2.20).
Замечание. Как известно [38], построение точки XN при помощи алгоритмов 1 и 3 доказано и возможно. Сходимость алгоритмов 2 и 4 доказывается аналогично доказательству сходимости алгоритмов 1 и 3. Для гарантии включения итерационной точки в область Д0) необходимо правильно выбрать возрастающую функцию tp(f).
Надлежащий выбор параметра р в зависимости от заданной точности решения вспомогательных задач обеспечивает требуемую точность решения задачи (4).
Здесь р - число р =р(е) , р 0 такое, что из включения х{С) є Д0) будет следовать неравенство \f(x(C)) -/ е; L - константа Липшица для функций/ , определенных на множестве G, L 0, \f(x)-f(y)\ L\\x-y\\,\/x,yeG и G Rn; Р,у- параметры аппроксимаций, где у є [О1) и р 0 ; д- р) - функция, обратная к модулю выпуклости д(р) и 0 р р ; Ск - коэффициент штрафа, вычисленный по следующему правилу: Ск=а к, где а - параметр, используемый для вычисления коэффициентов штрафа; множество А(а) - аппроксимация допустимого множества; g(x) - функция равномерно выпуклая на множестве ДО) с неубывающим модулем выпуклости 3(р); выпуклое и замкнутое множество Д(0) удовлетворяет условию Слейтера, т.е {x:xeR,g(x) O} = 0; точка х є Argmin{/(x),x є D(0)}; p - число, где p є(Q,-irfi{g(x),x єRn}; p - число, где p є (О,р), где pG(0-M{g(x\xGRn}); V{x) - функция штрафа; к- номер итераций; а - число, где а = тах{«: А (а) с ДО)}. 2.5 Тестовые задачи. Сравнительный анализ В этом разделе сравнивается эффективность применения алгоритмов метода штрафных функций с неполной минимизацией вспомогательных функций. Рассматриваются задачи выпуклого программирования.
В ходе проведенного тестового эксперимента, задачей которого было выявление лучших значений для вводимых параметров, а также сравнение эффективности алгоритмов, были реализованы алгоритмы с неполной минимизацией вспомогательных функций. Контрольные примеры представляют собой задачи выпуклого программирования с ограничениями.
Поле для ввода целевой функций
Принятие управленческих решений в планировании производства, ориентированного на учет эффекта масштаба происходит последовательно. Изначально на основе известных данных строиться экономико математическая модель. Процесс работы с программы начинается с главного окна, в котором необходимо ввести данные – целевую функцию, систему ограничений, входные параметры, выбрать начальную точку и конечное число итераций. Далее необходимо выбрать оптимальный алгоритм из списка представленных алгоритмов. По кнопке «Решить» рассчитать оптимальный план производства и реализации продукции при ограниченных ресурсах, учитывающих влияние нескольких факторов производства (выпуск бракованной продукции и эффект масштаба производства) (Рис 3.8). Полученное оптимальное решение можно экспортировать в файл, после чего провести анализ данных относительно выпуска продукций и получения максимальной прибыли.
Программный комплекс имеет синтаксический анализатор математических формул, что позволяет решать многие задачи выпуклого программирования. Разработанная система на основе алгоритмов метода штрафных функций с неполной минимизацией вспомогательных функций может быть использована: руководителями, экономистами, бухгалтерами - для принятия управленческих решений и расчета максимальной прибыли предприятия с учетом выпуска брака и эффекта масштаба производства; при проведении практических занятий для дисциплин, использующих математические методы в экономике и менеджмента.
Представленный выше метод штрафных функций в работе был реализован при помощи интегрированной среды визуального программирования Borland Delphi Version 7.0. [26,30,61]. Приложение для решения задачи планирования производства, ориентированного на учет эффекта масштаба производства имеет синтаксический анализатор математических формул [41,46]. При этом задачи выпуклого программирования решаются с помощью различных алгоритмов метода штрафов. Главное окно приложения представлено на следующем рисунке:
Меню о разработчике приложения 3.2 Задача планирования производства, ориентированная на учет эффекта масштаба производства и неизбежного выпуска брака В данном разделе рассматривается практическая задача модели планирования производства, ориентированная на учет эффекта масштаба производства. Задача решается с помощью программного комплекса.
ОАО «КАМАЗ» и немецкий концерн «ZF» открыли новый корпус совместного предприятия «ЦФ КАМА» по производству коробок передач. Предприятие ОАО «Лизинговая компания КАМАЗ» - является дочерним предприятием ОАО «КАМАЗ» предлагает покупку продукции в лизинг. «ЦФ КАМА» производит два вида коробок передач Ecosplit-16s151 и Ecosplit -16sl820 при этом использует 369 видов деталей для сборки коробок. Производство продукции, помимо годной продукции, сопровождается также выпуском определенного количества брака. Благодаря немецким технологиям и инновациям производителю «ЦФ КАМА» удалось добиться эффекта масштаба производства, в результате которого с увеличением объемов выпускаемой продукции снижается ее себестоимость и растет прибыль.
В табл. 3.1 приведены численные значения затрат ресурсов на производство одной усл.ед. (шт.) годной продукции (коэффициенты ац) и затраты ресурсов на производство одной усл.ед. (шт.) бракованной продукции (коэффициенты кц).Значения прибыли (млн. руб) от реализации одной усл.ед. (шт.) продукции без учета (коэффициенты Cj) и с учетом (коэффициенты lj) эффекта масштаба производства приведены в таблице (3.2). Требуется найти оптимальный план производства продукции, т.е. объемы выпуска х1 и х2 годной продукции коробок передач Ecosplit -16s151 и Ecosplit - 16s1820, обеспечивающий максимальную суммарную прибыль.
Ресурсы (запчасти) № Расход ресурсов на производствоодной усл.ед. (шт.) годной (ац) ибракованной (кц) продукцииEcosplit-16s151 и Ecosplit - 16sl820 ,усл.ед. (шт.) Ограничения наресурсы(запчасти) (Ь}), усл.ед
Решаем задачу алгоритмами метода штрафных функций с неполной минимизацией вспомогательных функций [114]. Неполная минимизация означает, что процесс минимизации осуществляется по эвристическому критерию. В качестве вспомогательной функций, использовалась функция: F(x,C) = f(x)+CV(x), C 0 , где С - штрафной параметр, гарантирующий попадание точки минимума вспомогательной функций в множество
Замечание. В работе Фукина И.А., Заботина Я. И. было сформулировано определение p - аппроксимируемости функций, обобщающее понятие p -регулярности ограничений задач математического программирования. Также было доказано, что для любого є 0 существует p 0, такое что неравенство
Результаты численного решения этой нелинейной математической модели имеют вид: хг =120,1, х2 =8,4 , Fmax =21,7 млн. руб. Полученные оптимальные значения переменных модели и максимальное значение целевой функции означают, что для достижения максимального значения суммарной прибыли ( = 21,7 млн. руб.) при наличии выпуска бракованной продукции и эффекта масштаба производства, необходимо производить 120 (шт.) коробок передач Ecosplit-16s151 и 8 (шт.) коробок передач Ecosplit-16s1820.
Из таблицы 3.3 видно, что наличие бракованной продукции при выпуске существенно снижает суммарный объем выпуска качественной продукции, а эффект масштаба приводит к увеличению максимальной прибыли и оказывает существенное влияние на оптимальные планы выпуска продукции. Пренебрежение влияния как фактом выпуска брака и эффекта масштаба производства приводит к неадекватным значениям оптимального выпуска продукции, значительно отличающихся от реальных.