Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: мат.программирование - оптимальное деление отрезка LL на N1 отрезков дл. L1 . .  (Прочитано 22879 раз)
0 Пользователей и 1 Гость смотрят эту тему.
DneprSMV
Помогающий

kz
Offline Offline
Пол: Мужской

« : 04-11-2011 15:55 » 

Подскажите люди добрые - где искать-читать.
Задача разделить оптимально отрезок длиной LL на N отрезков заданных длин (L1*N1), (L2*N2), ....
С учетом дополнительных ограничений для N1, N2 .... (например, N1>=3, 0<=N1,<=2 )
---
Вопрос возник не из-за неумения пользования wiki или googl, а по причине огромного объема инф-ии
(а выбрать нужное, требуется достаточно хорошо знать математику)
Исходные.
1. Задача как для оптимизационной должна даваться в кач-ве примера. Мнеб достаточно ссылки.
2. Разделы математики - линейное программирование, матем. прогр-ие, дискретная математика.
(давно сталкивался с транспортной задачей)
3. В математ. теории я разбираюсь слабо. Задача-решение нужно для прикладного использования.
4. Нужен алгоритм в матем. описании или C.
---
Всем спасиб Улыбаюсь
Записан

"Не слушайте никаких советов, в том числе и этот" (Сократ ?)
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #1 : 04-11-2011 16:01 » 

Переформируй вопрос.
Оптимальное деление отрезка
Относительно чего?


Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
DneprSMV
Помогающий

kz
Offline Offline
Пол: Мужской

« Ответ #2 : 04-11-2011 16:27 » 

Sla,
да есть труба, ее надо разделить на куски стандартной длины L1, если остается кусок-обрезок, то можно использовать меньшую стандартную длину L2 (в качестве "довеска"), если не влазит L2 - еще меньшую L3 . . .
Если целесообраней с точки зрения минимизации отходов, можно взять, например N1*L1+N2*L2+N3*L3
(N - кол-во отрезков, L - дилины из стандартного "набора")
Целевая функция - неиспользованный "обрезок" должен быть минимальной длины.
---
Есть задача проконтролировать выполнение работ по этой тематике, поэтому надо и самому разобраться хотябы с основами минимально.
---
Улыбаюсь Сейчас вписал "довесок" - появилась другая аналогия со взвешиванием Улыбаюсь
« Последнее редактирование: 04-11-2011 16:33 от DneprSMV » Записан

"Не слушайте никаких советов, в том числе и этот" (Сократ ?)
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #3 : 04-11-2011 16:35 » 

Уже более конкретно...
Поищи алгоритмы оптимального раскроя

Идея след.
Трубы соединяются по диаметру (одна к одной, образуя некоторую "плоскость")
А дальше оптимальный раскрой. 
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
DneprSMV
Помогающий

kz
Offline Offline
Пол: Мужской

« Ответ #4 : 04-11-2011 16:59 » 

Sla,
насколько понял, тут будет переход в 2D и соотв. появится вторая переменная которая с одной стороны является константой, с другой стороны может усложнить алгоритм.
(задача, допустим, может решаться чисто математически - с отрезком - и соотв. "диаметром" = 0 )
Хотя может я не вижу "плюсов" перхода на "2D". За идею спасибо.
"Оптимальный раскрой" искал, но там масса коммерческих ссылок, причем на 2D системы.
Вот вспомнилась типовая школьная задача со "взвешиванием" Улыбаюсь
"На одной чаше весов - NNN кг. Как уравновесить весы использую грузы по ......, "
Но там алгоритм "перебора".
Записан

"Не слушайте никаких советов, в том числе и этот" (Сократ ?)
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #5 : 04-11-2011 17:26 » 


Мы правильно друг друга понимаем?

* fig1.jpg (15.61 Кб - загружено 2468 раз.)
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #6 : 04-11-2011 17:49 » 

Я думаю, что если речь о трубе, то количество кусков, из неё нарезаемых, порядка единиц или десятков. А значит без всякого проигрыша по скорости эта задача решается полным перебором (т.е. подстановкой друг к другу) всех требуемых кусков, и выбор варианта с наименьшим неиспользованным обрезком.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
DneprSMV
Помогающий

kz
Offline Offline
Пол: Мужской

« Ответ #7 : 04-11-2011 18:07 » 

Sla,
Да.
Но мне каж-ся двумерное представление задачу усложнит.
В попавшихся мне примерах (в основном по экономике-планированию) фигурируют
системы лин. уравнений вида N1*L1 + N2*L2 ..... + NiLi = LL
, системы ограничений вида N1 > 10, N2<2 ....
и "целевая" функция вида
  LL(длина заготовки) - f(N1,N2,Ni L1,L2,Li) --> 0
  LL(длина заготовки) - f(N1,N2,Ni L1,L2,Li) >= 0
----
решается с использованием матриц.
Но решения для "деления отрезка" не нашел Жаль
(хотя задача вроде "базовая" - напр. разрезать отрезок LL=5м, на заготовки, исходя из стандартных размеров L1=1.1 м, L2=0.5 м, с максимальным использованием длин L1, но с "остатком от резки" не более 0.7 м - Т.е. если остаток более 0.7, то можно сократить кол-во L1 и увеличить L2)


Добавлено через 2 часа, 32 минуты и 16 секунд:
Я думаю, что если речь о трубе, то количество кусков, из неё нарезаемых, порядка единиц или десятков. А значит без всякого проигрыша по скорости эта задача решается полным перебором (т.е. подстановкой друг к другу) всех требуемых кусков, и выбор варианта с наименьшим неиспользованным обрезком.
В общем-то да. Но интересует именно матем. метод.
-------
Вот нечто подобное (Пример 3, раскрой ткани).
http://www.mathelp.spb.ru/book1/lprog2.htm
Приведена постановка задачи, решение (матем). Будем посмотреть.
 
« Последнее редактирование: 04-11-2011 20:40 от DneprSMV » Записан

"Не слушайте никаких советов, в том числе и этот" (Сократ ?)
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #8 : 05-11-2011 08:38 » 

DneprSMV, тогда тебе нужно математически точно описать условия. Я, например,
Цитата: DneprSMV
(например, N1>=3, 0<=N1,<=2 )
Вот этого не понимаю совсем. Тут ошибка знака, и имелось в виду 0<=N1<=3 или что? И если даже наложены допуски на количества в виде неравенств, то во всём этом отсутствует
Цитата: DneprSMV
с максимальным использованием длин L1, но с "остатком от резки" не более 0.7 м
Из неравенств вида 0<=N1<=3, 0<=N2<=5 не следует, что N1=3 предпочтительнее N2=5.

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
DneprSMV
Помогающий

kz
Offline Offline
Пол: Мужской

« Ответ #9 : 05-11-2011 10:33 » 

Dimka,
Да, неверно неравенство привел.

С учетом дополнительных ограничений для N1, N2 .... (например, N1>=3, 0<=N1,<=2 )
должно быть
  . . . . . . . . . . . . . . . . . . . . . . . .  (например, N1>=3, 0<=N2<=2 )
(должно быть не менее 3 отрезков длины L1, но не более 2 отрезков длины L2)
количества отрезков N1 соответствует длинам L1 итд.
В #Ответ 2 прикладная формулировка (резка трубы на заготовки).
Записан

"Не слушайте никаких советов, в том числе и этот" (Сократ ?)
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #10 : 05-11-2011 13:25 » 

В общем, даны потребности в кусках трубы длин Li, количества которых заданы неравенствами вида Ai<=Ni<=Bi. Задача: порезать трубу на куски, чьи размеры и количество соответствуют условиям. Оптимальным решением является решение с минимальным неиспользованным остатком трубы. При этом каждое неравенство нужно стараться максимизировать, а порядковый индекс неравенства играет роль приоритета: при равной оптимальности (минимальности неиспользованного остатка) отдаётся предпочтение максимизации Ni перед максимизацией Nj, если i<j.

У нас тут есть функция отображения вектора Ni на скаляр T. T=L-sum(Li*Ni), где T - размер неиспользованного остатка, L - длина трубы, Li - длина куска трубы, Ni - количество кусков Li-го размера. Надо min T, но при этом областью допустимых значений являются T>=0.

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

Пусть N1>=3, 0<=N2<=2. Перебор будет включать в себя варианты: (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2), (5, 0), ... Т.е. младший разряд числа увеличивается на 1 до достижения верхней границы, затем сбрасывается в нижнюю границу, а более старший разряд увеличивается на 1.

Поскольку неравенства могут не накладывать ограничений сверху, всё равно есть общее ограничение T>=0. Т.е. если наращивать младший разряд, в конце концов выйдем из области допустимых значений, станет T<0. Здесь нужно младший разряд сбросить до нижней границы, и увеличить на 1 более старший разряд. Ограничение снизу есть всегда Ni>=0, даже если не указано явно.

Таким методом можно перебрать все сочетания Ni между собой. Ну а выбрать из этого наилучшее (как по T, так и по приоритету между Ni при одинаковом T для нескольких вариантов) - тривиально.
« Последнее редактирование: 05-11-2011 14:02 от Dimka » Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
DneprSMV
Помогающий

kz
Offline Offline
Пол: Мужской

« Ответ #11 : 05-11-2011 18:20 » 

Dimka,
За детальное описание спасибо. Шас попробую разобраться.
Скорее всего задачу будут решать именно так - "интеллектуальным" перебором
(через ограничивающие условия и сбор статистики по оптимальности вариантов).
Вариантов будет не очень много, тк. будет "базовый" размер L1, и возможные "довески" - скорее всего не более 2 типов - L2 и L3.
Я попробовал загнать задачу в Excel - оно решает, но метод итерационно-оптимизационный.
Записан

"Не слушайте никаких советов, в том числе и этот" (Сократ ?)
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #12 : 05-11-2011 19:52 » 

Коротко говоря, вектор Ni - это точка многомерного пространства. Мысленно это пространство можно представить как матрицу. Но у матрицы границы ровные, а здесь - нет. Всё что надо, это пройтись по всем точкам - метод тот же, что при обработке многомерных массивов, построчное "сканирование". Например, вложенными циклами. Либо одним циклом, но с более "хитрым" правилом перехода от итерации к итерации.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
DneprSMV
Помогающий

kz
Offline Offline
Пол: Мужской

« Ответ #13 : 06-11-2011 10:50 » 

Dimka,
Да, похоже перебор будет эффективен.
вчера вроде нашел раздел, подходящий под эту задачу.
Математическое программирование, но раздел "Нелинейное программирование. Градиентный метод"
Там фигурируют частные производные и гиперпространство. Так что поиск матем. метода я решил на этом для себя закрыть. Хотя если кто найдет алгоритм будет интересно.
----
Метода не намного эффективнее чем перебор. Для 2 переменных ф-ии оптимизации огранизуется 2D плоскость. Для n переменных - соответственно n-мерное гиперпространство.
Прямого решения нет - все равно используются итерации по гиперпространству с поиском "пиков" и "впадин".
----
Хотя может я и ошибся. "У любой сложной задачи есть простое и понятное неправильное решение"  Улыбаюсь
----
ps - лит. И.Ф.Полунин "Курс математического программирования"  Минск 1975, с.333 - "Градиентный метод"
« Последнее редактирование: 06-11-2011 10:54 от DneprSMV » Записан

"Не слушайте никаких советов, в том числе и этот" (Сократ ?)
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #14 : 06-11-2011 16:28 » 

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

Если же оптимизируемая величина имеет линейную зависимость от координаты в гиперпространстве, а само пространство ограничено линейными неравенствами, используют симплекс-метод. Краткая суть его в том, что оптимизируемая величина вдоль каждой прямой границы гиперпространства даёт либо монотонно изменяющуюся прямую, либо константную прямую. Из этого следует, что оптимум обязательно лежит в одной из вершин гипермногогранника границ гиперпространства. А значит не надо "сканировать" всё пространство - достаточно перебрать все вершины, которые являются пересечениями линейных границ, заданных неравенствами. Это существенно ускоряет поиск решения.

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
DneprSMV
Помогающий

kz
Offline Offline
Пол: Мужской

« Ответ #15 : 06-11-2011 20:27 » new

Dimka,
Да у меня нет возражений. Кроме того для меня лично не стоит задача реализовать это в железе.
Нужно сориентироваться в "предметной области". Но мои IQ имеют максимум на линейных задачах Улыбаюсь
Надо ли мне будет разбираться глубже с математикой - сказать не могу. Будет видно через месяц-два. Пока считаю базовым "переборно-оптимизированный" метод, какой ты привел.
---
Реалтайм фигурирует разве что в том смысле, что задача должна гарантированно решаться за определенное время - конкретно - порядка 10 секунд (пока идет "отработка" по основной длине отрезков L1). ПК не проходит. Это избыточно, и с точки зрения надежности не проходит (10-15 секундный ресет, не говоря уж о причудах-"особенностях" ОС). Кроме того, вытягивать работу алгоритма на теоретический максимум смысла нет, материал - железо, диаметр порядка 3-10 см. Улыбаюсь
Записан

"Не слушайте никаких советов, в том числе и этот" (Сократ ?)
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines