ЭКОНОМИКА И МАТЕМАТИЧЕСКИЕ МЕТОДЫ, 2015, том 51, № 3, с. 117-125
МЕТОДЫ ОПТИМИЗАЦИИ
ОБ ОПТИМАЛЬНОМ ВЛОЖЕНИИ ТЕЛА В ОКТАЭДР
© 2015 г. А.А. Вотяков
(Москва)
Чтобы правильно оценить стоимость природного кристалла, надо знать, какие изделия можно изготовить из него. Говоря языком математики, в геометрическое тело, имеющее форму кристалла, необходимо вложить тело, имеющее форму изделия. Вложение бриллианта в октаэдр - это классическая проблема технологии производства ювелирных изделий, алгоритмы решения которой исследованы в настоящей работе. Задача вложения сведена к задаче линейного программирования. Осуществлена оценка сложности алгоритмов. Доказано, что сложность алгоритмов вложения тела в кристаллы, относящиеся к классу октаэдров, линейно зависит от числа граней кристалла.
Ключевые слова: природные кристаллы, алмаз, Куллинан, октаэдр, вложение в октаэдр, невязка, аффинный инвариант, критерий совместности, округлый октаэдр, условия непротиворечивости, оценка сложности.
Классификация 1ЕЬ: С610.
1. ВВЕДЕНИЕ
Природные кристаллы могут обладать огромной стоимостью, а операции обработки необратимы. Первой операцией, с которой начинается обработка кристалла и от которой зависит его дальнейшая судьба, - разделение на части.
Самый крупный природный кристалл алмаза «Куллинан», найденный 25 января 1905 г., весил 3106 карат. Камень был подарен королю Эдуарду VII в день рождения, 9 ноября 1907 г. Камень решили огранить, для чего изготовили 5 точных копий «Куллинана» из стекла. Четырем ювелирным фирмам была представлена возможность предложить свой вариант обработки уникального камня, и одна копия осталась для музея. 23 января 1908 г. камень был передан для огранки амстердамской фирме «И.И. Ассер и Ко». Согласно плану обработки, предложенному фирмой, камень следовало расколоть по имевшейся на нем трещинке на две части. Как поведет себя огромный кристалл, можно было только гадать. 10 февраля 1908 г. было осуществлено раскалывание. Лучший огранщик фирмы Йозеф Аскер закрепил кристалл, сделал засечку, установил вдоль нее специальную стамеску, нанес точно выверенный удар и потерял сознание. Наличие в камне трещинки - признак того, что материал камня напряжен, поэтому от удара он мог обесцениться, разлетевшись на мелкие части. Его сознание было не готово увидеть это.
Придя в себя, Йозеф Аскер увидел сияющие лица и вскоре смог встать на ноги. Камень раскололся идеально - на две части, весившие 2029,94 и 1068,09 карата. Вся работа по огранке «Куллинана» была завершена в ноябре 1908 г., а камни переданы заказчику.
Распиливание и раскалывание необратимы, поэтому, прежде чем разделить кристалл, его тщательно изучают, чтобы выяснить, что из него можно изготовить, какие конкретные изделия можно вложить в кристалл и сколько они будут стоить. Однако изготавливать для этого стеклянные копии в условиях массового производства нецелесообразно, современные вычислительные средства позволяют сделать электронное моделирование формы кристаллов и процессов вложения изделия в кристалл.
В настоящей работе рассматривается простейшая нетривиальная форма природных кристаллов - октаэдр, а также ее естественные математические обобщения.
2. МАТЕМАТИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ ОКТАЭДРА И МАТЕМАТИЧЕСКОЕ ВЛОЖЕНИЕ В ОКТАЭДР
Идеальный октаэдр - это одно из Платоновых тел, имеющее восемь граней (восьмигранник). На рис. 1 показано, что изображенное на нем тело является общей частью (пересечением) четырех слоев:
-1<-х + у + г <1,
(1)
-1< х - у + 2 <1,
-1< х + у - 2 <1,
-1<-Х - у - 2 <1,
т.е. множеством допустимых решений системы неравенств (1).
Идеальный октаэдр неплохо выглядит, однако идеальные кристаллы крайне редко встречаются в природе. Природа, плотно упаковывая атомы друг к другу, следит только за углами
между гранями. Поэтому математической моделью природного октаэдра является множество допустимых решений системы неравенств
а1 <-х + у+2 < Ь1,
а2< х - у+2 < Ь 2, а3 < х + у - 2 < Ь3, а 4 < -х - у - 2 < Ь 4.
(2)
Рис. 1. Октаэдр в кристаллографических осях координат
По определению, каждое допустимое решение системы неравенств (2) - точка, вложенная в октаэдр (2). Вложению множества точек соответствует ситуация, при которой каждая точка является допустимым решением системы неравенств (2). Для изделий, изготавливаемых на ограночном диске, поверхность готового изделия образована вершинами, ребрами и плоскими многоугольниками. Если каждая вершина изделия {(х., у., 2.) | у = 1, ..., т} - допустимое решение системы (2), то изделие оказывается вложенным в кристалл.
Действительно, если все вершины изделия - допустимые решения системы (2), то автоматически выполняются соотношения
а 1 < а 1 < -х + у + 2 < Ь1 < Ь1,
а2 < а2 < х - у+2 < Ь2 < Ь 2, а3 < а3 < х + у - 2 < Ь'3< Ь 3, а4 < а4 < -х - у - 2 < Ь 4 < Ь 4,
(3)
где
т}, , т},
а1 = тт{-х. + у. + 2. |у = 1, ..., т}, Ь1 = тах{-х. + у. + 2. |у = 1, .. а2 = тт{ х. - у. + 2. | у = 1, ..., т}, Ь2 = тах{ х. - у. + 2. | у = 1, а3 = тт{ х. + у. - 2. | у = 1, ..., т}, Ь3 = тах{ х. + у. - 2. | у = 1, ..., т}, а4 = тт{-х. - у. - 2. | у = 1, ..., т}, Ь\ = тах{-х. - у. - 2. | у = 1, ..., т}.
Значит, вместе с изделием в октаэдр (2) вкладывается октаэдр
а 1 < -х + у + 2 < Ь1, а2< х - у + 2 < Ь2, а3 < х + у - 2 < Ь'3, а4 < -х - у - 2 < Ь 4,
(4)
являющийся кристаллической моделью изделия, размеры которого невозможно изменить, потому что каждая из восьми граней (4) касается изделия. Верно и обратное. Каждый раз, когда кристаллическую модель изделия (4) удается вложить в кристалл (2), содержащееся в модели изделие оказывается вложенным в (2) автоматически.
Имеется реальное сырье - материальные тела, поверхность которых образована плоскими гранями: кубы, октаэдры, ромбододекаэдры и др. В данной работе - это октаэдры; в общем случае - трехмерный многогранник
а < Ах < Ь. (5)
Помимо сырья, имеются вычисляемые кристаллические модели изделия - трехмерные многогранники того же самого типа, что и сырье, которые, во-первых, содержат в себе конкретное изделие, а, во-вторых, каждая из их граней касается изделия
-а' < Ах < Ь'. (6)
Если изделие жестко привязано к кристаллической решетке сырья, то оно представлено одной моделью; в противном случае оно состоит из нескольких моделей - по одной на каждый вариант поворота. Ввиду того что кристаллическая модель изделия (6) - это один из элементов технических условий, связанных с изготовлением изделия, мы вправе потребовать, чтобы начало координат модели (6) совпадало с какой-то точкой изделия - центром изделия (в этом случае 0 < а', 0 < Ь)
При сложном ценообразовании, например в ювелирном производстве, когда стоимость изделия меняется скачком при переходе из одной весовой группы в другую, изделие, занимающее начало весовой группы, служит вариантом того же самого изделия, отличающегося ценой.
Задача. Имеется многогранник (5), представляющий кристалл, и множество кристаллических моделей изделия, являющихся многогранниками (6), каждый из которых обладает ценой, совпадающей с ценой изделия. Требуется выделить многогранник (6), обладающий максимальной ценой, который можно вложить в многогранник (5) параллельным переносом.
3. ВЛОЖЕНИЕ ТОЧКИ ВМЕСТО КРИСТАЛЛА
От вложения кристалла (6) в кристалл (5) до вложения точки (0, 0, 0) кристалла (6) в кристалл типа (5) нас отделяет один шаг. Срезая с граней кристалла (5) слои толщиной аЪ[, получаем остаток кристалла (5)
а + а' < Ах < Ь - Ь' - (7)
ядро вложения.
Теорема. Многогранник (6) можно вложить в многогранник (5) тогда и только тогда, когда ядро вложения (7) непусто.
Доказательство. Необходимость. Предположим, что нам удалось вложить многогранник (6) в многогранник (5), тогда центр изделия должен отстоять от граней (5) не ближе, чем от граней вложенного многогранника (6), что и выражено в каждом из неравенств системы (7). Значит, центр является решением системы неравенств (7), следовательно, она совместна.
Достаточность. Предположим, что ядро вложения непусто, тогда для некоторого вектора х' выполняется соотношение
а + а' < Ах' < Ь - Ь'. (8)
Перемещая начало координат системы (6) в точку х', приходим к неравенству
-а' < А(х - х') < Ь'. (6')
Складывая соотношения (8) и (6'), получаем для каждого допустимого решения х системы (6') соотношение а < Ах < Ь, свидетельствующее о том, что каждое решение системы неравенств (6') является решением системы неравенств (5), а это значит, что (6) вложено в (5). ■
4. НЕВЯЗКИ И КРИТЕРИИ
При работе с кристаллами приходится иметь дело с двумя системами координат - внешней, относительно которой задается представление кристалла в виде системы линейных неравенств (5), и внутренней - (6), относительно которой фиксируется положение дефектов (пороков), в той или иной мере присущих каждому природному кристаллу.
Основная характеристика внутренней системы координат - расстояние до грани, а основная функция - расстояние до границы полупространства, естественное обобщение которой принято называть невязкой. Полупространству
Ь < ах х + ау у + а2 2 (9)
соответствует невязка
ах х + ау у + а2 2 - Ь, (10)
принимающая нулевые значения на грани, положительные во внутренних точках полупространства и отрицательные в остальных случаях.
Складывая различные невязки, мы получаем в некоторых случаях результат, не зависящий от (х, у, 2) - аффинный инвариант. Неотрицательные элементы этого класса функций будем называть аффинными критериями.
Простейший критерий - толщина слоя. Два полупространства определяют множество, которое принято называть слоем
а0 < ах х + ау у + а2 2 < К (11)
его граням соответствуют две невязки
ах х + ау у + а2 2 - a0, (12)
-ах х - ау у - а2 2 + К (13) сумма которых является критерием - в любой точке (х, у, 2) она равна
Ьо - ао. (14)
Формально она может принимать отрицательные значения, однако это означает, что формирующая ее система ограничений (11) не имеет решений (противоречива). Соответственно, система неравенств (2) несовместна, если хотя бы один из четырех критериев
0< Ь1 = Ь1 - а 1,
ОСЬ 2 = Ь 2 - а 2,
(15)
0< Ь 3 = Ь3 - а3, 0< Ь 4 = Ь 4 - а 4
не выполняется. Однако э
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.