мат.программирование - оптимальное деление отрезка LL на N1 отрезков дл. L1 . .

[DneprSMV]

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

[Sla]

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

[DneprSMV]

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

[Sla]

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

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

[DneprSMV]

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

[Sla]

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

[Dimka]

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

[DneprSMV]

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
Приведена постановка задачи, решение (матем). Будем посмотреть.
 

[Dimka]

DneprSMV, тогда тебе нужно математически точно описать условия. Я, например,

(например, N1>=3, 0<=N1,<=2 )

Вот этого не понимаю совсем. Тут ошибка знака, и имелось в виду 0<=N1<=3 или что? И если даже наложены допуски на количества в виде неравенств, то во всём этом отсутствует

с максимальным использованием длин L1, но с "остатком от резки" не более 0.7 м

Из неравенств вида 0<=N1<=3, 0<=N2<=5 не следует, что N1=3 предпочтительнее N2=5.

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

[DneprSMV]

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

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

[Dimka]

В общем, даны потребности в кусках трубы длин 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 для нескольких вариантов) - тривиально.

[DneprSMV]

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

[Dimka]

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

[DneprSMV]

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

[Dimka]

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

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

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

[DneprSMV]

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