«Рекомендовано Учебно-методическим объединением по образованию в области прикладной информатики в качестве учебного пособия для студентов вузов, обучающихся по специальности Прикладная информатика (по областям) МОСКВА ...»
-- [ Страница 8 ] --
С математической точки зрения идея морфологического пе ребора базируется на получении размещений с повторениями из к по л, число которых в общем случае подсчитывается, как уже показано, а в частном случае при одинаковом числе значений каждого из параметров (т.е. при /cj - kj-... = к. =...= к^^^ = к) определяется с помощью известной теоремы комбинаторики где п - число строк МЯ;
к - число элементов в каждой строке.
Для сокращения перебора этапы 3 и 4 могут быть совмеще ны, а явно неприемлемые варианты можно сразу исключить из рассмотрения в п. 5.
Следует отметить, что, строго говоря, речь об оптимизации идти не может. Идею поиска наилучшего варианта (вариантов) решения лучше квалифицировать как постепенно ограничиваемый перебор, который с самого начала сокращается благодаря фор мированию МЯ, поскольку число размещений с повторениями меньше числа сочетаний, по мере увеличения объемов МЯ раз рыв увеличивается и ограничение перебора сказывается в боль шей степени. Затем область выбора решения ограничивается в результате исключения явно неприемлемых вариантов, а дальней шее ограничение области возможных решений можно организо вать путем введения и учета количественных, а затем (при прочих равных условиях) и качественных критериев, подобно тому, как это предлагается далее в модификации ММЯ применительно к задачам планирования при позаказной системе производства.
Возможны следующие пути выбора решений из МЯ (рис. 1):
применение одного критерия, полностью исключающего все варианты решений, кроме одного (рис. 1, а)\ последовательное применение нескольких критериев А, В, С, постепенно исключающих все варианты, кроме одного (рис. 1, б)\ расчленение проблемы на подпроблемы (или задачи - на под задачи) и последовательное применение нескольких критериев для выбора по одному варианту решения по каждой из подпроблем (подзадач), которые, вместе взятые, и составляют искомое реше ние (рис. 1, в).
В последнем случае может быть получено не одно решение, составленное из решений подпроблем, а несколько таких реше ний, и тогда для уменьшения числа этих вариантов дальнейшее сужение области допустимых решений может осуществляться введением дополнительных критериев (как правило, качествен ных), как это делается, например, в [1].
Следует также оговорить, что решения по подпроблемам, из которых формируется общий вариант решения, могут быть взаи мозависимыми (в частности, при размещении по линиям сборки один и тот же заказ не может в соответствующем плановом перио де помещаться на разные взаимозаменяемые линии сборки [1]).
Ф. Цвикки и его последователи разрабатывали и исследова ли МЯ различного вида. Например, известен вариант МЯ, в ко тором значения одного и того же параметра откладывались и по горизонтальной, и по вертикальной оси двухмерной матрицыящика», и варианты решений получались на пересечении раз личных значений параметров, т.е. как элементы этой матрицы.
МЯ могут быть также не только двухмерными. Трехмерные МЯ и МЯ большей размерности находят, например, применение при разработке прогнозов и при макропроектировании вариан тов новой техники.
Однако при формировании и анализе многомерных МЯ, осо бенно при анализе проблем организационного управления, воз никают существенные трудности в их представлении лицам, при нимающим решения, и в интерпретации результатов. Поэтому удобнее, используя идею морфологического подхода, разрабаты вать языки моделирования (автоматизации моделирования, ав томатизации проектирования и т.п.), которые применяются для «порождения» возможных ситуаций в системе, возможных вари антов решения и часто как вспомогательное средство формиро вания нижних уровней иерархической структуры целей и функ ций или организационных структур систем управления. В этом случае термин «морфологический подход» применяется в более широком смысле.
Предложенные Ф. Цвикки методы нашли широкое примене ние как средство активизации изобретательской деятельности. А при моделировании задач автоматизации проектирования, задач планирования, например распределения заказов по плановым периодам, размеш;ения их по производствам, линиям сборки и т.п., удобным средством оказался ММЯ, который охарактеризу ем несколько подробнее.
Обратим внимание на тот факт, что при формировании мор фологической таблицы (морфологического ящика) другие мето ды морфологического моделирования могут использоваться как вспомогательные.
Модификации морфологического моделирования для задач пла нирования при позаказиой системе производства однотипной продукции. В практике объемно-календарного планирования ока залось удобным как бы перевернуть двухмерный МЯ и комбини ровать не элементы строк, а элементы столбцов (такие таблицы привычнее для работников плановых подразделений).
Рассмотрим модификацию метода морфологического ящика на упрощенном примере.
Предположим, что цех получает задание на производство продук ции не в штуках, а в виде заказов, включающих изделия, одинаковые по трудоемкости изготовления, но имеющие определенные отличительные особенности (например, различную окраску, комплектацию и т.п.). Так может планироваться производство приборов разного рода, специаль ного оборудования, автомобилей для экспорта, специализированных интегральных элементов электронных устройств и т.д.
Для простоты допустим, что речь пойдет о сборочном цехе и о про изводстве достаточно крупных изделий, объемы заказов которых исчис ляются в штуках.
Пусть требуется выполнить следующие заказы: Z1 = 10, Z2 = 20, Z3 = = 30, Z4 = 40, Z5 = 50, Z6 - 60 (объемы заказов даны в условных едини цах; это могут быть либо изделия большого размера, либо объемы в тысячах штук и т.п.). Для их выполнения в цехе имеются три взаимоза меняемые сборочные линии, по которым заказы нужно распределить по возможности более равномерно, но в то же время не дробить заказы на части, так как это усложняет ведение документации и учет поставок про дукции заказчику.
Эта задача может быть отнесена к классу задач загрузки оборудо вания.
При постановке данной задачи с применением математического про граммирования целевая функция может, например, иметь следующий вид:
где Ф. - общий фонд времени работыу-го вида оборудования (в данном случае линий сборки) в плановом периоде;
Л'. - количество изготавливаемых изделий /-го вида;
а.. - трудоемкость изготовления одного изделия /-го вида нау-м виде Таким образом, даже если не выполнять одно из требований задачи не делить заказы на изделия, то и в этом случае задача не может быть представлена в форме наиболее исследованной и имеющей стандартное программное обеспечение задачи линейного программирования, раз ность в выражении (3) может менять знак (возможна либо недогрузка, либо перегрузка оборудования), т.е. целевая функция немонотонна и ее минимизация не имеет смысла. Разумеется, существуют подходы к ре шению задач в такой постановке. Однако применяемые приемы затруд няют понимание моделей и интерпретацию результатов на практике.
Известны эвристические алгоритмы решения этой задачи. Напри мер, задаваясь Ф. и х. и зная (из нормативно-справочной информации) ^/.., вычисляют фактическую трудоемкость изготовления всех изделий Т., коэффициенты загрузки оборудования /i, его пропускной способности Г|, перегрузку и недогрузку оборудования Ал'^ -Ах., по значениям кото рых судят о необходимости изменения х-. Процедура повторяется до тех пор, пока не получены приемлемые значения +Ах. и -Ах.(рис. 2).
В таком эвристическом алгоритме можно учесть больше факторов производственного процесса; например, при вычислении можно учесть коэффициенты сменности, износа и переналадки оборудования и т.п.
Однако и этот алгоритм не позволяет выполнить одно из требова ний, содержащихся в условиях данной задачи, - не дробить заказы. Это требование можно выполнить, поставив задачу целочисленного про граммирования с булевыми переменными. Однако такая постановка в еще большей мере усложнит практическое использование модели.
Можно предложить и другие эвристические алгоритмы: расположить заказы в порядке возрастания и соединять крайние или просуммировать объемы заказов и разделить на число линий сборки, а затем пытаться подобрать усредненный объем.
Однако, во-первых, при большом числе заказов эти алгоритмы так же нереализуемы, а во-вторых, если в приводимом примере первый за каз имеет объем не 10, а 20 единиц, то сумма не делится на 3 без дробле ния не только заказов, но и изделий.
Рассмотрим возможность применения для решения этой за дачи метода морфологического ящика*.
Сформируем из заказов морфологическую матрицу - МЯ (табл.
1). Формировать МЯ будем не из векторов-строк, как в исходном варианте Ф. Цвикки, а из векторов-столбцов, что удобнее для ра ботников плановых подразделений (похоже на привычные для них таблицы планов загрузки производств, кварталов и т.п.).
При формировании столбцов можно предложить какой-либо принцип объединения заказов в группы.
Например, в одном из вариантов применения этого метода при формировании МЯ для распределения заказов по кварталам было предложено объединить заказы в группы с учетом заказчиков * Впервые задача была исследована и программно реализована студен тками И.Н. Фаенсон (на примере распределения заказов по кварталам) и Г.И. Корсуновой (на примере распределения заданий на выполнение проек тов в НПО).
и приоритетности выполнения их заказов, и получены следую щие группы: экспортные заказы, заказы для других отраслей и внутриотраслевые заказы.
В рассматриваемой задаче заказы вначале объединим подряд в 2 группы: А = яВ = (табл. 1, a). Если приемлемое решение не будет получено, то МЯ можно перефор мировать, объединив заказы по-другому.
На основе полученной матрицы-«ящика» можно, комбинируя элементы столбцов (по одному из каждого столбца), образовать возможные размещения заказов по линиям сборки (обозначен ным в МЯ L = ), из которых далее нужно сформи ровать требуемое решение или варианты решения по принципу, приведенному на рис. 1, в, т.е. решение должно состоять из трех размещений, отражающих загрузку всех трех линий сборки; при этом один и тот же заказ не может планироваться для выполне ния более чем на одной линии, и все заказы должны быть выпол нены и войти в решение. Идея исключения заказов выбранных вариантов иллюстрируется табл. 1, в.
рениями нужно образовать разные массивы для символьной и чис ловой информации, т.е. отделить массивы наименований заказов ZA и ZB, которые нужно хранить и представлять ЛПР в символьном виде, и объемы заказов OZA и OZB (числа), и связать массивы ZA - OZA и ZB - OZB общими переменными (табл. 1, б). Для со кращения перебора можно также связать общей переменной с мас сивом L один из массивов заказов.
Принципиальный алгоритм получения размещений с повто рениями приведен на рис. 3, а. Пользуясь этим алгоритмом, мож но получить область допустимых решений, т.е. возможных раз мещений заказов по линиям.
Если эта область получается очень большой, то в алгоритм можно ввести ограничения по суммарному объему S заказов, выполняемых на одной линии SMIN и SMAX (рис. 3, 5), варьи руя которыми, можно расширять и сужать область допустимых решений.
Далее применяют алгоритмы для исключения выбранных ва риантов на каждом очередном шаге (первоначально эти алгорит мы были названы алгоритмами «вычеркивания»), которые при ведены на рис. 3, < и г.
На практике крайне редко бывают ситуации, когда удается по лучить абсолютно одинаковую загрузку линий (или станков, квар талов и т.п.). Поэтому задача ставится как задача минимизации перегрузки или недогрузки оборудования, плановых периодов.
При этом, как видно из табл. 1, в, может получиться несколь ко вариантов решения, которые в отношении первоначального количественного критерия (числа изделий) равноценны.
Для уточнения решения можно ввести дополнительные крите рии - трудоемкость, объем реализуемой продукции или прибыль от ее реализации и т.п., с помощью которых можно ограничивать область допустимых решений аналогично рассмотренному.
Кроме того, можно далее ввести качественные критерии. На пример, из двух равноценных вариантов с перегрузкой одной из линий можно выбрать вариант с перегрузкой линии, на которой производятся хорошо отработанные конструкции изделия, и, напротив, недогрузить линию, на которой производится вновь осваиваемое изделие.
Аналогично при решении задачи загрузки плановых перио дов можно выбрать вариант, в котором недогружен летний квар тал, на который приходится наибольшее число отпусков, или учесть критерий пожелания приоритетного заказчика выполнить его заказ пораньше.
Ввод L, ZA, ZB, OZA, OZB, N Ввод L, ZA, ZB, OZA, OZB, N Ввод SMIN, SMAX Ввод L, ZA, ZB, OZA, OZB, N Ввод Л1, Ввод L, ZA, ZB, OZA, OZB, N ввoцA^,в^.AZB Ц1), ZA(I), ZB(J), S Таким образом, применяя морфологические! подход, получа ем человеко-машинную процедуру принятия решений, которая позволяет в интерактивном режиме выбирать варианты решения, последовательно уточнять критерии, а при необходимости - воз вратиться и переформировать МЯ.
Отметим, что с помощью морфологического подхода факти чески получена методика постепенного ограничения области до пустимых решений. Иными словами, морфологический подход оказался методом активизации, который помогает ЛПР в поста новке задачи и организации поиска ее решения, т.е. в постепен ной формализации задачи.
В математическом отношении рассмотренная процедура не является процедурой оптимизации. Ее можно квалифицировать как постепенно ограничиваемый перебор.
В реальных условиях принципы постановки задачи и разра ботки алгоритмов сохраняются, но конкретизируются с учетом особенностей задач и условий производства. Особая необходи мость в использовании морфологического подхода возникает в условиях разнотипного производства.
Планирование загрузки оборудования в условиях позаказного производства разнотипной продукции"^. Предположим, что при распределении годовой производственной программы разнотип ного производства по кварталам нужно учесть следующие про изводственно-экономические факторы: наличие изделий с дли тельностью производственных циклов, превышающей плановый период (квартал); незавершенное производство на начало и ко нец года (переходящие заказы или партии изделий); сроки и ко личество изделий, в том числе заказами и партиями; возможность варьирования размерами партий изделий; концентрацию выпус ка одноименных и конструктивно однородных изделий в одном или смежных плановых периодах (в качестве показателей конст руктивной однородности можно ввести коэффициент конструк тивной преемственности изделий) и т.п.
Основным критерием, как и в предыдущей задаче, будем счи тать требование равномерной загрузки оборудования (по разным производствам или в разных плановых периодах, в нашем случае кварталах), которую формально можно выразить в виде допустиПример подготовлен студенткой СПбГТУ И.В. Корнеевой.
мых отклонении от среднеквартальнои загрузки, уменьшением которой можно сузить область допустимых решений, а увеличе нием - расширить ее.
Ограничение перебора возможных вариантов размещения заказов или партий изделий по плановым периодам определяет ся прежде всего принципами формирования МЯ. В частности, в рассматриваемой задаче координаты МЯ определяются следую щим образом: число строк в МЯ равно числу плановых перио дов, т.е. по 4 кварталам {Kf), число столбцов зависит от числа заказов и партий и от конкретных производственно-экономичес ких условий производства.
Например, для учета производственно-экономических факторов, рассмотренных в начале постановки задачи, в МЯ можно выделить сле дующие столбцы (табл. 2):
1) специальные заказы СЗ., сроки выпуска которых жестко заданы и привязаны к соответствующему кварталу (в МЯ это отражается общим индексом у кварталов и заказов, т.е. общей переменной); 2) заказы Д., изделия которых имеют длительность производственного цикла боль ше квартала; 3) изделия серийного и массового выпуска Р., распределя емые равномерно (пропорционально числу рабочих дней); 4) распреде ляемые заказы и партии изделий РЗ., сроки которых жестко не заданы;
5) распределяемый заказ Р35., изделия которого имеют длительность про изводственного цикла три квартала и в связи с этим разделены на три условных заказа РЗ5,', Р357'. ^^зз ^^^^ сокращения перебора эти заказы связаны общим индексом с заказами группы РЗ., но могли бы иметь и независимый индекс); 6) заказы и партии конструктивно однородных (с изделиями заказов СЗ.) изделий КО., которые целесообразно изготав ливать в том же квартале, что и специальные заказы СЗ., имеющие кон структивную однородность с ними (что и отражено общим индексом /);
7) и 8) - прочие заказы и партии изделий ПЗА. и ПЗБ., количество изде лий в которых может меняться (что отражается в модели путем пере формирования МЯ). Например, в приведенном МЯ заказ ПЗ, разделен на партии, содержащие 5 и 15 изделий; заказ ПЗ-, - на партии из 10 и изделий; изделия заказа ПЗБ имеют производственный цикл два кварта ла, и заказы ПЗ3 и ПЗ4 разделены на партии, состоящие из четырех и двух изделий. Столбцы 7 и 8 в общем случае могут быть не связаны ин дексом (переменной). В этом случае при выборе вариантов решения нуж но учитывать, что ПЗ30 выполняется после ПЗз; (т.е. в следующем квар тале), а ПЗ42 - после ПЗ^, (чтобы это не учитывать в алгоритме выбора решения, нужно столбец 8 в МЯ связать с кварталами общей перемегпюй).
Кроме того, в МЯ, приведенном в качестве примера в табл. 2, учте но, что А J - заказ, переходящий с предыдущего года, поэтому он поме щен в первую строку (первый квартал) и в первый столбец заказов, свя занный общим индексом со столбцом кварталов; заказ Е3 обязательно должен быть выпущен в третьем квартале, заказ С выпускается двумя партиями по 25 штук во втором (С-,) и четвертом (С^) кварталах (они тоже помещены в первый столбец, связанный переменной с квартала ми); заказ Д. с длительностью цикла два квартала должен быть завер шен во втором квартале (для этого Д. разделен на части Д / и Д /, кото рые помещены в первый и второй кварталы также путем образования столбца, связаьнюго общей переменной со столбцом кварталов). Оценка каждого заказа обозначена индексом этого заказа с буквой «О» перед ним.
В целом правила формирования М Я определяются конкрет ными производственно-экономическими условиями и эвристичес кими правилами, которыми руководствуются работники пла новых подразделений предприятия. Эти правила полезно сфор мулировать, создать автоматизированную диалоговую процеду ру формирования МЯ в виде экспертной системы, постепенно на капливающей новые правила, возникающие в реальных условиях производства, и на основе этого опыта совершенствовать и уско рять процессы планирования.
Обратим внимание, что в приведенном примере число разме щений заказов и партий по кварталам R = 4^ = 256, а если бы не было столбцов, связанных переменными, то область допустимых решений была бы существенно больше.
Дальнейшее сокращение числа вариантов размещений дости гается за счет критериев, ограничивающих область принятия ре шений последовательным их введением. Прежде всего (как и в уже рассмотренном упрощенном примере) следует учесть критерий равномерной загрузки (или минимальной перегрузки либо недогрузки кварталов).
При этом следует иметь в виду, что если в случае однотипного производства можно было в качестве исходного критерия использовать количество изделий, то при разнотипном производ стве необходимо сразу в качестве критерия выбирать трудоемкость.
В реальных условиях не всегда удается определить усреднен ную трудоемкость для всего технологического цикла сложного изделия, и тогда общая оценка трудоемкости может быть заме нена несколькими оценками трудоемкости изготовления изделия на разных производствах или с использованием разных видов оборудования. В последнем случае можно первоначально разде лить общую задачу планирования на ряд подзадач загрузки от дельных участков или видов оборудования (например, сборка, окраска, регулировка и т.д.), получить для этих участков вариан ты равномерной загрузки, а затем сформировать сетевые модели вариантов технологического цикла изделия.
В качестве дополнительного критерия можно использовать ограничение по фондам материально-технического снабжения, т.е. учесть предварительно составленный план получения пред приятием соответствующих материалов, покупных полуфабри катов, комплектующих изделий и т.п., и повлиять на изменение этого плана. В числе дополнительных критериев могут быть ис пользованы такие, как объем реализуемой продукции, себестои мость, прибыль, расход заработной платы, а также уже рассмот ренные качественные критерии.
Расширению практического применения МЯ существенно способствует автоматизация морфологического моделирования.
При этом важно автоматизировать не только получение вариан тов решения, т.е. собственно перебор, но и получение оценок этих вариантов, и даже формирование МЯ.
• 1. В о л к о в а В. Н. Основы теории систем и системного анализа: учеб.
для вузов / В.Н. Волкова, А.А. Денисов. - СПб.: Изд-во СПбГТУ, 1997. С. 142-145, 394-404. 2. О д р и н В. М. Метод морфологического анализа технических систем / В.М. Одрин. - М.: ВНИПИ, 1989. 3. О д р и н В. М.
Морфологический анализ систем / В.М. Одрин, С.С. Картавов. - Киев: Наукова думка, 1977. 4. С и с т е м н ы й анализ в экономике и организации про изводства: учеб. для вузов / Под ред. С.А. Валуева, В.Н. Волковой. - Л.: По литехника, 1991.-С. 91-95,231-244. 5. Z w i c k y F. Morfological astronomy/ F. Zwicky: Berlin: Springer-Verlag, 1957. 6. Z w i с к у F. Morphology of justice in the space age and the Boundaries at Outer space / F. Zwicky // Automatica Acta. - 1969. - № 14. - P. 615-626. B.H. Волкова, В.А.Дуболазов МУЛЬТИАГЕНТНЫЕ СИСТЕМЫ - термин, применяющийся для названия систем, предназначенных для организации взаимо действия с разнородными источниками информации.
«