Автоматизированная система подбора рациональной комплектации средств вычислительной техники

Размещено на http://www.allbest.ru/

Автоматизированная система подбора рациональной комплектации средств вычислительной техники

Лысков О.Э.

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

Введём два термина. Тип детали - это её абстрактное название. Например: видео карта, звуковая карта, мышь и т. д. Так как детали одного типа различаются по множеству признаков, то каждому типу соответствует множество видов детали. Пусть N={N1, N2,…, Nn} - множество типов деталей, а Ni = {Mi1, Mi2,…, Mim} - множество видов деталей конкретного типа. Причём количество видов детали конкретного типа зависит от самого типа: m=f(Ni); i=1, n. Тогда прайс-лист можно представить в виде одномерного массива, каждый элемент которого является одномерным массивом переменной длины. Пусть P(x) - цена детали х, а Q(x) - количество деталей х в наличии. Пусть заказчику необходимо N' типов деталей в количестве Q' на общую стоимость P'.

Обозначим конкретную деталь парой Mij Sl; i=1,n; j=1,m; m=f(Ni); l=1,k. Здесь Mij - деталь конкретного вида и типа, имеющаяся в наличии у предприятия, а Sl - деталь конкретного типа, необходимая заказчику. Видно, что у Sl только один индекс, а у Mij - два. Это объясняется тем, что покупатель заказывает в основном детали по типу, а вид подготавливает продавец. Причём, на складе может и не оказаться детали нужного вида и типа, поэтому будет взята деталь того же типа, но другого вида. Итак, продающей фирме нужно подобрать такой набор деталей S={S1, S2, …,Sk}, чтобы выполнялись следующие условия:

(1)

(2)

(3)

(4)

(5)

(6)

Условие (1) учитывает, что заказчик выделил на покупку ограниченное количество денег. Условие (2) показывает, что количество купленных деталей ограничено количеством деталей в наличии у продавца. Условие (3) говорит, что типы и виды деталей выбирались на конкретном предприятии с N типами деталей. Условие (4) показывает, что заказчику предоставят нужное ему количество деталей. Условие (5) учитывает, что по возможности в набор следует включить наилучшие детали, т. е. наиболее дорогие. Условие (6) показывает, что все детали должны быть совместимы.

Следует отметить, что условия (1) - (6) действительны, если в наборе деталей S количество деталей каждого типа и вида постоянно и равно единице. Решение задачи сводится к оптимальному подбору видов Mij для каждого типа Si (i=1,k).

Однако условий (1) - (6) может быть явно недостаточно. А что, если покупатель не просто заказывает товар, а действует, опираясь на какие-то нормативы? В данном случае, нормативные документы будут являться ещё одной системой ограничений поставленной задачи.

Пусть V - множество нормативных ограничений для предполагаемого итогового набора деталей. Оно будет иметь следующий вид: V={V1a,V2b,…,Vrx}, где Vij - нормативные ограничения для типа деталей Sj, а i - номер ограничения во множестве V. Причём rk. (r - количество ограничений V, k - количество типов деталей набора S). Получается, что не для всех типов деталей из S существуют ограничения из V, т. е. jJ, J{1,k}. Причём VVH, где VH - множество всех ограничений в каком-то нормативном документе. Следует добавить, что каждый элемент Vij может включать несколько ограничений для типа деталей Sj.

Теперь добавим к условиям (1) - (6) ещё одно, указывающее следование нормативам продавца и покупателя:

(7)

Применение симплекс-метода для решения поставленной задачи следует считать неразумным. Во-первых, симплекс-метод включает в себя рутинные математические вычисления. Такие методы устаревают. Причём такой параметр, как совместимость, сложно выразить количественно. /1/ Искусственный интеллект (ИИ), как одно из направлений информатики, всё быстрее разрастается и укрепляет позиции. Поэтому для решения задачи следует обратиться к одному из направлений ИИ: системе, основанной на знаниях. Во-вторых, условия (6) и (7) подразумевают использование для решения задачи базы знаний. А ведь если и попытаться создать, например, гибридную экспертную систему, являющуюся надстройкой над симплекс-методом, то задача станет сложнее на порядок. Стыковка разных методологий порождает целый комплекс теоретических и практических трудностей. /2/

Идя в ногу со временем, можно решить задачу с помощью построения интеллектуальной системы (ИС) или автоматизированной системы (АС). Источником знаний могут служить нормативные документы, учтённые в условии (7), прайс-лист, а также литература по совместимости деталей или мнение эксперта по подбору деталей.

Что физически представляет собой параметр совместимости? Современные машины и механизмы имеют сложную структуру и собираются из множества деталей. Комплектующие каким-то образом соединяются друг с другом. Детали совместимы, если при их физическом соединении обеспечивают работу всей машины или механизма в должном порядке.

Совместимость иерархична. Деталь какого-то уровня иерархии имеет некий "слот" под деталь нижестоящего уровня, а деталь нижестоящего уровня имеет некоторый параметр совместимости со слотом детали вышестоящего уровня. Если обозначить в дереве совместимости уровни иерархии как U1, U2,…, Ut, где U1 - верхний уровень, а Ut - самый нижний, то совместимость имеет вид Ui+1[Sl]Ui[Pr], где Sl - слот, Pr - параметр совместимости. Обычно Sl и Pr - символьные строки.

Словесно правила совместимости можно изобразить следующим образом:

Если существует корпус ATX и блок питания ATX, то они совместимы.

Если существует корпус AT и блок питания AT, то они совместимы.

В других случаях детали несовместимы.

В базе знаний их можно представить, например, так:

Корпус[Слот]БП[Параметр_сравнения]"=[ATX][ATX]|[AT][AT].

Тогда правые части всех предложений построят дерево совместимости, а левые - правила для всех сравниваемых типов деталей.

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

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

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

Для всех типов прайс-листа вычисляются средние цены и их сумма. Весовой коэффициент конкретного типа - отношение средней цены данного типа к сумме средних цен всех типов. Это доля типа детали в прайс-листе по средней цене.

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

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

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

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

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

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

Рисунок 1 - Блок-схема алгоритма

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

2. Считать, что полный путь не найден.

3. Считать, что подходящий вид не найден.

4. Подходящий вид не найден и текущий вид существует в прайс-листе?

5. Совместим ли текущий тип со всеми зафиксированными типами?

6. Суммарная стоимость фиксированных типов и текущего вида меньше или равна входной стоимости за минусом общей недооценки?

7. Выбрать следующий вид для конкретного типа.

8. Зафиксировать текущий тип и вычислить общую недооценку. Считать, что подходящий вид найден.

9. Все типы зафиксированы?

10. Считать, что полный путь найден.

11. Перейти к рассмотрению следующего типа.

12. Подходящий вид не найден?

13. Можно ли снять фиксацию с предыдущего типа?

14. Снять фиксацию с предыдущего типа и вычислить общую недооценку.

15. Считать, что полный путь найден и все комбинации перебраны.

16. Перейти к рассмотрению первого вида.

17. Найден ли полный путь?

18. Все типы зафиксированы?

19. Разность между входной ценой и суммарной ценой набора меньше минимального отклонения?

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

21. Все ли комбинации перебраны?

22. Величина минимального отклонения не равна очень большому числу?

23. Вывести рациональный набор, входную цену и суммарную стоимость набора.

24. Обработать ситуацию "Решение не найдено".

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

Для каждого типа повторять:

О ориентировочная цена; min минимальная цена; max максимальная цена;

если о - > max то промежуток выборки [max - 2; max] иначе

если о + < min то промежуток выборки [min; min+2] иначе

промежуток выборки [o - ; o + ]

Литература

1. Системы управления базами данных и знаний: Справ. изд. / А.Н. Наумов, А.М. Вендров, В.К. Иванов и др.; Под ред. А.Н. Наумова. - М.: Финансы и статистика, 1991. - 352 с.: ил.

2. Базы знаний интеллектуальных систем / Т.А. Гаврилова, В.Ф. Хорошевский. - СПб.: Питер, 2001. - 384 с.: ил.

Размещено на Allbest.ru