Как решить задачу о раскрое в Excel

Автор Alice Liddell, 20.09.2015, 22:53

« назад - далее »

Alice Liddell

Здравствуйте,

Дано условие задачи:

Есть стальная лента заданной ширины (l=1250 миллиметров), ее нужно раскроить на n более узких лент (разной или одинаковой ширины) таким образом, чтобы в результате раскроя получилось заданное соотношение весов раскроенных лент. При каждом виде раскроя получается некий расход. Заданы ширина каждой ленты (каждого вида ленты) и их массы, и их соотношения. Сумма ширин лент не обязательно равна ширине исходной. Каждому способу раскроя соответствует некий расход.  Найти самый оптимальный способ.

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

Способ раскроя l_i (набор векторов). В конце раскроя надо получить заданное соотношение по весу раскроенного металла. (Например- 300 тонн такой-то ленты, 400 тонн другой ленты). Это нужно получить с минимальным отходом.

(написать на excel)

(Количество лент, на которые можно резать рулон, не более 10-ти).

Пыталась найти похожее в интернете, однако, дается лишь максимум определение задачи. Очевидно, это подвид задачи об оптимизации отходов, однако как решать такую задачу, не совсем понятно.

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

MCH

Цитировать(написать на excel)
Это учебная задача или нужно для работы?
Если учебная - то нужно ее решить с помощью надстройки "Поиск решения"
Если рабочая, то тема оптимального раскроя достаточно сложная.

Приложите пример Ваших данных.
Например, есть неограниченное кол-во лент шириной 1250 мм, необходимо нарезать их на полосы 400 мм - ??? штук, 300 мм - ??? штук, 100 мм - ??? штук с минимальными отходами.
Тогда можно будет решить задачу оптимизации

Alice Liddell

#2
Добрый день, спасибо вам большое за то, что откликнулись.

Скажите пожалуйста, почему не рекомендуется использовать данную надстройку для рабочей задачи?

Можно как пример взять следующие цифры- есть 5 исходных лент, нарезать нужно- 8 лент шириной 400 мм, 5 лент шириной 300 мм и 9 лент шириной 100 мм.

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

MCH

Вы так и не ответили, это учебное задание или рабочее?
Цитата: Alice Liddell от 24.09.2015, 17:38Скажите пожалуйста, почему не рекомендуется использовать данную надстройку для рабочей задачи?
В реальных условиях, как правило, требуется нарезать большое кол-во деталей (как вариантов длин, так и количества самих деталей), и количество различных вариантов раскроя получается очень большим. "Поиск решения" не применим в виду его ограничений (200 изменяемых ячеек).
Даже по приложенному Вами варианту: 400 - 8 шт, 300 - 5 шт, 100 - 9 шт, получается 57 различных вариантов раскроя заготовок длиной 1250 мм

Во вложении два примера раскроя, первое получено динамическим программированием (решения задачи "сумма подмножеств"), второе - "поиском решения"

IKor

За ночь поиск решения нашел то, что руками находится менее чем за минуту...
:)

MCH

Цитата: IKor от 25.09.2015, 09:57
За ночь поиск решения нашел то, что руками находится менее чем за минуту...
:)
Я по другому использовал "Поиск решения" (см. вложение).
Сгенерировав предварительно все варианты раскроя заготовки.
Решение находится за секунды.

IKor

Цитата: MCH от 25.09.2015, 12:22
Сгенерировав предварительно все варианты раскроя заготовки.
Решение находится за секунды.
Правильно ли я понимаю, что для решения другой задачи потребуется заново заполнять таблицу вариантов, аналогичную I9:K65 ?
В таком случае, время заполнения нужно добавить к полученным секундам... :)

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

MCH

#7
Цитата: IKor от 25.09.2015, 15:17В таком случае, время заполнения нужно добавить к полученным секундам... :)
Алгоритм составления карт раскроев достаточно простой и программным способом их составление занимает доли секунды
Пример решения данной задачи см. на видео: https://yadi.sk/i/EmLRtD_MjKy62

Цитата: IKor от 25.09.2015, 15:17Для заданной задачи один из вариантов раскроя вручную находится быстрее, чем заполняется ваша таблица
IKor, попробуйте найти "ручное" решение для исходных данных в задаче раскроя описанной в Википедии: https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D1%80%D0%B0%D1%81%D0%BA%D1%80%D0%BE%D1%8F
Видео с решением задачи через "Поиск решения": https://yadi.sk/i/-vueHRbSjKy8v
Пример решения с картами раскроя - во вложении
Стоит отметить, что не все специализированные программы линейного раскроя могут раскроить данные из Википедии в 73 заготовки (обычно в 74 или более)

При более сложных примерах не удается применить "Поиск решения", упираемся в ограничения - 200 изменяемых ячеек.