文/數(shù)據(jù)俠 Singh

　　當(dāng)你在逛超市的時(shí)候，你有沒有想過(guò)商場(chǎng)里的商品的擺放方式有什么講究？隨著新零售時(shí)代的到來(lái)，超市如今已經(jīng)開始逐漸轉(zhuǎn)向精細(xì)化運(yùn)營(yíng)時(shí)代。面對(duì)成千上萬(wàn)商品，通過(guò)數(shù)據(jù)收集和分析技術(shù)不斷提升銷售效率是零售超市們?nèi)缃褡铌P(guān)心的事情。其中，如何讓貨架空間最大化是其中的關(guān)鍵因素之一。數(shù)據(jù)俠Deepesh Singh使用python和貪婪算法告訴你：貨架空間優(yōu)化的奧義就藏在那些簡(jiǎn)單的數(shù)據(jù)里。

　　定義我們的問(wèn)題

　　在商店里，一個(gè)產(chǎn)品的位置很大程度上影響了它的銷售情況。為不同的產(chǎn)品，不同類別分配適當(dāng)?shù)目臻g和布局，在零售業(yè)中起著至關(guān)重要的作用。

　　從零售商的角度來(lái)看，鑒于貨架位置的價(jià)值，確保零售空間的充分利用，對(duì)于商店價(jià)值最大化的工作至關(guān)重要。

　?。▓D片說(shuō)明：超市中常見的貨架擺放方式）

　　一般來(lái)說(shuō)，POS機(jī)附近的貨架會(huì)為客戶提供最大的曝光度。顧客在排隊(duì)結(jié)賬時(shí)客觀上必須瀏覽這些列表商品。盡管這些商品的價(jià)格只有幾塊錢，如果在正確的時(shí)間，正確的地點(diǎn)，以正確的數(shù)量銷售正確的商品，就可以幫助商店賣出更多的商品，這是零售業(yè)收入和盈利能力的關(guān)鍵。

　　這一方面導(dǎo)致了品牌間的戰(zhàn)爭(zhēng)——?jiǎng)僬卟拍苷紦?jù)商店中最好的展示位；另一方面，商店也需要考慮到所有不同商品的銷售情況，通過(guò)整體規(guī)劃優(yōu)化其盈利能力。

　　雖然這個(gè)邏輯很好理解，但應(yīng)用起來(lái)可并不簡(jiǎn)單。空間優(yōu)化所需的信息在整個(gè)業(yè)務(wù)中的大部分時(shí)間都是模糊、復(fù)雜、分散的。

　　某些產(chǎn)品在整個(gè)營(yíng)銷中可能扮演的是至關(guān)重要的角色; 其他產(chǎn)品可能只是附屬品，用來(lái)提供更高的邊際效用。因此，僅僅使用一個(gè)變量來(lái)衡量他們就變得非常困難。

　　更何況，平均一個(gè)零售商店里就有將近3萬(wàn)個(gè)SKU（stock keeping unit庫(kù)存單位）。每年在零售店還會(huì)推出數(shù)千種的新產(chǎn)品。面對(duì)如此大數(shù)據(jù)量的問(wèn)題，優(yōu)化就變得非常困難。

　　但是我們的目標(biāo)很明確：就是通過(guò)整合擺放策略，最大化超市的銷售總額。

　　用線性規(guī)劃來(lái)優(yōu)化的策略

　　在分析正式開始前，我們?cè)賮?lái)說(shuō)一點(diǎn)基礎(chǔ)知識(shí)。首先，什么是優(yōu)化呢？說(shuō)起來(lái)很簡(jiǎn)單，優(yōu)化就是在特定約束條件（constrains）下找到最佳解決方案的科學(xué)過(guò)程。

　　我們每天其實(shí)都會(huì)遇到各種優(yōu)化的問(wèn)題。優(yōu)化可以是找到工作場(chǎng)所和辦公室之間的最短路徑; 可以是最大限度地提高收入/客戶的幸福感，或者最小化成本/債務(wù)，不一而足。

　　一句話，優(yōu)化就是把一個(gè)真實(shí)世界的問(wèn)題，用數(shù)學(xué)的方法進(jìn)行建模，然后用數(shù)學(xué)方法在約束條件下求解。優(yōu)化在市場(chǎng)營(yíng)銷，制造業(yè)，金融，在線廣告，機(jī)器學(xué)習(xí)以及任何你可以想象的所有領(lǐng)域都很有用。

　　線性規(guī)劃（Linear Programming，也稱為線性優(yōu)化）是指在需求由線性關(guān)系表示的數(shù)學(xué)模型中實(shí)現(xiàn)最佳結(jié)果（如最大利潤(rùn)或最低成本）的方法。線性程序可以表示為：決策變量目標(biāo)函數(shù)：必須是線性的限制：必須是線性等式或不等式。

　　線性規(guī)劃算法在可行空間中找到一個(gè)點(diǎn)，其中如果存在這樣一個(gè)點(diǎn)，則目標(biāo)函數(shù)具有最?。ɑ蜃畲螅┑闹?。單純形法（simplex algorithm）是最常用的線性規(guī)劃算法。

　　整數(shù)規(guī)劃是線性規(guī)劃的一個(gè)特殊情況，其中決策變量被限制為整數(shù)。對(duì)于整數(shù)規(guī)劃的問(wèn)題，我們一般只有二元輸出結(jié)果，即非0即1。

　　下面我們就以一個(gè)簡(jiǎn)單的例子來(lái)說(shuō)明優(yōu)化是具體如何操作的。這雖然是一個(gè)很小的問(wèn)題，但是相同的概念可以被擴(kuò)展到更大的問(wèn)題上。讓我們現(xiàn)在小數(shù)據(jù)的情況下來(lái)了解問(wèn)題。

　　假設(shè)一個(gè)有3個(gè)貨架的零售店：貨架1，貨架2和貨架3。每個(gè)貨架分別有3個(gè)、3個(gè)和4個(gè)架子（如下表所示）。我們必須出售3家公司的產(chǎn)品：Unilever（聯(lián)合利華，英荷聯(lián)合公司），Godrej（戈德瑞，印度公司）和Dabur（印度草藥公司）。Unilever, Godrej和Dabur三家公司分別有3種、3種、2種不同的產(chǎn)品。

　　我們?cè)诰仃囍锌吹降臄?shù)字是將特定產(chǎn)品放置在特定一排（rack）中的特定一個(gè)貨架（shelf）上實(shí)現(xiàn)的銷售增量（lift）。

　　現(xiàn)在，由于產(chǎn)品的利潤(rùn)率/庫(kù)存成本/需求/過(guò)期時(shí)間等差異，商店希望優(yōu)化每個(gè)產(chǎn)品在貨架上的位置，并最大化銷售總額（產(chǎn)品數(shù)量），同時(shí)考慮到一些已有的限制條件。

　　決策變量將采用與lift矩陣（10* 8）相同大小的矩陣的形式。矩陣內(nèi)的元素是一個(gè)二元變量：1表示產(chǎn)品/貨架的匹配是對(duì)的（Yes）；0表示產(chǎn)品/貨架的匹配是錯(cuò)的（No）。我們將從所有元素都是0的矩陣開始，并允許求解器在需要時(shí)更改為1。

　　要注意的是：我們目標(biāo)函數(shù)的目標(biāo)就是最大化所有商品的總銷售額。

　　這里用的限制是：一個(gè)貨架（shelf）上最多只能有某個(gè)公司的一個(gè)產(chǎn)品（行約束）產(chǎn)品不能擺放超過(guò)一定數(shù)量的貨架。這是按照上圖所示的產(chǎn)品順序給出的列約束。產(chǎn)品的最大出現(xiàn)情況如下，這些限制可以歸因于產(chǎn)品類型/利潤(rùn)率/需求或任何其他適用于商店的理由。

　　上圖的意思是是聯(lián)合利華的產(chǎn)品1不能銷售一次以上；Godrej的產(chǎn)品1不能上架超過(guò)兩次。其他情況依次類推。（根據(jù)不同商店對(duì)不同商品的策略和理解不同，實(shí)際情況中可能會(huì)有多種多樣的限制。但我們這里只是希望展示如何實(shí)際解決線性優(yōu)化的問(wèn)題，所以就只給出一個(gè)簡(jiǎn)單的限制條件。）

　　當(dāng)我們確定了目標(biāo)函數(shù)、限制約束條件后，這種簡(jiǎn)單的線性優(yōu)化就可以使用EXCEL中的solver功能進(jìn)行操作。我們最終目標(biāo)函數(shù)算出來(lái)最大的銷售量是4197。最大情況下給出的決策矩陣如下圖。

　　但是Excel有個(gè)致命的缺陷，就是它無(wú)法處理大樣本的數(shù)據(jù)。另外，如果有很多限制條件的話，Excel跑起來(lái)也會(huì)非常地吃力。但還好我們有Python來(lái)救場(chǎng)。

　　數(shù)據(jù)太“大”怎么辦？Python說(shuō)這個(gè)它能干

　　用EXCEL來(lái)進(jìn)行優(yōu)化太繁瑣了，不利于用于日常操作。Python可以很容易地解決數(shù)據(jù)大小的問(wèn)題，只會(huì)受到計(jì)算速度的限制。此外，一旦編碼/自動(dòng)化，這個(gè)程序就可以應(yīng)用于任何數(shù)據(jù)量的問(wèn)題；任何新的約束條件也可以隨時(shí)加入進(jìn)來(lái)。

　　在這里，我使用了python中的Pulp庫(kù)。求解器（solver）我用的是開源的CBC。當(dāng)然還有其他一些商用的solver，如CPLEX，GUROBI等，這些solver可用于data size的問(wèn)題，因?yàn)樗鼈兊乃俣雀?，結(jié)果更好。

　　當(dāng)我們重復(fù)一遍上述過(guò)程后，你會(huì)發(fā)現(xiàn)Python得到的結(jié)果和Excel得到的結(jié)果完全一致。再次印證了結(jié)論，4197是總銷售增量的最大值。

　　現(xiàn)在我們來(lái)討論下大數(shù)據(jù)會(huì)帶來(lái)什么樣的問(wèn)題。在這個(gè)例子中，我們知道每個(gè)決策變量可以取值為0或1，即2 ^ 1也就是2個(gè)可能的值。

　　如果現(xiàn)在是2個(gè)決策變量，可能組合的總數(shù)可以是2 ^ 2也就是4，其中一個(gè)/多個(gè)都可以給出目標(biāo)函數(shù)的優(yōu)化值。當(dāng)情況需要考慮的有80個(gè)決策變量時(shí)，總的組合是2 ^ 80。決策變量增多帶來(lái)的問(wèn)題是指數(shù)性增加的而不是線性的。

　?。ㄓ糜?jì)算復(fù)雜性理論（Computational complexity theory）的理論來(lái)說(shuō)，就是指數(shù)時(shí)間算法O（2 ^ n）]。即使是最好的電腦，指數(shù)時(shí)間算法的問(wèn)題也是非常大強(qiáng)度的。正如在我們的例子中，所有2 ^ 80組合都需要被評(píng)估以找到優(yōu)化的解決方案。）

　　這里開始就需要商業(yè)理解和專業(yè)知識(shí)的幫助了。一名行業(yè)專家可以很快地排除掉不合適的組合，通過(guò)使用合適的約束條件，減少需要排查的可能組合的總數(shù)，從而大大降低了計(jì)算量。

　　生活中無(wú)處不在的“優(yōu)化”商機(jī)

　　上面我們展示優(yōu)化問(wèn)題的基本實(shí)現(xiàn)過(guò)程，接下來(lái)讓我們來(lái)了解優(yōu)化問(wèn)題在其他領(lǐng)域的一些應(yīng)用。

　　谷歌的AdWords：Google使用線性規(guī)劃來(lái)優(yōu)化在線廣告。Google在其搜索頁(yè)面上有不同的廣告窗口，并基于PPC（每次點(diǎn)擊的價(jià)格），CTR（點(diǎn)擊率）和廣告客戶的預(yù)算——這些約束條件，來(lái)分配廣告窗口和播放次數(shù)（這個(gè)是決策變量）以最大化其收入（目標(biāo)函數(shù)）。AdWords帳戶約占Google收入的97％。

　　（圖片說(shuō)明：Google Adword廣告系統(tǒng)的收費(fèi)標(biāo)準(zhǔn)靈活，會(huì)根據(jù)點(diǎn)擊和來(lái)電通話次數(shù)等效果來(lái)收取費(fèi)用，約束條件較多，是線性優(yōu)化的經(jīng)典案例；圖片來(lái)源：Google Adword官網(wǎng)截圖）

　　航空公司的收益管理（Revenue Management）：航空公司使用線性優(yōu)化來(lái)決定提供多少打折機(jī)票（決策變量），在考慮到預(yù)測(cè)的需求（約束條件）和飛機(jī)型號(hào)（有限的座位，也是約束條件）情況下，最大化其收入（目標(biāo)函數(shù)）。

　　癌癥治療：線性規(guī)劃用于通過(guò)輻射來(lái)治療癌癥患者。在有限的輻射水平下（約束條件）向腫瘤細(xì)胞進(jìn)行靶定位輻射，并且同時(shí)健康組織應(yīng)暴露于最少量的輻射下（使目標(biāo)函數(shù)最小化）。

　　電視頻道的推廣廣告：一個(gè)電視頻道有數(shù)十個(gè)節(jié)目，但卻有數(shù)以千計(jì)的促銷，且廣告需要在這幾十個(gè)節(jié)目中穿插。通過(guò)線性優(yōu)化，他們決定在哪個(gè)廣告位進(jìn)行電視廣播，并保持高收視率（目標(biāo)函數(shù)）。這里的約束條件可以是每次廣告的預(yù)算，一個(gè)廣告最大的出現(xiàn)次數(shù)等等。

　　約會(huì)網(wǎng)站：線性優(yōu)化也被用于線上約會(huì)網(wǎng)站，比如eHarmony?；诿總€(gè)用戶填寫的問(wèn)卷，eHarmony計(jì)算兩個(gè)人之間的匹配值，并使用線性規(guī)劃等優(yōu)化算法來(lái)確定用戶的最佳匹配對(duì)象。這里可能的限制是男性只與女性相匹配; 男性用戶需要匹配的是女性，反之亦然。

　　這次給大家演示的只是一個(gè)非常簡(jiǎn)單的例子，如果是真實(shí)的貨架優(yōu)化問(wèn)題，那涉及到的可是成百上千個(gè)貨架。而相應(yīng)的約束條件也會(huì)增加到成百上千個(gè)。所有這一切的目的就是讓一個(gè)商品出現(xiàn)在正確的地方，從而使得銷售量最大化。

　　注：本文編譯自Deepesh Singh 的博客文章《 A Beginner’s guide to Shelf Space Optimization using Linear Programming》，文中圖片除特殊標(biāo)注外，均來(lái)自原文。本文僅為作者觀點(diǎn)，不代表DT財(cái)經(jīng)立場(chǎng)

　　在優(yōu)化貨架問(wèn)題中，作者還嘗試了“貪婪算法”來(lái)代入優(yōu)化模型。不過(guò)貪婪算法本身的算法邏輯并不適合本文的整體優(yōu)化問(wèn)題，DT君編譯時(shí)省略了這部分嘗試的內(nèi)容。

　　DT君送福利：在原文中，作者詳細(xì)地列出了EXCEL和Python的操作代碼及步驟，為了保證閱讀流暢度，我們沒有將其羅列在文中。感興趣的讀者可以后臺(tái)回復(fù)“擺放藝術(shù)”，獲取作者原文鏈接。

　　編譯 | 數(shù)問(wèn)團(tuán)隊(duì)

　　題圖 | 視覺中國(guó)

　　期待更多數(shù)據(jù)俠干貨分享、話題討論、福利發(fā)放？在公眾號(hào)DT數(shù)據(jù)俠（ID：DTdatahero）后臺(tái)回復(fù)“數(shù)據(jù)社群”，可申請(qǐng)加入DT數(shù)據(jù)社群。

　　數(shù)據(jù)俠門派

　　本文數(shù)據(jù)俠 Deepesh Singh 是一位數(shù)據(jù)科學(xué)愛好者。他是一名持續(xù)的學(xué)習(xí)者，熱愛探索數(shù)據(jù)科學(xué)的不同領(lǐng)域。他是NIT Silchar的一名工程師，擁有IIM-L和KSB（印第安納大學(xué)）商業(yè)分析一年的證書，目前正在解決分析機(jī)構(gòu)班加羅爾辦事處的業(yè)務(wù)問(wèn)題。在工作之外，他喜歡會(huì)議主持人，在健身房鍛煉，練習(xí)、教導(dǎo)空手道。

　　DT字幕組

　　感謝“數(shù)問(wèn)”團(tuán)隊(duì)對(duì)本文的翻譯貢獻(xiàn)。

　　數(shù)問(wèn)數(shù)據(jù)科學(xué)平臺(tái)是一個(gè)一站式數(shù)據(jù)玩家的驛站，目前有問(wèn)答、競(jìng)賽、工作、線下活動(dòng)等內(nèi)容版塊。任何數(shù)據(jù)愛好者都可以在平臺(tái)上提問(wèn)題、找答案、分享學(xué)習(xí)資料和經(jīng)驗(yàn)、對(duì)接資源等。他們希望幫助各個(gè)階層的數(shù)據(jù)使用者解決“從哪里來(lái)”，“到哪里去”的問(wèn)題。

　　“DT字幕組”致力于發(fā)掘和傳播全球數(shù)據(jù)領(lǐng)域的優(yōu)質(zhì)內(nèi)容，長(zhǎng)期招募組員，歡迎郵件聯(lián)系：。

　　加入數(shù)據(jù)俠

　　“數(shù)據(jù)俠計(jì)劃”是由第一財(cái)經(jīng)旗下DT財(cái)經(jīng)發(fā)起的數(shù)據(jù)社群，包含數(shù)據(jù)俠專欄、數(shù)據(jù)俠實(shí)驗(yàn)室系列活動(dòng)和數(shù)據(jù)俠聯(lián)盟，旨在聚集大數(shù)據(jù)領(lǐng)域精英，共同挖掘數(shù)據(jù)價(jià)值。了解數(shù)據(jù)俠計(jì)劃詳情請(qǐng)回復(fù)“數(shù)據(jù)俠計(jì)劃”，投稿、合作請(qǐng)聯(lián)系。