組合優化 - 創建傢俱時最大化利潤

Question

某些公司提供大型木製面板。這些面板被切成所需的部分。例如，爲了製作書架，他們必須從大面板上剪下一些碎片。在大多數情況下，豬面板不是從100％使用，會有一些損失，一些剩餘的部分，不能使用。所以爲了最大限度地減少損失，他們必須找到大面板/面板上單獨部件的最佳佈局。我認爲這被稱爲「二維矩形箱包裝問題」。

現在它變得更有趣了。

並非所有面板都是相同的，它們可以有略微不同的色調。理想的書架是由所有從一塊麪板或多塊相同色調的面板切割而成的。但書架可以製作成不同的特性（理想的一種;不同色調的一件;兩件......，三種不同的彩色印版使用等等）。每種質量都有自己的價格。 （質量上乘越貴）。

現在我們有一些庫存的木板，並要求一些傢俱（如100個書架）。目標是使利潤最大化（例如，創建一些理想質量的產品，一些質量較低的產品以減少材料損失）。

如何解決這個問題？如何將它與垃圾箱包裝問題結合起來？和提示，論文/文章將不勝感激。我知道我可以用整數線性規劃來最小化/最大化一些函數和不等式，但我真的不知道如何解決這個問題。 （請不要考慮真實的scenerio，例如最好只創建理想的...想象一下，剩餘材料的損失是每平方釐米X錢，Y是特定的價格產品質量和X和Y可以是「任意的」）

Answer 1

我可以給出這些問題如何解決以及爲什麼你特別困難的想法。

在典型的優化問題中，您希望相對於一定數量的變量（例如長度）來最大化或最小化函數（例如能量）。例如，春天應該花多長時間才能使儲存的能量最小化。答案只是一個數字，即春天的平衡長度。另一個例子是「我們應該以什麼價格設定我們的產品以實現利潤最大化？」 （太貴了，沒有人會買任何東西，太便宜了，你不會支付你的費用。）再次，答案只是一個數字，最優價格。像這樣的優化可以用普通微積分來處理。

更困難的優化問題是答案不是數字，而是函數，如形狀。一個例子是：掛鏈爲了最小化其引力勢能而形成的形狀。或者：爲了實現利潤最大化，我們應該從這些董事會中裁剪出什麼樣的形狀？這種類型的問題是使用變分計算來解決的，這是非常困難的。

在任何情況下，當以數字方式解決優化問題時，需要遵循幾個基本步驟。首先，您必須定義一個函數，例如您想要針對某些變量的「削減」最大化的利潤（削減，參數），並固定其他參數的「參數」。 「params」存儲的信息包括您擁有的木材數量和種類，以及不同類型傢俱的價值。

第二步是拿出了削減的最集中的猜測，我們把它叫做cuts_guess。爲了做到這一點，你需要提出一個算法，該算法將建議你可以使用你所擁有的耗材實際製作的一套傢俱。例如，如果您可以在每塊木板上至少製作一個書架，那麼這可能是您最初使用木材的最佳方式。

第三階段是優化。對於初始化，設置cuts_best = cuts_guess和profit_best = profit_guess = profit（cuts_guess，params）。然後你需要（一種算法）對'削減'進行小的僞隨機變化，並檢查利潤是增加還是減少。記錄您找到的最佳切割組合以及相應的利潤。通常情況下，如果存在一些隨機性，最好的做法是爲了探索最多的可能性，而不是被困在一個糟糕的選擇上。如果查找「蒙特卡羅算法」，你會找到這方面的例子。

無論如何，所有這些對你的問題都會很困難。如何猜測變量（例如長度），然後如何改變該猜測（例如增加或減少長度）很容易。關於如何在電路板上放置缺口或如何進行小小的改變，如何做出「猜測」並不明顯。