Подскажите идею решения следующей задачи

[Amigo]

Пусть дан «Основной» прямоугольник со сторонами x=2, 0<y<2 ,
Фиксированный набор прямоугольников P1,P2,…,Pn со
Сторонами P1={X1,Y1)- в количестве K1 штук, P2={X2,Y2)- в количестве K2 штук ,…
P1={Xn,Yn)- в количестве Kn штук соответственно причём Xi,Yi<1,9

Требуется :
1)Найти минимальное значение y- стороны «Основного» прямоугольника , так что бы
на основном прямоугольнике могли разместится все фиксированные прямоугольники не
имея попарного пересечения т.е PiPj= при ij.
2)Указать это расположение.

Пробовал решать так: перебераем все варианты возможного размещения фиксированных
прямоугольников и выбираем оптимальный... Но как их перебрать если их бесконечное
множество? Ведь первый прямоугольник P1 можно расположить где угодно внутри основного.

[PAV]

Фиксированные прямоугольники не могут располагаться один внутри другого?

[Amigo]

Нет не могут!

[juna]

Вряд ли существует полностью корректное численное решение вашей проблемы. Если и существует, то вычислительные затраты не будут стоить результата. Но есть полезные эвристики подобия, которые можно использовать:
1. вряд ли повороты прямоугольников на угол, отличный от 90 град. дадут более рациональное замощение площади основного прямоугольника;
2. наиболее подобные прямоугольники основному прямоугольнику дают лучшее замощение.
Отсюда вытекает следующий эмпирический алгоритм:
1. принимают шаг h по у, n=1, у:=2-hn.
2. сортируют прямоугольники на группы по признаку подобия для имеющейся части основного прямоугольника, учитывая их количество (здесь множество путей)
3. производят замощение по оси х прямоугольниками из группы наиболее подобных, переходят к п.2
4. Фиксируют результат, n:=n+1; переходят на п.1
5. выбирают наименьшее y.
Как видите, предлагаемое решение более подходит к тематике Computer Science.

[Amigo]

Благодарю Артамонов Ю.Н. за то, что Вы откликнулись на мою задачу
и нашли время что бы изложить свой метод решения. Правда я не совсем понял
предложенный вами алгоритм в часности строку: " 1. принимают шаг h по у, n=1, у:=2-hn "
а также понятие "наиболее подобный". Буду очень Вам признателен если Вы уточните
эти понятия.

Заодно хочу поделится с Вами своими соображениями которые возможно Вы сможете
уточнитть или дополнить:
1) Поскольку сторона основного прямоугольника 0<y<=2 при фиксированной стороне х=2
то его площадь Soсн<=4. Введём в расмотрение функционал S=S(t1,t2,..,tn) ставящий в
соответствие каждому набору <t1,t2,..,tn> ,где 0<=t1<=K1,.., 0<=tn<=Kn площадь,
очевидно, что S:=t1*x1*y1+..+tn*xn*yn , если за М обозначить множество всевозможных
наборов <t1,t2,..,tn> ,где 0<=t1<=K1,.., 0<=tn<=Kn то очевидно ,что |M|=(k1+1)*..(kn+1)
однако не все входящие в М наборы допускают некоторое расположение на основном
прямоугольнике очевидно ,что для всех наборов для которых выполняется соотношение
S(t1,t2,..,tn)>4 расположение заведомо не возможно. Для всех остальных наборов
такое расположение отрицать нельзя, обозначим за S-множество "всех подозрительных
по расположению " прямоугольников, очевидно |S|<=|M|. Теперь основная трудность нашей задачи свелась к следующей : а)Определить для каждого набора T пренадлежащего S
возможность расположения на "основном" прямоугольнике и б) Ответить можно ли
определить число S(t1,t2,..,tn)<=h<4 такое , что для данного набора по этому числу
также существует некоторый раскрой?

В связи с этим для некоторых часных случаев у меня наметился следуюший подход :
1.Все прямоугольники из набора T имеют хотябы одну одинаковую сторону.
Обозначим длину этой стороны за L тогда y=m*l+r , где m-целое r<l, то есть разбиваем
основной прямоугольник на m-прямоугольников длины L и один длины r .Для каждого из найденных прямоугольников состовляем последовательно задачу линейного программирования и решаем её (мне представляется , что такой подход даст наилучшее решение).
2."Достаточно большое" количество прямоугольников из набора T имеют хотябы одну одинаковую сторону.
Эту задачу решаем подобно первой задаче.

P.S
Я прекрасно понимаю, что в изложенном только что сообщении больше слов чем смысла,
но дискуссия на эту тему мне крайне важна!

[PAV]

Тема перенесена из форума "Математика" в "CS"

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

Тогда можно организовать полный перебор задачи. Разумеется, если прямоугольков будет много, это очень неэффективно. А, кстати, каков порядок их количества?

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

Количество способов упорядочить прямоугольники (с учетом деления на группы одинаковых и неотличимости прямоугольников одного размера) равно соответствующему полиномиальному коэффициенту

$\frac{(K_1+\cdots+K_n)!}{K_1!\times\cdots\times K_n!}$

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

[PAV]

Было бы конечно неплохо применить что-то вроде динамического программирования, но можно ли это сделать в данной задаче я пока не понимаю.

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

Можно спросить - эта задача учебная или промышленная?

[Amigo]

Разумеется ,что данная задача может возникать как в промышленности так и в
учебном курсе, например "Операционное исчисление" . Дело в том , что не давно
один мой знакомый (работник цеха) предложил мне решить подобную задачу которую
можно сформулировать так: "Предприятие покупает цельные металические листы
на заводе, имеющие форму прямоугольника с размерами 1250*2000 мм , из этого
листа изготавливаются различные фасонные изделия, каждое фасонное изделие
обязательно должно быть 2-х метровым по длине , а развёртка изделия по ширине
не может превышать 500 мм (вообщето может но превышение данной величины
ведёт к изменению технологии производства) , на предприятие приходят последовательно
заказы на изготовление различных партий фасонных изделий, для изготовления изделий
необходимо предоставить заявку в цех, в которой должно содержатся какие изделия
и в каком колличестве необходимо изготовить а также необходимо приложить схему
для раскроя каждого отдельного листа. На предприятии также имеется склад в
котором хранятся остатки от предыдущих раскроев цельного листа в различных
количествах. Естественно возникает вопрос:"Как укомплектовать заказы так и
предоствить заявку в цех вместе с схемой раскроя , что бы количество отходов было
минимально а заказы были выполнены" , при этом имеются ещё 2-а условия:
1)Если в процессе раскроя листа или остатка получился остаток меньше 59<мм
то этот остаток списывается (то есть в склад на дальнейшее хранение не заносится)
2)Склад имеет ограниченный объём поэтому внесение в него новых остатков не
желательно по этому при осуществлении раскроя в начале необходимо задействовать
остатки на складах а лишь потом цельные листы (даже если в последнем случае
раскрой не является оптимальным)."

Должен Вам сказать , что эта задача была мною полностью решена если Вас интерисует
я могу предоставить алгоритмы (на Delphi) или саму программу.
Естественно меня заинтерисовал вопрос "Как решить подобную задачу ,если фасонные изделия имеют не одинаковую длину". Попробовав решить её самостоятельно
я убедился , что это не легко. По этому я и решил обратится за помошью на Ваш форум.

Меня же интерисует данная задача ИСКЛЮЧИТЕЛЬНО в учебных целях. Так как
готовые программы в Internete распространены (например Cutting 3 ).

P.S
В internete я нашел книгу по этой теме, математика Кантаровича "Рациональный раскрой
промышленных материалов" к сожалению эта книга представленна там в смысле
"обложка" а не сама книга, поэтому если у кого либо имеется электронный вариант
данной книги, просьба выложить ссылки на данном форуме.
P.P.S
Интересно можно ли вместо смайликов разместить знаки объеденения, пересечения и д.р

[PAV]

Я посмотрел на http://www.poiskknig.ru по слову "раскрой",
получил ссылку на книгу Мухачевой с тем же названием, которое Вы указали.

[juna]

Мне также приходилось для производства подобные задачи решать. При производстве оконных рам предприятие получало огромные заказы. Математическая постановка задачи в следующем - разложить на хлысте заданной длины заготовки разной длины в необходимом количестве с целевой функцией минимизации расхода хлыстов и возникновения обрезков. Разница лишь в том, что здесь раскладывают по длине, а у Вас по площади. В конечном итоге задача сводилась к типовой задаче целочисленного программирования. На практике при реализации она решалась симплекс – методом, а небольшие остатки раскидывались по хлыстам эвристическим алгоритмом (нет еще нормальных методов целочисленного программирования, чтобы их запрограммировать под 10000 уравнений и все их хорошо решить). Скажу, что составленная и проданная программа оказалась существенно эффективнее «дяди Васи» и всех других эвристических методов данного предприятия вместе взятых.
Итак, Вашу задачу можно попытаться свести к данной с некоторыми особенностями:
1.дробим все прямоугольники, включая основной на однородные элементы – маленькие квадраты, например, находим их как наименьшее общее кратное.
2.вытягиваем площадь основного прямоугольника в линию из данных маленьких квадратиков.
3.в отношении прямоугольников замощения все их маленькие квадратики объединены в группы. Постановка группы таких квадратиков на основной квадрат эквивалентно тому, что они размещаются по линии через фиксированное расстояние, равное длине основного прямоугольника.
4.начинают комбинировать такие подстановки, на этом пути, я думаю все должно свестись к задаче линейного программирования.

[Amigo]

Артамонов Ю.Н. писал(а):

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

Что то я не очень понимаю про какие именно группы Вы говорите? Эти группы представляют собой некоторый отрезок?- размещаемый на линии основного прямоугольника, длина которого равна числу маленьких квадратиков?

Артамонов Ю.Н. писал(а):

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

Не могу понять почему именно эквивалентно.