Re: [工數] 原料裁切求解最佳模式
※ 引述《shunit (dontshunit)》之銘言：
: 有一家工廠生產一個20公分長的原料，目前有三家公司分別來訂購
: 5公分15000支、7公分20000支及9公分30000支，
: 該工廠的裁切台可以設定以下6種裁切方式，
: 1. 請寫一個模式求解剩餘料最少的裁切方式，剩餘料包括廢料及超出訂單的部分(只寫模
: 式即可,不必求解);
: 2. 請用Σ form重寫模式。
: https://i.imgur.com/7s2Dd0Y.jpg
: 不知道這發文該如何分類
: 雖然不求解但好複雜想出最佳模式腦袋已打結
這是作業研究中的Cutting Stock Problem
計算複雜度為NP-hard
對於中型或大規模的問題要在合理的時間內找到最佳解很困難
本問題是小規模 只有三種需求跟六種切割的模式
推文之中有人一開始用直觀式的想法要大量使用廢料為零的模式D
這就是作業研究中所謂的Heuristics 啟發式算法的想法
不保證找到的解為全局最佳 但是求解時間快
工業界的困難問題通常都用Heuristics
因為有時候找到一個可行滿足所有限制的解都很花費時間了 不在乎全局最佳
Cutting Stock problem在作業研究的課程中通常是拿來講解「分解式演算法」
Decomposition method for large-scale optimization
因為變數跟限制式很多的時候如果能夠聰明的分解問題透過迭代來找到全局最佳
會比直接用求解器(optimization solver)求解快
而Cutting Stock對應的分解演算法叫做(delayed) column generation
因為本問題在實際應用上 最佳化模型的變數會比限制式多出非常多
需要透過分解式的演算法 去慢慢的加入變數 而不是一次列出求解
怎麼求解超出原Po的需求就不多說
想回文澄清一下這是 作業研究的整數規劃範圍
而不是線性代數也不是線性規劃 （線性規劃我們通常指變數為連續而不是離散）
回到原Po的問題
已知參數
給定 m 個訂單 每份訂單對應 q_j 個需求 j = 1~m
另外總共有k種切割方式 每一種切割方式會產生 c_i 個剩餘料 i = 1~k
讓a_ij 代表訂單j在切割方式i可裁出的方式
定義決策變數 x_i 為裁切方式i的使用次數 注意x_i 為非負整數
目標函數為極小化剩餘料
min 4x_A + 3x_B + x_C + x_E + 2x_F
限制式
2x_B + 2x_C + 4x_D + x_E >= 15000 訂單一的需求
x_A + x_B + 2x_E >= 20000 訂單二的需求
x_A + x_C + 2x_F >= 30000 訂單三的需求
x_i >= 0 and integer
求解之後為 x_D = 1250, x_E = 10000, x_F = 15000
因為是NP-hard的關係，直覺上可能會想要使用沒有廢料的裁切方式D去滿足需求
但最佳解並不是這樣，另外這個問題是小規模m=3 k=6 所以可以推論出來
但是想像100種裁切方式30份訂單就不可能用這樣推論的
第二題general form 我都幫你定義好index了 要寫出來並不難
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 104.187.117.98 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1666832775.A.668.html
※ 編輯: illousion (104.187.117.98 美國), 10/27/2022 09:11:49
推
10/27 09:49,
1年前
, 1F
10/27 09:49, 1F
推
10/27 13:53,
1年前
, 2F
10/27 13:53, 2F
討論串 (同標題文章)
