Раскрой двумерного материала

[Dialectic]

Математиков часто обвиняют в том, что они любят заниматься математикой "для души".
Решают задачи, которые совершенно никому не нужны. Но есть задачи, математические, которые насколько мне известно до сих пор удовлетворительно не решены. Но вместе с тем, имеют огромное практическое значение. Одна из таких задач - задача раскроя двумерного материала. Эта задача имеет множество различных вариантов: когда раскрой производится лобзиком, гильятиной или ёще чем-то. Мы рассмотрим самый простой вариант: когда у нас имеется прямоугольный лист фиксированной длины и ширины. И куча маленьких прямоугольничков различных размеров. Требуется разместить их на прямоугольнике так, чтобы они не пересекались и остаток от незаполненной части базового прямоугольника был бы наименьший.
Можно записать эту задачу так:
Дан некий "базовый" прямоугольник P и
$n_1$ прямоугольников типа $P_1$
$n_2$ прямоугольников типа $P_2$
...
$n_n$ прямоугольников типа $P_n$
Требуется указать какое количество прямоугольников типа $P_i$ нужно задействовать,
чтобы:
а)Они все сумели разместиться на прямоугольнике P не пересекаясь друг с другом
б) $z=S(P) - (k_1S(P_1)+k_2S(P_2)+...+k_mS(P_m))-->min$ ,где $S(x)$ - площадь прямоугольника типа "х".
Какие у кого есть мысли?
Можно ли эту задачу привести к алгебраическому виду? Скажем составить какие- либо уравнения, решая которые c учётом минимизации целевой функции Z можно получить один из правильных ответов? (в силу возможной симметрии размещения прямоугольников, эта задача видимо не имеет однозначного решения)

[Xaositect]

Dialectic в сообщении #201682 писал(а):

Какие у кого есть мысли?

Есть мысль, что задача NP-трудная, т.к. можно построить сведение задачи о рюкзаке к ней.
То есть решать надо эвристическими алгоритмами.

[Dialectic]

Xaositect писал(а):

Dialectic в сообщении #201682 писал(а):

Какие у кого есть мысли?

Есть мысль, что задача NP-трудная, т.к. можно построить сведение задачи о рюкзаке к ней.
То есть решать надо эвристическими алгоритмами.

А что за задача о рюкзаке? Никогда не слышал.

[Pi]

Dialectic в сообщении #201691 писал(а):

А что за задача о рюкзаке? Никогда не слышал.

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

Dialectic в сообщении #201682 писал(а):

Решают задачи, которые совершенно никому не нужны.

Если тебе не нужно, то какое право ты имеешь судь о том что это никому не нужно?
С твоим то уровнем знаний тем более...

[Xaositect]

Задача о рюкзаке: дано множество предметов, для каждого задан вес и цена. Требуется положить в рюкзак заданной грузоподъемности максимально ценный набор.
А я, когда писал "задача о рюкзаке", имел в виду другую связанную задачу(о сумме подмножеств): дано множество чисел, выяснить, существует ли в нем подмножество с заданной суммой. Эта задача NP-полная, а значит задача о рюкзаке NP-трудная. Задача раскроя тоже на них похожа.

[Dialectic]

Xaositect писал(а):

Задача о рюкзаке: дано множество предметов, для каждого задан вес и цена. Требуется положить в рюкзак заданной грузоподъемности максимально ценный набор.
А я, когда писал "задача о рюкзаке", имел в виду другую связанную задачу(о сумме подмножеств): дано множество чисел, выяснить, существует ли в нем подмножество с заданной суммой. Эта задача NP-полная, а значит задача о рюкзаке NP-трудная. Задача раскроя тоже на них похожа.

Да, по видимому так и есть. Но если так, то тогда действительно нужно заниматься эвристиками. Что же здесь можно попробывать? Какие варианты подходы существует?
Вы не в курсе?

[Xaositect]

Нет, я про приближенные алгоритмы для NP-трудных задач оптимизации знаю очень мало, но вообще это тема достаточно хорошо разработанная. Попробуйте поискать по ключевым словам knapsack problem approximation algorithms

[Dialectic]

Pi писал(а):

Dialectic в сообщении #201691 писал(а):

А что за задача о рюкзаке? Никогда не слышал.

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

Dialectic в сообщении #201682 писал(а):

Решают задачи, которые совершенно никому не нужны.

Если тебе не нужно, то какое право ты имеешь судь о том что это никому не нужно?
С твоим то уровнем знаний тем более...

Товарищ Pi,Вы и в дальнейшем собираетесь рыскать по моим темам и писать оффтоп?
У Вас занятий больше нет? Если нет, то я не против. Мне будет приятно, что со мною следует свита, хоть и не очень вменяемая.Но у каждого свои недостатки, что ж поделаешь...

[Prorab]

Похожие задачи уже обсуждались, там есть и ссылки на литературу

http://dxdy.ru/topic1864.html#14122

http://dxdy.ru/topic9798.html

[Pavia]

А я бы посоветовал обратиться к специалисту.
http://forum.sources.ru/index.php?showuser=65275
она этой проблемай занимается уже очень давно. Несколько лет.

[mserg]

Никто математиков уже давно не упрекает. Одни над ними одни смеются, другие ругают матом.

Представьте себе заводик/фабрику, на которой есть прямоугольный раскрой материала. Задача у них ставится следующим образом: сколько можно сэкономить на отходах и сколько это будет стоить. Для того чтобы вообще что-то произошло, инженер, скажем в течение года, должен собрать информацию, какие были заготовки и как их раскроили. Ну, в крайнем случае, должен вестись учет отходов. Вот эта самая база по фактическому раскрою – исходная точка для начала математических работ. Если собрать данные со 100 заводов/фабрик, то потенциальная сумма получится внушительной - можно основательно потратиться на создание системы оптимизации раскроя, получив хорошие деньги за основательную работу. Буржуи так и делают и даже не в рамках одной корпорации – берите выше, отсюда и зарплаты у ихних ученых.
Вопрос об абсолютном оптимальном раскрое вообще не стоит, так как стоимость необходимого для этого компьютерного оборудования может многократно превзойти саму экономию при раскрое. Суть методов, которые применяются для подобных задач, одинакова: вероятностное снижение основания экспоненты трудоемкости. Хотя число шагов $1.1^n$ и $10^n$ растет экспоненциально с ростом $n$, но основание $1.2$ все-таки предпочтительнее основания $10$.
Обычно ядро решения таких задач содержит в себе метод ветвей и границ и «хренову тучу» суть полиномиальных алгоритмов, применение которых могут снизить основание экспоненты роста. Это и линейное программирование, и «распространение ограничений», и «энергетический критерий» сжатия границ переменных расположения элементов на листе, и «энергопредшествование», и всевозможные эвристики ветвления и быстрого получения хорошего решения, и т.д. Даже задача о рюкзаке может быть прямо применена. Скажем, размеры всех нарезаемых листов кратны 100, а разрезаемый лист 12745x94853. Ясно, можно рассматривать задачу с листом 12700x94800. Этот метод снижения размерности можно обобщить и решать рюкзаком. Метод ветвей и границ, который в каждом узле что-то «химичит» (сжимает значения переменных, находит допустимые решения, добавляет отсекающие ограничения и т.п.) получил название «метода ветвей и отсечений». Никакого противоречия между «точными» и «эвристическими» методами никогда не существовало – все это укладывается в единую схему поиска.
Подлость заключается в том, что используемые полиномиальные алгоритмы не гарантируют экспоненциального снижения сложности, а могут еще и ухудшить трудоемкость. Т.е. будет полный перебор и еще и применение бесполезных полиномиальных алгоритмов, которые ничего не дают. К счастью, вероятность такого сценария минимальна, если проверка алгоритмов делается на реальной базе задач раскроя. Если данные для проверки сделаны генератором – проблемы практически гарантированы. Обычно ядро оптимизации содержит «ключи», позволяющие включать/выключать различные возможности, и подобрать наиболее подходящий и устойчивый вариант поиска наилучшего раскроя в конкретных условиях.

А теперь реальность, связанная с придурками (модератор, сделай мне замечание за правду). Извиняюсь, - с нашими «профессиональными» математиками. [Вырезано самоцензурой] . Инженер c завода/фабрики тоже учился у наших математиков. Разумеется, он сам захочет решить эту задачу, которую в мире (а то и во вселенной!) никто толком решать не умеет. О сборе данных, конечно, даже не позаботится. Очевидно, что ничего хорошего у него не выйдет – слишком сложно. И сам ничего сделать не может, и другим не даст заработать. И так 100 инженеров на всех 100 заводах/фабриках. Лично сталкивался с такой ситуацией: сидит этот инженер, получает зарплату, отвлекает других, меня не пускает на предприятие, а в это время это самое предприятие продолжает нести убытки. Вот так у нас обстоит дело с высокими технологиями и прочим раскроем материала....

[Vassil]

В книге И. В. Романовского "Алгоритмы решения экстремальных задач", "Наука",
Главная редакция физико-математической литературы, Москва 1977, начиная со
стр. 287 можно прочитать § 9. Плоская задача раскроя.

Мне кажется, что Ваша задача там сводится к процессу динамического
программирования. Описана процедура, опирающаяся на переработку
списков. Реализация списков расмотрена раньше в книге, базировано
на Алголе.

[mserg]

Разумеется, никуда ничего не сводится. Романовский придумал просто чудо-задачу, чтобы получилось эффективное доминирование вариантов. Ну, где это видано, нарезать только те детали, которые нравятся (суммарно наиболее дорогие)? Ерунда все это. Как показывает практика, небольшое изменение условий и данных в дискретных задачах, делает простые методы неработоспособными. Да и нет задач подобных следующим:
* Прочитал книжку – запрограммировал и внедрил
* Не отрывая мягкого места от стула, придумал чудо-метод и опубликовал – пусть все пользуются
* ….
Это никому не нужно. Люди, которые это умеют – тоже никому не нужны. Больше не нужны толпы инженеров, которые знают методы - все простое сколько-нибудь нужное давно запрограммировано. В реальной жизни люди занимают некоторые позиции: инженер на производстве, архитектор пакета оптимизации, математик-исследователь, и т.д. – специализация неизбежна и каждый должен себя «правильно спозиционировать».

Есть другие, реальные задачи:
* Сбор реальных данных по реальным задачам
* Изобретение методов сокращения вариантов
* Создание ядра, позволяющего описывать задачи, подключать схемы поиска и методы сокращения вариантов
* ….

Есть и более продвинутая задача. Дано формальное описание задачи и наборы данных к ним. На выходе – «оптимальный» алгоритм решения задачи. Это более реальная задача, чем поиск супер-метода двумерного раскроя. Да, здесь нужно думать, изобретать. Но не этого ли хотел автор темы?