Методы и алгоритмы принятия решений по выбору оборудования технических систем при нечетких целевых требованиях тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Будяков, Андрей Николаевич

• Будяков, Андрей Николаевич
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Будяков, Андрей Николаевич

Введение..........................................................................................................................4

Глава 1 Современные подходы к разработке систем поддержки принятия решений для выбора оборудования технической системы................................14

1.1 Особенности обработки информации в системах поддержки принятия решений для параметрического выбора оборудования.........................................15

1.2 Нечеткие множества и нечеткая логика как инструмент формализации требований к выбору в системах поддержки принятия решений.........................21

1.3 Анализ возможности применения нечеткого логического вывода для выбора оборудования с максимальным соответствием требованиям...............................30

1.4 Анализ методов выбора в условиях нечеткости и многокритериальности ... 39

1.5 Выводы и постановка задач исследования........................................................47

Глава 2 Обработка исходной информации для выбора на основе нечеткой логики и расчет соответствия оборудования требованиям...............................49

2.1 Структурная модель процессов обработки информации при формировании и анализе требований к выбору оборудования..........................................................49

2.2 Разработка методики описания локальных целевых информационных характеристик оборудования в терминах нечеткой логики..................................54

2.3 Разработка алгоритма вычисления соответствия типов оборудования по совокупности локальных нечетких требований.....................................................59

2.4 Пример реализации методики формализации требований к выбору оборудования на основе нечеткой логики...............................................................67

2.5 Задание соответствий требованиям на множестве альтернативных типов оборудования.............................................................................................................. 72

2.6 Выводы по второй главе.....................................................................................73

Глава 3 Разработка метода многоцелевого выбора оборудования...................75

3.1 Построение скалярной задачи выбора по критерию соответствия требованиям................................................................................................................ 75

3.2 Решение целочисленной задачи линейного программирования при выборе

оборудования..............................................................................................................82

3.3 Выводы по третьей главе....................................................................................85

Глава 4 Апробация и исследование метода выбора оборудования на численных примерах..................................................................................................86

4.1 Условия и задачи численной апробации модели выбора................................86

4.2 Проверка на адекватность логической интерпретации выбора по предложенной модели...............................................................................................87

4.3 Исследование целочисленных алгоритмов.......................................................91

4.4 Исследование параметрической чувствительности модели выбора оборудования..............................................................................................................94

4.5 Выводы по четвертой главе................................................................................99

Заключение.................................................................................................................101

Список литературы...................................................................................................103

Приложение А Акт о внедрении результатов диссертационной работы......114

Приложение Б Скриншоты электронных таблиц с основными результатами исследований..............................................................................................................115

Приложение В Свидетельство о государственной регистрации программы 116

Введение диссертации (часть автореферата) на тему «Методы и алгоритмы принятия решений по выбору оборудования технических систем при нечетких целевых требованиях»

Введение

Актуальность. Актуальной задачей синтеза технической системы является выбор такого состава системных элементов, который обеспечит возможность достижения максимальной функциональной эффективности. В частности, эта задача возникает при синтезе производственной системы, представленной совокупностью взаимодействующих элементов оборудования. Необходимо выбрать такое оборудование, которое будет наиболее адекватно производственным условиям. При этом требования к выбору формулируются в виде задания совокупности в общем случае нечетких (интервальных) значений целевых параметров потенциального оборудования, описывающих множество альтернативных вариантов. Подход, основанный на нечеткости требований, обеспечивает взаимозаменяемость альтернатив и возможность их оптимального выбора. Число характеристических параметров сложного оборудования может превышать несколько десятков, а их значения в альтернативных видах оборудования зачастую противоречивы предъявляемым требованиям. Поэтому выбор оборудования, способного в процессе выполнения производственной технологии обеспечить достижение наилучших показателей эффективности, часто оказывается сложной задачей, требующей разработки информационной автоматизированной системы поддержки принятия решений (СППР). Характерным примером технической системы является комплекс оборудования для добычи нефти и газа.

На нефтегазовых месторождениях России сложилась неблагоприятная геолого-технологическая структура нефтяных и газовых запасов, характеризующаяся сложными природными условиями в местах новых разработок, продолжительными сроками эксплуатации, высокой долей трудно извлекаемых запасов, а также разнообразием приведенных особенностей на технических объектах (скважинах, транспортных системах и т.п.). В этой связи существенную актуальность приобретают задачи выбора адекватного эксплуатационного оборудования, которое в значительной степени определяет

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

Степень разработанности темы исследования. Формализацией нечетких характеристик, их сравнительным анализом и агрегированием занимались отечественные (Балашов В.Г.; Блюмин С.Л.; Борисов А.Н.; Борисов В.В.; Леденева Т.М. и др.) и зарубежные (ChanF.T.S.; ChangP.-T.; DetynieskiM.; HajekP.; KazerooniA.; RaoP.B.; YangerR.R. и др.) ученые. Практически везде отмечается необходимость развития или адаптации известных методов для новых задач. Кроме того, результаты сравнения нескольких пар характеристик «требование -значение» из набора параметров могут оказаться противоречивыми, противоречивыми могут быть и требования к выбору, что приводит к нетривиальным задачам многокритериального выбора. Задача состоит в оптимальном удовлетворении количественной и качественной потребности производства в выбранном типе оборудования, т.е. выборе количества единиц оборудования, что влечет еще одну особенность задачи выбора -целочисленность.

Таким образом, возникает нетривиальная задача многокритериальной дискретной оптимизации, включающая нечеткие компоненты. Известны различные подходы к решению задач дискретной оптимизации, в частности, при выборе оборудования, начиная от постановок в форме задач линейного программирования (Ашманов С.А.; Финкельштейн Ю.Ю.; Хоботов О.Н.; ChanF.T.S. и др.) с применением последующих отсечений нецелочисленных решений и до применения в нелинейных случаях бионических алгоритмов, таких, например, как генетический алгоритм (Еремеев А.В.; Курейчик В.М.; BalasE.; DarrelW.; HollandD.; NiehausW. и др.). Все известные подходы основаны на

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

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

Диссертационная работа выполнена в рамках одного из основных научных направлений Воронежского государственного университета «Разработка моделей, методов и алгоритмов обработки информации для создания информационных технологий и систем нового поколения» (№ гос. регистрации 01201263910).

Объект исследования - система поддержки принятия решений при выборе альтернативных типов оборудования для совокупности производственных технических систем.

Предмет исследования - методы и алгоритмы анализа и оптимального выбора альтернативных типов оборудования для производственных технических систем.

Цель исследования заключается в достижении максимальной эффективности технических систем путем разработки алгоритмов сравнительного анализа альтернативных вариантов оборудования на основе обработки информации его характеристических параметров и предъявляемых нечетких требованиях, а также разработке и исследовании методов оптимального выбора и распределения оборудования по совокупности технических систем.

Для достижения поставленной цели решались следующие задачи исследования:

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

2. Разработка методики математической формализации нечетких требований к выбору оборудования и оценки агрегированного по параметрам соответствия типов альтернативного оборудования предъявляемым требованиям на основе экспертизы характеристических параметров оборудования в терминах нечетких высказываний.

3. Разработка алгоритма расчета агрегированного соответствия оборудования по совокупности локальных соответствий характеристических и целевых параметров.

4. Разработка постановки задачи и метода оптимального выбора оборудования с максимальным соответствием техническим требованиям производственной системы и удовлетворяющим коммерческим требованиям его приобретения.

5. Численная апробация и анализ предложенных моделей и алгоритмов на примерах выбора оборудования для производственных технических систем нефтегазовой отрасли.

Научная новизна. В диссертационной работе получены следующие результаты, характеризующиеся научной новизной:

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

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

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

Тематика исследований соответствует паспорту специальности 05.13.01 по разделам: п. 2 «Формализация и постановка задач системного анализа, оптимизации, управления, принятия решений и обработки информации»; п. 4 «Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации»; п.9 Разработка проблемно-ориентированных систем управления, принятия решений и оптимизации технических объектов; п. 13. «Методы получения, анализа и обработки экспертной информации».

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

Практическая значимость исследования заключается в разработке методического и математического обеспечения СППР для повышения эффективности функционирования производственных технических систем за счет информационной поддержки принятия решений при выборе и распределении

оборудования по совокупности этих систем. Результаты работы использованы ПАО «Газпром нефть» при разработке автоматизированных систем снабжения на базе программного обеспечения SAP ERP в рамках проекта «Разработка системы подбора аналогов для замены материалов», что подтверждается соответствующим актом (Приложение А).

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

Предложения, выносимые на защиту:

1. Методика математической формализации требований к выбору оборудования, в виде конъюнктивной формы нечетких логических высказываний о целевых параметрах оборудования, обеспечивающая описание желаемого состояния элементов технической системы.

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

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

Степень достоверности и апробация результатов. Достоверность результатов диссертационной работы основана на корректном использовании апробированного математического аппарата и подтверждении полученных теоретических положений вычислительным (компьютерным) экспериментом.

Научные положения, теоретические и практические результаты диссертационной работы докладывались и обсуждались на XXVI Международной научно-технической конференции «Современные технологии в задачах управления, автоматики и обработки информации» (14-17 сентября 2017, 14-20 сентября 2018, г. Алушта); XVIII Международной научно-практической конференции «Информатика: проблемы, методология, технология» (7-8 февраля 2018, г. Воронеж); XII Всероссийской научно-технической конференции «Актуальные проблемы развития нефтегазового комплекса России» (12-14 февраля 2018, г. Москва) и докладов на международных форумах компании SAP (Москва, 2010-2018 гг.), а также на научных семинарах факультета компьютерных наук Воронежского государственного университета.

Публикации. Основные результаты работы опубликованы в 12 научных работах, в том числе 4 работы - в изданиях, рекомендованных ВАК Минобрнауки РФ. В работах, опубликованных в соавторстве, лично соискателю принадлежит: [20,30,33] - разработка структуры информационных процессов между базой данных, НСИ, СППР в рамках единого информационного пространства системы; [18-19,29] - постановка задачи «обезличенного» выбора оборудования; идея совмещения процессов выбора и распределения оборудования в рамках модернизации транспортной задачи и проведение численного эксперимента; [31,34] - формирование базы данных технических и коммерческих параметров оборудования и методика параметрического анализа оборудования; [32] -методика «обезличенного» формирования технических и коммерческих требований; [16-17] - методика формирования нечетких требований и алгоритм оценки соответствий.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и трех приложений. Список использованной литературы содержит 105 наименований. Основная часть работы изложена на 116 страницах машинописного текста, включая 34 рисунка и 8 таблиц.

Во введении обоснована актуальность темы диссертационной работы, сформулирована цель и задачи исследования, определены научная новизна и практическая значимость результатов работы.

В первой главе диссертации «Современные подходы к разработке СППР для выбора оборудования технической системы» уточняется понятие технической системы и анализируются особенности обработки информации в СППР для параметрического выбора оборудования. Формулируются и анализируются требования к выбору оборудования. Исследуется возможность использования нечетких логических высказываний для формулировки требований, а также возможность использования инструментария нечеткого логического вывода для выбора оборудования. Показаны основные проблемы, препятствующие применению нечеткого логического вывода для решения задачи выбора оборудования в условиях нечетких требований. Обосновывается целесообразность использования для выбора критериальных методов. Отмечаются такие особенности задачи выбора как многокритериальность и дискретность результатов выбора и анализируются возможные подходы к решению задачи выбора с учетом указанных особенностей.

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

Во второй главе «Обработка исходной информации для выбора на основе нечеткой логики и расчет соответствия оборудования требованиям» представлена методика математической формализации нечетких требований к выбору оборудования и оценки агрегированного по параметрам соответствия типов альтернативного оборудования предъявляемым требованиям на основе экспертизы характеристических параметров оборудования в терминах нечетких высказываний. Приводится структурная модель процессов обработки информации при формировании и анализе требований к выбору оборудования в составе информационной системы управления предприятием, определившая состав и взаимодействие задач обработки информации в составе системы поддержки принятия решений. Предложена методика описания целевых

информационных характеристик оборудования в терминах нечеткой логики, обеспечивающая возможность формирования множества альтернативных типов однородного оборудования, применение оптимального выбора на этом множестве, а также более детальное с информационной точки зрения описание целевых параметров оборудования. Предложен способ вычисления локального соответствия типов однородного оборудования предъявляемым техническим и коммерческим требованиям на основе вычисления функций принадлежности локальных целевых характеристик. Разработан алгоритм вычисления агрегированного соответствия типа альтернативного оборудования параметрически заданным требованиям на основе вычисления многомерных функций принадлежности для классов «важных» и «не важных» параметров. Приводится численный пример реализации методики формализации требований к выбору оборудования.

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

Четвертая глава «Апробация и исследование метода выбора оборудования на численных примерах» описывает численный эксперимент по выбору и

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

В заключении излагаются основные результаты диссертации.

В приложениях приведены скриншоты электронных таблиц Excel с основными результатами исследований метода выбора оборудования; свидетельство о регистрации разработанных программ; акт о внедрении результатов диссертации.

Глава 1 Современные подходы к разработке систем поддержки принятия решений для выбора оборудования технической системы

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

Рассматривая любую индустриальную производственную систему, следует различать в ее составе техническую и технологическую подсистемы. Техническая подсистема - искусственно созданная система, предназначенная для удовлетворения определенной потребности, существующая: 1) как изделие производства, 2) как устройство, потенциально готовое совершить полезный эффект, 3) как процесс взаимодействия с компонентами окружающей среды, в результате которого образуется полезный эффект [36-37]. К техническим системам относятся отдельные машины, аппараты, приборы, сооружения, их элементы в виде узлов, блоков, агрегатов и др. В этом смысле производственное оборудование следует рассматривать как компоненты технической системы.

Основные источники знаний и информации о технической подсистеме -конструкторская документация и эксперты, способные устанавливать соответствие характеристик элементов технической подсистемы необходимым режимам технологического процесса производства. Совокупность свойств, знания которых, по мнению разработчиков систем, необходимы для решения задач управления технологическим процессом, содержится в инструкциях по эксплуатации. В них приведены сведения о конструкции, принципе действия, характеристиках (свойствах) системы, ее составных частях.

Технология - это процесс производства продукции, реализуемый технической подсистемой [1, 63]. Таким образом, техническую подсистему производственной системы следует рассматривать как инструмент реализации ее технологической составляющей.

1.1 Особенности обработки информации в системах поддержки принятия решений для параметрического выбора оборудования

Для анализа особенностей обработки информации в СППР рассмотрим основные процедуры принятия решений, которые можно отобразить в виде схемы, показанной на рисунке 1.1.

Синтез множества альтернатив Анализ информационных характеристик альтернатив Выбор одной или нескольких альтернатив

Рисунок 1.1 - Схема основных процедур принятия решений

Рисунок 1.1 показывает, что система поддержки принятия решений требует большого количества специфической информации и информационных технологий для ее обработки. Действительно, множество альтернатив представляет собой информационный объект, который может быть выделен как класс эквивалентности или толерантности из некоторого более широкого информационного множества. Альтернативы могут быть представлены своими информационными характеристиками, на основе которых можно формировать критерии выбора альтернатив с желаемыми свойствами. Наконец собственно выбор представляет собой некоторую информационную технологию, иногда достаточно сложную.

При формализации выбора типа оборудования, реализующего конкретную стадию технологии, множество альтернатив представляет собой допустимые (взаимозаменяемые) типы оборудования, выпускаемые промышленностью, с полным перечнем своих информационных характеристик. Множество альтернативных вариантов оборудования будем называть однородным оборудованием одинакового функционального назначения, элементы которого различаются значениями своих информационных характеристик, например, мощностью двигателя, геометрическими размерами, производителем, ценой и т.п. Типы однородного оборудования взаимозаменяемы с той или иной степенью соответствия предъявляемым требованиям. Информационные характеристики

оборудования могут быть представлены либо в виде числовых значений его параметров, либо в виде наименований (буквенный или числовой код).

Современный подход при проектировании сложных технических объектов не предполагает при формулировке требований к выбору однородного оборудования указания его конкретных типов, обеспечивающих функционирования объекта [32]. Вместо этого в проекте указывается наиболее полный перечень требуемых характеристик обезличенного оборудования в виде набора целевых значений технических параметров. При этом целевые значения задаются допустимым множеством значений допустимые интервалы мощности двигателя; допустимые интервалы размеров, допустимые интервалы производительности и т.п. Такой подход при выборе оборудования принято называть параметрическим выбором [105]. Параметрическое описание требований, с одной стороны расширяет возможности выбора, с другой стороны обеспечивает высокую степень детализации требований, что в свою очередь позволяет выбирать, в рамках имеющихся возможностей, наиболее эффективное оборудование, повышать производительность производственных объектов. Следует заметить, что параметрическое описание предъявляет повышенные требования к решению задачи выбора.

Анализ информационных характеристик необходимо проводить по тем или иным критериям. В данном случае критерии должны задаваться требованиями, предъявляемыми к оборудованию не только производственными условиями, но и коммерческими условиями рынка. Технические требования к информационным характеристикам оборудования формируются в процессе проектной разработки для нового месторождения или проектной корректировки при изменении условий функционирования действующего месторождения. Подготовку технических требований осуществляют проектировщики технологических процессов [16].

Коммерческие требования задаются исходя из сложившейся конъюнктуры рынка. Целевые значения параметрических характеристик также, как и для технических требований, задаются числовыми интервалами или качественным описанием. Параметрами коммерческих требований выступают: допустимый

Список литературы диссертационного исследования кандидат наук Будяков, Андрей Николаевич, 2018 год

х - -

с - Ь с - Ь

, при х е [с;Ь].

(2.12)

Блок-схема алгоритма вычисления локальных и агрегированных соответствий типов альтернативного оборудования предъявляемым нечетким требованиям показана на рисунке 2.8.

Расчет агрегированного соответствия будет производится по правилу, структурно идентичному модели Сугено [11, 12], но с нелинейной функцией принадлежности заключения.

Правило имеет следующий вид:

ЕСЛИ " Р1 есть х1 л Р2 есть х2 л ... л Рп есть хп" ТО " У" (2 13)

где У = {^Тг- (х)}; JUj - значения функций принадлежности (2.12) локальных

требований, построенных с учетом выделения «важных» и «не важных» параметров в соответствии с рисунком 2.7.

Рисунок 2.8 - Блок-схема алгоритма вычисления локальных и агрегированных соответствий альтернативных типов оборудования предъявляемым требованиям

2.4 Пример реализации методики формализации требований к выбору оборудования на основе нечеткой логики

В разделах 2.2 и 2.3 были описаны информационные процессы формализации требований к выбору оборудования, приведенных в структурной модели информационных процессов СППР (рисунок 2.2) как компоненты с номерами от 1 до п + 2. Следующий компонент - занесение формализованных требований в шаблонную форму, рассмотрим на примере описания требований к центробежному насосу.

В качестве шаблонной формы представления требований на многих предприятиях используется так называемый опросный лист. Поступление в СППР заявок от группы производственных процессов (например, от нескольких месторождений) сопровождается для каждого однородного оборудования опросным листом, куда заносятся желаемые нечеткие значения характеристических параметров оборудования, то есть нечеткие технические требования релевантные конкретным условиям производственного процесса.

В упрощенном виде опросный лист можно представить таблицей значений характеристических параметров. Например, такая таблица для различных вариантов центробежных насосов типа НД будет иметь вид, показанный в таблице 2.1.

Таблица 2.1 - Упрощенное представление опросного листа технической

политики для центробежных насосов

Тип насоса Расход, м3/ч Напор, м Частота вращения, об/мин Мощность эл. двиг., КВт Масса, кг

НД 420 - 630 30 - 90 1000 - 1500 55 - 315 1750 - 2760

Как видно, таблица 2.1 включает как точечное качественное значение (НД), так и количественные интервальные значения допустимых характеристик насосов. На основании таблицы 2.1 можно делать выбор оборудования по правилу

«если значения характеристик оборудования попадают в допустимые интервалы, то оборудование можно закупать» (2.14)

Словесная форма (2.12) описания правила не позволяет осуществить на его основе автоматический выбор, более того, такой выбор не обеспечивает оптимальную степень соответствия техническим требованиям. Задавая диапазоны допустимых значений характеристик, существующий опросный лист не указывает, как распределяется степень соответствия этих значений внутри диапазона для конкретного технологического объекта с его особенностями. Эта информация плохо формализуется, но очевидно, что она важна для выбора. Сегодня носителем такой информации может являться только человек, который использует ее при выборе в меру своей квалификации.

Как уже отмечалось, формализацию информации о степени соответствия значений характеристик оборудования особенностям технологического объекта предлагается задавать в форме функций принадлежности нечетких логических высказываний [14].

Для преобразования опросного листа в форму нечетких логических высказываний будем рассматривать верхнюю строку таблицы 2.1 как перечень имен соответствующих лингвистических переменных - Р^пеес. Такая интерпретация оправдана тем, что термы этих лингвистических переменных (нижняя строка таблицы 2.1) заданы интервальными значениями. Таким образом, для перехода к нечетким высказываниям достаточно задать на этих интервалах функции принадлежности.

Рассмотрим примеры линейных функций принадлежности для характеристик центробежного насоса из таблицы 2.1.

Пусть информация по расходной характеристике насоса (второй столбец таблицы 2.1) для конкретного технологического объекта формулируется в виде нечеткого высказывания: «допустимый диапазон расхода лежит в промежутке 500-630м /ч, при этом нижняя граница хотя и допустима, но нежелательна; чем выше расход, тем больше соответствие насоса производственному объекту».

Другими словами, для рассматриваемого производственного объекта промежуток от 420 до 500 м /ч не подходит, более высокий расход допустим, при этом чем больше расход, тем лучше соответствие условиям объекта в пределах диапазона, заданного в таблице 2.1. Расход в этом высказывании является нечеткой величиной, заданной на множестве значений х е [500,630] с помощью лингвистических термов, например, таких как «высокий», «средний», «низкий». Принадлежность каждого значения этого промежутка, например терму «высокий расход», задается функцией принадлежности ¡и(х) е [0,1], показанной в таблице 2.2, во втором столбце. В таблице 2.2 показаны функции принадлежности и для остальных характеристик центробежного насоса. При этом функции принадлежности могут вырождаться в точку, как показано в первом и четвертом столбце таблицы 2.2. Это означает, что соответствующие характеристики имеют единственное допустимое значение. Например, тип насоса допустим только НД; частота вращения - только 1500 об/мин. В последней строке таблицы 2.2 показаны обозначения соответствующих нечетких высказываний.

Таблица 2.2 - Упрощенное представление опросного листа технической политики для центробежных насосов с привязкой к конкретному

производственному объекту

Тип насоса

Расход,

3/ м /ч

Напор, м

Частота вращения, об/мин

Мощность эл. двиг., КВт

Масса, кг

НД

420 - 630

30 - 90

1000 - 1500

55 - 315

1750 - 2760

А

В

С

Б

Е

Б

Теперь выбирая оборудование можно рассчитать степень соответствия его локальных характеристик требованиям производственного объекта. Например, рассмотрим характеристики насоса 8НДв-НМа, который присутствует на рынке

оборудования и может рассматриваться как альтернативное оборудования для выбора. Характеристики этого насоса заданы в размерности, указанной в таблице 2.1, следующим образом: тип - НД; расход - 550; напор - 82; частота вращения -1500; мощность - 250; масса - 2400. Подставляя эти значения в соответствующие функции принадлежности можно рассчитать соответствие насоса 8НДв-НМа техническим требованиям конкретного производственного объекта. Например, для лингвистической переменной «напор» функция принадлежности (см. таблицу 2.2) описывается на отрезке значений аргумента [70; 90] выражением ц( х) = 0,05 х - 3,5. Подставляя в это выражение значение напора насоса 8НДв-НМа - 82, получим значение функции принадлежности - 0,6. Это значение принимаем в качестве локальной степени соответствия указанного насоса техническим требованиям производственного объекта. Значения локальных соответствий показаны в нижней строке таблицы 2.3.

Таблица 2.3 - Степень соответствия отдельных характеристик насоса требованиям конкретного технологического объекта

Тип насоса

Расход, м3/ч

Напор, м

Частота вращения, об/мин

Мощность эл. двиг., КВт

Масса, кг

НД

420 - 630

30 - 90

1000 - 1500

55 - 315

1750 - 2760

НД М( х) = 1

550

м( х) = 0,7

82

ц( х) = 0,6

1500

м( х) = 1

250

х) = 0,3

2400

ц( х) = 0,5

Таким образом, модифицированная форма опросного листа содержит все значения локальных соответствий заданным техническим требованиям.

Теперь можно рассчитать агрегированное соответствие насоса 8НДв-НМа техническим требованиям, заданным таблицей 2.2. Если таблица 2.3 содержит только важные параметры, то на основании выражения (2.3) агрегированное соответствие будет равно 0,3. Аналогично определяется степень соответствия

коммерческим требованиям. Коммерческие требования задаются сотрудниками централизованной закупочной организации, в основном, из рациональности расходования финансовых средств и соблюдения условий поставки оборудования. Допустим, что коммерческие требования состоят из нечетких описаний двух характеристических параметров рынка оборудования: желаемой цены и желаемых сроков поставки оборудования на производственный процесс: РКом = Рц и

Р

= Р„

2 " ср

Пусть желаемые значения этих параметров (коммерческие требования) заданы следующими выражениями:

Рц е [100; 200] тыс. руб., Рр е [10; 20] дней с момента заказа

Функции принадлежности на заданных интервалах определены экспертом в виде, показанном на рисунках 2.9 а) и 2.9 б).

100 200 10 13 20 х2

Рисунок 2.9 - Функции принадлежности локальных требований по цене (а) и локальных требований по срокам поставки (б) Для насоса 8НДв-НМа изготовитель (поставщик) определил цену 150 тыс. руб. и срок поставки 15 дней. По аналогии с вычислением локального и агрегированного соответствия техническим требованиям, можно вычислить локальные и агрегированные соответствия коммерческим требованиям. Нетрудно посчитать, что цРц (150) = 0,5 и ¡лРср (15) = 0,7 .

Агрегированное соответствие коммерческим требованиям вычисляется на основе выражения (2.13) и составляет 0,5. В данном случае параметры не разделялись на «важные» и «не важные».

2.5 Задание соответствий требованиям на множестве альтернативных типов

оборудования

Пусть рынок оборудования может предъявить для выбора некоторое количество типов однородного оборудования. Рассмотрим множество альтернативных типов оборудования в виде множества номеров 3 = {у'}, каждому типу соответствует свой номер ' е (1,2,... , т).

Сначала рассмотрим, как задается соответствие техническим требованиям. Технические требования формируются для каждого производственного процесса индивидуально. Пусть в системе поддержки принятия решений имеются заявки на выбор оборудования от й производственных процессов (месторождений). Каждому месторождению поставим в соответствие номер к е (1,2,... , й). Тогда можно рассматривать степень соответствия ' -го типа однородного оборудования к -му производственному процессу. Такое соответствие можно представить матрицей

...

(Л к)

(2.15)

т1 Iтй)

В выражении (2.13) ^^ - означает степень агрегированного соответствия ' -

го типа однородного оборудования к -му производственному процессу, которое вычисляется по методике, определенной в разделах 2.3 и 2.4. Смена обозначения функции принадлежности (^ вместо ¡и ) произведена для различия соответствия техническим и коммерческим требованиям.

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

поставщиками. Каждому предприятию-поставщику поставим в соответствие номер I е {1,2,... , п}. Тогда можно рассматривать степень соответствия ' -го типа однородного оборудования I -му предприятию-поставщику. Такое соответствие можно представить матрицей

(Мц) =

'Ми ... МтЛ

\Мп1 ...

(2.16)

где ц.. - означает степень агрегированного соответствия у -го типа

однородного оборудования I -му предприятию-поставщику, которое вычисляется по методике, определенной в разделах 2.3 и 2.4.

Матрицы (2.15) и (2.16) определяют необходимые соответствия между оборудованием, техническими и коммерческими требованиями. На основе информации, содержащейся в этих матрицах можно строить модель оптимального выбора однородного оборудования.

2.6 Выводы по второй главе

Результаты, полученные в главе 2, позволяют сформулировать следующие выводы:

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

2. Предложена методика описания целевых информационных характеристик оборудования в терминах нечеткой логики. Такой подход обеспечил возможность формирования множества альтернативных типов однородного оборудования, применение оптимального выбора на этом множестве, а также более детальное с информационной точки зрения описание целевых параметров оборудования.

3. В результате анализа операций нечеткой логики предложен способ вычисления локального соответствия типов однородного оборудования предъявляемым техническим и коммерческим требованиям на основе вычисления функций принадлежности локальных целевых характеристик.

4. Разработан алгоритм вычисления агрегированного соответствия типа альтернативного оборудования параметрически заданным требованиям на основе вычисления многомерных функций принадлежности для классов «важных» и «не важных» параметров. Этот алгоритм позволил преобразовать исходную нечеткую информацию к четким значениям соответствий, что позволит далее рассматривать детерминированные модели оптимального выбора.

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

Глава 3 Разработка метода многоцелевого выбора оборудования

3.1 Построение скалярной задачи выбора по критерию соответствия

требованиям

В главе 2 был разработан алгоритм вычисления агрегированного соответствия типа альтернативного оборудования параметрическим требованиям. Агрегированные соответствия предложено отображать в виде двух матриц соответствий (2.15) и (2.16). Элементы этих матриц можно рассматривать как весовые характеристики ребер двудольного графа (рисунок 1.14), т.е. как параметры су в критерии (1.23) классической постановки транспортной задачи,

так как они характеризуют эффективность назначения оборудования соответствующим требованиям. Это означает, что по каждому из двух видов требований (технические и коммерческие) можно формулировать модель выбора, аналогичную (1.23-1.27) и обеспечивающую максимальное соответствие выбранного типа оборудования требованиям.

Для построения модели выбора по техническим требованиям обозначим множество альтернативных типов однородного (взаимозаменяемого) оборудования I = {у}, у = 1,..., т - тип однородного оборудования. При этом будем считать, что каждому у -му типу оборудования ставится в соответствие его количество г у е {0; X+}, определяемое предложениями из потенциальных

источников - поставщиков. Будем рассматривать К производственных процессов с уникальными именами к = 1,..., й, подающих заявки на оборудования и формирующих к -е технические требования. Все производственные процессы к е К, должны получить оборудование из I в количестве г у; при этом каждому

сочетанию имен ук е I х К присваивается значение 77^ук е [0,1] - значение совокупного соответствия у -го типа оборудования к -му техническому требованию. Будем считать, что каждый к -ый производственный процесс

формирует свой столбец матрицы (л^), анализируя соответствие к -ых технических требований и характеристик типов оборудования у = 1,2,...,т. Соответствие характеристик типов оборудования и технических требований производственных процессов можно отобразить двудольным графом, показанным на рисунке 3.1.

Количество ] -го типа оборудования назначенного к -му производственному процессу обозначим у ]к., имея ввиду, что потребность производственного

процесса может быть обеспечена различными взаимозаменяемыми типами однородного оборудования.

Рисунок 3.1 - Двудольный граф, задающий соответствие между типами ресурсов

и техническими требованиями заказчиков.

Потребное количество оборудования к -му производственному процессу обозначим ук.

В качестве критерия выбора по соответствию техническим требованиям будем рассматривать средневзвешенное значение соответствия, как функцию от переменных у ^ [41]:

т <1

ЕЕ^кУук ]=1 к=1

т<

Е Е уд

}=1к=1 (3.1)

Такой критерий нельзя рассматривать как линейный относительно переменных у к . Однако, следует иметь в виду, что сумма в знаменателе есть

постоянная величина, равная ^ Ук . В таком случае задача остается в классе задач

к=1

линейного программирования. Естественно потребовать максимизации критерия соответствия.

Окончательно модель выбора по техническим требованиям имеет вид:

1

d т

У'" >тах;

к=1

к=1 ]=1

X У]к ]=1

к — 1,..., d;

X У]к= г], у= 1,..., т;

к=1

d т

X ук = Х о;

к=1

У=1

(3.2)

(3.3)

(3.4)

(3.5)

(3.6)

у к е {0; г + } ; 1 = 1,..., п.

Здесь г}к - параметр, характеризующий степень соответствия назначения у

-го типа оборудования к -му требованию; г+ - множество целых положительных чисел.

Критерий (3.2) интерпретируется как требование назначения на объекты предприятий как можно большего количества ресурсов с высокой степенью технического соответствия. Ограничение (3.3) означает, что каждое к -е предприятие должно получить оборудования в требуемом количестве ук. Ограничение (3.4) означает, что количество оборудования у -го типа будет полностью распределено по предприятиям. Ограничение (3.5) означает, что все типы оборудования в полном количестве должны быть распределены по производственным процессам. В этом случае модель выбора будет сбалансированной. Выполнение ограничений (3.4) и (3.5) обеспечивается при необходимости введением фиктивных производственных процессов.

к

V

к

Результатом выбора является назначение количества единиц однородного оборудования ] -го типа к -му производственному процессу таким образом, чтобы типы оборудования максимально соответствовали техническим требованиям и удовлетворяли количественной потребности.

Введем необходимые обозначения для задачи выбора оборудования по коммерческим требованиям. Обозначим множество источников поставки оборудования I с уникальными именами г = 1,..., п, для каждого из которых заданы г -е коммерческие требования. Каждый источник г е I, может поставлять оборудование из ] ; при этом каждому сочетанию имен ц е I х ] присваивается значение ¡лц е [0,1] - значение совокупного соответствия Ц -го типа оборудования г

-му коммерческому требованию. Соответствие характеристик типов оборудования и технических требований производственных процессов можно отобразить двудольным графом, показанным на рисунке 3.2.

Рисунок 3.2 - Двудольный граф, задающий соответствие между типами ресурсов

и коммерческими требованиями Количество Ц -го типа оборудования назначенного г -му коммерческому требованиюобозначим хц, имея ввиду, что г -ый источник может обеспечить

несколько взаимозаменяемых типов однородного оборудования.

Количество оборудования разных типов, которое может обеспечить -ый источник обозначим аг. Количество оборудования Ц -го типа во всех источниках

обозначим Ь;.

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

у

>=1у=1

п т

ЕЕ хи

I=1 у=1

(3.7)

Функция (3.7) так же как и для критерия технического соответствия, легко приводится к линейному виду с учетом того, что знаменатель (3.7) представляет

п

собой такую же константу, что и в (3.1) - ^ а1 .

I=1

Окончательно модель выбора по коммерческим требованиям формируется аналогично модели выбора по техническим требованиям и имеет следующий вид:

1

и х'7 >тах;

Xа «

1=1

1=1 ]=1

X ху= а1, 1 = п;

у=1

п

X хч= гу, у= 1'-'т;

г=1

п т

X а1 = Х г1;

1=1 у =1

хи е {0; г + }; 1 = 1,..., п, у = 1,..., п.

(3.8)

(3.9)

(3.10)

(3.11)

(3.12)

Здесь - параметр, характеризующий степень соответствия назначения у ■ го типа оборудования -му источнику.

Критерий (3.8) интерпретируется как требование закупать как можно больше ресурсов с максимальной степенью соответствия коммерческим требованиям. Ограничение (3.9) означает, что каждый г -ый источник должен поставить все имеющееся у него оборудование. Ограничение (3.10) означает, что каждый ц -ый тип оборудования будет полностью распределен по производственным процессам. Ограничение (3.11) означает, что все типы оборудования в полном количестве должны быть распределены по производственным процессам. В этом случае модель выбора будет сбалансированной. Выполнение ограничений при необходимости обеспечивается введением фиктивных поставщиков.

Результатом выбора является назначение количества единиц однородного оборудования Ц -го типа г -му источнику таким образом, чтобы типы оборудования максимально соответствовали коммерческим требованиям и удовлетворяли количественной потребности.

Критерии (3.2) и (3.8) могут вступать в противоречие по неопределенной переменной Гц, значение которой зависит от искомых переменных Хц и у ^ .

Другими словами, удовлетворяя отдельно технологическим и коммерческим требованиям, будут получены разные значения Гц, т.е. приобретаться и

распределяться будет разное количество ресурсов. Такой вывод подтверждается результатами численных экспериментов, проведенных в главе 4. Очевидно, что такое решение не может устраивать.

Выходом из положения является сведение многоцелевой (векторной) задачи к одноцелевой (скалярной). Поскольку все функции критериев и ограничений являются линейными [35, 66], можно воспользоваться аддитивной сверткой критериев (3.2) и (3.8) в форме выпуклой линейной комбинации критериев (3.2) и (3.8). В частном случае, значения весовых коэффициентов свертки Я и (1 -Л), Л е [0;1]могут быть равны, если допустить коммерческие и технические требования равнозначными. В зависимости от вида приобретаемых ресурсов равнозначность требований может не соблюдаться. В этом случае весовой

коэффициент Л е [0; 1], позволяет задавать доминирование одного из требований.

Кроме того, поскольку величина Гц определяется в процессе решения и заранее не

известна, необходимы условия сопряжения двух задач назначения. Сопряжение обеспечивается требованием равенства приобретаемых и распределяемых ресурсов:

Е х1] У]к; У/

I к . (3.13)

Теперь структуру выбора можно представить трехдольным графом (рисунок

3.3).

Рисунок 3.3 - Трехдольный граф, задающий соответствия между предложением и требованиями (техническими и коммерческими) к ресурсам Будем считать, что каждый поставщик I предлагает один тип ресурса Ц е ] в количестве а{ с уникальными значениями коммерческих и технических характеристик.

Установление рационального соответствия между тремя множествами: ресурсами, поставщиками и заказчиками сводится к выбору значений переменных Хц и у к таким образом, чтобы заказчики получили ресурсы с максимальным

соответствием их техническим требованиям, а поставщики поставили эти ресурсы с минимальными отклонениями от коммерческих требований, сформулированных закупщиком.

Окончательно модель выглядит следующим образом [18]:

ЕЕ+ (1 -ЕЕ^]кУ]к ^тах

Е а I

Е

к / к

х, у

X;;

Е У]к = ук; ^ } •

Е X/= а; ; •

Ех/ =Е у к; V;

/ к • ?

; у/к е {0; г + }; X/ > 0; у/к > 0; V/, к

(3.14)

(3.15)

(3.16)

(3.17)

(3.18)

Модель (3.14-3.18) позволяет выбирать оборудование таким образом, чтобы одновременно в максимальной степени удовлетворять как техническим, так и коммерческим требованиям.

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

Как отмечалось в главе 1, раздел 1.4, в случае линейности задачи математического программирования для получения целочисленных решений следует использовать методы отсечения, например, такие как метод Гомори или метод ветвей и границ.

3.2 Решение целочисленной задачи линейного программирования при

выборе оборудования

Рассмотрим решение задачи (3.14 - 3.18) с позиций метода ветвей и границ

[38].

В соответствии с этим методом сначала должно быть получено решение (3.14-3.18) без учета целочисленности, т.е. обычным симплекс-методом [23, 97]. Если обычный подход приводит к целочисленным решениям, то целочисленная задача линейного программирования считается решенной. Если полученные решения дробные, то далее применяется собственно метод ветвей и границ.

Рассмотрим алгоритм метода ветвей и границ применительно к нашей задаче выбора оборудования (3.14-3.18). Метод ветвей и границ относится к комбинаторным алгоритмам [77].

Допустим, что на первом шаге мы получили дробное решение (хотя бы одно) в виде дробных значений переменных Хц; у^, V/, Ц, к .

Обозначим искомые переменные в виде вектора г и выделим дробные компоненты этого вектора - г1. Тогда интервал

[ г,-] < < [ ] +1,

где [ ] - означает целую часть числа г,, не содержит допустимых решений с целочисленной координатой г,.

Следовательно, допустимое целое значение г, должно удовлетворять неравенствам

г, < [ г, ] или г1 > [ г1 ] +1.

Для граничных значений г, < [ г, ], г, > [ г, ] +1 вычисляются значения критериальной функции (3.14).

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

(3.14).

По выбранной ветви решается обычная задача линейного программирования. Если полученный ответ удовлетворяет условию целочисленности, то задача решена. В противном случае добавляются новые ограничения, обладающие следующими свойствами:

- они должны быть линейными;

- они должны отсекать найденный оптимальный нецелочисленный план;

- они не должно отсекать ни одного целочисленного плана.

Такие ограничения называются правильными отсечениями.

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

Задача 1

Задача 4 Задача 5 Задача б зада ш /

Рисунок 3.4 - Графическая интерпретация метода ветвей и границ Геометрический смысл добавления каждого нового линейного ограничения состоит в проведении дополнительной прямой (гиперплоскости), которая отсекает от многоугольника (многогранника) допустимых решений его часть вместе с оптимальной точкой с нецелыми координатами. В отсекаемую часть не должна попасть ни одна точка с целыми координатами. В результате новый многогранник решений содержит все точки с целыми координатами, содержавшиеся в первоначальном многограннике решений. Следовательно, полученное при этом многограннике оптимальное решение будет целочисленным.

Суть алгоритма метода Гомори состоит в следующем: симплекс-методом решается задача линейного программирования без учета требования целочисленности; если полученное оптимальное решение не целочисленно, среди дробных чисел решения выбирается элемент с наибольшей дробной частью и составляется дополнительное ограничение; полученная новая задача решается двойственным симплекс-методом; перечисленные действия повторяются до получения целочисленного результата.

3.3 Выводы по третьей главе

Результаты, полученные в главе 3, позволяют сформулировать следующие выводы:

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

2. Поскольку модификация транспортной задачи остается в классе задач линейного программирования, для получения целочисленного решения следует использовать метод ветвей и границ или метод Гомори.

3. Для выбора метода получения целочисленного решения целесообразно провести исследование характеристик метода ветвей и границ и метода Гомори на численных примерах.

Глава 4 Апробация и исследование метода выбора оборудования на

численных примерах

4.1 Условия и задачи численной апробации модели выбора

Целью численной апробации модели выбора и распределения оборудования является проверка ее работоспособности, а также выявление ряда свойств, которые необходимо учитывать при практическом применении этой модели. Рассматриваемая численная апробация не затрагивает проблемы оценки локального и агрегированного соответствия оборудования, предъявляемым требованиям. Эти проблемы и численная апробация оценки соответствия были рассмотрены в главе 2. В этой главе будем считать, что матрицы: г/ .к

соответствий / -х типов оборудования к -м техническим требованиям и

соответствий / -х типов оборудования / -м коммерческим требованиям, уже получены в соответствии с алгоритмами, описанными в разделе 2.3.

Использование для численной апробации промышленных статистических данных, например, нефтегазовой компании, затруднено как соображениями корпоративной конфиденциальности, так и громоздкостью соответствующих информационных структур. Поэтому в разделах 4.2. и 4.3 для численной апробации были использованы упрощенные исходные данные, которые, однако, не препятствуют общности результатов исследования. В разделе 4.4 для проведения численного исследования были использованы данные, заимствованные в справочной литературе и веб-сайтах производителей нефтегазового оборудования [63, 65, 102,103].

В результате исследования планируется:

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

2. Проанализировать, с точки зрения трудозатрат машинной реализации, основные методы получения целочисленных решений.

3. Исследовать характер изменения результирующих соответствий при изменении соотношения предпочтений между техническими и коммерческими требованиями.

4.2 Проверка на адекватность логической интерпретации выбора по

предложенной модели

Для проведения численной апробации сформируем необходимые исходные данные и построим модель выбора как это показано в работе [19].

Будем считать, что три производственных предприятия, являющиеся структурными единицами крупной компании, подготовили в закупочную организацию компании свои индивидуальные заявки на некоторое однородное оборудование, например, насосы. Насосы выпускаются в виде трех взаимозаменяемых типов. В заявках указано распределение соответствий типов насоса техническим требованиям данного предприятия. На основе полученных заявок можно сформировать матрицу ^ , которая показана в таблице 4.1. Там

же приводится информация о количественных потребностях в данном виде оборудования.

Таблица 4.1 - Техническое соответствие ^^ типов насосов производственным

процессам предприятий

Заказчик 1 Заказчик 2 Заказчик 3

Тип насоса, 1 =1 1 1 0,8

Тип насоса, 1 =2 0,9 0,8 1

Тип насос, 1 =3 0,7 0,9 1

Количество в заказе 5 7 3

Допустим, что насосы указанных типов выпускают и продают два завода. Предложения этих заводов по количеству поставки и соответствие коммерческим

требованиям

Ми

показаны в таблице 4.2. Таблица 4.2 - Соответствие ¡иу предложений заводов и коммерческих

требований

Предложение заводов Коммерческие требования закупщика

Кол-во Завод /тип Тип насоса 1 Тип насоса 2 Тип насоса 3

поставки насоса

3 1/1 1 0 0

10 1/2 0 1 0

8 1/3 0 0 0,9

5 2/1 0,9 0 0

4 2/2 0 0,8 0

5 2/3 0 0 1

Нетрудно заметить, что общее количество предлагаемых производителями альтернативных типов насосов - 3+ 10 + 8 + 5 + 4 + 5 =35 превышает общее потребное количество насосов в консолидированном заказе - 5 + 7 + 3 = 15. Это означает, что есть возможность выбора закупаемого оборудования с максимальным соответствием выставленным коммерческим требованиям. В то же время выбор надо сделать так, чтобы полученные насосы были распределены по предприятиям с максимальным соответствием заявленным техническим требованиям.

Для решения задачи оптимального выбора используем математическую модель (3.14-3.18). Было принято равное распределение значимости технических и коммерческих требований, что соответствует значению параметра Л = 0,5 . Для решения был использован программный пакет Microsoft Office Excel с надстройкой «Поиск решения». Модель (3.14-3.18) при заданных исходных данных принимает вид

Окончательно модель выглядит следующим образом:

^IIМу + —II УукЛук ^ тах

35 г=1 у=1 35 у=1 к=1 Х,У •

?

4 4 4 4

I Уу1= I у у 2= I Уу з =I У у 4 =20;

у=1 у=1 у=1 у=1

I Х1 у = 3 I Х2у = 10; I х3у = 8 I Х4у = 5 I Х5у = 4 I х6у = 5

у=1

у=1

у=1

у=1

у=1

у=1

6 4

£ ху = I Уук;у = !;2;3;4-

г=1 к=1

(4.1)

(4.2)

(4.3)

(4.4)

Х;

-у; Уук е {0;г Ху ^ 0; у^ ^ 0 ^ у, к (4 5)

Решение задачи выбора ресурсов и их поставщиков по предложенной модели удобно представить в виде трехдольного графа «производители» - «типы ресурсов» - «предприятия» (рисунок 4.1), на котором показано: у каких производителей приобретены насосы различных типов, в каком количестве (вес дуги графа) распределены насосы и с каким соответствием (в скобках) коммерческим и техническим требованиям.

г } к

ЗАВОД 1 <

ЗАВОД 2 <

г 1 а V

3(1)

2 о IX

4(1) / 7(1)^

3 о 5(0,9) ^^ -ч 4(0,9)

Г 1 а V

2 о >-з<0—О

т 3

3 а

Рисунок 4.1 - Результаты выбора и распределения насосов по предприятиям Введенные для обеспечения условия (4.5) фиктивный ресурс и фиктивное предприятие и распределенные на него оставшиеся насосы на рисунке 4.1 не показаны.

Результаты решения при Л = 0,5 показывают, что на заводе 1 были закуплены на максимально выгодных условиях 1 и 2 типы насосов. Поскольку наиболее востребованный 1 тип насосов оказался в дефиците (потребность в качестве основного ресурса 13, при выгодном коммерческом предложении 3), пришлось закупить коммерчески менее выгодную партию насосов типа 1 на заводе 2. Насосы типа 3 полностью и выгодно закуплены на заводе 2. Таким образом, логическая интерпретация полученного решения вполне адекватна поставленной задаче.

Распределение полученных ресурсов осуществлено также вполне логично. Предприятия 2 и 3 качеством закупки удовлетворены полностью. Вследствие дефицита насосов типа 1, заказчику 1 дополнительно поставлены менее желаемые насосы типа 2. Все заказчики получили требуемое количество насосов.

Полученные результаты можно сравнить с существующей технологией выбора оборудования, которая исходит из коммерческих требований и учета технических требований в бинарной форме - «можно использовать»; «нельзя использовать». Применение существующей технологии к рассматриваемому примеру обеспечит выбор оборудования по коммерческим требованиям с соответствием везде равным 1: 3 насоса первого типа и 10 насосов второго типа с первого завода; 2 насоса третьего типа со второго завода. В этом случае существующая технология выбора может обеспечить соответствие техническим

4 3

ООП/ 3 • 1 + 2 • 0,8 + 7 • 0,8 + 3 • 1 __ ^ требованиям на 88% = БСтех = ^^-=------100% . В то

тех 23 \5

время как предлагаемый подход дает 97% соответствия. Таким образом, на этапе выбора и распределения оборудования можно получить 9% повышения эффективности производства за счет более рационального выбора насосов.

Проведенная численная апробация предложенной модели выбора оборудования работоспособна и позволяет получать решения логически адекватные поставленным целям.

4.3 Исследование целочисленных алгоритмов

Анализ трудоемкости методов получения целочисленных решений проведем для методов Гомори и метода ветвей и границ.

Метод Гомори реализует механизм отсечения. Суть алгоритма состоит в следующем: симплекс-методом решается задача линейного программирования без учета требования целочисленности; если полученное оптимальное решение не целочисленно, среди дробных чисел решения выбирается элемент с наибольшей дробной частью и составляется дополнительное ограничение; полученная новая задача решается двойственным симплекс-методом; перечисленные действия повторяются до получения целочисленного результата.

Рассмотрим в качестве примера решение задачи ЦЛП [18]

F = 0,9x11 + 0,8x22 + 0,6 уп + 0,8у21 ^ max, x11 < 3,57, x22 < 3,

<

У11 + У21 = 5, X11 + Х22 = У11 + у21, x11, Х22 , у11, у 21 G Z

Представим эту задачу в каноническом виде и для поиска целочисленного решения применим метод Гомори.

F = -0,9x11 - 0,8x22 - 0,6 у11 - 0,8 у21 ^ min, < Хц ^ Х33 — 3,57, Х22 ^ X44 — 3,

уп + у21 = 5, Х11 + Х22 = у11 + у21-

Оптимальное решение рассматриваемого примера, полученное симплекс-методом: x11 = 3,57;x22 = 1,43; у11 = 0; у21 = 5 не целочисленное, значит, следует ввести новое ограничение вида

q — q1 • X11 — q2 ' x22 _ q3 ' у11 _ q4 ' у21 _ q5 ' X33 _ q6 ' X44 ^ X55 = 0

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

Таблица 4.3 - Часть симплекс-таблицы оптимального плана

Базис План х11 х22 У11 У 21 х33 х44

х11 3,57 1 0 0 0 1 0

q = 3,57 - 3 = 0,57 , q1 = q5 = 1 - 1 = 0 , д2 = q3 = q4 = = 0

Тогда дополнительное ограничение имеет вид

0,57 + х55 = 0

Коэффициенты дополнительного ограничения добавляются новой строкой в симплекс-таблицу оптимального плана, и выполняется решение двойственной задачи. В процессе решения задачи дважды добавлялось дополнительное ограничение.

С помощью метода Гомори было получено оптимальное целочисленное решение х11 = 3; х22 = 2; у11 = 0; у21 = 5 .

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

Выполним решение задачи вышеприведенного примера методом ветвей и границ.

В оптимальном решении, вычисленном на первом этапе алгоритма,

переменная х11 = 3,57 имеет дробное значение, поэтому рассмотрим две

подзадачи с учетом дополнительных ограничений

^ = 0,9х11 + 0,8х22 + 0,6 у11 + 0,8у21 ^ тах, х11 < 3,57, х22 < 3,

У11 + У21 = 5, х11 + х22 = У11 + У21,

х11 " 3 (4.6)

F = 0,9x11 + 0,8x22 + 0,6 уп + 0,8у21 ^ max, x11 < 3,57, x22 < 3,

У11 + У21 = 5, x11 + x22 = У11 + у21,

X11 > 4.

(4.7)

Подзадача (4.6) имеет оптимальное целочисленное решение x11 = 3; x22 = 2; у11 = 0; у21 = 5 при значении целевой функции F = 8,3. Подзадача (4.7) не имеет решений, данная ветвь в дальнейшем не рассматривается.

Также в оптимальном решении исходной задачи нецелочисленное значение имеет переменная x22 = 1,43 . Рассмотрим ветвление задачи по переменной x22

F = 0,9x11 + 0,8x22 + 0,6 у11 + 0,8у21 ^ max, x11 < 3,57, x22 < 3,

у11 + у21 = 5, x11 + x22 = у11 + у21,

x22 ^ 1.

(4.8)

F = 0,9x11 + 0,8x22 + 0,6 у11 + 0,8у21 ^ max, x11 < 3,57, x22 ^ 3 у11 + У21 = 5, x11 + x22 = У11 + У21,

x22 — 2.

(4.9)

По аналогии с ветвлением по переменной х11, подзадача (4.9) имеет

решение х11 = 3; х22 = 2; у11 = 0; у21 = 5 . Подзадача (4.8) решений не имеет.

На рисунке 4.2 представлено дерево решения исходной задачи методом ветвей и границ.

Исходная задача

-•- • ♦

1 г 1 г 1 г