小弟供職于某電商公司，公司有自己的加工中心，加工中心的重要職責之一就是根據(jù)收到的訂單，為客戶分揀打包好每個訂單中包含的產(chǎn)品。常規(guī)分揀流程：每天結(jié)單后，系統(tǒng)會統(tǒng)計好當天所有訂單中包含的所有產(chǎn)品，并分別放入分揀貨架，一個貨架放置一種產(chǎn)品。例--------------------------------------------------------------當天供有4個訂單：訂單1（包含產(chǎn)品,Ax1、Bx3、Cx2、Dx4）訂單2（包含產(chǎn)品,Bx2、Cx3、Dx2、Ex2）訂單3（包含產(chǎn)品,Cx2、Dx4、Ex2、Fx2）訂單4（包含產(chǎn)品,Ax1、Bx3、Cx2、Dx2）那么，系統(tǒng)會統(tǒng)計出：當天所有訂單共包含產(chǎn)品：Ax1、Bx8、Cx9、Dx12、Ex4、Fx2，轉(zhuǎn)運工會將這些產(chǎn)品按指定數(shù)量分別放置到6個貨架上分揀工每拿到一個訂單，分揀貨架上相應(yīng)產(chǎn)品的貨架格子燈會亮起，分揀工根據(jù)亮燈情況將產(chǎn)品放入該訂單盒子，完成一次分揀---------------------------------------------------------------------------------目前的問題來了，之前公司有100個分揀貨架。當天訂單產(chǎn)品種數(shù)之和小于100時，這套系統(tǒng)工作正常沒有問題，但是隨著公司業(yè)務(wù)量的不斷增大，每天的訂單產(chǎn)品種數(shù)總和一但大于100時，系統(tǒng)肯定無法工作了。最簡單的辦法就是增加物理貨架的個數(shù)，但由于場地等其他原因，投入非常巨大，并且物流貨架也不可能無限制的增加，所以我們想通過軟件算法去解決這個問題，我相信業(yè)內(nèi)一定有同樣的處理辦法，思路如下：例：系統(tǒng)將每天的訂單分為多個批次，保證每個批次的訂單所包含產(chǎn)品種類小于或等于100，且這批訂單中包含的種數(shù)小于或等于100種，這樣以后無論產(chǎn)品種數(shù)怎么提升無非就是訂單分解成幾批次的問題了。但是目前困擾的就是這個最優(yōu)算法改怎么寫？例：今天所有訂單產(chǎn)品類目總和是170種，共100個訂單，每個訂單中包含的產(chǎn)品及數(shù)量是已知的，只有100個分揀貨架。求解：將這些訂單拆分成幾個批次（批次數(shù)越小越好，減少轉(zhuǎn)運次數(shù)），每個批次的訂單包含的產(chǎn)品種數(shù)小于或等于100，那么應(yīng)該怎么分？每個批次應(yīng)該具體是哪些訂單？求一個最優(yōu)解該算法已經(jīng)超出小弟知識范圍，請數(shù)學大牛支招----萬分感謝！

　　我還沒能解決題主的問題。說一下我到目前為止的思路吧，權(quán)當拋磚引玉。我甚至都不保證我思考的方向是正確的。

　　首先，既然貨架的容量可以當作無限大（見原題評論），那么，每個訂單中每種產(chǎn)品的數(shù)量就不重要了，重要的只是有無。于是可以用一個0/1向量表示一個訂單，向量的長度是所有產(chǎn)品的種類數(shù)，向量中的1表示訂單中有這種產(chǎn)品，0表示沒有。所有訂單的向量可以排成矩陣，例如：

　　第一行表示1號訂單中有2、3、5號產(chǎn)品，以此類推。

　　現(xiàn)在假設(shè)只有3個貨架（100太大了，畫不來……），那么上邊這批訂單可以這樣處理：

　　1) 先用3個貨架分別裝1、2、5號產(chǎn)品，搞定2、3號訂單；

　　2) 再用3個貨架分別裝2、3、5號產(chǎn)品，搞定1號訂單；

　　3) 最后用3個貨架分別裝3、4、5號產(chǎn)品，搞定4號訂單。

　　這樣總共需要3個批次。

　　把上面的矩陣的行列交換一下次序，讓新矩陣的每行分別對應(yīng)原矩陣的第2、3、1、4行，每列分別對應(yīng)原矩陣的第1、2、5、3、4列（即按照處理訂單和產(chǎn)品的順序排列），可以看得更清晰：

　　矩陣沿對角線形成三個塊（前兩行是一個塊，排版比較困難……），各塊之間沒有重疊的行，每個塊的寬度都是3（貨架數(shù)目），且從左向右排列。每個塊代表一個批次。

　　我對原問題的建模就是：尋找一種交換訂單矩陣各行各列的方法，使得交換后的矩陣能夠劃分成盡可能少的塊。

　　然后我發(fā)現(xiàn)我不會解這個問題……

　　==========================

　　然后題主又提出說，可以把包含產(chǎn)品種類比較多的訂單拆開。

　　這樣的話，就又有一種思路：不是按行分批，而是按列分批，像這樣：

　　豎線左右分別是兩批，但是這樣有兩個訂單被拆了。

　　與之前的思路相比，這種思路要求解的問題有兩點不同：

　　1) 只需要考慮交換各列，不需要考慮交換各行（雖然把矩陣排成對角的樣子思考更方便）；

　　2) 目標函數(shù)要綜合考慮批數(shù)和被拆開的訂單數(shù)了。

　　很不幸，這個問題我也不知道怎么解……

　　謝邀。

　　也感謝 @王赟 Maigo

　　寫的答案，已經(jīng)建立了一個很好的模型?？戳藛栴}評論，題主表示「拆單的問題可以忽略不計」，所以接下來就只討論第一種模型。

　　這里我在王赟同學的模型基礎(chǔ)上，再把問題重新描述一下：

　　設(shè)，用來表示所有的訂單，每一行表示一個訂單，一個訂單里需要的物品，就在相應(yīng)的列上置1，否則就是0，比如（還是拿王赟同學的例子）

　　第一行表示1號訂單中有2、3、5號產(chǎn)品，以此類推。按照題主的假設(shè)，沒有拆單，也就是說D矩陣每一行的元素加起來，不會超過貨架個數(shù)（我們設(shè)為 k 吧）

　　現(xiàn)在我做一點操作，怎么操作呢，就是在某些元素的位置上加1。比如我在第2行最后一個元素位置上加1，于是第2行和第3行就變成一樣了：

　　這樣我們就可以看出來，第1行可以單獨成為一批，第2行和第3行可以合并為一批，第4行還是單獨一批。并且很容易看出，在某些位置加1的這個操作，對訂單分批來說，是沒有影響的。

　　那么A矩陣為什么就可以分為這樣3批呢？因為A矩陣的秩（rank）是3，也就是說，A矩陣的秩是多少，就可以分為多少批。

　　所以我們的目標就明確了：需要做一些操作，在原始矩陣的某些位置上加1，使得結(jié)果的矩陣的秩（rank）要越小越好，當然，A矩陣每一行的元素加起來不能超過貨架個數(shù)（也就是 k）

　　用數(shù)學式子表達出來，就是（對矩陣E的約束做了松弛）：

　　其中，

　　這就轉(zhuǎn)化為一個優(yōu)化問題了，不過很遺憾，這個優(yōu)化問題是不好求解的（我沒仔細證明過是不是NP，在E矩陣滿足原始約束的情況下應(yīng)該是對的，松弛之后我不能確定，但至少是非凸的，這就不好求解了）

　　雖然嚴格求解不好解，但是我們可以求一個近似解。我們可以用核范數(shù)（nuclear norm）來近似秩（rank），也就是把優(yōu)化的目標函數(shù)變成：

　　這就變成一個凸優(yōu)化問題了，就可以有很多有效的方法快速地進行求解！

　　比如用 Boyd 教授開發(fā)的 CVX 工具包（CVX: Matlab Software for Disciplined Convex Programming

　?。?，幾行代碼就搞定了

　　這里 matA 就是最后的結(jié)果，把 matA 里重復(fù)的行去掉，每一行就是一個批次了！每一行里面的1就是要取的物品。

　　這雖然是松弛了目標函數(shù)之后得到的近似解，但是在實際應(yīng)用中應(yīng)該也足夠用了。

　　為什么要一個品種一個貨架呢？ 把一定量的訂單匯總后，把訂單內(nèi)的所有品種揀在同一貨架或容器里，在分揀到對應(yīng)的訂單中去

　　醫(yī)用試劑瓶如何分揀？人工分揀？耗時耗力！馬克拉伯機器視覺免費軟件SGVision輕松解決，采用的算法為形狀匹配與像素統(tǒng)計的調(diào)用。

　　下方鏈接進入馬克拉伯學院馬克拉伯,一個機器視覺應(yīng)用開放社區(qū)

　　醫(yī)用試劑瓶分揀（原圖）

　　一、 檢測與實現(xiàn)功能

　　本案例通過調(diào)用相應(yīng)算法實現(xiàn)不同試劑瓶的分揀。

　　二、 檢測系統(tǒng)需求分析

　　1.為了獲得最優(yōu)的打光效果，這里選用背光源從下往上打光；

　　2.為了達到檢測要求，這里選用500W黑白網(wǎng)口相機，工業(yè)高像素級25mm定焦鏡頭；

　　注意：這里背光源打光，所以不需要調(diào)整光源角度。我們所須要注意的是相機焦距和物距的調(diào)整以及相機參數(shù)的設(shè)置，將樣品盡量調(diào)整到清晰。

　　三、檢測具體步驟

　　1.調(diào)用形狀匹配算法，選擇樣品1進行形狀匹配，選中你想測試的區(qū)域并設(shè)置模板待用。如下圖： 圖一

　　注意：這里調(diào)用形狀匹配主要是為了給樣品做一個位置配準，右邊參數(shù)要調(diào)整好，這樣才能準確找到樣品位置并做糾正。

　　2.調(diào)用像素統(tǒng)計算法，框選樣品1，并設(shè)置相應(yīng)合格范圍。圖二

　　注意：匹配源一定要選擇我們設(shè)置的形狀匹配，合格標準一定要設(shè)置在樣品檢測結(jié)果范圍內(nèi)。不然會顯示NG

　　3.點擊測試，區(qū)分出樣品1和樣品2： 圖三 OK圖，即樣品1圖四 ok圖 樣品1圖五 OK圖樣品1圖六NG圖樣品2圖七 NG圖 樣品2

　　所有算法設(shè)置完，點擊右下方的測試按鈕，檢測所有算法設(shè)置是否無錯誤，若無，點擊確定退回主界面，點擊主界面“檢測”按鈕即可開始檢測產(chǎn)品。