Алгоритм раскроя прямоугольных листов

[hasherfrog]

Ищу алгоритм (не готовую программу) для оптимального раскроя листов материала прямоугольной формы. Нужно полное матес\матическое описание с формулами. Нашел пока только книгу Мухачева Э.А. Рациональный раскрой промышленных материалов. Применение в АСУ. -М . :Машиностроение. 1984. Но ее к сожалению нет в библиотеке. Поделитесь ссылками или скажите в каких еще книга поискать.

[hasherfrog]

Оригинальное решение

А вообще-то есть

много чего

по поводу.

[pva]

Это стандартная задача, решается вроде симплекс-методом. Посмотри задачу (не помню книги) об оптимальном распиливании бревна. Идея примерно такая:

Нужно чтобы суммарный остаток материала был минимальным.

X[n]=sum(x[n,i])+r[n], sum(r[n])->min. Переписываешь в канонической форме и вперёд.

[pva]

hasherfrog

По ссылке на "оригинальное решение" не удается ничего скачать, если можно то еще ссылку на этот материал или если есть пошли на мыло.

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

Посоветуте самый простой в реализации.



[s]Исправлено: Prisoner, 1:43 10-06-2004[/s]

[hasherfrog]

Нда, что-то пропала ссылка. Посмотрите тогда

это

.

А вообще,


Цитата:



В настоящее время существует множество алгоритмов оптимизации раскроя. Среди  них выделяют следующие:

• безусловная однопараметрическая оптимизация;

• методы исключения интервалов;

• методы с использованием производных;

• генетические алгоритмы.