Выполнение оптимизации на VB6.0 по раскрою

Здравствуйте! Прошу помощи.

Научите, пожалуйста, бегло решать оптимизационные задачи на раскрой материалов с помощью Visual Basic 6.0

Условия. На рынке имеется неограниченное количество досок, длиной 350 см. Нам нужно подсчитать оптимальную закупочную партию для выполнения заказа, чтобы отходы, оставшиеся обрезки — были минимальные.
По принципу одного дня: купили, распилили и продали. Нет склада, где хранить обрезки — поэтому все остатки вывозятся на свалку, как мусор.
По заказу клиента нужны следующие заготовки:
1) длина заготовки № 1 = 185 см, количество — 127 штук;
2) длина заготовки № 2 = 165 см, количество — 178 штук;
3) длина заготовки № 3 = 143 см, количество — 335 штук;
4) длина заготовки № 4 = 87 см, количество — 526 штуки;
5) длина заготовки № 5 = 26 см, количество — 958 штуки.

0

Сообщение от Willi2001 Потребуется досок l=350: 127 + 51 + 162 + 141 + 16 + 1 = 498 штук

Сообщение от Pro_grammer Считал чуть меньше 3-х минут, долго данные вводил в программу. Расчет ТС верный!

Решение в 498 заготовок - не самое оптимальное, данные исходные детали можно уложить в 497 заготовок:
185 + 87 + 26*3 = 350 (остаток 0) - 26 повторений
185 + 165 = 350 (остаток 0) - 101 повторение
87*4 = 348 (остаток 2) - 125 повторений
165 + 26*7 = 347 (остаток 3) - 77 повторений
143*2 + 26*2 = 338 (остаток 12) - 167 повторений
143 + 26*7 = 325 (остаток 25) - 1 повторение

Итого: 26+101+125+77+167+1= 497 заготовок

Решал своей программой по раскрою (реализовано на VBA в Excel)
На решение потребовалось примерно полминуты, из которых 29 секунд - ввод данных и 1 секунда - поиск решения.
Все полученные схемы во вложении, а также видео, как производится расчет.
Данная задача имеет множество разных решений (для 497 заготовок), одно из которых я выложил. В данном варианте производится максимизация остатка от последней заготовки.

На текущий момент реализовал алгоритм решения задачи линейного раскроя с помощью динамического программирования (DP), в основе которого решение задачи "сумма подмножеств" или "задача о рюкзаке", когда "рюкзаков" много.
Также реализовал решение методом целочисленного линейного программирования (LP) на базе метода Гилмора-Гомори
Данный способ (линейное программирование) позволяет найти оптимальное решение, которое не всегда находится динамическим программированием.

Нашел тему на форуме по окнам, по сравнению различных программ по линейному раскрою:
http://forum-okna.ru/index.php?showtopic=35118

По результатам расчетов на тестовых данных, мои алгоритмы обошли все упомянутые там специализированные программы, свои результаты выложил на 5й странице

Вложения

CSP_m-ch.rar (516.2 Кб, 32 просмотров)

1

m-ch, у тебя пила тоньше.

0

Сообщение от Catstail Важен алгоритм. Опиши его, а программа в данном случае второстепенна.

Если задачу рескроя не сводить к "жадному" алгоритму или тривиальному "задача о рюкзаке", то методы ее решения уже давно сформулированы и описаны:
http://citeseerx.ist.psu.edu/v... 1&type=pdf
http://www.dcc.fc.up.pt/~fdabr... report.pdf
В основе - целочисленное линейное программирование, которое основывается на концепции Контаровича.

Здесь сложным моментом является построение LP модели и дальнейшее ее решение.
Если основываться на методе Гилмора-Гомори, то необходимо найти рациональные (оптимальные по Парето) схемы раскроя, алгоритм не сложный, но таких схем может быть очень много, десятки тысяч (или миллионы и более), если используются заготовки большого размера и нужно изготовить много различных деталей малого размера, поэтому данный способ не всегда применим.

При реализации метода Валерио де Карвальо (когда вместо схем раскроя составляются возможные дуги) столкнулся со сложностью, при построении LP модели из несколько десятков тысяч переменных на ее решение уходят минуты или десятки минут. В качестве решателя LP модели использую библиотеку lpsolve (она имеет достаточно удобный API и может запускаться из различных приложение написанных на различных языках программирования).
При этом, если полученную модель в виде файла mps подсунуть в коммерческий Gurobi Optimization (в качестве демонстрации можно воспользоваться бесплатно: http://www.neos-server.org/neo... i/MPS.html)
То на решение данной модели уходят секунды.

Добавлено через 6 минут

Сообщение от SoftIce у тебя пила тоньше.

Ну, да.
Я размер (ширину) реза занулил

1

Сообщение от m-ch мои алгоритмы обошли все упомянутые там специализированные программы

Ну и где они, хваленые ваши алгоритмы?
Мы в этой теме вроде как не пиписками меримся, а знаниями делимся.

0

Сообщение от Pro_grammer Ну и где они, хваленые ваши алгоритмы?

Программа (в том виде как она есть) продается, но могу дать подробное описание алгоритма.
Знающему человеку не составит труда реализовать его на любом языке программирования.

Ссылки на методологию с использованием линейного программирования я дал в 23 посте
Достаточно наглядное описание на русском языке есть здесь: http://al-vo.ru/spravochnik-ex... excel.html

Для указанных данных есть 18 вариантов рациональных схем раскроя:

Во вложении составленная модель, которая решается с помощью "Поиск решения" в Excel

Альтернативные алгоритмы:
Серия "жадных" алгоритмов на примере задачи об упаковки в контейнеры (принципиально от задачи раскроя не отличается):
Next Fit Algorithm

First Fit Algorithm

Worst Fit Algorithm

Best Fit Algorithm

"Жадные" алгоритмы достаточны просты в реализации, работают очень быстро, но дают, как правило, не оптимальное решение.

Применение алгоритма "Задачи о рюкзаке" ("Сумма подмножеств")


Генетический алгоритм

Вложения

SolverMS.xlsx (91.2 Кб, 55 просмотров)

0

Сообщение от Pro_grammer Ну и где они, хваленые ваши алгоритмы?

Demo-версию выложил здесь: https://www.cyberforum.ru/post8704132.html

1

Сообщение от m-ch Demo-версию выложил здесь

Спасибо, интересно было посмотреть.
А вот в чем преимущество линейного алгоритма от динамического? Т.к. в демо нет возможности сравнить, скажите, там быстрее считает или точнее?
Экспериментировал с настойками Быстро->Очень медленно, вроде на точность расчетов не влияет?
И ещё вопрос, с "Экспорт в PDF" ясно, там очевидно формируется отчет в PDF.
А вот кнопка "Создать отчет" что делает ( в полной версии )?

0

Сообщение от Pro_grammer А вот в чем преимущество линейного алгоритма от динамического?

В основе динамического алгоритма - решение задачи о рюкзаке методом целочисленного динамического программирования. Реализовать данные метод очень легко.
1. Берем первую заготовку
2. Динамическим программированием подбираем детали сумма которых меньше или равна размеру заготовки с определенным допуском погрешности.
3. Исключаем из перечня детали, которые использовали.
4. Берем следующую заготовку и переходим на п. 2
и т.д. пока не закончатся заготовки или детали.
Данный метод, как правило, намного лучше "жадного" алгоритма.
Результат раскроя сильно зависит от сортировки заготовок и деталей, поэтому с помощью перемешивания запускаем решение несколько раз и выбираем лучший вариант.
Метод "Быстро" отличается от "Медленно" количеством итераций (попыток решения).
Как правило способ "Медленно" и "Очень медленно" находит решение лучше чем при "Быстром" способе.
Данные метод не гарантирует нахождения оптимального раскроя, но хорошо справляется с задачей для реальных данных (в оконном производстве), когда заготовка имеет большой размер (6 или 6,5 метров), а детали небольшой (от 0,5 метра до 2х метров).

Алгоритм с использованием линейного программирования основан на методологии Л.В. Кантаровича (Канторович Л.В., Залгаллер В.А. "Рациональный раскрой промышленных материалов")
Принцип решения: составляем все возможные рациональные (оптимальные по Парето) схемы раскроя. Здесь также применяем динамическое программирование.
Далее строим lp-модель с указанием в качестве целевой функции минимизацию количества используемых заготовок. Решать систему можно как встроенным в Excel инструментом "Поиск решения" (решать не очень удобно, т.к. стандартный Solver имеет большие ограничения на количество переменных), так и сторонними библиотеками: http://sourceforge.net/projects/lpsolve, https://projects.coin-or.org/Cbc, http://www.gurobi.com/
Как результат, будет найдено оптимальное решение (использование наименьшего количества заготовок). Можно также автоматизировать максимизацию полезного остатка от последней заготовки.
Данные способ хорошо работает при небольшом размере заготовок и достаточно большом размере деталей (20% - 30% от размера заготовки).
Ограничение метода - при малом размере деталей относительно заготовки, может быть огромное количество схем раскроя (несколько сотен тысяч или миллионов), что не позволит найти решение системы либо на решение уходит очень много времени, но в данном случае с задачей раскроя хорошо справляется динамическое программирование.
Сочетание методов DP и LP позволяет находить оптимальное решение.

Сообщение от Pro_grammer А вот кнопка "Создать отчет" что делает ( в полной версии )?

На кнопку "Создать отчет" пока не повешен макрос, т.к. требования у всех разные, приходится индивидуально подходить к составлению отчетов.

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

Вложения

CSP.zip (5.74 Мб, 49 просмотров)

3

m-ch, как с вами связаться?

0

smivan85, какой вопрос? Можете написать мне в личку

0

m-ch, вопрос о стоимости вашей программы... в личку я пока не могу написать видимо, и нигде вашего емейла не нашел. Мой емейл - логин + собака яндекс

0

smivan85, демо версия, на которую есть ссылка полностью функциональна и без ограничений
Кроме того, на excelworld, где выложена сама демо версия есть и другие мои варианты линейного раскроя, в т.ч. с открытым кодом.

0

SoftIce, SoftIce, а можно посмотреть код, пожалуйста?

0

Yaszon, что именно Вам нужно, открытый код именно от программы SoftIce или от любого другого приложения по раскрою? Думаю, что в начале нужно оценить качество раскроя различных программ, если приложите свои исходные данные, то смогу их раскроить своей программой, сможете оценить качество раскроя

0

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

Вложения

CSP_LP_cut_Wizard.xlsx (207.5 Кб, 30 просмотров)

1