Дано:

Набор деталей разной длины (для простоты — брусков)
Которые нужно напилить из бревен.

Имеются так же бревна длиной 8 и 12 метров

Требуется: распределить эти детали по бревнам, чтобы сумма остатков после распилки была наименьшей.

При этом лучше один остаток 3 метра, чем три остатка по 1 метру (судя по всему нелинейный критерий оптимизации)

В какую сторону копать?

Здравствуйте, defrag, Вы писали:

D>В какую сторону копать?

Для начала — задача оптимального раскроя.

Здравствуйте, defrag, Вы писали:

D>Дано:

D>Набор деталей разной длины (для простоты — брусков)
D>Которые нужно напилить из бревен.

D>Имеются так же бревна длиной 8 и 12 метров

D>Требуется: распределить эти детали по бревнам, чтобы сумма остатков после распилки была наименьшей.

D>При этом лучше один остаток 3 метра, чем три остатка по 1 метру (судя по всему нелинейный критерий оптимизации)

D>В какую сторону копать?

симплекс метод

У симплекс метода линейная целевая функция

Здравствуйте, defrag, Вы писали:

D>У симплекс метода линейная целевая функция
Ну так попробуй сотворить линейную целевую функцию
например вот так:
min: Sum_i(Rest_i) + Sum_i(SomeCoef/Rest_i)

Sum_i — сумма по i, Rest_i — i-й остаток, SomeCoef — некий коэффициент, который можно попробовать подобрать экспериментально

Хм, не плохо.
А что делать в случае Rest_i=0

Здравствуйте, defrag, Вы писали:

D>Хм, не плохо.
D>А что делать в случае Rest_i=0

Sum_i(SomeCoef/(Rest_i+1))

ну или добавлять не 1, а некую другую константу, определяющую "минимальный единичный" остаток.

Таким образом имеем следующую постановку задачи:

дано L1....Li — длины деталей
Q1...Qi — количество деталей i-ой длины
Lbr1.... Lbrт — длины бревен
Nxy — количество деталей длины Ly в бревне Lbrx

тогда имеем систему неравенств

N11*L1+N12*L2+...+N1i*Li<=Lbr1
.............................
............................. (1)
Nm1*L1+Nm2*L2+...+Nmi*Li<=Lbrm

N11+N21+..+Nm1=Q1
................. (2)
.................
N1i+N2i+..+Nmi=Qi


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

Я правильно понимаю?

Здравствуйте, defrag, Вы писали:


D>Далее следует неравенства 1 преобразовать в равенства путем введемия дополнительных переменных...
Т.е. остатков.
D>И искать базисное решение от которого плясать дальше?

D>Я правильно понимаю?
Вполне


ЗЫ
А каким образом задается количество бревен каждой длины?

B>ЗЫ
B>А каким образом задается количество бревен каждой длины?

Это тоже часть задачи

Это тоже нужно определить.

Есть идея. Задать начальное количество бревен сумма длин которых равна или чуть больше суммы длин деталей.
Попытаться решить задачу. Если нет ни одного решения. Добавить бревно. и повтороить. И т.д.

Вот только кажется симплекс метод даст нецелочисленные решения.

Как перейти к целочисленным?

Есть такая известная задача- Задача о рюкзаке. Смысл ее в том, что есть рюкзак который вмещает S кг веса, и есть набор i = 1...N предметов каждый Mi кг. Нужно выбрать такие предметы, чтобы "унести" в рюкзаке как можно больше, но не превысить предельную норму. Так вот существует доказательство, что это задача класса NP- т.е. реашется полным перебором.
Я все это говорил к тому, что ваша задача это более общий случай задачи о рюкзаке (рюкзаков у вас много). Так что никак кроме полным перебором не решить.

Здравствуйте, ukman, Вы писали:

U>Есть такая известная задача- Задача о рюкзаке. Смысл ее в том, что есть рюкзак который вмещает S кг веса, и есть набор i = 1...N предметов каждый Mi кг. Нужно выбрать такие предметы, чтобы "унести" в рюкзаке как можно больше, но не превысить предельную норму. Так вот существует доказательство, что это задача класса NP- т.е. реашется полным перебором.
U>Я все это говорил к тому, что ваша задача это более общий случай задачи о рюкзаке (рюкзаков у вас много). Так что никак кроме полным перебором не решить.

Эта "известная задача о рюкзаке" вообще-то совсем другая. Там у каждого предмета есть объем и некоторая стоимость/полезность. И необходимо максимизировать стоимость/полезность выбранных предметов в пределах объема рюкзака. Она действительно NP-трудная. Решается обычно с помощью динамического программирования, если позволяют ограничения на ресурсы и входные данные. Подробнее тут http://en.wikipedia.org/wiki/Knapsack_problem
А эта задача больше похожа на Cutting stock problem

Интересные статьи.

А по-русски как эти методы называются?
Cutting stock problem в принципе похоже по смыслу на задачу об оптимальном раскрое
А вот Delayed Column Generation как не переводил, ничего вразумительного в русском поиске не нашел.

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

Здравствуйте, defrag, Вы писали:

B>>ЗЫ
B>>А каким образом задается количество бревен каждой длины?

D>Это тоже часть задачи
D>Это тоже нужно определить.

D>Есть идея. Задать начальное количество бревен сумма длин которых равна или чуть больше суммы длин деталей.
D>Попытаться решить задачу. Если нет ни одного решения. Добавить бревно. и повтороить. И т.д.

D>Вот только кажется симплекс метод даст нецелочисленные решения.
D>Как перейти к целочисленным?

Что-то я не совсем понял — а сколько бревен каждой длины должно быть в этой сумме? В этом ведь главная трудность?
Я бы попробовал сделать следующим образом:
В исходные неравенства добавил бы заведомо большие количества бревен каждой длинны, а в целевую функцию добавил бы слагаемое, определяющее стоимость использованных бревен...

B>В исходные неравенства добавил бы заведомо большие количества бревен каждой длинны...
Для нахождения минимального количества бревен каждой длины можно использовать задачу упаковки (bin-packing problem). Насколько я знаю, существует достаточно много методов ее решения...

_DA>Эта "известная задача о рюкзаке" вообще-то совсем другая. Там у каждого предмета есть объем и некоторая стоимость/полезность. И необходимо максимизировать стоимость/полезность выбранных предметов в пределах объема рюкзака.

Да вы педант.
Я просто немного перефразировал, чтобы было больше похоже на исходную задачу. Если в вашей формулировке поменять объем на массу, а функцию полезности приравнять к объему/весу, то получится в точности что я сказал. Главное другое- задача класса NP и решается за экспоненциальное время.

Здравствуйте, ukman, Вы писали:

_DA>>Эта "известная задача о рюкзаке" вообще-то совсем другая. Там у каждого предмета есть объем и некоторая стоимость/полезность. И необходимо максимизировать стоимость/полезность выбранных предметов в пределах объема рюкзака.

U>Да вы педант.

U>Я просто немного перефразировал, чтобы было больше похоже на исходную задачу. Если в вашей формулировке поменять объем на массу, а функцию полезности приравнять к объему/весу, то получится в точности что я сказал. Главное другое- задача класса NP и решается за экспоненциальное время.

Ну быть педантом, так до конца. Вспомним

"Есть такая известная задача- Задача о рюкзаке. Смысл ее в том, что есть рюкзак который вмещает S кг веса, и есть набор i = 1...N предметов каждый Mi кг. Нужно выбрать такие предметы, чтобы "унести" в рюкзаке как можно больше, но не превысить предельную норму. Так вот существует доказательство, что это задача класса NP- т.е. реашется полным перебором."

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

_DA>То есть нужно максимизировать количество предметов в рюкзаке, не превысив суммарный вес S. Так вот эта задача решается следующим образом: сортируем предметы по неубыванию веса, потом жадным алгоритмом берем предметы пока рюкзак не заполнится.

Что значит "по не убыванию" веса?
Попробуйте заполнить рюкзак на 10 (уе ) предеметами 7 5 4 3 2 1 вашим алгоритмом?

Здравствуйте, ukman, Вы писали:


_DA>>То есть нужно максимизировать количество предметов в рюкзаке, не превысив суммарный вес S. Так вот эта задача решается следующим образом: сортируем предметы по неубыванию веса, потом жадным алгоритмом берем предметы пока рюкзак не заполнится.

U>Что значит "по не убыванию" веса?
То и значит
U>Попробуйте заполнить рюкзак на 10 (уе ) предеметами 7 5 4 3 2 1 вашим алгоритмом?

сортировка: 1 2 3 4 5 6 7
заполнение: 1 2 3 4 | 5 6 7
Четыре предмета поместили.

А как тогда система уравнений выглядеть будет?