Содержание к диссертации
Введение
Глава 1. Математическое моделирование процесса оптимизации параметров производственных систем в условиях интервальной неопределенности 12
1.1 Состояние проблемы 12
1.2 Выбор подхода к математическому моделированию производст венных систем с интервальной неопределенностью параметров 16
1.3 Определенные, неопределенные и интервальные числа 18
1.4 Алгебра интервальных чисел 21
1.5 Некоторые особенности интервальных чисел и действий над ними 23
1.6 Математическое моделирование функций в условиях неопределенности 24
1.7 Задача оптимизации функций в условиях неопределенности 26
1.8 Метод сравнения интервалов 27
1.9 Решение задачи условной оптимизации целевой функции в условиях неопределенности 31
1.10 Выводы по главе 1 33
Глава 2. Интервальная задача математического моделирования и оптимизации себестоимости и эффективности продукции производственных систем 36
2.1 Постановка задачи математического моделирования и оптимизации себестоимости и эффективности продукции производственных систем 36
2.2 Метод и алгоритм математического моделирования и оптимизации себестоимости (эффективности) продукции производственных систем с двумя видами выпускаемых изделий 40
2.3 Пример решения задачи моделирования и оптимизации себестоимости (эффективности) продукции производственной системы с двумя видами выпускаемых изделий 45
2.4 Метод и алгоритм математического моделирования и оптимизации себестоимости (эффективности) продукции производственных систем
с произвольным числом выпускаемых изделий 50
2.5. Пример решения задачи моделирования и оптимизации себестои
мости (эффективности) продукции производственной системы с не
сколькими видами изделий выпускаемой продукции 57
2.6. Метод решения детерминированных задач нелинейного
математического программирования 60
2.7. Детерминированная задача квадратичного математического программирования и метод ее решения 64
2.8. Интервальная задача квадратичного математического программирования и метод ее решения 67
2.9. Выводы по главе 2 71
Глава 3. Производственная система с интервальными параметрами 73
3.1 Постановка интервальной задачи математического моделирования и оптимизации функционирования производственно-транспортных систем 73
3.2 Детерминизация задачи 78
3.3. Условия существования решения задачи и алгоритм его отыскания 81
3.4 Математическое моделирование производственной деятельности предприятия в виде производственной функции 83
3.5 Основные требования к производственным функциям 86
3.6 Виды производственных функций 89
3.7 Моделирование производства с помощью интервальных производственных функций 90
3.8 Численные методы моделирования производственных процессов с типовыми интервальными производственными функциями 94
3.9 Выводы по главе 3 97
Глава 4. Комплекс программ для работы с интервальными параметрами производственных систем 99
4.1 Метод и алгоритм математического моделирования решения производственных задач с интервальными параметрами 99
4.2 Парадигмы программирования 101
4.3 Структура комплекса программ 103
4.4 Описание разработанного комплекса программ 105
4.5 Пример решения интервальной транспортной задачи
4.6 Интервальная производственная задача расчета потреблению электроэнергии 113
4.7 Интервальная производственная задача по определению относительных значений величины выпуска продукции и числа занятых в производстве 117
4.8 Выводы по главе 4 134
Заключение 136
Список литературы 138
- Выбор подхода к математическому моделированию производст венных систем с интервальной неопределенностью параметров
- Метод и алгоритм математического моделирования и оптимизации себестоимости (эффективности) продукции производственных систем с двумя видами выпускаемых изделий
- Математическое моделирование производственной деятельности предприятия в виде производственной функции
- Интервальная производственная задача расчета потреблению электроэнергии
Выбор подхода к математическому моделированию производст венных систем с интервальной неопределенностью параметров
Неполнота информации о системе и вытекающие из этого проблемы математического моделирования систем в условиях неопределенности уже довольно продолжительное время и достаточно широко рассматриваются в работах зарубежных и отечественных ученых. При этом в большинстве работ применяются вероятностно-статистические, лингвистические или нечетко-множественные подходы к математическому моделированию систем. В качестве основного метода ухода от неопределенности заданных параметров системы используется метод точечных оценок параметров, выбираемых в центрах соответствующих областей неопределенности [ 9, 12, 13, 17-19, 41, 44, 46, 51, 71, 90, 91, 102, 106, 119, 123].
Несколько иной подход к проблеме математического моделирования систем в условиях неопределенности в связи с задачами оптимизации этих систем развит в работах [ 111, 118]. Здесь исследуются системы, определяемые задачами математического моделирования со случайными коэффициентами в системе ограничений, но с точно заданными коэффициентами целевой функции. Тогда для математического моделирования системы выбираются значения коэффициентов в системе ограничений, при которых эта система выполняется с высокой вероятностью p (например, p = 0,9) после чего решается получившаяся полностью определенная задача обычными методами математического моделирования. Если же не только коэффициенты ограничений, но и коэффициенты целевой функции случайны, то (в предположении, что речь идет о задаче максимизации) выбирается наихудшее возможное сочетание значений коэффициентов целевой функции из их областей неопределенности. Это дает полностью определенную задачу математического моделирования, которая решается обычными методами. Очевидно, что такое решение соответствует минимаксному методу.
Интервальный подход к проблеме математического моделирования систем в условиях неопределенности начался с работ, направленных на следующее: 1) анализ неопределенности, возникающей при вычислениях по данным с ошибками в условиях чисто детерминированной (интервальной) информации об ошибках; 2) анализ неопределенности из-за возникновения ошибок округления при расчетах на компьютерах. Эти две задачи стимулировали поток публикаций зарубежных и отечественных ученых по созданию математического аппарата интервальных вычислений [1, 4, 21, 23, 28, 31, 40, 45, 52, 88, 89, 96, 98, 100, 101, 107, 110, 117, 118, 121, 122].
Этот аппарат позволяет вести вычисление интервальных функций и анализировать их, составлять и решать интервальные уравнения, интервальные задачи оптимизации и т.д. Однако результаты решений всех этих задач, полученные с помощью указанного аппарата, имеют принципиально интервальную форму. Другими словами, в рамках данного подхода невозможно получить решение задачи с интервальными исходными данными в форме точно задуманного числа. Это не всегда удобно, особенно когда речь идет о задачах принятия решения (в экономике, социальной сфере и т.д.). Поэтому в ряде работ, в первую очередь, связанных с принятием экономических решений, были предложены различные приемы, позволяющие при исследовании систем с интервальными исходными данными получать точные (однозначные) решения [19,20,21,24] .
Все изложенные выше подходы к изучению функционирования систем в условиях неопределенности обладают одной общей принципиальной особенностью. Эта особенность заключается в том, что при математическом моделировании системы области возможных значений неопределенных собственных параметров системы и области возможных значений внешних, влияющих на нее факторов, заменяются соответствующими точными значениями - «представителями» указанных областей, выбираемыми из соображений приемлемости, целесообразности или оптимальности, понимаемых в традиционном смысле. Такая замена позволяет свести исходную задачу моделирования системы в условиях неопределенности к задаче моделирования системы в условиях полной определенности, после чего остается лишь применить к последней хорошо известные детерминистические методы, чтобы получить ее решение и тем самым решение (в указанном выше смысле) исходной задачи [13,19].
Однако, указанная замена одной задачи на другую неэквивалентна, поскольку любая система, функционирующая в условиях неопределенности «содержит» в себе целое множество (в общем случае бесконечное) полностью определенных систем. Таким образом, проблема математического моделирования систем в условиях неопределенности остается. Она может быть сформулирована следующим образом: можно ли заменить моделирование системы, функционирующей в условиях неопределенности, моделированием конечного числа К (К 1 ) систем в условиях полной определенности так, чтобы второе было в строго определенном смысле эквивалентно первому? Понятно, что с практической точки зрения число К должно быть не слишком большим.
В 1990-е годы был предложен систематический подход к решению сформулированной проблемы для систем с интервальной неопределенностью [54,56,61,63] . Этот подход основан на том давно известном факте, что алгебраические операции над интервалами (сложение и вычитание, умножение и деление) сводятся к соответствующим операциям над точными числами - границами указанных интервалов. Это означает, что любую статическую систему, функционирующую в условиях неопределенности, с количественной характеристикой в виде интервальной функции [у1{х)у2{х)\ можно представить парой статических систем, функционирующих в условиях полной определенности, количественные характеристики которых суть ух{х)(нижняя граничная система) и у2(х) (верхняя граничная система).
Таким образом, оказывается возможным решать проблему моделирования статической системы в условиях неопределенности сведением к моделированию эквивалентной ей пары (т.е. К = 2) статических, полностью определенных (детерминированных) систем. Для того, чтобы сделать это возможным и для других, более сложных классов систем в условиях неопределенности, нужно вышеуказанное полезное свойство алгебраических операций над интервалами распространить и на другие необходимые операции, определив их надлежащим образом. Для динамических, оптимальных и некоторых других систем такой дополнительной необходимой операцией являются операции сравнения интервалов и выделение большего и меньшего из них. Построение этих операций таким образом, чтобы они обладали вышеуказанными полезными свойствами алгебраических операций над интервалами, было выполнено в работах [54, 58, 59, 61, 66], после чего и появился подход, позволяющий сводить моделирование, расчет и оптимизацию системы с интервальной неопределенностью к решению аналогичных задач для К = 2 полностью определенных (детерминированных) систем. Этот подход, получивший название математической детерми-низации, открыл дорогу математическому моделированию функционирующих в условиях неопределенности систем разнообразного назначения: экономических, социальных, технических, производственных, военных и т.д. - с использованием хорошо разработанных и эффективных методов исследования полностью определенных (детерминированных) систем. Вышесказанное определило цель и задачи диссертационного исследования.
Метод и алгоритм математического моделирования и оптимизации себестоимости (эффективности) продукции производственных систем с двумя видами выпускаемых изделий
Метод решения сформулированной в п. 2.1 интервальной задачи дробно-линейного математического программирования, позволяющей моделировать и оптимизировать формирование удельной себестоимости (удельной эффективности) продукции производственной системы, базируется на методе математической детерминизации, являющемся общим методом решения произвольных интервальных задач условной оптимизации (см.главу 1). Этот метод будет продемонстрирован ниже на примере задачи с п = 2 переменными, позволяющей моделировать и оптимизировать формирование удельной себестоимости (удельной эффективности) производственной системы си = 2 изделий. Тогда решаемая задача звучит следующим образом: найти максимальное значение интервальной дробно-линейной целевой функции в предположении, что коэффициенты целевой функции и ограничений Cj, dj, bt, a - интервалы вида с,- = [с1 ,с]2 ], dt = [dJ1 dJ2 ], bt =[b j1 ,bJ2 ], a j =[ал1 ,ал2 ], в которых с , d1, аг]1 , b1 - минимальные значения интервальных коэффициентов (нижние границы интервалов), а с 2, d 2, аг]2 , Ь2- максимальные значения интервальных коэффициентов (верхние границы интервалов). Будем считать, что знаменатель целевой функции (2.4) всегда неотрицателен и, кроме того, не равен 0 в области неотрицательных решений системы линейных неравенств (2.5) .
Начнем с решения базовой, детерминированной задачи дробно-линейного математического программирования, которая в нашем случае звучит так: найти максимальное значение детерминированной дробно-линейной целевой функции F=c1x1 + c2 d 1 x 1+d2 x 2 при детерминированных линейных ограничениях фі = аі1х1 + а2х2 bt, і = ,т , х1, х2 0 (2.7) в предположении, что знаменатель целевой функции (2.6) всегда неотрицателен и, кроме того, не равен 0 в области неотрицательных решений системы линейных неравенств (2.7).
Чтобы найти решение поставленной детерминированной задачи оптимизации (2.6), (2.7), сначала находим известными методами решение ее системы линейных ограничений (2.7), что дает многоугольник допустимых решений задачи. Далее полагаем значение целевой функции (2.6) равным некоторому фиксированному числу h0. Получаем соответствующую фиксированную прямую, проходящую через начало координат. Вращая построенную прямую вокруг начала координат, получаем множество всех прямых, проходящих через начало координат и имеющих различные возможные значения параметра h0. Из этих прямых определяем экстремальную - ту, которая находится в пределах многоугольника допустимых решений и имеет максимальное значение параметра h0 среди всех прямых, находящихся в указанных пределах.
Согласно теории [70], экстремальная прямая , если она существует, имеет общую точку с многоугольником допустимых решений в одной из его угловых вершин. Таким образом, вращая построенную прямую вокруг начала координат, мы либо находим вершину (вершины) многоугольника допустимых решений, в которой целевая функция принимает максимальное значение ( т.е. находим решение задачи условной оптимизации (2.6), (2.7)), либо устанавливаем отсутствие решения (в случае, если вращаемая прямая не имеет общих точек с многоугольником допустимых решений в его угловых точках). Итак, алгоритм нахождения решения детерминированной задачи дробно-линейного математического программирования включает следующие шаги: 1. В системе ограничений задачи (2.7) заменяются знаки неравенств на знаки точных равенств и строятся определяемые этими равенствами прямые. 2. Находятся полуплоскости, определяемые каждым из неравенств системы ограничений задачи. 3. Находится многоугольник допустимых решений задачи в виде пересечения полуплоскостей, найденных на шаге 2.. 4. Строится прямая, уравнение которой получается, если положить значение целевой функции (2.6) равным некоторому постоянному числу h0. 5. Вращая построенную прямую вокруг начала координат (меняя значение h0), определяем точку максимума, т.е. точку, в которой h0 = max , или, если ее нет, устанавливаем неразрешимость задачи.
Теперь перейдем к решению собственно интервальной задачи дробно-линейного математического программирования (2.4), (2.5). Будем решать поставленную интервальную задачу методом математической детерминизации, т.е. сведением к двум аналогичным детерминированным задачам (см. главу 1). Используем алгоритм решения, приведенный в главе 1. Применительно к рассматриваемой задаче он конкретизируется следующим образом [ 81,84 ].
Математическое моделирование производственной деятельности предприятия в виде производственной функции
С помощью этого метода в главе 2 дано решение задачи дробно-линейного математического программирования, которая является математической моделью процессов математического моделирования и оптимизации ряда удельных показателей производства в условиях неопределенности, например, минимизации себестоимости одного выпускаемого изделия или максимизации удельной эффективности выпускаемых изделий, приходящейся на единицу их себестоимости. В связи с этим представляется естественным распространение подхода к математическому моделированию и условной оптимизации, основанного на методе математической детерминизации, и на другие, практически важные классы прикладных задач математического моделирования и условной оптимизации производственных систем при наличии неопределенности.
В настоящей главе рассматривается важный класс таких задач – моделирование и оптимизация процессов обеспечения необходимыми ресурсами от различных источников самых разнообразных систем, создаваемых человеком (производственные системы, ЖКХ силы и т.д.). К математическим моделям таких систем относят транспортную задачу линейного программирования. При этом неопределенность, которая при решении этих задач будет учитываться, как и везде в данной диссертации, является неопределенностью интервального типа, когда параметры изучаемой системы задаются интервалами возможных значений. Однако особенность интервального варианта транспортной задачи линейного математического программирования по сравнению с другими интервальными задачами условной оптимизации состоит в его смешанном характере, когда коэффициенты при неизвестных у целевой функции - интервальные величины, а коэффициенты при неизвестных в ограничениях - детерминированные величины. С другой стороны, ограничения в транспортной задаче линейного математического программирования имеют специальный вид по сравнению с ограничениями в общей задаче линейного математического программирования. Все это делает целесообразным выделение транспортной задачи линейного математического программирования при наличии интервальной неопределенности, служащей математической моделью оптимального по стоимости процесса обеспечения необходимыми ресурсами различных, в первую очередь, производственных систем, в отдельный класс задач, для которых имеет смысл искать более эффективные, чем в общем случае, методы решения задач условной оптимизации.
Начнем с рассмотрения детерминированной, т.е. не имеющей неопределенности, версии транспортной задачи линейного программирования, служащей математической моделью оптимального по стоимости процесса обеспечения необходимыми ресурсами различных детерминированных (полностью определенных) производственных систем.
Детерминированная постановка транспортной задачи линейного математического программирования формулируется следующим образом [85] . Имеется т производителей некоторой продукции и и ее потребителей. Известны стоимости с перевозки единицы продукции от каждого /-го производителя к каждому у-му потребителю. Известны также производительности 6г каждого /-го производителя и потребности Ъ\ каждого 7-го потребителя. Необходимо прикрепить потребителей к производителям таким образом и запланировать перевозку продукции от производителей к прикрепленным потребителям в таких количествах, чтобы суммарные перевозки от каждого производителя ко всем прикрепленным к нему потребителям не превышали производительности данного производителя, суммарные перевозки от всех производителей к любому прикрепленному к ним потребителю покрывали его потребность, а суммарная стоимость всех перевозок (.т.е. перевозок от всех производителей ко всем прикрепленным к ним потребителям) была минимальна.
Здесь х -неизвестный план перевозок продукции от /-го производителя к 7-му потребителю, с - стоимость перевозок единицы продукции от /-го производителя к у-му потребителю, /У - производительность /-го производителя, /У -потребность 7-го потребителя. Все эти величины образуют соответствующие векторы и матрицы : X = х - матрицу объемов перевозок от производителей к потребителям, С = с - матрицу стоимостей единиц перевозок от производителей к потребителям, Ь = Щ- вектор производительностей, /У = \\Ь \\- вектор потребностей. Коэффициенты с.., /У, /У в (3.1) - (3.3), по смыслу задачи, являются неотрицательными величинами. Таким образом, в поставленной задаче требуется найти такой (оптимальный) план перевозок от производителей к потребителям, при котором суммарные перевозки от каждого производителя ко всем прикрепленным к нему потребителям не превышают его производительности, суммарные перевозки от всех производителей к любому прикрепленному к ним потребителю покрывают его потребности, а суммарная стоимость всех перевозок минимальна.
Задача (3.1) - (3.3) представляет собой некоторую стандартную задачу линейного математического имеет решение при следующем необходимом и достаточном условии [70] т.е. когда суммарная производительность превышает суммарную потребность (точнее, не меньше ее). Для программирования, т.е. задачу с ограничениями-неравенствами. Эта задача отыскания решения транспортной задачи (3.1) -(3.3) разработан ряд специальных методов, главные из них - распределительный метод и метод потенциалов [70].
Недетерминированная (интервальная) транспортная задача линейного математического программирования, изучаемая ниже, отличается от детерминированной задачи (3.1) - (3.3) тем, что коэффициенты в ней имеют вид замкнутых интервалов .. =[с;1,су2], г = [b1,bi2], =[Ь b ], в которых находятся возможные значения их величин, причем конкретные значения коэффициентов внутри указанных интервалов неизвестны. Так что матрица коэффициентов е.. целевой функции задачи (3.1) является здесь интервальной матрицей = [c1,ci2] =[01 ,02 ], где Q = с1 - минимальная, а С2 = с2 максимальная детерминированные матрицы коэффициентов, составленные из минималь-ных(максимальных) значений коэффициентов. Аналогично, имеем интервальный вектор ограничений перевозок сверху = [6;1,bi2] = [b1 ,b2], где Ь1 = \\Ь1\\-минимальный, а b2=\\bi2\\- максимальный детерминированный вектор ограничений сверху, составленный из минимальных (максимальных) значений этих ограничений.
Интервальная производственная задача расчета потреблению электроэнергии
Противоречивость требований к комплексу программ обуславливает выбор среды программирования как одного из важнейших условий успешного решения поставленной задачи. Применение таких программных систем как Microsoft Visual Studio или Borland Delphi позволяет выполнить программу как самостоятельное приложение.
Такие математические пакеты прикладных программ как Mathcad, Maple, Mathematica имеют широкий набор математических функций и широкий набор встроенных средств графической визуализации [2], но не позволяющий включить в разработку базу результатов и исходных данных.
Необходимо помнить, что для реализации программного комплекса необходим язык программирования, допускающий объектно-ориентированный подход, переопределение операций и обладающий библиотеками графических функций. Из языков общего назначения сюда можно отнести С++, С#, Python, Vala, D и т. д. 6
Кроме перечисленных языков общего назначения существует целый ряд специализированных скриптовых языков программирования или, как их еще называют, языков пакетной обработки. Работа с программой на таком языке осуществляется в консоли при помощи специального программного интерпретатора. Применение скриптовых языков для решения нашей задачи более целесообразно, так как это позволит сделать модули программного комплекса открытыми, а также позволит сократить сроки разработки за счет отказа от графического интерфейса. К скриптовым языкам относятся Python, Ruby, Perl, Matlab, Octave и т. д.
В настоящее время существуют системы компьютерного моделирования различных процессов и явлений. Среди них есть универсальные средства, которые позволяют решать различные задачи математического программирования, такие как MathCad, Maple, MATLAB и др. Обобщая вышеизложенное, можно заключить, что самым удобным вариантом является система с открытым кодом, имеющая в своем составе язык, ориентированный на математическое моделирование. Анализ показал, что наиболее в полной мере указанным требованиям отвечает операционная среда объектно ориентированного программирования Borland Delphi v.7 путем взаимодействия с системой прикладных программ MatLab [2]. MatLab универсален, обладает широким набором функций, выпускается для различных операционных систем, гибок, имеет собственный язык программирования, ориентированный на работу с матрицами. Включает большой набор математических функций, допускает интеграцию с Microsoft Word и Excel. MatLab имеет большие возможности для графической визуализации результатов и дальнейшего расширения функциональности, позволяет создавать встроенные приложения с графическим интерфейсом, имеет средства для интеграции с базами данных. Также MatLab позволяет конвертировать программный код из собственного языка в язык C++, что дает возможность при необходимости выполнить программу как самостоятельное приложение и разрабатывать программы для встраиваемых систем, что полезно для дальнейшего внедрения комплекса 7 программно на практике. Автором был разработан комплекс программ для моделирования производственных интервальных задач (транспортная задача, определение производственной функции). Главное окно комплекса программ представлено на рисунке 4.4.
Модель построения интервальных производственных функций и решения задач оптимизации была реализована в системе MATLAB, которая представляет собой уникальный сплав программных и алгоритмических средств с широкой гаммой специализированных предложений. На базе ядра MATLAB созданы многочисленные расширения, обеспечивающие моделирование и анализ систем [2].
Для решения задач линейного математического программирования используется встроенная функция linprog. Однако средств решения транспортной задачи в MATLAB не предусмотрено, поэтому был разработан m-файл – функция transp, который, используя встроенную функцию Matlab linprog, позволяет решить транспортную задачу.
На рисунке 4.5 представлены экранные формы разработанной программы для ввода исходных данных интервальной транспортной задачи, в которые можно вручную или выгружать исходные данные из файла.
Схема алгоритма функции transp представлена на рисунке 4.7. Приведенные результаты разработки программы решения интервальной транспортной 9 задачи являются примером части разработанного комплекса программ, представляющего и другие интервальные задачи: производственной, по выпуску продукции и производственной по потреблению электроэнергии.
Приведем результаты исследования интервальной транспортной задачи, полученные с помощью разработанной программы (подраздел 4.4).
Условие задачи: Допустим, что некая компания, занимающаяся ремонтом автомобильных дорог, в следующем месяце собирается проводить ремонтные работы на пяти участках автодорог. Песок на участки ремонтных работ может доставляться из трех карьеров. Месячные объемы предложений по доставке песка из всех этих карьеров известны. Также, в соответствии с планом производства ремонтных работ известны с точностью до интервалов значений месячные объемы потребностей по участкам работ. Кроме того, имеются экономические оценки транспортных затрат на перевозку одной тонны песка из различных карьеров на различные ремонтируемые участки. Требуется: разработать оптимальный план перевозок песка из различных карьеров на различные участки ремонта автодорог, который обеспечивал бы минимальные совокупные транспортные издержки. Т.к. суммарные мощности поставщиков и потребителей равны, то данная модель является закрытой моделью транспортной задачи. В таблице 4.1 показаны исходные данные.
