Abstract

Abstract

Приведено описание усовершенствованной методики решения многовариантных неформализованных задач класса выбора и принятия решений, являющихся наиболее распространенной категорией производственных задач. Подробно рассмотрены проблемы решения задач выбора. Для моделирования и решения указанных задач рекомендуется использовать специальные программные средства.

Full Text

Общеизвестно, что одним из приоритетных направлений современного научно-технического процесса является автоматизация инженерного труда на базе новых компьютерных технологий. Как свидетельствует отечественный и мировой опыт, внедрение вычислительной техники во все сферы человеческой деятельности создает условия для повышения производительности и качества труда. В настоящее время масштабы применения вычислительной техники во всех сферах производства постоянно возрастают. Наиболее широко применяют вычислительную технику в научных и проектных организациях, в учебных заведениях. На некоторых крупных предприятиях подготовка производства выполняется с использованием систем автоматизированного проектирования. Однако на производстве большинство специалистов работают без компьютеров. Причины такого положения связаны, в первую очередь, с характером производственной деятельности. Труд специалиста можно представить как последовательное решение различных задач, а эти задачи настолько разнообразны, что содержание и необходимую последовательность их выполнения определить заранее, как правило, не представляется возможным. В связи с этим если и удается автоматизировать, то решение не всего комплекса вопросов, а только отдельных наиболее часто встречающихся задач. Другой особенностью практических задач является то, что в массе своей они относятся к категории неформализованных, т.е. задач, исходные данные и результаты решения которых нельзя выразить в числовой форме и точный алгоритм решения которых изначально неизвестен. К таким задачам нельзя применить традиционные методы математической оптимизации и поэтому их трудно автоматизировать. На практике специалисты решают производственные задачи, опираясь прежде всего на свои знания и опыт работы. Однако из-за преобладания субъективного фактора в работе существует большая вероятность принятия неоптимальных и даже ошибочных решений. Очевидно, создание доступной для практического использования общей методики решения разнообразных по содержанию задач следует считать актуальным. Основы методики решения неформализованных задач. На кафедре сварочного производства Пермского национального исследовательского политехнического университета в результате многолетних исследований, проводившихся применительно к многовариантным неформализованным задачам сварочного производства, разработана информационная технология решения задач класса выбора и принятия решений. При ее создании использовали некоторые положения теории искусственного интеллекта, теории нечетких множеств, системного анализа и автоматизированного проектирования. Практическая часть работы заключалась в построении табличных и графических моделей типовых задач сварочного производства, отличающихся исключительным разнообразием и множественностью. Анализ большого объема экспериментальных данных (всего было построено свыше 500 моделей) позволил выявить проблемы моделирования и решения задач указанного класса, а также разработать научно обоснованные рекомендации, инвариантные предметным областям. В основу подхода принято положение о том, что значительное большинство производственных задач формулируется (или может быть сформулировано) как задачи выбора наиболее предпочтительного варианта из нескольких предположительно возможных. Ввиду распространенности таких задач они выделены в отдельный класс, для них разработали основы теории и методы решения [1]. Методика разработана применительно к задачам выбора, а также другим сложным задачам, в которых всегда имеются элементы выбора. Основные положения методики сводятся к следующему: – неформализованная задача может быть сформулирована как задача выбора предпочтительного в определенном отношении варианта из нескольких конкурирующих. Правилом предпочтения является соответствие решения заданным условиям задачи; – для решения поставленной задачи всегда необходимо проводить сбор и анализ дополнительной информации, отсутствующей в условии задачи; – если альтернатив не менее 4–5, то выбор не очевиден и требует учета нескольких факторов, а постановка задачи формализуется в виде таблицы соответствий; – результат решения задачи получают обработкой данных таблицы соответствий по универсальному алгоритму, однотипному для всех задач; – при большом количестве альтернатив и вариантов условий задачи табличную модель трудно анализировать визуально. В этих случаях модель анализируют с помощью граф-схем алгоритмов выбора решений или специальных программных средств; – на основе анализа построенной модели выбирают метод ее корректировки, приводя к виду, приемлемому для пользователя; – во многих случаях для упрощения решения целесообразно разделять сложную задачу на несколько более простых и решать их как систему взаимосвязанных подзадач; – для задач выбора из 2–3 альтернатив таблицы соответствий не строят. В этом случае альтернативы сравнивают по частному критерию, выбранному из числа влияющих факторов, или по комплексному критерию, учитывающему значимость нескольких факторов; – успешного решения многих неформализованных задач можно достигнуть при совместном использовании процедур выбора, расчета и численных оценок. Пояснения к приведенным положениям имеются в работе [1]. Таблицы соответствий и граф-схемы алгоритмов. В проведенных исследованиях решение всех задач предусматривало прохождение следующих этапов: – отбор вариантов решений, из которых возможен выбор; – сбор информации об альтернативах и факторах, влияющих на выбор; – построение модели задачи в форме таблицы соответствий; – выявление и преодоление возможной неоднозначности решений при некоторых исходных условиях; – разработка схемы алгоритмов поиска оптимальных решений и их анализ. Принципиально важным из перечисленных этапов является построение моделей задач в форме таблиц соответствий. Форма таблицы соответствий (ТС), предложенная Г.К. Горанским [2], является одним из видов таблиц решений, предназначенных для формализованного представления задач выбора и принятия решений. Общий вид и структура ТС показаны на рис. 1. Таблица соответствий представляет собой прямоугольную матрицу, разделенную на три области. В область прибытия ТС помещают возможные варианты решений (альтернативы), из которых осуществляют выбор, а в области отправления указывают условия, влияющие на выбор, и их значения. Соответствия между значениями условий и решениями указывают в клетках матрицы с помощью значений булевой функции (1 или 0). Нули, как правило, в матрицу соответствий не записывают, оставляя клетки пустыми. Все перечисленные понятия кодируют цифровыми и буквенно-цифровыми кодами (см. рис. 1, б). Тем самым формализуются необходимые знания о предметной области задачи. б Рис. 1. Общая структура таблицы соответствий Т (Х, Y): а – области ТС; б – общий вид ТС, обозначения параметров и значений параметров Каждая таблица является моделью не одной, а множества однотипных по условиям и целям задач, общее число которых равно количеству возможных вариантов задания условий выбора решений по ТС. Формальное решение конкретной задачи сводится к нахождению строки или строк таблицы, в которых для всех без исключения элементов заданного кортежа исходных данных указано наличие соответствий. Название соответствующей строки (строк) в области прибытия показывает решение задачи. Дополнительно следует иметь в виду, что условия выбора решений X1, X2, …, Xn по существу являются независимыми переменными, или входными параметрами, а возможные решения у1, у2, …, уn – выходными параметрами. Эти термины приняты в теории моделирования и используются в дальнейшем изложении. Представление моделей задач в форме таблиц соответствий обладает многими преимуществами. Алгоритм поиска решений по таблице является универсальным и не зависит от содержания задачи. При построении ТС из источников информации извлекается только минимально необходимая для решения задачи информация, а вся остальная (сопутствующая) информация отсеивается. Таким образом, форма ТС позволяет сжимать исходную информацию. Во многих случаях одна ТС способна содержать в себе информацию о сотнях и тысячах вариантах решения однотипных по постановке и целям задач. Наряду с отмеченными достоинствами таблицы соответствий имеют ряд недостатков. В частности, по таблицам соответствий невозможно визуально просмотреть все возможные варианты решений и оценить качество построенной модели, ее пригодность для практического применения. Поэтому предложено анализировать ТС с помощью специальных граф-схем, создаваемых на базе соответствующих ТС [1–3]. Пример решения задачи. Проиллюстрировать изложенную выше методику моделирования и решения задач выбора можно на примере, взятом из работы [4]. Таблица, приведенная ниже, является таблицей соответствий, построенной по данным справочника [5], и предназначена для выбора марки электрода для сварки коррозионно-стойкой стали в зависимости от четырех признанных существенными факторов. Нетрудно заметить формализованность, простоту и компактность табличной модели. По ней можно определить решение для 108 вариантов возможных условий задачи. Однако проанализировать все эти варианты непосредственно по таблице очень сложно. Такую возможность предоставляет построенная на основе ТС граф-схема алгоритмов поиска решений (рис. 2). Граф-схема представляет собой геометрическое построение в виде расширяющегося книзу «дерева», состоящего из вершин и соединяющих их дуг. Вершины графа отождествляют с параметрами ТС, а дуги – со значениями параметров. Конечным вершинам приписывают некоторые решения из области прибытия ТС или решение у = Æ, что означает отсутствие решения. Таблица соответствий в задаче выбора марки электрода для сварки коррозионно-стойкой стали YМарка электродаХ1 – марка, группа сталиХ2 – требования к МКК*Х3 – Т, ºСХ4 – коррозионная среда Типа Х13Типа 18-10Типа 18-10Т03Х16-Н15М315Х18Н 12С4ТЮДвухслойныеНетОбычныеЖесткиеКомнатнаяДо 350До 600Средней агрессивностиТипа HNO3 12345612312312 1ОЗЛ-8 11 1 1 1 2ОЗЛ-3 1 1 1 1 3ЗИО-81 11 1 1 4УОНИ-13/НЖ1 1 1 1 5ОЗЛ-22 1 1 1 1 6ОЗЛ-14а ОЗЛ-36 1 1 1 1 7ОЗЛ-7 1 11 1 8ЦЛ-11 1 1 11 9ЦЛ-9 1 1 11 1 10ОЗЛ-20 1 11 1 11НИАТ-1 11 1 1 1 12ЭА-400/10У 11 1 1 1 *МКК – межкристаллитная коррозия. Рис. 2. Граф-схема алгоритмов выбора марки электрода (обозначение кодов по ТС) Граф-схема по существу является аналогом ТС, но обладает большей наглядностью. По ней можно видеть все многообразие алгоритмов и логику выбора решений. Схему можно анализировать по направлению от корня графа к элементам и в противоположном направлении. Двигаясь по схеме сверху вниз, можно определить, например, что если сварное соединение предназначено для работы в среде средней агрессивности (х41), но не предъявляются требования стойкости металла против межкристаллитной коррозии (х21), а материалом конструкции является сталь типа Х13 (х11), то рекомендуется сварка электродами марки УОНИ-13/НЖ (у4). Возможно и решение обратных задач – определение условий назначения конкретной марки электрода (движение по схеме снизу вверх). Для специалиста, занимающегося анализом качества модели, некоторым неудобством является то, что вершины и дуги графа обозначены кодами и в процессе анализа постоянно приходится расшифровывать коды. В проведенных исследованиях введена практика дополнительного построения блок-схем, аналогичных граф-схемам, но с указанием на них натуральных обозначений блоков и связей. Проблемы решения задач. Выше были отмечены достоинства методики, основанной на моделировании и решении задач выбора с помощью ТС. Тем не менее на практике эта методика не получила заметного распространения, несмотря на то, что ее развитием занимались многие исследователи. Анализ результатов исследований показал, что при решении задач возникают затруднения, связанные, главным образом, с неполнотой и неточностью первичной информации о задачах. Это проявляется на всех этапах решения (от изучения условий задачи до анализа полученных результатов). Для устранения названных трудностей приходится обращаться к дополнительным источникам информации. Но при этом изначально неизвестно, где можно найти необходимые сведения, что именно следует собирать и в каком виде фиксировать. Трудности имеются и при построении ТС и граф-схем. В ТС наиболее сложным является формирование области отправления: отбор влияющих на выбор факторов и формулирование их значений; указание соответствий в матрице таблицы значениями двузначной логики (1 или 0). Самой трудоемкой операцией является ручное построение граф-схем. С увеличением вводимых в модель параметров размеры граф-схем и их сложность резко возрастают. В проведенных экспериментах редко удавалось построить приемлемые по сложности граф-схемы при количестве входных параметров свыше 5–6 и количестве клеток в матрице ТС свыше 600–700. Наиболее актуальной в общей проблематике решения задач по методике Горанского оказалась проблема, которую можно назвать неоднозначностью решений, генерируемых моделью. Суть проблемы состоит в том, что при некоторых сочетаниях значений входных параметров применяемый алгоритм поиска решений по табличной модели может приводить к более чем одному решению. Неоднозначность хорошо видна на граф-схемах, где некоторым конечным элементам ветвей графа бывает приписано два и более решений. В работах по моделированию задач с неоднозначностью решений приходится встречаться постоянно, даже в самых простых задачах. В большинстве случаев неоднозначность рекомендаций не устраивает тех, кто решает задачи, так как модель не выполняет своего основного назначения – помогать в выборе определенного решения из нескольких возможных. Актуальность проблемы неоднозначности решений потребовала проведения специальных исследований. В результате разработаны приёмы и методы ее устранения [1], в частности предложен новый тип таблицы соответствий. В клетках матрицы такой модели наличие соответствий указывают не с помощью единиц и нулей, а степенями принадлежности (введены в теории нечетких множеств [6]), которые могут принимать любые значения в пределах от 0 до 1. Для входных параметров модели, выражаемых натуральными числами (например, размеры, масса, стоимость и т.п.), строят функции принадлежности и по ним определяют степени принадлежности. Для символьных значений входных параметров степени принадлежности устанавливают субъективно, на основе бинарных сравнений. По сравнению с традиционными ТС модели со степенями принадлежности являются более информативными, точными и однозначными. Автоматизация решения сложных задач. В проводимых исследованиях особое внимание уделялось вопросам автоматизации решения задач выбора. Цель автоматизации – сделать процесс решения более простым и точным. В настоящее время автоматизация решения производственных задач осуществляется в системах автоматизированного проектирования, управления и диагностики. Наибольшим разнообразием отличаются системы автоматизированного проектирования (САПР). Практика эксплуатации САПР показала, что они относительно легко позволяют автоматизировать только хорошо формализованные виды работ типа расчетных и оформительских. Решение же остальных задач автоматизировано в небольшой степени. При функционировании САПР система выводит на экран монитора текущую справочную информацию и соответствующие меню, а принятие решений по большинству вопросов возлагается на пользователя. Работа с меню – это, по существу, аналог безмашинного выбора наиболее предпочтительного варианта из нескольких возможных. Отсюда в целом низкий уровень автоматизации проектных операций и сохранение недостатков ручного проектирования. Во многих промышленно развитых странах все более широкое применение находят интеллектуальные компьютерные системы, называемые экспертными или советующими. Основное их достоинство заключается в возможности использования для решения широкого круга вопросов, в том числе сложных неформализованных задач выбора. Однако создание экспертных систем (ЭС) посильно только коллективам высококвалифицированных специалистов, требует больших трудозатрат и денежных средств. С помощью продукционных правил, из которых формируются базы знаний ЭС, можно формализовать различные связи между входными и выходными параметрами изучаемых объектов. Аналогичными возможностями обладают и ТС, что привело к созданию программных средств, использующих совместно достоинства обоих названных формализмов: компактность и простоту ТС и полноту содержания знаний в продукционных правилах. Компьютерная система для решения задач выбора. Разработана специализированная компьютерная система для моделирования и решения задач выбора непосредственно на экране дисплея. В качестве инструмента создания моделей выбрана программа MS Excel, которая предоставляет необходимые визуальные средства работы с ячейками таблиц и встроенный язык программирования Visual Basic для реализации вычислительных алгоритмов. Программа предусматривает создание, редактирование и пользование ТС при работе в режимах «Редактирование» и «Решение». В режиме «Редактирование» оператор может с помощью простых средств управления построить на экране дисплея ТС в таком же виде, как это производится вручную. Кодировать входные и выходные параметры не обязательно, что удобно для эксперта-разработчика и для пользователя. Далее следует этап тестирования построенной модели на примерах с разными условиями моделируемой задачи. Наглядность связей между значениями входных параметров и возможными решениями обеспечивается подсветкой ячеек перечисленных величин. Оператор последовательно указывает значения входных параметров, намеченные в качестве исходных данных задачи, и при каждом таком указании осуществляется подсветка указанных значений и соответствующих им возможных решений. По мере ввода данных количество подсвеченных клеток в области отправления ТС возрастает, а количество подсвеченных ячеек решений может сокращаться или оставаться неизменным. Во втором случае оператору видно, какие решения при конкретных условиях не разделяются. Это позволяет ему оценивать адекватность построенной модели и принимать решение, следует ли ее корректировать. При работе с готовой табличной моделью в режиме «Решение» конечный пользователь только указывает значения входных параметров из условия конкретной задачи и на экране сразу видит искомое решение. Разработанная компьютерная система представляет собой оболочку для построения табличных моделей объектно-ориентированных задач выбора независимо от их тематики, не имеет принципиальных ограничений по количеству учитываемых альтернатив, входных параметров и их значений и может быть использована для решения задач в разных предметно-ориентированных областях. Сделаем следующие выводы. Большинство производственных задач относится к категории неформализованных многовариантных, трудных в решении из-за необходимости учета разнообразных факторов, неполноты и неточности исходных данных. Разработана технология решения задач класса выбора и принятия решений и программные средства для ее компьютерной реализации. Методика проста в освоении конечными пользователями, позволяет упростить решение многих сложных производственных вопросов в разных предметных областях.