12. Об уменьшении количества локальных экстремумов

Пусть, например, необходимо разместить выкройки на прямоугольнике наименьшей площади.

Рис. 60.

Предположим, что точке соответствует некоторый локальный экстремум (рис. 60, а). Очевидно, что точками локальных экстремумов, равноценных данному, окажутся точки которым соответствуют размещения выкроек, изображенных на рис. 60, б, в, г. Кроме того, если допускается переворачивание выкроек (или каждая из выкроек имеет оси симметрии), то локальный экстремум будет в точках которым соответствуют д, е, ж, з (рис. 60). Координаты точек соответственно

Таким образом, общее количество локальных экстремумов в рассматриваемой задаче кратно четырем, а если допускается переворачивание выкроек или каждая из выкроек имеет ось симметрии, то кратно восьми. Такое четырех- или восьмикратное увеличение количества локальных экстремумов затрудняет задачу поиска глобального экстремума. Уменьшить количество локальных экстремумов можно следующим образом Стороны а и прямоугольника, на котором размещены выкройки, являются функциями параметров размещения выкроек

Например, в гл. 6, 10 эти величины находятся по формулам (6.97) и (6.98). Случаи в, г, ж, з (рис. 60) будут исключены, если потребовать, чтобы выполнялось неравенство

Пусть есть полюс выкройки Размещениям а, б, д, е (рис. 60) соответствуют положения Для того чтобы сохранить лишь положение необходимо, чтобы выполнялись неравенства

Следовательно, одновременное выполнение условий (6.105) и (6.106) даст возможность получить лишь один из восьми локальных экстремумов. Неравенства (6.105) и (6.106) должны быть присоединены к условиям непересечения выкроек и условиям их размещения на материале.

Рис. 61.

Если рассматривается задача о размещении выкроек на полубесконечной полосе заданной ширины а (задача 10), то количество локальных экстремумов можно уменьшить вдвое, если не разрешается перевод рачивать выкройки, или вчетверо — в противном случае.

Интересно отметить, что если материал раскроя есть круг, то количество параметров размещения выкроек можно уменьшить на единицу. В самом деле, одинаковыми оказываются всякие размещения выкроек, которые могут быть совмещены с помощью осевого поворота на некоторый угол. Следовательно, можно потребовать, чтобы полюс одной из выкроек лежал на оси абсцисс, положив, например,

Сокращение количества локальных экстремумов можно произвести не только тогда, когда материал раскроя имеет оси симметрии, но и тогда, когда в рассматриваемой задаче есть одинаковые выкройки. Для этого достаточно упорядочить одинаковые выкройки, потребовав, например, чтобы выполнялись неравенства где абсциссы полюсов одинаковых выкроек. Эти неравенства необходимо присоединить к условиям непересечения выкроек и условиям их размещения на материале.