2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Оптимальная 2d укладка в прямоугольник
Сообщение02.08.2017, 01:47 


15/04/10
985
г.Москва
Рассматривается 2d-задача оптимального раскроя или мощения прямоугольниками $b , h$ прямоугольной области $B , H$ (Она же задача оптимальной (максимальной) раскладки одинаковых ящиков в 1 ряд по высоте)
Будем рассматривать не все множество укладок а только с одинаковым расположением плиток в столбцах (строках).
Частные случаи
V-укладка (прямоугольник $B , H$ мостится плитками $b , h$так что размер $ h$ вдоль $H$)
$m=[\frac{B}{b}]$ $n=[\frac{H}{h}]$ $k=m \cdot n$
H-укладка (прямоугольник $B, H$ мостится плитками $b , h$ так что размер $ b$ вдоль $H$)
$m=[\frac{B}{h}]$ $n=[\frac{H}{b}]$ $k=m \cdot n$
Общий случай
VH(i)-укладка $i$-столбцов V-укладки оставшиеся $j$ –H-укладки.
При этом $j=[\frac{B-i \cdot b}{h}]$ $k_1=i \cdot [\frac{H}{h}]$
$k_2 =j \cdot [\frac{H}{b}] $ $k=k_1+k_2 $
Далее путем расчета при разных i находится максимальное k и соответствующая пара $i,j$ задающая вид укладки. (при таких укладках неважно как чередуются V- и H-столбцы.
Примеры расчета
а) $B=30;H=40 ; b=2.6; h=3.5;$
$k = 120 ,   116 ,  127  , 123  , 119  , 115 ,  126 ,  122 ,  118 ,  114  , 125 ,  121$
максимальное количество укладок $К=127$ получено при $i=2,j=7 $т.е при 2 рядах V-укладки и 7 рядах H-укладки
б)$B=30;H=40 ; b=2.7; h=6.1;$
$k =  56 ,  62 , 68 , 60 ,  66 ,  58 ,  64  , 56  , 62 ,  54 ,  60,  66$
максимальное количество укладок $К=68$ получено при $i=2,j=4 $т.е при 2 рядах V-укладки и 4 рядах H-укладки
Вопрос. Для корректности предложенного решения надо доказать или опровергнуть утверждение, что оптимальные укладки достигаются именно на множестве VH(i)-укладок а не на каких-то иных

 Профиль  
                  
 
 Re: Оптимальная 2d укладка в прямоугольник
Сообщение02.08.2017, 02:13 
Заслуженный участник


20/08/14
11070
Россия, Москва
eugrita в сообщении #1237564 писал(а):
Для корректности предложенного решения надо доказать или опровергнуть утверждение, что оптимальные укладки достигаются именно на множестве VH(i)-укладок а не на каких-то иных
По моему данное утверждение опровергается примером: 4 прямоугольника 2х3 в квадрат 5х5, укладка по или против часовой стрелки с шагом 90°, не является VH (какова вообще нереализуема).
С другой стороны, полно конфигураций когда именно VH укладка будет оптимальной.
Т.е. истинность утверждения зависит от (соотношения) параметров задачи.
PS. Если бы эта задача решалась настолько просто (VH укладкой), она не была бы NP-полной. ;-)

 Профиль  
                  
 
 Re: Оптимальная 2d укладка в прямоугольник
Сообщение02.08.2017, 02:22 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Я не очень понял, что означает
eugrita в сообщении #1237564 писал(а):
$m=[\frac{B}{b}]$ $n=[\frac{H}{h}]$ $k=m \cdot n$
Вы не догадались применить какие-нибудь знаки препинания?

eugrita в сообщении #1237564 писал(а):
Для корректности предложенного решения надо доказать или опровергнуть утверждение, что оптимальные укладки достигаются именно на множестве VH(i)-укладок а не на каких-то иных
Как насчёт укладки плиток $2\times 3$ в прямоугольник $5\times 5$?

P.S. Пока писал, тот же контрпример предложил Dmitriy40.
P.P.S. Знак умножения в виде косого креста кодируется "\times".

 Профиль  
                  
 
 Re: Оптимальная 2d укладка в прямоугольник
Сообщение02.08.2017, 02:55 
Заслуженный участник


20/08/14
11070
Россия, Москва
Someone в сообщении #1237571 писал(а):
Я не очень понял, что означает
Имхо это попытка получить количество вмещающихся элементов, только квадратные скобки должны означать округление вниз до целого и по идее, eugrita, изображаться другими скобочками: $m=\left\lfloor \frac{B}{b} \right\rfloor$.

 Профиль  
                  
 
 Re: Оптимальная 2d укладка в прямоугольник
Сообщение02.08.2017, 02:58 


15/04/10
985
г.Москва
$m=[\frac{B}{b}]$ [] - обозначают целую часть , $m$ мах возможное количество рядов
$n=[\frac{H}{h}]$ -мах возможное количество плиток в одном ряду

Да я понимаю задача сложная и оптимальное решение при отдельных соотношениях размеров не
на VH(i) укладках. Но все таки хочется выделить максимально общие утверждения когда можно все таки ограничиться VH(i) укладками

 Профиль  
                  
 
 Re: Оптимальная 2d укладка в прямоугольник
Сообщение02.08.2017, 03:06 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Dmitriy40 в сообщении #1237573 писал(а):
изображаться другими скобочками
Проблема не в скобочках (у математиков квадратные скобки вокруг числа как раз и означают функцию "целая часть", то есть, "округление вниз"). Я же прямо написал, что проблема в знаках препинания.

(Оффтоп)

P.S. И вы оба нарушаете правила записи формул.

 Профиль  
                  
 
 Re: Оптимальная 2d укладка в прямоугольник
Сообщение03.08.2017, 08:36 


15/04/10
985
г.Москва
---

-- Чт авг 03, 2017 09:52:15 --

1)обнаружил что даже в этой постановке задача недоделана
(рассматривались одинаковые укладки $b,h$ и $h,b$ только по столбцам.
Но можно и нужно сравнивать с одинаковыми укладками по строкам.
Поэтому немного меняю терминологию принятую сначала
Vh-укладка (прямоугольник BxH мостится плитками bxh так что размер h вдоль H)
Vb-укладка (прямоугольник BxH мостится плитками bxh так что размер b вдоль H)
(здесь однотипные укладки, поэтому не важно как мостится - по строкам или по столбцам)
Комбинированная укладка по столбцам
Vhb(i)-укладка по столбцам. i-столбцов Vh-укладки оставшиеся j – Vb -укладки.
Комбинированная укладка по строкам
Hhb(i)-укладка по строкам. i-строк размером h вдоль B, оставшиеся j размером b вдоль B
2) ниже приведены расчеты по скорректированной программе частично с рис-пояснениями
Изображение
и более крупных укладок
Изображение

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: tolstopuz, Vladimir Pliassov


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group