VPF::Нарезка арматуры - Форум программистов

Slowler

Дата 16.2.2007, 19:26 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 16.2.2007

Репутация: нет
Всего: нет

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

Это сообщение отредактировал(а) Slowler - 16.2.2007, 19:28

podval

Дата 16.2.2007, 20:16 (ссылка)

(нет голосов)

Загрузка ...

Где я? Кто я?

Профиль
Группа: Экс. модератор
Сообщений: 3094
Регистрация: 25.3.2002
Где: СПб

Репутация: 18
Всего: 62

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

SoWa

Дата 17.2.2007, 05:27 (ссылка)

(нет голосов)

Загрузка ...

Харекришна

Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 6
Всего: 74

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

--------------------

Всем добра smile

Reptile

Дата 17.2.2007, 12:19 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 115
Регистрация: 30.9.2006
Где: Украина, Первомай ск

Репутация: нет
Всего: 3

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

)

Я тоже уже неделю бьюсь над этим вопросом вот что получилось:
Для этого решения необходимо использовать Симплекс метод. Его можно скачать здесь пример эго использования здесь. Следующим этапом стал подбор ограничений для него( написал на 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

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

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »