TY - JOUR TI - Алгоритм поиска оптимального варианта огранки драгоценного камня максимальной массы с заданными отклонениями от симметричности T2 - Бизнес-информатика IS - Бизнес-информатика KW - выпуклый многогранник KW - комбинаторная структура KW - вписанный многогранник KW - огранка драгоценного камня KW - отклонение от симметричности KW - задача нелинейного программирования KW - солвер AB - Д.С. Кокорев - аспирант лаборатории распределенных вычислительных систем, Институт проблем передачи информации им. А.А. Харкевича РАН     Адрес: 127051, г. Москва, Большой Каретный пер., д. 19 стр. 1E-mail: korvin-d@yandex.ru      В статье рассматривается задача нахождения многогранников заданной формы внутри других невыпуклых многогранников. Данная задача является частным случаем третьей части 18-й проблемы Гильберта. Она имеет практическое применение в компьютерном моделировании трехмерных объектов, автономном перемещении роботов, ювелирной промышленности. Эта математическая задача интересна с точки зрения ее применения для нахождения огранок драгоценных камней внутри неограненного камня.      В статье предлагается метод поиска вписанных многогранников, основанный на сведении данной задачи к задаче нелинейного программирования и решения ее с помощью готовых программных средств. Основной идеей является то, что задача легко описывается в терминах нелинейного программирования. Целевой функцией является объем искомого многогранника. Ограничения включают в себя сохранение комбинаторной структуры, содержание многогранника внутри другого, выпуклость и дополнительные ограничения, необходимые для практических целей.      В статье рассмотрены две реализации алгоритма: клиент-серверное приложение и локальное приложение. Приведены их достоинства и недостатки. Алгоритм описан не только с математической точки зрения, но и с точки зрения некоторых его прикладных особенностей. По сравнению с предыдущими статьями автора добавлен метод, который позволяет решать невыпуклый случай задачи, что является значительным шагом с математической точки зрения. Кроме того, это позволяет использовать алгоритм на всех этапах огранки драгоценных камней. В конце статьи даны актуальные оценки эффективности и времени работы алгоритма, в том числе на слабых процессорах, и описаны планы дальнейшего развития алгоритма. Работа выполнена при поддержке Российского научного фонда (проект 16-11-10352).  AU - Д. С. Кокорев UR - https://bijournal.hse.ru/2017--2 (40)/208605851.html PY - 2017 SP - 40-46 VL -