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

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

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

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

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

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

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

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

　　這樣總共需要3個(gè)批次。

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

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

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

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

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

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

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

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

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

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

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

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

　　謝邀。

　　也感謝 @王赟 Maigo

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

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

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

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

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

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

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

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

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

　　其中，

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

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

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

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

　?。瑤仔写a就搞定了

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

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

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

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

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

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

　　一、 檢測(cè)與實(shí)現(xiàn)功能

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

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

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

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

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

　　三、檢測(cè)具體步驟

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

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

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

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

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

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