Настоящая работа посвящена решению следующей проблемы. Пусть имеется техническая система, состоящая из подсистем, узлов или элементов. Каждый из узлов системы может быть реализован несколькими способами. Каждая из реализаций узла отличается от других значениями измеряемых параметров. Свойства технической системы характеризуются значениями контролируемых параметров. Значения измеряемых параметров узлов и контролируемых параметров системы связаны известными соотношениями. Задача заключается в выборе таких реализаций узлов системы, чтобы значение одного заданного контролируемого параметра было минимальным, а значения остальных контролируемых параметров удовлетворяли установленным ограничениям.
Любой набор реализаций узлов в дальнейшем будем называть вариантом технической системы. Вариант технической системы будем называть допустимым, если значения его контролируемых параметров удовлетворяют ограничениям.
Проблема заключается в большом количестве вариантов системы даже при небольшом количестве узлов и их реализаций. Например, если техническая система содержит сто узлов, каждый из которых может быть реализован всего двумя способами, то получаем 2100 & Ю30 вариантов технической системы. Если такое количество вариантов просматривать на вычислительной машине с частотой 109 Гц, причем таким образом, чтобы за один такт генератора просматривать один вариант, то, с учетом того, что 1 год ри 31 ¦ 106 е., для просмотра всех вариантов потребуется Ю30: (109 • 31 • 106) «32 • 1012 лет.
К рассматриваемой проблеме относится задача выбора оптимального варианта сложного изделия, которая всегда встречается на этапах его создания. Например электронное устройство всегда содержит большое количество элементов, которые могут быть заменены на другие с теми же номиналами, но отличающиеся фирмой или страной изготовителем. В частности, микросхемы для плат ЭВМ могут быть японскими, тайваньскими, американскими, российскими и т. д. В данном случае в качестве измеряемых параметров элементов могут использоваться надежность, стоимость, габариты, потребляемая мощность и т. п. Эти же параметры, но для всего устройства могут использоваться в качестве контролируемых параметров технической системы. Задача в данном случае может формулироваться, как выбор варианта сложного изделия минимальной стоимости, имеющего значения вероятности безотказной работы, габаритов, потребляемой мощности в заданных ограничениях.
К данной проблеме относится также задача выбора оптимального варианта системы управления. Пусть на этапе создания системы управления был произведен расчет ее параметров. При реализации блоков системы управления из-за дискретного ряда значений номиналов элементов и их вариаций внутри допуска реальные параметры блоков могут отличаться от расчетных. В итоге система управления может иметь в зависимости от реализаций ее блоков различные качественные характеристики, запас устойчивости, частоту среза, время переходного процесса и др. Более точное изготовление блоков управления требует дополнительных затрат и увеличивает стоимость системы управления. В данном случае в качестве измеряемых параметров блоков управления могут использоваться реальные значения передаточных коэффициентов, постоянных времени, коэффициентов демпфирования, а также обычные параметры стоимости, надежности и энергопотребления. В качестве контролируемых параметров системы могут использоваться запас устойчивости, стоимость, энергопотребление и надежность. В данном случае задача может формулироваться, как выбор оптимального варианта системы, минимизирующего либо суммарную величину отклонений параметров от расчетных величин, либо один из контролируемых параметров, например стоимость или надежность, при условии выполнения ограничений по другим контролируемым параметрам.
Широкий класс актуальных задач, связанных с выбором конфигурации сетевых структур, также может быть отнесен к рассматриваемой проблеме. Пусть имеется сетевая структура, например сеть дорог или механических конвейеров, переносящих потоки элементов. Необходимо найти оптимальную конфигурацию сети, чтобы обеспечить максимальное прохождение потока по ней и при этом исключить переполнение на отдельных дугах. Здесь в качестве элемента технической системы следует принять дугу ветви, а под реализацией — ее состояние, возможность пропускать или не пропускать через себя поток. В данном случае в качестве измеряемых параметров элементов, дуг сетевой структуры, можно использовать пропускную способность дуги, а в качестве контролируемых параметров технической системы — величины потоков, проходящих через сеть и пропускные способности ее отдельных дуг.
К этому же классу задач относится задача обеспечения надежности сетевой структуры за счет введения дополнительных резервных дуг. В данном случае число резервных дуг определяет различные реализации элементов системы. Вероятность безотказной работы и стоимость введения резервных дуг являются измеряемыми параметрами элементов. Задача может формулироваться как обеспечение допустимого уровня надежности сетевой структуры при минимизации ее стоимости.
Задача синтеза дискретного программного закона управления также может быть сформулирована как задача выбора оптимального варианта технической системы. Пусть в определенные моменты времени для обеспечения качества управления необходимо найти значения управляющего воздействия из конечного множества возможных величин. Будем считать технической системой всю совокупность управляющих воздействий, элементами системы — управляющее воздействие в определенный момент времени, множеством возможных реализаций элемента — конечное множество значений, которое может принимать управляющее воздействие. Под контролируемыми параметрами системы здесь следует считать параметры, определяющие качество управления и значения выходных сигналов объекта управления. Эти же параметры могут также считаться и измеряемыми параметрами элементов, если они определены для одного дискретного момента управления. В данном случае задача выбора оптимального варианта технической системы формулируется как построение оптимального дискретного закона управления при заданных ограничениях на управляющее воздействия и параметры объекта управления.
К задаче выбора оптимального варианта технической системы могут быть приведены и много других практических задач из различных областей техники. Таким образом задача выбора оптимального варианта технической системы имеет широкое прикладное значение, а создание метода ее решения является важной научнотехнической проблемой.
В большинстве случаев исходные данные этой проблемы, а именно измеряемые параметры реализаций з^злов системы, располагаются в таблицах баз данных. Например, можно определить для каждого узла системы соответствующую таблицу, столбцы которой указывают на измеряемые параметры узла, а строки — на его реализации. Всего имеем столько таблиц, сколько имеет техническая система узлов с неоднозначной реализацией. Контролируемые параметры технической системы представляют собой функциональные зависимости от значений измеряемых параметров узлов, хранящихся в таблицах. Вся совокупность вариантов технической системы определяется декартовым произведением таблиц. Таким образом проблема выбора оптимального варианта технической системы заключается в поиске данных в декартовом произведении таблиц, обеспечивающих минимум значений одной заданной функциональной зависимости и удовлетворяющих ограничениям значениями других определенных функциональных зависимостей.
Сами функциональные зависимости, описывающие связь между значениями измеряемых параметров узлов и контролируемых параметров технической системы, могут представлять собой, в общем случае, сложные нелинейные соотношения. Каждую таблицу можно интерпретировать как функцию, аргументами которой является номер строки таблицы, а значениями — величины измеряемых параметров соответствующей реализации узла. Номерам строк таблицы или номерам реализаций узла можно поставить в соответствие целые числа, поэтому каждый столбец таблицы, описывающий связь между номером реализации элемента и значением одного измеряемого параметра, будет представлять собой скалярную функцию целочисленного аргумента. Так как измеряемые параметры узла сами являются аргументами функциональных зависимостей, описывающих связь контролируемых параметров системы с измеряемыми параметрами ее узлов, то в итоге получаем, что функциональные зависимости между контролируемыми параметрами системы и номерами реализаций ее узлов являются функциями целочисленного аргумента. Более точно они представляют собой вещественные функции, аргументами которых являются векторы с компонентами из ограниченных множеств целых чисел. Следовательно проблема выбора оптимального варианта технической системы может быть формализована, как задача дискретной оптимизации.
В общем случаем рассматриваемая проблема выбора оптимального варианта технической системы приводит к наиболее сложному классу нелинейных задач дискретной оптимизации с таблично заданными функциями. Это объясняется тем, что функциональные зависимости между контролируемыми параметрами системы и измеряемыми параметрами узлов могут носить произвольный нелинейный характер, таблицы, содержащие значения измеряемых параметров, не могут быть все одновременно упорядочены по значениям контролируемых параметров системы, так как это равносильно просмотру всех вариантов, что сложнее нахождения одного оптимального. Данный класс задач мало изучен и ранее решался только методом прямого перебора всех вариантов.
Задача дискретной оптимизации с алгоритмической точки зрения относится к классу труднорешаемых [25, 35, 54, 65]. Особенностью этих задач является, то, что для них сегодня неизвестно ни одного алгоритма их решения с полиномиальной скоростью сходимости, т. е. алгоритма, время работы которого ограничена полиномом конечной степени от параметров, определяющих объем входных данных или сложность задачи. Заметим, что наиболее простая и исследованная задача дискретной оптимизации, задача линейного целочисленного программирования также является труднорешаемой, в то время, как задача линейного нецелочисленного программирования имеет решение в классе алгоритмов с полиномиальной скоростью сходимости [78].
Алгоритмы для решения задач дискретной оптимизации практически всегда имеют экспоненциальную скорость сходимости, поэтому время вычислений с помощью данных алгоритмов растет быстро с увеличением параметра, определяющего сложность задачи. Для рассматриваемой проблемы выбора оптимального варианта технической системы параметрами, определяющими сложность задачи, являются количество узлов системы и количество их реализаций, так как полное число вариантов системы определяется произведением из сомножителей, количество которых равно числу узлов системы, а значения каждого сомножителя равно количеству реализаций узла. Следовательно даже при небольшом количестве узлов системы и реализаций каждого узла число вариантов технической системы оказывается довольно значительным.
Быстрый экспоненциальный рост времени вычислений алгоритмов труднорешаемых задач приводит к тому, что скорость их решения мало зависят от мощности вычислительных средств. Увеличение скорости счета вычислительных машин в несколько тысяч раз не приводит к соответствующему эффекту при решении задач данного класса. Скорость решения задач дискретной оптимизации зависит прежде всего от используемых методов и алгоритмов. Сегодня не существует универсальных эффективных методов для решения задач дискретной оптимизации. Каждый из существующих методов для обеспечения необходимой скорости вычислений использует особые свойства рассматриваемой задачи.
Среди наиболее общих методов решения задач дискретной оптимизации можно выделить [46, 50, 53, 54, 56, 65, 67] метод последовательного анализа и отсеивания вариантов, метод ветвей и границ, динамическое программирование и метод лагранжевой релаксации. Все эти методы требуют от целевой и ограничивающих функций специальных свойств и эффект от их применения связан с их использованием. Все существующие методы решения задач дискретной оптимизации включают построение подмножества возможных решений и проверку наличия в нем оптимального. Если в результате выясняется, что в подмножестве не существует оптимального решения, то данное подмножество отсеивается. Эффективность методов решения задач дискретной оптимизации достигается, если время проверки подмножества возможных решений меньше, чем время проверки всех возможных решений из этого подмножества.
Все существующие методы решения задачи дискретной оптимизации являются эвристическими в том смысле, что для любого метода всегда можно подобрать задачу с такими исходными данными, что ни одно из подмножеств не будет отсеяно в результате проверок и для нахождения решения приходится проверять все возможные решения. Таким образом все существующие алгоритмы решения задачи дискретной оптимизации в наихудшем случае приводят к прямому перебору. Эффективность алгоритмов определяется малой вероятностью встречи наихудшего случая. Для достижения этой цели используются специальные свойства целевой и ограничивающих функций задачи. Если при ослаблении требования дискретности, т. е. при переходе к непрерывному аргументу возникает задача математического программирования, для которой имеются эффективные методы решения, например задача с унимодальной целевой функцией и выпуклыми ограничениями или задача линейного программирования, то их оптимальное решение дает оценку значения целевой функции задачи дискретного программирования, так как решение непрерывной задачи не может быть хуже дискретной. Полученные оценки целевой функции могут использоваться при проверке подмножеств возможных решений. Из других специальных свойств целевой и ограничивающих функций, при получении решения используются аддитивность, монотонность, рекурсивная монотонность и др.
Рассматриваемая проблема выбора оптимального варианта технической системы приводит к задаче дискретной оптимизации с таблично заданными целевой и ограничивающими функциями. Так как таблицы неупорядочены, а функциональные зависимости контролируемых параметров системы от измеряемых параметров узлов может носить нелинейный характер, то получаем наиболее общий вид задачи дискретной оптимизации, когда при переходе к непрерывному аргументу, целевая функция не является унимодальной, а ограничения не являются выпуклыми. Сегодня для решения таких задач дискретной оптимизации используется достаточно трудоемкий метод перебора, который в данном случае включает просмотр всех возможных вариантов технической системы. Отсюда следует, что построение метода выбора оптимального варианта технической системы позволит создавать алгоритмы для решения нового класса задач дискретной оптимизации с таблично заданными функциями, поэтому является актуальной научной проблемой.
Поиск по табличным данным осуществляется на практике в системах управления базами данных. Современные базы данных в большинстве случаев являются реляционными, поэтому используют табличную организацию хранения информации. Для быстрого поиска в таблицах системы управления базами данных используют последовательно индексированный поиск с помощью бинарных или В-деревьев [49]. Для осуществления поиска данные предварительно сортируются по одному или нескольким параметрам. При решении рассматриваемой задачи выбора оптимального варианта технической системы с помощью использования механизмов реляционной базы данных получаем поиск в нормализованных таблицах по совокупным критериям, контролируемым параметрам технической системы. Так как заранее не известно как влияет значения измеряемого параметра на величины совокупных критериев, то сортировка каждой таблицы не имеет смысла и система управления базами данных будет осуществлять проверку всех значений в декартовом произведении таблиц, т. е. всех вариантов технической системы.
Для решения рассматриваемой проблемы выбора оптимального варианта технической системы в настоящей работе предложен метод бимоногонного разложения функций [8−12, 16]. Метод заключается в представлении целевой и ограничивающих функций в виде разности двух монотонно неубывающих функций. Такое представление позволяет строить оценки предельных значений функций на подмножествах вариантов. Полученные оценки используются для проверки достаточных условий отсутствия в подмножестве оптимального варианта системы. Данное представление всегда возможно для ограниченных функций и оно не однозначно.
Метод бимонотонного разложения функций базируется на идее, предложенной Лоулером и Беллом в 1966 году [97], которые разработали алгоритм для решения задач дискретной оптимизации специального вида. Особенностью рассматриваемой ими задачи являлось то, что все ограничивающие функции представляли собой разность двух монотонно неубывающих функций. Это использовалось для дополнительной проверки подмножеств возможных решений, получаемых в результате перечисления бинарных векторов в лексикографическом порядке. В работе Лоулера и Белла не рассматривались вопросы построения бимонотонного разложения различного вида функций и точность этих оценок, а использовались функции, которые уже имели вид разности двух монотонно неубывающих функций. Методы построения бимонотонного разложения функций различного вида, в том числе и таблично заданных, а также исследование бимонотонного разложения с точки зрения получения наиболее точных оценок предельных значений функций до настоящего периода не рассматривались.
Исследование бимонотонного разложения функций позволяют создать метод и алгоритмы для решения важной научно-технической проблемы выбора оптимального варианта технической системы. Данный метод базируется на теоретических исследованиях и включает формальные процедуры построения бимонотонного разложения таблично заданных функций, совокупность рекомендаций для построения бимонотонного разложения различных функций, используемых в задачах выбора оптимального варианта технической системы, и алгоритмы поиска оптимального варианта на основе бимонотонного разложения функций.
Метод бимонотонного разложения и алгоритмы поиска оптимального варианта, построенные на его основе, могут применяться не только для решения проблемы выбора оптимального варианта технической системы, но и при решении других проблем, где необходимо получать оценки предельных значений функциональных зависимостей, например при решении задач оптимизации в условиях неопределенности или в интервальном анализе. Поэтому разработка метода бимонотонного разложения и алгоритмов поиска оптимального варианта открывает новые направления для научных исследований и для решения актуальных практических задач в технике, экономике, экологии безопасности и др.
Основная цель диссертационной работы заключается в построении метода и алгоритмов для решения новой важной научно-технической проблемы выбора оптимального варианта технической системы. Для достижения поставленной цели в работе необходимо решить следующие задачи:
— провести теоретические исследования бимонотонного разложения функций с точки зрения построения наиболее точных оценок ее предельных значений;
— с учетом требования получения наиболее точных оценок предельных значений функций разработать формальную методику построения бимонотонного разложения таблично заданных функций;
— разработать методики построения бимонотонного разложения функций различного вида, часто используемых в прикладных задачах выбора оптимального варианта технической системы;
— разработать алгоритмы выбора оптимального варианта методом бимонотонного разложения функций.
— провести теоретические и экспериментальные исследования метода бимонотонного разложения функций при решении прикладных задач дискретной оптимизации.
Настоящая работа состоит из введения, семи глав и приложения. В первой главе представлена постановка проблемы выбора оптимального варианта технической системы. Показано, что проблема выбора оптимального варианта технической системы формализуется, как задача нелинейной дискретной оптимизации с таблично заданными функциями. Сформулирована отдельно задача дискретной оптимизации с полиномиально табличными функциями. Приведен обзор известных методов решения нелинейных задач дискретной оптимизации.
Во второй главе представлен метод бимонотонного разложения функций. Приведено теоретическое исследование бимонотонного разложения функций. Введено понятие минимального бимонотонного разложения, которое дает наилучшие оценки ее предельных значений. Получены необходимые и достаточные условия минимального бимонотонного разложения функций. Представлены алгоритм получения минимального бимонотонного разложения табличных скалярных функций. Приведена методика построения бимонотонного разложения полиномиально табличных функций.
В третьей главе приведены алгоритмы выбора оптимального варианта технической системы методом бимонотонного разложения функций. Алгоритмы включают построение интервалов на множестве вариантов и проверку оценок предельных значений функций, полученных с помощью бимонотонного разложения. Основные схемы алгоритмов базируются на лексикографическом перечислении и методе ветвей и границ, частным случаем которого является метод многомерного деления пополам. Для хранения промежуточных результатов алгоритмы используют стек. Приведен анализ скоростей сходимости алгоритмов и получены качественные оценки количеств итераций при условии равно вероятного отсеивания всех интервалов.
В четвертой главе представлен вычислительный эксперимент. Эксперимент направлен на исследование эффективности алгоритмов, определение их скорости сходимости в зависимости от размерностей задачи дискретной оптимизации. Дополнительно проведен эксперимент по исследованию влияния модификации размерностей задачи на скорость сходимостей алгоритмов.
В пятой главе представлено описание применения метода би-монотонного разложения функций для решения проблемы выбора оптимального варианта технической системы в особых условиях. Разработан метод получения формального описания задачи выбора оптимального варианта в условиях неопределенности, с ограничениями запаса, с неявными и логическими ограничениями. Все полученные формальные соотношения имеют вид полиномиально табличных функций, или ступенчатых функций Хевисайда.
В шестой главе представлено решение практической задачи выбора оптимального варианта вычислительной системы. Проблема формулируется как задача дискретной оптимизации с полиномиально табличными функциями. Приведен вычислительный эксперимент решения рассматриваемой задачи со случайно заданными исходными данными.
В седьмой главе представлено решение практической задачи синтеза закона управления потоком автотранспорта в сети автодорог. Задача формулируется как задача дискретной оптимизации с полиномиально табличными функциями и логическими ограничениями. Приведен вычислительный эксперимент, который показал высокую эффективность разработанных алгоритмов.
5.5. Выводы.
1. Разработан метод решения проблемы выбора оптимального варианта технической системы в условиях неопределенности, когда необходимо выбрать часть элементов системы при условии, что неизвестен выбор другой части элементов. Известные методы решения данной проблемы заключались в использовании минимакса, т. е. находился такой вариант определенной части системы, при условии, что неопределенная часть будет выбираться наихудшим способом. Решение проблемы методом минимакса оказывалось трудоемким и требовало больших вычислительных затрат. Показано, что с помощью метода бимонотонного разложения функций проблема выбора оптимального варианта в условиях неопределенности решается значительно эффективней, так как неопределенная часть элементов системы заменяется значениями граничных вариантов интервала, поэтому задача решается только для определенной части элементов системы, и мощность множества вариантов в этом случае значительно сокращается.
Доказано, что, если бимонотонное разложение всех функций задачи позволяет построить точные оценки их предельных значений на интервале, то решение задачи с методом бимонотонного разложения функций совпадает с решением, полученным с помощью метода минимакса.
2. Разработан метод решения задачи выбора технической системы при ограничениях запаса, когда значения, принимаемые элементами из контролируемого множества, ограничены. Для описания ограничений запаса используется индикаторная функция, принимающая единичное значение, когда значение элемента принадлежат контролируемому множеству. С помощью индикаторной функции подсчитывают количество элементов, принимающих значения из контролируемого множества. Для описания ограничений запаса используется представление индикаторной функции разностью монотонно неубывающих функций Хевисайда, которые являются функциями скалярного аргумента и принимают единичное значение при неотрицательном аргументе и нулевое значение при отрицательном аргументе. Объединение положительных и отрицательных функций Хевисайда обеспечивает получение бимонотонного разложения функции, описывающей ограничения запаса.
3. Разработан метод построения бимонотонного разложения функций, заданных неявно, когда ограничивающая функция вычисляется по максимальному или минимальному значениям некоторой совокупности функций. Для бимонотонного разложения данной ограничивающей функции первоначально осуществляется бимонотонное разложение каждой функции из рассматриваемой совокупности, по которым берется максимум или минимум. Затем, если ограничивающая функция является максимумом значений функций, то ее бимонотонное разложение представляет собой разность между максимумами первых и вторых функций разложения. Если ограничивающая функция представляет собой минимум значений функций, то ее бимонотонное разложение представляет собой разность между минимумами первых и вторых функций разложения.
4. Разработан метод решения задачи выбора технической системы при логических ограничениях, когда ограничения представляют собой логическое высказывание, заключающееся в том, что, если часть элементов системы принимает определенные значения, то другая часть элементов должна принимать другие определенные значения. Для описания логических ограничений используются многомерные полиномиальные функции, которые дают нулевое значение при выполнении ограничений и положительное значение при невыполнении логических условий. Замена логических выражений полиномами позволяет построить бимонотонное разложение функций и дополнительные ограничения, проверяемые для граничных значений интервалов.
6. ВЫБОР ОПТИМАЛЬНОГО ВАРИАНТА ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ.
Рассмотрим популярную сегодня задачу выбора оптимального варианта технической вычислительной системы, персонального компьютера. Допустим, что у некой организации возникла необходимость в приобретении партии персональных компьютеров. Вполне допустимо, что с целью экономии средств организация решила не закупать готовые персональные компьютеры, а приобрести их составные модули, а затем сборку и конфигурирование операционной системы произвести собственными силами, сэкономив на этом определенную часть средств. Современные персональные 1ВМ-совместимые компьютеры допускают возможность сборки из отдельных блоков, практически не требуя высококвалифицированной подготовки. Удобство конструкции и соответствие международным стандартам модулей, выпускаемых отдельными фирмами, позволяет без особого труда осуществить операции сборки и конфигурирования.
Обычный выбор персонального компьютера по его основным техническим параметрам, типу процессора, тактовой частоте генератора, емкостью оперативной памяти, емкостью жесткого диска, кратностью скорости вращения лазерного компакт-диска, размерам диагонали монитора и т. п. оказывается недостаточным. Из-за большого разнообразия фирм-изготовителей и фирм-поставщиков одинаковые по основным техническим параметрам компьютеры могут сильно отличаться по стоимости в зависимости от качества сборки, надежности, торговой марки фирмы-изготовителя отдельных элементов и т. п. Например значительно отличаются по стоимости компьютеры, собранные в Азии, в России, в Европе или в США. На цену вполне могут влиять, предоставляемые магазином гарантии и время существования на российском рынке фирмы-поставщика.
В настоящее время на компьютерном рынке существует довольно большое количество фирм, выпускающих отдельные модули для персональных компьютеров. Выпускаемые модули отличаются друг от друга отдельными параметрами, например строимостью, качеством, надежностью, техническими параметрами и другими. Дополнительные отличия в множество однотипных модулей вносят фирмы-поставщики и магазины. Один и тот же модуль, изготавливаемый одной и той же фирмой в различных магазинах может иметь различную стоимость, которая включает помимо оптовой цены фирмы-изготовителя и накладные расходы магазина. К тому же продаваемый модуль может иметь различную по срокам гарантию и различное вид рекламации и гарантийного обслуживания, что также сказывается на цену модуля.
При выборе модулей для компьютера следует учитывать их совместимость, так как не каждый модуль может свободно стыковаться с любом другим. Например материнская плата., обычно включает разъем для процессора, в соответствии с которым и следует приобретать процессор.
Вполне очевидно также, что покупку всех модулей следует производить в малом количестве магазинов, максимум в двух или в трех, чтобы сократить накладные расходы при гарантийном обслуживании и упростить процесс оплаты и контроля качества покупаемых товаров.
Все разнообразие модулей, предлагаемых в рекламных проспектах и журналах, позволяет собрать огромное количество персональных компьютеров, имеющих практически одинаковые основные технические характеристики, но отличающихся друг от друга стоимостью и другими дополнительными параметрами. Отсюда возникает актуальная практическая задача, среди всего многообразия предлагаемых компьютерных модулей выбрать такие, чтобы собранный из этих модулей компьютер имел минимальную стоимость и отвечал дополнительным требованиям.
Рассмотрим более подробно задачу выбора оптимального варианта персонального компьютера. Основными составляющими модулями персонального компьютера считаем следующие:
1 — материнская плата с набором микросхем «чипсетом» ,.
2 — процессор (CPU),.
3 — оперативная память (RAM),.
4 — монитор,.
5 — видеокарта,.
6 — накопитель на жестком магнитном диске (HDD),.
7 — считыватель лазерных компакт-дисков с контроллером (CD ROM),.
8 — модем.
Все эти модули в дальнейшем будем называть элементами технической системы, персонального компьютера. Все элементы присутствуют на рынке в различных реализациях, которые зависят не только от их технических характеристик, но и от фирм изготовителя и поставщика.
Рассмотрим контролируемые параметры технической системы. Параметр, который используется в качестве целевой функции, т. е. значение которого должно быть минимизировано в процессе выбора оптимального варианта технической системы, является стоимостью персонального компьютера. Стоимость будем определять в виде суммы стоимостей отдельных модулей. 8 min /о (х) = min У^ toi (xj), (6.1) г=1 где xi — номер реализации г-го модуля персонального компьютера, toi (xi) ~ стоимость ж^-й реализации г-го модуля, г — 1,., 8.
Вторым контролируемым параметром технической системы выбираем параметр надежности. В качестве измеряемого параметра надежности технической системы определяем величину обратную средней наработки на отказ или интенсивность отказов 8 1 tn (%i) ~ интенсивность отказов аз^-й реализации ¿—го модуля персонального компьютера, г = 1,., 8, — заданная интенсивность отказов персонального компьютера.
Третьим контролируемым параметром технической системы считаем ее эффективность. Под эффективностью понимаем сумму эф-фективностей каждого из модулей персонального компьютера. Эффективность модуля определяется по результатам тестирования, которые периодически публикуются в компьютерных журналах (см. например «Компьютер пресс»). При определении эффективности модуля производится сравнительный анализ его различных реализаций по времени выполнения теста. Наихудшей реализации модуля придается единичное значение, а остальным реализациям модуля присваиваются величины от нуля до единицы, соответствующие отношению времени работы данной реализации к времени работы наихудшей реализации модуля. Эффективность всего персонального компьютера определяем суммированием эффективностей его модулей. 8.
2(х) = < /*, (6.3) г=1 где t2i (x{) — эффективность а? г-й реализации г-го модуля персонального компьютера, г = 1,., 8, — заданная эффективность персонального компьютера.
При выборе оптимального варианта персонального компьютера необходимо учитывать особенности соответствия материнской платы и процессора. В настоящее время процессора и материнские платы выпускаются с различными типами разъемов наиболее популярные из которых — это Socket-7, Slot-1, Socket-370, Slot-A, FC-PGA и др. Придадим каждому типу разъема соответствующий номер, тогда номер разъема будем считать дополнительным параметром модулей персонального компьютера, процессора и материнской платы. При выборе оптимального варианта персонального компьютера необходимо выполнение логического ограничения, которое заключается в том, что, если реализация процессора персонального компьютера имеет какой-то номер разъема, то и материнская плата должна иметь такой же номер разъема. Формально данное ограничение запишем согласно рекомендациям, выработанным в разделе 5 в виде многомерного полинома, з (х) = (iai (®i) — tZ2{x2)f > 0, (6.4) где ?31 (xi) — номер разъема процессора реализации где ?32(^2) -номер разъема материнской платы реализации ж2. Условие (6.4) выполняется только при совпадении номеров разъемов у материнской платы и процессора.
Следующим требованием к выбору оптимального варианта технической системы, персонального компьютера является требование, заключающееся в том, чтобы все реализации модулей приобретались не более, чем в двух магазинах. Для того чтобы учесть это требование поставим в соответствие с каждым магазином, где будут приобретаться модули персонального компьютера, числовой номер. Этот номер будет очередным параметром каждого модуля персонального компьютера. Сформулируем требование в виде логического высказывания, получаем, что, если г-й модуль, г > 1, не приобретается в магазине, в котором приобретается первый модуль, то остальные модули должны приобретаться либо в магазине, где приобретается первый модуль, либо в магазине, где приобретается г-й модуль. Запишем данное логическое ограничение в виде многомерного полинома в соответствие с технологией представления логических высказываний в виде полиномов, описанной в разделе 5.
4(х) = X х (]Г — и^хг))2^^) — и{(хг))2 < 0, (6.5) й=г+1 / где — номер магазина, где приобретается реализация Х{ г-го модуля персонального компьютера, г — 1,., 8.
В результате выбор оптимального варианта персонального компьютера сводится к задаче (6.1)-(6.5) дискретной оптимизации с полиномиально табличными функциями. Для решения данной задачи проведем бимонотонное разложение всех функций задачи, для этого первоначально представим все исходные таблицы в виде разности двух монотонно неубывающих таблиц относительно номеров строк таблиц с неотрицательными значениями параметров элементов, м (3г) = — ?ы (Яг)? (б.б) где? йг (агг-), 1ы{х1) — монотонно неубывающие неотрицательные таблицы, к = 0,., 4, г — 1,., 8. Далее согласно методике, описанной в разделе 2.2 подставим полученные монотонно неубывающие таблицы в функции fj (х), 3 = 0,., 4, и представим эти функции в виде разности двух монотонно неубывающих функций. В итоге получим следующие функции бимонотонного разложения: 8 г=1 8 (6.8) г=1 где? = 0,1,2,3.
Для полиномиально табличной ограничивающей функции (6.4) имеем следующие функции бимонотонного разложения:
81(х) =*|1(яя) +*11(®1) +*12(®2) + §-2(х2)+.
2131(х1){32(х2) + 2*31 (*1)?з2(Я2), (6.9) зг (х) = 2г31(х1)г31(х1) + 213 г (х1){32(х2)+.
2Ц2(х2)132(х2) +2131(х1)г31(х1). (6.10).
Бимонотонное разложение полиномиально табличной ограничивающей функции (6.5) можно выполнить, используя соотношение (2.18) специально предназначенное для этого. Однако с целью простоты вычислительной реализации используем в данном операции над бимонами, описанными в разделе 2.5, и значения функций разложения получаем алгоритмическим путем без вывода их аналитических выражений.
АЛГОРИТМ 6.1. Вычисление первой функции /41 (х) бимонотон-ного разложения ограничивающей функции Д (х).
Шаг 0. Задано бимонотонное разложение скалярных табличных функций t4i (xi) = ?4г (а?г-) — ?4г (жг), г — 1,., 8. Присваиваем П = ?41(371), Г2 = ?41 (яз.) — Обнуляем основную сумму я = 0. Устанавливаем индекс, соответствующий номеру модуля г = 2.
Шаг 1. Обнуляем накопители сумм 51 = 0, = 0. Присваиваем.
91 = *4г (®г)> 92 = ¿-4"(ач).
Шаг 2. Вычисляем с помощью операций над бимонами [91, <72] = [п + 92, г2 + д1]2, к = 1 + 1. Шаг 3. вх = ик (хк), «2 = ?4.
Шаг 4. Выполняем операции над бимонами р, р2] = [в! + «2 + 01]2, [ге!, г*2] = [в! + г2, з2 +п]2, [д1,д2] = ["ъ «г].
Шаг 5. Накапливаем суммы ?1 = $ 1 + #1, $ 2 = 82 + 92-Шаг 6. Если к < гг, то переходим на шаг 4. Шаг 7. Накапливаем основную сумму 5 = 5 + 92 $ 2.
Шаг 8. Если I <п — 1, то переходим на шаг 1, иначе /41 (х) = в и завершаем вычисления.
АЛГОРИТМ 6.2. Вычисление первой функции /42(х) бимонотон-ного разложения ограничивающей функции /4 (х).
Шаг 0. Задано бимонотонное разложение скалярных табличных функций йг (а?г) = ?4г (#г) -?4г (^г')5 ® = 1,., 8. Присваиваем П — ?41(^1)? ?2 — ?41(^1) — Обнуляем основную сумму 5 = 0. Устанавливаем индекс, соответствующий номеру модуля г = 2.
Шаг 1. Обнуляем накопители сумм = 0, = 0- Присваиваем д = *4г (®-«)» 02 = ?4г (^г).
Шаг 2. Вычисляем с помощью операций над бимонами, = [г! + д2-Г2 +д]2, к = г + 1.
Шаг 3. й! ¦ ик (хк), в2 =.
Шаг 4. Выполняем операции над бимонами [р1, — [^1 +#2? «2 + #1]2, [г/1, гг2] = ["1 + г2,$ 2 + Г1]2, [51,02] = ["1, «2][ггь и2].
Шаг 5. Накапливаем суммы 51 = «1 + 52 = з2 + д2.
Шаг 6. Если & < п, то переходим на шаг 4.
Шаг 7. Накапливаем основную сумму з = в + д>152 + д2"1.
Шаг 8. Если г < п — 1, то переходим на шаг 1, иначе /42(х) = 5 и завершаем вычисления.
В результате работы алгоритмов получаем численные значения функций /41 (х), /42(х) бимонотонного разложения ограничивающей функции /4(х), без их аналитического представления.
В результате задачу выбора оптимального варианта персонального компьютера (6.1)-(6.4) можно представить в следующем виде: тЬ{/01(х)-/02(х)}, (6.11) лМ-Ых)</-, (6.12).
Для задачи в данной постановке используем алгоритмы выбора оптимального варианта технической системы, представленные в разделе 3.
Рассмотрим конкретный пример, когда каждый модуль персонального компьютера имеем по восемь реализаций, тх =. — тв = 7. Пусть для выбираемого персонального компьютера выдвинуты следующие требования:
— интенсивность отказов всего персонального компьютера должна составлять величину не более = 7 ¦ 10~Б час-1,.
— эффективность персонального компьютера не должна превышать величины =5.5,.
— процессор и материнская плата должны иметь одинаковые разъемы под процессор,.
— все модули должны приобретаться не более, чем в двух магазинах.
Необходимо из реализаций основных модулей персонального компьютера выбрать такие, чтобы они удовлетворяли установленным требованиям и при этом стоимость компьютера была минимальной.
Исходные данные для задачи представлены в таблицах 6.1−6.34. В этих же таблицах указаны бимонотонные разложения таблиц. Всего согласно исходным данным имеем.
Х| = 88 = 16 777 216 вариантов компьютеров.
Оптимальный вариант персонального компьютера выбирался с помощью алгоритма 3.11 многомерного деления пополам с лексикографическим перечислением. В результате вычислений был выбран следующий оптимальный вариант х= (5,5,5,0,4,4,5,1).
Стоимость оптимального варианта персонального компьютера составила о (х) = 728 условных единиц (у.е.).
Интенсивность отказов оптимального варианта персонального компьютера составила величину i (x) = 6.92 • 10~5 час" «1.
Эффективность оптимального варианта персонального компьютера составила величину.
2(х) =5.43 < /2* =5.5.
Процессор и материнская плата оптимального варианта персонального компьютера имеют один и тот же разъем под номером 1, что соответствует разъему Socket-7.
Все реализации модулей оптимального варианта персонального компьютера приобретаются в двух магазинах под номерами 2 и 3. Магазины для приобретения элементов составили следующий вариант (3,2,2,2,3,3,2,2,).
В магазине под номером 2 приобретаются процессор, оперативная память, монитор, считыватель лазерных компакт-дисков с контроллером и модем. В магазине под номером 3 приобретаются материнская плата с набором микросхем «чипсетом», видеокарта и накопитель на жестком магнитном диске.
Всего алгоритм для поиска оптимального варианта персонального компьютера проверил 273 301 вариант, остальные были отсеяны в результате неудовлетворения интервальным ограничениям, полученным с помощью бимонотонного разложения функций. Таким образом проверке подверглись только 1.6% вариантов. Эффективность работы алгоритма составила Ре = 61.387. Время вычислений на персональном компьютере с процессором 5×86, 133 Mhz, составило 438.8 с.
Стоимость в у.е. реализаций материнской платы.
ЗАКЛЮЧЕНИЕ
.
1. Разработаны впервые метод и алгоритмы решения крупной научно практической проблемы выбора оптимального варианта технической системы. Метод позволяет решать задачи выбора оптимального варианта технической системы с таблично заданными функциями, используя бимонотонное разложение целевой и ограничивающих функций. Ранее подобные задачи решались либо методом перебора, либо с использованием особых свойств функций.
2. Проведено исследование бимонотонного разложения функций с точки зрения получения точных оценок предельных значений функций на интервалах частично упорядоченного множества вариантов. Показано, что бимонотонное разложение функций неоднозначно, и в зависимости от вида разложения могут быть получены различные оценки предельных значений функций. Доказано, каким образом возможно получение улучшенных оценок.
3. Введено определение минимального бимонотонного разложения функций, дающего неулучшаемые оценки предельных значений функций. Минимальное бимонотонное разложение имеет минимальные значения функций разложения среди всех других разложения на рассматриваемом интервале. Минимальное бимонотонное разложение для каждого интервала с точностью до постоянной единственно и дает наименьшую верхнюю и наибольшую нижнюю оценки предельных значений функций.
4. Получены и обоснованы необходимые и достаточные условия, которым должно удовлетворять минимальное бимонотонное разложение. Для того, чтобы бимонотонное разложение было минимальным необходимо и достаточно равенство нулю произведений всех первых разностей обеих функций разложения. Сформулирована проблема построения минимального бимонотонного разложения для различных функций.
5. Разработан метод построения бимонотонного разложения для полиномиально табличной функции. Доказано, что для получения более точных оценок предельных значений функций с помощью данного бимонотонного разложения необходимо построение минимального бимонотонного разложения таблиц, входящих в качестве аргумента в полиномиально табличные функции. Для построения минимального бимонотонного разложения произвольной табличной функции исходная таблица представляется в виде двух монотонно неубывающих таблиц, построчная разность которых дает значения исходной таблицы, причем в соседних строках одна из двух монотонно неубывающих таблиц имеет одинаковые значения.
6. Разработаны новые алгоритмы выбора оптимального варианта технической системы методом бимонотонного разложения функций. Алгоритмы включают построение интервалов на множестве вариантов и проверку для них оценок предельных значений функций с помощью бимонотонного разложения. Для построения интервалов используются схемы лексикографического перечисления, ветвей и границ и многомерного деления пополам. Получены оценки скоростей сходимости алгоритмов при условии равновероятного отсеивания всех рассматриваемых интервалов.
7. Разработаны новые методы выбора оптимального варианта технической системы в условиях неопределенности, а также при наличии ограничений запаса, неявных и логических ограничений. Методы также используют бимонотонное разложение всех функциональных зависимостей, описывающих ограничения и критерий оптимальности.
8. С помощью разработанных алгоритмов метода бимонотонного разложения решены прикладные задачи выбора оптимального варианта вычислительной системы синтеза оптимального программного закона управления автотранспорта в сети автодорог. Обе решенные задачи имеют актуальное значение и содержат описания целевой функции и ограничений в виде сложных нелинейных полиномиально табличных функций. Применение разработанных алгоритмов позволило значительно снизить число проверяемых вариантов.
Разработанный метод позволяет находить оптимальный вариант технической системы при таблично заданных исходных данных. Табличная организация данных является наиболее часто используемой в практических задачах, возникающих на этапах создания технических систем. Неупорядоченные табличные данные не позволяли ранее использовать для решения практических задач известные эффективные методы оптимизации, так как таблично заданные функции имеют наиболее общий характер. Поэтому разработка специального метода для решения задач с таблично заданными функциями является важным научно практическим результатом.
Метод решения проблемы выбора оптимального варианта технической системы использует бимонотонное разложение целевой и ограничивающих функций. Данный подход позволяет не рассматривать особые свойства функций, типа линейности, сепарабельности, унимодальности, выпуклости и др. Теоретические исследования бимонотонного разложения функций, проведенные в работе, открывают новое направление в области математического программирования по его применению к различным задачам оптимизации.
