Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Нарезка арматуры

Автор: Slowler 16.2.2007, 19:26

Даны длины необходимых прутьев. Нужно нарезать их из длинных прутьев определенного размера, чтобы максимально сэкономить материал (Исключить длинные обрезки).
Есть ли алгоритмы позволяющие решить эту задачу.
Помогите мне пожайлуста решить. smile

Автор: podval 16.2.2007, 20:16

Целочисленное линейное программирование. Задача формулируется с пол-пинка.

Автор: SoWa 17.2.2007, 05:27

http://alglib.sources.ru/
Книжки: А.Кофман "Методы и модели исследования операций".
Могу скинуть на мыло(10Мб) Там есть вроде такая задача.
Oftop: скинхэды режут арматуру, чтобы побольше армию собрать smile

Автор: Reptile 17.2.2007, 12:19

Цитата(Slowler @ 16.2.2007, 19:26

)

Я тоже уже неделю бьюсь над этим вопросом вот что получилось:
Для этого решения необходимо использовать Симплекс метод. Его можно скачать http://www.openproj.ru/simplex/simplex.zip пример эго использования http://www.openproj.ru/simplex/simplgui.zip. Следующим этапом стал подбор ограничений для него( написал на Delphi но надеюсь алгоритм будет понятен) а сама идея следующая: необходимо перебрать все варианты(комбинации) размеров(на которые необходимо разрезать) для этого я решил перебрать соответствующие индексы массива в котором находятся размеры порезок, вот пример для 5-ти разрезов:

Код


procedure TForm1.Button1Click(Sender: TObject);
begin
   p1('12345');
end;

procedure TForm1.p1(s:string); // 
var i,j,c:integer;
k  : string;
begin
 for i:=1 to length(s) do
  begin
     k := '';
     p2(s,k,i);// рекурсивная функция которая перебирает все варианты
   for i := 0 to Memo1.Lines.Count-1 do // удаление повторений из Memo1
     for j := i+1 to Memo1.Lines.Count do
     begin
         if Memo1.Lines.Strings[i] = Memo1.Lines.Strings[j] then
         Memo1.Lines.Delete(j);
     end;
end;

procedure TForm1.p2(s,z:string;i:integer);// рекурсивная функция которая перебирает все варианты
var
  j, c    : Integer;
  k       : String;
begin
   k := z;
     for j := i to length(s)-1 do
     begin
       k := k + s[j]+'+';
       for c := j+1 to length(s) do
       begin
         if c < length(s) then
           p2(s,k,c);
         Memo1.Lines.Add(k + s[c]);// вывод всех вариантов в Memo1
       end;
     end;
end;

Результат:

Код


1+2+3+4+5
1+2+3+4
1+2+3+5
1+2+3
1+2+4+5
1+2+4
1+2+5
1+2
1+3+4+5
1+3+4
1+3+5
1+3
1+4+5
1+4
1+5
2+3+4+5
2+3+4
2+3+5
2+3
2+4+5
2+4
2+5
3+4+5
3+4
3+5
4+5

Этот этап я завершил smile

, теперь необходимо отсеять варианты которые не подходят, например '2+3' - это значит что мне необходима комбинация r[2] и r[3](где r - массив с размерами порезок), если сумма r[2]+r[3] превысит длину прута из которого будем нарезать, то этот вариант необходимо тоже исключить.
Далее(после отсеивания) я запишу строку '4+5' в массив t[0..4] как

Код


t[0] = 0; 
t[1] = 0;
t[2] = 0;
t[3] = r[4];
t[4] = r[5];

А этот массив и будет коэффициентами в ограничениях для симплекс метода. smile

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

Буду рад критике и исправлениям ошибок.