Введение 3
1 Постановка задачи 4
2 Решение задачи 6
3 Существующие решения 12
3.1 Реверсивный поиск 12
3.2 Алгоритм, основанный на единственности разложения 14
3.3 Двойственный алгоритм 15
4 Численные эксперименты 16
Заключение 18
Список литературы 19
Приложение 21
Задача поиска крайних точек суммы по Минковскому конечных многогранников естественным образом возникает во многих приложениях: например, в численных алгоритмах недифференцируемой оптимизации, основанных на квазидифференциальном и кодифференциальном исчислениях [1], при решении систем n алгебраических уравнений с n переменными [2], в задаче размещения спутниковых антенн [3], в оптимизации расстановки шаблонов при вырезании деталей из листов металла [4], в некоторых задачах вычислительной биологии [5], в анализе допусков при проверке, удовлетворяет ли сборка деталей задаваемым ограничениям [6].
Существующие известные методы [7-9] имеют свои недостатки и преимущества в плане необходимых входных данных и скорости работы. Также приведено сравнение эффективности существующих методов и метода, предлагаемого в данной работе.
Рассматриваемый метод основан на результатах работы [10]. Также приведена его программная реализация на языке МАТГАВ.
В работе решена задача о поиске крайних точек суммы по Минковскому ограниченных многогранников. Приведён сравнительный анализ существующих алгоритмов и предложенных в данной работе, даны рекомендации по их выбору.
На языке MATLAB написана программная реализация предложенных алгоритмов.
