комбинаторная оптимизация - максимальная прибыль при создании мебели

Question

Некоторая фирма снабжена большими деревянными панелями. Эти панели разрезаны на требуемые детали. Чтобы сделать, например, книжную полку, они должны вырезать кусочки с большой панели. В большинстве случаев панель свиньи не используется от 100%, будет некоторая потеря, некоторые остаточные части, которые не могут быть использованы. Поэтому, чтобы свести к минимуму потерю, они должны найти оптимальное расположение отдельных частей на большой панели/панели. Я думаю, что это называется «проблема упаковки двумерного прямоугольника».

Теперь это становится более интересным.

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

Теперь у нас есть несколько деревянных панелей на складе и запрос на мебель (например, 100 книжных полок). Цель состоит в том, чтобы максимизировать прибыль (например, создавать некоторые из них в идеальном качестве, а некоторые - в меньшем качестве, чтобы снизить потери материала).

Как решить эту проблему? Как совместить его с проблемой упаковки корзины? И намеки, документы/статьи будут оценены. Я знаю, что могу минимизировать/максимизировать некоторую функцию и неравенства с целым линейным программированием, но я действительно не знаю, как это решить.

(пожалуйста, не считайте реальным scenerio, когда, например, было бы лучше создать только идеальные ... представьте себе, что потеря из оставшегося материала равна X деньгам на см^2, а Y - цена для конкретных качество продукта и что X и Y могут быть «произвольными»)

Answer 1

Я могу дать представление о том, как эти проблемы решены и почему ваши особенно трудны.

В типичной проблеме оптимизации вы хотите максимизировать или минимизировать функцию (например, энергию) относительно заданного числа переменных (например, длины). Например, как долго должна быть пружина, чтобы минимизировать накопленную энергию. Ответ - это просто число, равновесная длина пружины. Другой пример: «какую цену мы должны установить, чтобы наш продукт максимизировал прибыль?» (Слишком дорого, и никто не купит ничего, слишком дешево, и вы не будете покрывать свои расходы.) Опять же, ответ - это просто номер, оптимальная цена. Подобные оптимизации обрабатываются обычным исчислением.

Гораздо более сложная проблема оптимизации заключается в том, что ответ не является числом, а функцией, подобной форме. Примером является: какая форма будет висит цепочкой, чтобы свести к минимуму ее потенциальную энергию гравитации. Или: какую форму мы должны вырезать из этих досок, чтобы максимизировать прибыль? Этот тип проблемы решается с помощью вариационного исчисления, что очень сложно.

В любом случае, при численном решении задач оптимизации необходимо выполнить несколько основных шагов. Сначала вам нужно определить функцию, например, прибыль (разрезы, параметры), которую вы хотите максимизировать по отношению к некоторым сокращениям переменных, с параметрами других параметров. «params» хранит информацию, такую ​​как количество и тип дерева, который у вас есть, и количество денег, которое стоит различный тип мебели.

Второй шаг - придумать предположение о наилучшем наборе разрезов, назовем его cuts_guess. Чтобы сделать это, вам нужно разработать алгоритм, который предложит набор мебели, который вы могли бы сделать, используя имеющиеся у вас материалы. Например, если вы можете сделать по крайней мере одну книжную полку с каждой доски, то это может быть вашим первоначальным предположением о наилучшем способе использования дерева.

Третий этап - это оптимизация. Для инициализации установите cuts_best = cuts_guess и profit_best = profit_guess = profit (cuts_guess, params). Затем вам нужно (алгоритм) сделать небольшие псевдослучайные изменения «разрезами» и проверить, увеличивается или уменьшается прибыль. Запишите наилучший набор разрезов, который вы найдете, и соответствующую прибыль. Обычно лучше всего, если есть какая-то случайность, чтобы исследовать наибольшее количество возможностей и не «застревать» на плохом выборе. Вы найдете примеры этого, если будете искать «алгоритм Монте-Карло».

В любом случае, все это будет очень сложно для вашей проблемы. Легко понять, как выбрать переменную (например, длину), а затем как изменить это предположение (например, увеличить или уменьшить длину). Не совсем очевидно, как сделать «предположение» о том, как разместить вырез на доске или как сделать небольшое изменение.