10. Задача оптимального раскроя с круговыми выкройками при наличии ограничений на расстояния между ними

В настоящем параграфе рассматривается следующая задача. Дано круговых выкроек радиусов

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

Примем в качестве параметров размещения выкроек координаты их центров

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

Материал расположим так, чтобы по одной из его сторон проходила ось абсцисс, а по другой — ось ординат. Пусть сторона, лежащая на оси абсцисс, имеет длину а, а сторона, лежащая на оси ординат — длину Тогда для того, чтобы выкройка лежала на

материале не ближе, чем на расстоянии от его края, необходимо, чтобы выполнялись неравенства

Функция цели представляет собой площадь области т. е. Учитывая, что

функцию цели можем записать в виде

Оказывается удобным к системе неравенств (6.95) и (6.96) присоединить неравенство

где

т. е. площадь прямоугольника со сторонами на котором заведомо могут. разместиться все выкройки. Применяя операцию свернем неравенства (6.95), (6.96) и (6.100) в одно неравенство вида

Таким образом, приходим к задаче нелинейного программирования с нелинейной функцией цели (6.99) и областью допустимых решений (6.102). Рассматриваемая задача является многоэкстремальной, т. е. может иметь яесколько локальных экстремумов, среди которых должен быть выбран тот, которому соответствует наименьшее значение цели.

Для решения этой задачи на ЭВМ был использован алгоритм, описанный в конце гл. 5, 5. Начальная точка случайно выбирается в -мерном пространстве переменных с помощью программного датчика псевдослучайных чисел с нормальным законом распределения на интервале с вероятностью вырождения последовательности чисел Попадание в область допустимых решений осуществляется с помощью несколько видоизмененного метода нелокального поиска, описанного в работе И. М. Гельфанда и М. Л. Цейтлина [5]. Для автоматической регулировки величины шага используется специальная подпрограмма обучения. В первой же точке принадлежащей области допустимых решений, подсчитывается значение функции цели, которая затем засылается на место значения в неравенство (6.100). Этим самым область допустимых решений урезается таким образом, что точка оказывается на границе новой области допустимых решений. Затем снова включается подпрограмма стремления в область допустимых решений и т. д. до тех пор, пока не достигается локальный минимум.

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

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

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

Оптимальное решение, приведенное на рис. 53, было получено в первой же начальной точке.

Пример 2. В предыдущей задаче радиус одной из выкроек был уменьшен до 0,4. Машиной со второй попытки найдено решение, изображенное на рис. 54, а. Размещение выкроек, изображенное на рис. 54, б, было воспринято как локальный экстремум в первой попытке.

Рис. 53.

Заметим, что если в задаче имеется несколько одинаковых выкроек, то, если не принять специальных мер, о которых будет сказано ниже, число локальных экстремумов может оказаться весьма большим. В самом деле, если локальным экстремумом является точка -метры размещения одинаковых выкроек, то локальным экстремумом (с прежним значением функции цели) окажется также точка Если одинаковых выкроек к штук, то количество локальных экстремумов, таким образом, увеличивается в С раз.

Рис. 54.

Пример 3. Выкройки заданы радиусами Начальная точка изменялась 51 раз. Наименьшее значение площади описанного прямоугольника (рис. 55, а). Кроме того, было получено еще два локальных экстремума, значения функции цели у которых близки к (рис. 55. б, в), Данные об этих экстремумах приведены в табл. 10.

Пример 4. Радиусы цоколей ламп и электролитических конденсаторов равны: Исходя из конструктивных и технологических соображений, необходимо выдержать следующие расстояния между элементами:

Таблица 10 (см. скан)

Рис. 55.

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

Рис. 56.

С помощью ЭВМ было рассмотрено 60 локальных минимумов. Наилучшим решением оказалось то, которое приведено на рис. 56, а. На рис. 56, б, в приведены два ближайших к нему решения. Данные об этих решениях приведены в табл. 11.

Пример 5. Сохранив размеры выкроек такими же, как и в примере 3, рассмотрим задачу о размещении выкроек на полубесконечной полосе шириной см (задача 10).

Таблица 11 (см. скан)

В этом случае функцию цели (6.99), а следовательно, и левую часть неравенства (6.100), следует заменить выражением

Рис. 57.

Из 67 локальных экстремумов наилучшим оказался тот, который изображен на рис. 57, а. Ему соответствует длина полосы Близкие к оптимальному решения приведены на рис. 57 б, в. Данные об экстремумах приведены в табл. 12.

Таблица 12 (см. скан)