Содержание к диссертации
Введение
1 Постановка задачи. Необходимый математический аппарат 10
1.1 Состояние проблемы
1.2 Свойства пространства булевых переменных 19
1.3 Классы псевдобулевых функций 22
1.4 Постановка задачи оптимизации 25
1.5 Свойства множества допустимых решений задачи
1.6 Идентификация свойств псевдобулевых функций 28
1.6.1 Применение регулярного алгоритма оптимизации для идентификации свойств
1.6.2 Идентификация свойств посредством квадратичной 29 аппроксимации
1.6.2.1 Способы квадратичной аппроксимации 31
псевдобулевых функций
1.6.2.2 Определение свойств квадратичной функции 32
Выводы 34
2 Эффективность известных методов решения задач условной псевдобулевой оптимизации 36
2.1 Составление обобщенной функции со штрафом
2.2 Регулярные точные алгоритмы безусловной оптимизации 38
2.3 Локальный поиск 40
2.3.1 Алгоритмы локального поиска для оптимизации псевдобулевых функций
2.3.2 Локальный поиск для условной оптимизации 46
2.4 Схема метода ветвей и границ 49
2.4.1 Общая схема метода ветвей и границ
2.4.2 Алгоритм метода ветвей и границ для задачи с неявно заданными функциями 51
2.4.3 Приближенные алгоритмы метода ветвей и границ 55
2.4.4 Условная оптимизация изотонных псевдобулевых функций 56
Выводы 59
3 Регулярные точные процедуры оптимизации, реализующие свойства классов задач 61
3.1 Классы задач условной псевдобулевой оптимизации
3.1.1 Свойства функций ограничений 62
3.1.2 Свойства целевых функций 65
3.2 Алгоритмы псевдобулевой оптимизации со структурно монотонными целевыми функциями и функциями ограничений 67
3.3 Алгоритмы псевдобулевой оптимизации с монотонными функциями ограничений 72
3.3.1 Случай монотонной целевой функции
3.3.2 Случай унимодальной целевой функции 76
3.3.3 Случай целевой функции общего вида 79
3.4 Алгоритмы псевдобулевой оптимизации с унимодальными функциями ограничений 81
3.4.1 Случай монотонной целевой функции
3.4.2 Случай унимодальной целевой функции 84
3.4.3 Случай целевой функции общего вида 86
3.5 Алгоритмы псевдобулевой оптимизации с функциями ограничений общего вида 87
3.5.1 Случай монотонной целевой функции
3.5.2 Случай унимодальной целевой функции 89
3.5.3 Случай целевой функции общего вида 90
3.6 Системьгограничений 91
Выводы 92
4 Приближенные алгоритмы условной псевдобулевой оптимизации 94
4.1 Случайный поиск граничных точек
4.2 Гриди алгоритмы 9
4.2.1 Основные принципы и обоснование гриди эвристики
4.2.2 Гриди алгоритмы для условной псевдобулевой оптимизации 100
4.2.3 Оценка точности гриди алгоритмов 103
4.3 Адаптивный случайный поиск 105
4.4 Экспериментальные исследования приближенных алгоритмов 108
Выводы 111
Заключение 113
Список использованных источников 115
- Свойства пространства булевых переменных
- Локальный поиск для условной оптимизации
- Алгоритмы псевдобулевой оптимизации со структурно монотонными целевыми функциями и функциями ограничений
- Гриди алгоритмы для условной псевдобулевой оптимизации
Введение к работе
Актуальность темы. Решение большинства реальных задач в области принятия решений требует формализации рассматриваемой ситуации, в которой следует осуществить выбор, в виде оптимизационной задачи определенного класса. Оптимальный выбор одной из нескольких допустимых альтернатив по определенному критерию соответствует присвоению переменным формализованной задачи конкретных значений из области допустимых значений. Часто переменные могут принимать лишь одно из двух значений - ноль или единица. Соответствующие задачи называются задачами оптимизации с булевыми переменными или задачами псевдобулевой оптимизации.
Как правило, при решении практических проблем исследователь имеет дело с конкретной постановкой задачи условной псевдобулевой оптимизации. Данная работа направлена на построение алгоритмов решения классов задач, покрьшающих все множество задач условной псевдобулевой оптимизации. Кроме того, большинство известных методов предполагает задание целевых функций и ограничений в виде алгебраических выражений, в то время как во многих реальных задачах часть функций либо все функции заданы алгоритмически, что делает невозможным применение к ним стандартных алгоритмов и требует разработки поисковых процедур оптимизации. В то же время анализ многих практических задач, сводящихся к задачам псевдобулевой оптимизации, позволяет выявить в них некоторые особенности в виде конструктивных свойств, присущих как целевым функциям, так и ограничениям, накладываемым условиями задачи. Следует также отметить, что при решении конкретной задачи полезно иметь информацию об эффективности алгоритмов, что дает возможность подобрать алгоритм с подходящей трудоемкостью.
Из всего выше сказанного следует необходимость разработки эффективных методов и алгоритмов решения классов задач псевдобулевой оптимизации с неявно заданными функциями, а также построения аналитических оценок трудоемкости алгоритмов. Для этого, прежде всего, необходимо детальное изучение свойств пространства булевых переменных и псевдобулевых функций.
Таким образом, высокая сложность и практическая значимость задач условной оптимизации с булевыми переменными наряду с необходимостью построения формального математического аппарата и его теоретической значимостью обусловили выбор темы диссертационного исследования и определили се ріиуодищсть.
. 1^
3 '
Цель работы - обоснование, построение и исследование методов решения задач условной псевдобулевой оптимизации с алгоритмически заданными функциями.
Поставленная цель определила следующие основные задачи исследования.
-
Проведение классификации задач условной псевдобулевой оптимизации и исследование свойств множеств допустимых решений вьщеленных классов задач.
-
Построение процедуры идентификации свойств алгоритмически заданных псевдобулевых функций.
-
Исследование эффективности известных методов решения задач условной псевдобулевой оптимизации.
-
Выявление и исследование свойств различных классов задач условной псевдобулевой оптимизации.
-
Разработка точных регулярных поисковых процедур, использующих особенности конкретных классов задач, с рекордными оценками трудоемкости.
-
Разработка малотрудоемких приближенных алгоритмов решения задач вьщеленных классов с априорными оценками точности.
Методы исследования. Аппарат теории множеств, теории вероятностей, исследования операций, дискретной оптимизации, математического программирования. Элементы теории вычислительной сложности.
Научная новизна работы:
-
Доказано, что оптимальное решение задачи условной оптимизации монотонной псевдобулевой функции находится среди крайних точек, вьщеленных определенным образом из множества граничных точек допустимой области; это свойство явилось основой для обоснования и построения точных и приближенных алгоритмов.
-
Для задач условной псевдобулевой оптимизации с унимодальными функциями ограничений доказана связность множества допустимых решений, что позволило установить ограниченность числа крайних точек для соответствующих классов задач.
-
Впервые разработана процедура идентификации свойств алгоритмически заданных псевдобулевых функций посредством аппроксимации функций квадратичными полиномами, позволяющая соотнести рассматриваемую задачу с одним из классов задач.
-
Впервые аналитически доказано преимущество по трудоемкости алгоритма локального поиска с переходом по первому улучшению по сравнению с алгоритмом наискорейшего спуска для оптимизации монотонных и слабо немонотонных псевдобулевых функций; обосно-
ван выбор обобщенной штрафной функции для применения локальной оптимизации к поиску граничных точек.
-
Построена новая процедура вычисления нижних границ подмножеств решений задачи для метода ветвей и границ без использования релаксации и методов непрерывной оптимизации, позволяющая использовать метод ветвей и границ для решения задач с алгоритмически заданными функциями.
-
Разработаны новые регулярные точные поисковые алгоритмы с аналитическими оценками трудоемкости для решения задач условной псевдобулевой оптимизации, реализующие информационную сложность классов задач.
-
Построены новые приближенные алгоритмы с аналитическими оценками эффективности для условной оптимизации монотонных псевдобулевых функций, предназначенные для решения задач больших размерностей.
Теоретическая и практическая ценность работы Теоретическая ценность работы для системного анализа заключается в том, что в ней изучены свойства выделенных классов задач условной псевдобулевой оптимизации, построены и теоретически обоснованы точные и приближенные алгоритмы их решения. Вьщеленные классы задач покрывают все множество задач условной псевдобулевой оптимизации. Разработанные алгоритмы применимы для решения любых практических задач, сводящихся к задачам оптимизации псевдобулевых функций. В частности, построенные алгоритмы были апробированы при решении задачи оптимизации загрузки технологического оборудования предприятия и задачи оптимизации систем отказоустойчивого программного обеспечения. Основные защищаемые положения:
-
Построенный математический аппарат идентификации свойств псевдобулевых функций позволяет сопоставить задачу условной псевдобулевой оптимизации с одним из выделенных классов задач.
-
Алгоритм локального поиска с выбранной обобщенной штрафной функцией, системой окрестностей и способом просмотра окрестности при решении задач условной псевдобулевой оптимизации эффективнее известных алгоритмов локального поиска.
-
Построенная схема ветвления по подкубам исключает неперспективные подкубы при минимальных вычислительных затратах; основанный на этой схеме алгоритм метода ветвей и границ не требует явного задания функций.
-
Регулярные точные алгоритмы решения выделенных классов задач условной псевдобулевой оптимизации, построенные с учетом выявленных свойств, имеют существенное преимущество по быстродействию перед полным перебором; построенный алгоритм оптимизации монотонных псевдобулевых функций с монотонными ограничениями является неулучшаемым по трудоемкости.
-
Алгоритм случайного поиска граничных точек с адаптацией, представляющий собой объединение случайного поиска граничных точек и гриди эвристики, является более эффективным, чем каждый
из них отдельно.
Апробация работы. Основные положения и отдельные результа
ты диссертационной работы докладывались и обсуждались на всерос
сийских конференциях «Решетневские чтения» (2001-2003 гг.), на
международной научно-практической конференции "САКС-2001" (г.
Красноярск), на XL международной научной конференции "Студент и
научно-технический прогресс" (г. Новосибирск) в 2002 году, на V ме
ждународном симпозиуме «Интеллектуальные системы
INTELS'2002» (г. Калуга), на всероссийских конференциях «Туполев-
ские чтения» (г. Казань) в 2002-2003 гг., на всероссийской научно-
технической конференции «Совершенствование технологии поиска и
разведки, добычи и переработки полезных ископаемых» (г. Красно
ярск) в 2003 году, на всероссийской научной конференции «Королев
ские чтения» (г. Самара) в 2003 г., на всероссийской научной конфе
ренции «Наука. Технологии. Инновации» (г. Новосибирск) в 2003 г.
Основные положения диссертационной работы и работа в целом обсуждались на научных семинарах кафедры системного анализа и исследования операций Сибирского государственного аэрокосмического университета.
Публикации. По теме диссертации автором опубликовано девятнадцать работ.
Структура и объем работы. Диссертация изложена на 131 странице машинописного текста. Состоит из введения, четырех глав, заключения и списка использованных источников, содержащего 156 наименований.
Свойства пространства булевых переменных
Вещественные функции, определенные на множестве булевых переменных, по аналогии с булевыми функциями принято называть псевдобулевыми [111]. Соответственно задачи оптимизации- псевдобулевых функций называются задачами псевдобулевой оптимизации.
Многие проблемы в экономике, банковском деле, промышленности, а также проблемы управления сложными: техническими объектами приводят к необходимости решения задач условной оптимизации с булевыми переменными. В [27] рассматривается проблема автоматизации = планирования товарного ассортимента торговых предприятий, которая сводится к решению многокритериальной задачи псевдобулевой: оптимизации с ограничениями. Задача нахождения-набора кредитных заявок (задача формирования кредитного портфеля банка) в [26] решается как поток задач условной1, оптимизации псевдобулевых функций. Большое внимание в последнее время уделяется задаче оптимального проектирования структуры отказоустойчивых систем управления с использованием подхода мультиверсионного программирования, формулируемой в виде задачи условной псевдобулевой оптимизации [28, 65, 66, 72, 120, 121]. Для ее решения-построен ряд оптимизационных моделей, в которых максимизируется критерий надежности с учетом стоимостного ограничения. Структура определяется набором булевых переменных, по которым и происходит максимизация критерия. В основном для решения таких задач нашли применение алгоритмы случайного поиска, например, алгоритмы схемы МИВЕР [2 47, 140, 141]. В некоторых работах [36, 43, 46, 130] были предприняты попытки построения регулярных алгоритмов.
Псевдобулевые функции играют важную роль в оптимизационных моделях в различных областях, таких как, проектирование [Г, 58; 69,..81, 149], теория надежности [137], теория-, вычислительных, систем [118], статистика (классификация) [142, 143], экономика [112], финансы [116, 125, 126], менеджмент (выбор проекта [153]), исследование операций, [103!, 139,. 151], дискретная математика (оптимизация- на графах [94,. 104, ГП ].),.. промышленность (календарное планирование и составление расписания [12, 14, 67,.84).88,.123-.148]);
Помимозадач оптимизации; псевдобулевые функции также появились во многих других: моделях, представляющих интерес в настоящее время- Они. составляют, к примеру, основной объект исследования в теории кооперативных игр,, где они рассматриваются; как характеристические функции игр с побочными платежами [73; 90; 108, 110, 131, 133; 146]: Они встречаются в. комбинаторной теории как функции ранга матроидов. [86 156] или как функции; связанные с определенными; параметрами графа, такими как. число стабильности, хроматическое число и т.д. [71, 94, 107, 132, 147]
Впервые задачи: псевдобулевой оптимизации подробно исследовались в, монографии [111]. В- этой- работе также были разработаны, методы решения аналитически заданных задач псевдобулевой оптимизации. В работе- Х79] псевдобулевые функции; рассматриваются; как функции множеств; т.е:-. функции; отображающие: семейство подмножеств конечного исходного множества во множество действительных чисел. Функциш множеств? зачастую: рассматриваются заданными алгоритмом, способным выдавать их значения: для любого подмножества заданного конечного исходного множества. В; некоторых: задачах; функция: множества может быть определена аналитическим выражением, что является весьма благоприятным случаем. Явное задание функций множеств делает возможным применение большого числа методов для: их анализа и оптимизации. Считается, что любая функция множеств; определенная на конечном исходном множестве, допускает аналитический способ задания. Однако в некоторых случаях определение аналитического выражения может быть значительно более трудоемкой процедурой, чем решение исходной задачи. Эта работа сосредоточена на тех функциях множеств, которые определены на конечном исходном множестве, представляющем собой множество булевых переменных, и не имеют известного аналитического задания. Особое внимание уделено специальным классам - монотонные и унимодальные псевдобулевые функции. Известно несколько эффективных схем для решения задач, в которых целевая функция и ограничения заданы аналитическими; выражениями. Это алгебраические методы [13, 21, 29, 30, 61, 70, 79, 85, 87, 89, 105, 109, 114, 129, 134, 135, 155] (наиболее известный - базовый,алгоритм Хаммера [79, 111]), в том числе методы линеаризации [60, 68, 100, 115, 152], методы квадратичной оптимизации [76, 77, 78, 80, 82, 106, 113]; различные методы с применением релаксации [45, 54,136]; Но в практических задачах очень часто целевая функция, а иногда и ограничения заданы алгоритмом или наблюдаются на выходе реальной системы. Это обстоятельство исключает возможность практического применения стандартных процедур математического программирования, опирающихся на известную структуру и-вид целевой функции и ограничений, что указано в монографии [3]. Именно для: таких случаев разрабатываются, поисковые методы. Обратим внимание на общую структуру поискового метода [19, 48]. Алгоритм решения задачи оптимизации представляет собой последовательную процедуру, имеющую рекуррентный характер. Это означает, что процесс поиска состоит из повторяющихся этапов, каждый из которых определяет переход от одногСР-решения к другому, лучшему, что и образует процедуру последовательного улучшения решения:
Локальный поиск для условной оптимизации
Оценки трудоемкости этого алгоритма для случая монотонных унимодальных псевдобулевых функций приведены в [52]. Но нет оценок точности подобных алгоритмов локального поиска при оптимизации полимодальных немонотонных псевдобулеых функций. Найденный локальный оптимум может сколь угодно отличаться от истинного решения задачи.
Ещё один оч нь важный вопрос - сколько следует взять точек для мультистарта и, самое главное, каким образом, их следует распределять в пространстве булевых переменных? Один из способов - это случайный наброс точек. Если число стартовых точек небольшое (т.е. существуют жесткие ограничения на ресурсы), то эти точки могут оказаться расположенными близко друг к другу. Тогда рациональнее использовать равномерное распределение стартовых точек в пространстве булевых переменных.
Но расположить несколько стартовых точек на одинаковых расстояниях друг от друга не представляется возможным. В связи с этим разработан следующий подход для выбора точек мультистарта. Допустим, требуется расположить 1 п точек. Пространство булевых переменных разбивается на / секторов с примерно равным количеством точек, причем таким образом, чтобы любой из уровней начальной точки находился только в одном из секторов. Каждый сектор в итоге должен состоять из одного или нескольких последовательных уровней. Количество уровней в секторе зависит от номеров этих уровней.
Метод ветвей и границ основан на идее разумного перечисления всех допустимых точек комбинаторной задачи оптимизации.
Впервые метод ветвей и границ был предложен Land и Doig [124] в 1960 году для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его "второе рождение" связано с работой [128], посвященной задаче коммивояжера. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей;и, границ и различным его модификациям. Столь большой успех объясняется тем, что авторы первыми обратили внимание на широту возможностей метода, отметили важность использования специфики задачи и сами воспользовались, спецификой задачи коммивояжера.
В основе метода ветвей и границ лежит идея последовательного разбиения множества: допустимых решений на подмножества. На каждом шаге метода элементы разбиения подвергаются проверке для выяснения, содержит данное подмножество оптимальное решение или нет. Проверка осуществляется посредством вычисления оценки снизу для целевой функции на данном подмножестве. Если оценка снизу не лучше рекорда — наилучшего из найденных решений, то подмножество может быть отброшено. Проверяемое подмножество может быть отброшено еще ив том случае, когда в нем удается: найти наилучшее решение. Если значение целевой функции на найденном решении лучше рекорда, то происходит смена рекорда. По окончанию работы алгоритма рекорд является результатом его работы.
Если удается отбросить все элементы разбиения, то рекорд — оптимальное решение задачиГ тЗ противном, случае, из неотброшенных подмножеств выбирается наиболее перспективное (например, с наименьшим значением нижней оценки), и оно подвергается разбиению. Новые подмножества вновь подвергаются проверке и т.д.
Вычисление нижней границы является важнейшим элементом данной схемы. Очевидно, что именно использование специфических структурных особенностей задачи дает возможность построить работоспособный алгоритм ветвей и границ. Рассматривается применение схемы для решения оптимизационной задачи, в которой все переменные являются булевыми, а целевая функция и ограничение унимодальны и монотонны: где С(Х) и А(Х) - унимодальные и монотонно возрастающие от Xй = (х,...,х) псевдобулевые функции.
Наиболее часто используемый вариант применения схемы метода:ветвей и границ для решения задачи псевдобулевой оптимизации заключается в следующем [54, 99]. Решается задача непрерывной оптимизации (как. правило, симплекс-алгощітмом), являющаяся ослаблением исходной задачи, и получается решение X , которое в общем случае не будет булевым. После этого задачу разбивают на две подзадачи, добавляя два взаимоисключающих и исчерпывающих все возможности ограничения. Пусть, например, компонента х1, в X не булева. Тогда в соответствующих подзадачах появляются, ограничения х, = 0 и х[=1. Дальнейшее ветвление происходит подобным обраТшюй алгоритм может быть довольно эффективным для задач, в которых целевая функция и ограничение определены в явном виде [33]. В реальных задачах очень часто целевая функция задана алгоритмически, т.е. невозможно вычислить, значение функции в точке, не являющейся булевой. Поэтому возникла необходимость исследования других вариантов применения схемы.
Алгоритмы псевдобулевой оптимизации со структурно монотонными целевыми функциями и функциями ограничений
Сразу следует указать на то, что структурно монотонные функции являются частным случаем монотонных функций, но в практической оптимизации они не представляют такойчбольшой важности, как монотонные функции. Поэтому постановки задач псевдобулевой оптимизации, в которых функции являются структурно монотонными, и соответствующие алгоритмы не имеют самостоятельного значения как инструмент решения практических задач. Но класс1 структурно монотонных функций является весьма полезным средством при апробации новых подходов в псевдобулевой оптимизации и при исследовании эффективности алгоритмов.
Как будет показано в дальнейшем, оценка сверху трудоемкости алгоритма оптимизации: структурно монотонной псевдобулевой функции при структурно монотонном ограничении совпадает с оценкой сверху трудоемкости алгоритма оптимизации монотонной псевдобулевой функции при монотонном ограничении. Но-анализ алгоритма со структурно монотонными функциями позволяет построить оценки трудоемкости в среднем. В случае монотонных функций построение оценок трудоемкости в среднем наталкивается на принципиальные трудности, которые будут рассмотрены ниже. Это относится и к более общим классам задач.
Согласно свойствам 3.5, 3.8 и следствию 3.4 в случае, когда целевая функция C(JO и ф$щкция ограничения А{X) структурно монотонно возрастают от ХеВ , оптимальное решение задачи принадлежит подмножеству допустимых (крайних) точек уровня ОД ґ0), который удовлетворяет одному из требований: 1) существует недопустимое решение на уровне Ок(Х); 2) на уровне Ом(Х) нет допустимых решений.
Таким образом, если существует уровень, на котором есть как допустимые, так и недопустимые решения, то оптимальное решение находится среди допустимых решений этого уровня, так как на более высоких уровнях допустимых решений нет, а на низших уровнях все решения хуже. Если же такого уровня не существует, то оптимальное решение принадлежит уровню, наиболее удаленному от точки Х\ на котором (все) решения допустимы, при этом на следующем уровне все решения недопустимы.
Следует отметить, что наибольшее число допустимых решений, подозрительных на оптимальное решение данной задачи, N" card{Ok(Xa)\ = С , где Ок(Х) - уровень с оптимальным решением задачи. Легко увидеть, что max С = с]"/2\ где [а] - целая часть числа а .
Предлагаются два варианта решения задачи для случая структурной монотонности обоих функций. Первый алгоритм начинает поиск из начальной точки Х, находит уровень Ок(Х) с недопустимым решением и перебирает этот уровень. Если на нем обнаружены допустимые решения, то лучшее из них принимается за оптимальное. Если допустимых решений на просмотренном уровне нет, то оптимальным решением является наилучшее допустимое решение низшего уровня Ok_i(X) .
В другом-варианте алгоритм начинает работу из точки Xі, определяет уровень Ок(Х) с допустимым решением и просматривает все точки этого уровня. Если на й9м кроме допустимых существуют и недопустимые решения, то лучшее из доп тимых принимается за оптимальное. Иначе просматривается высший уровень Ot (X) на предмет обнаружения допустимых решений. Эти два варианта не имеют существенных преимуществ друг перед другом.
Гриди алгоритмы для условной псевдобулевой оптимизации
В результате диссертационного исследования разработан математический аппарат решения задач условной псевдобулевой оптимизации с алгоритмически заданными функциями. Получены аналитические оценки точности и трудоемкости построенных алгоритмов. Основные]результаты работы: 1. Выделены классы задач условной псевдобулевой оптимизации с алгоритмически """Заданными функциями, обладающими специальными свойствами; выделенные классы задач покрывают все множество задач условной псевдобулевой оптимизации. 2. Доказано, что для задачи псевдобулевой оптимизации с унимодальным ограничением множество допустимых решений является связным множеством: Среди множества граничных точек допустимых решений выделено подмножество определенным образом расположенных крайних точек, среди которых находится оптимальное решение задачи в случае монотонности целевой функции. 3. Построен: математический аппарат для идентификации свойств алгоритмически заданных псевдобулевых функций. 4. Обусловлен выбор обобщенной штрафной функции, системы окрестностей и способа просмотра окрестности для наиболее эффективного использования алгоритмов локальной оптимизации для поиска граничных точек. 5. Построен алгоритм схемы метода\ ветвей и границ для решения задачи условной оптимизации монотонных псевдобулевых функций без вычисления значений функций в точках, не являющихся булевыми, что делает его пригодным для задач с алгоритмически заданными функциями; предложенная схема ветвления по подкубам позволяет исключать неперспективные подмножества с минимальными вычислительными затратами. _ 6. Исследованы свойства выделенных классов задач, на основании которых построены регулярные точные поисковые алгоритмы и получены аналитические оценки их трудоемкости. Алгоритм для оптимизации монотонных псевдобулевых функций с монотонными ограничениями реализует информационную сложность класса задач и в этом смысле является неулучшаемым. 7. В результате сравнительного анализа алгоритмов случайного поиска граничных точек для решения различных классов задач показано, что прямые алгоритмы более эффективны для задач со связным множеством допустимых решений, а двойственные - при несвязном множестве допустимых решений. 8. Построены приближенные регулярные алгоритмы в соответствии с принципами гриди эвристики для задач оптимизации монотонных псевдобулевых функций с различными типами ограничений. Построенные гриди алгоритмы представляют собой полиномиальную приближенную схему. 9. Разработаны алгоритмы случайного поиска граничных точек с адаптацией для задач оптимизации монотонных псевдобулевых функций с различными типами ограничений, позволяющие находить су б оптимальное решение с большей точностью.
