Задача - упаковка
Cтраница 1
Задача упаковки в классической постановке определяется следующим образом. [1]
Задача упаковки блоков является одной из важнейших инженерных задач. Она связана с распределением заданных блоков различного размера по стандартным блокам. [2]
Задачи упаковки максимально возможного числа предметов ( без наложения) в контейнере определенной формы и определенного объема встречаются во многих приложениях. Область этих приложений простирается от хранения консервных банок в маленьком буфете, до упаковки кабелей ( цилиндров) в большой цилиндрической трубе. Известно, что однажды одна компания по перевозке цитрусовых наняла в качестве консультанта математика, чтобы он отыскал наилучшие способы упаковки апельсинов в корзины, что позволило бы максимизировать использование корзин и минимизировать количество раздавленных апельсинов. Он помог уменьшить количество используемых корзин и, следовательно, стоимость перевозки и, конечно, количество испорченных апельсинов. [3]
Задачей упаковки и тем самым тары является передача необходимой информации об общих свойствах товара. [4]
Отметим, что задача упаковки блоков тесно связана с задачей разбиения графов на части с минимизацией суммарного числа связей К, когда заданное число объектов надо разместить в N блоках с выполнением заданных ограничений и с минимизацией числа блоков. [5]
Докажите, что задача упаковки множества является оМ - полной: для данного семейства множеств Sj, 1 / п, определить, содержит ли оно / попарно непересекающихся множеств. [6]
Для построения популяции альтернативных решений задачи упаковки блоков применяют также модификацию FF, называемую RFF ( refined first fit) - первый подходящий с удалением. [7]
Оно оказывается весьма существенным для задач максимальной упаковки баз матроидов, минимального покрытия исходного множества Е базами ( или независимыми множествами) матроида, а также отыскания максимального независимого множества двух матроидов на одном и том же множестве Е ( см. [ 1, гл. В настоящем разделе дано понятие увеличивающего или активного пути, интересного тем, что с его помощью всегда можно увеличить независимое множество суммы матроидов, если оно не максимально. Приведено конструктивное описание цикла суммы матроидов, которое существенно используется в дальнейшем. [8]
 |
Частичное решение. [9] |
Опишем оператор мутации, ориентированный на задачу упаковки блоков. В данной хромосоме выбираются, по случайному закону, несколько блоков и устраняются из решения. Естественно, появляются упущенные элементы, которые должны быть помещены в хромосому. Упущенные элементы вначале являются базисом для возможного улучшения неизмененных блоков во время стадии замены. Когда замена уже невозможна, FFD-эвристика используется для завершения формирования решения. [10]
Алгоритмы FFD и BF для построения популяции альтернативных решений задачи упаковки блоков реализуются аналогично. [11]
Заметим, что задача о паросочетании для гиперграфов эквивалентна задаче вершинной упаковки для графов. Поскольку обе задачи NP-полные, то, возможно, это не удивительно. Однако построения, используемые при сведении одной задачи к другой, действительно очень просты. Прежде всего пусть Н - гиперграф, и определим его граф пересечений L ( H) как простой граф, вершинами которого являются ребра гиперграфа Н, причем вершины смежны тогда и только тогда, когда соответствующие им ребра пересекаются. [12]
 |
Частичное решение. [13] |
В заключение отметим, что рассмотренные эвристики совместно с ГА для решения задачи упаковки блоков позволяют находить оптимальные и квазиоптимальные решения. [14]
Со времен работ Никвиста и Шеннона известно, что проектирование оптимальных кодов для такого канала эквивалентно задаче упаковки шаров. Теоретические исследования информационных возможностей таких каналов требуют знания параметров наилучших упаковок шаров в пространствах больших размерностей. [15]
Страницы: 1 2