Excel與Google Sheets中實現線性規劃求解

• 2019 年 10 月 4 日
• 筆記

很久沒更新過APS系列文章了，這段時間項目工作確實非常緊，所以只能抽點時間學習一下運籌學的入門知識，算是為以後的APS項目積累點基礎。看了一些運籌學的書（都是科普級別的）發現原來我目前面對的很多排產、排班、資源分配和路線規劃問題，都是運籌學上的典型案例。與此同時，除了繼續使用Optaplanner來做我們的規劃類項目外，還花點時間去研究了一下Google OR-Tools開源規劃引擎，這是Google旗下的一個開源求解器，接下來我會專門寫一些關於Google OR-Tools應用的文章，並與Optaplanner作些關聯對比。

本篇先向大家展示一下兩個規劃工具，在求解線性規劃問題上的應用方法，分別是Microsoft Office的Excel里的」規劃求解」組件和Google Dos中的Spreadsheet上提供的Linear Optimization插件。這兩個工具都可以作為規劃問題的求解器。因為它們是以插件或軟體功能形式提供的，在靈活性和擴展性方面限制還是比較大，但是因為不涉及軟體開發的技能，普通用戶都能很好地應用它們來解決一些現實業務中遇到的規則問題。

因為Google的Linear Optimization是Google文件服務中的Spreadsheet（Google提供的類似於Excel的電子表格程式），因為目前中國的網路情況（你懂的），訪問它需要自己想辦法，我們公司總部不在中國境內，所以我們的辦公網路經過註冊，是可以合法訪問外界的；關於網路方面不在本篇中討論，大家自己科學解決就可以了。

規劃問題

下面先給出本次我們需要求解的線性規劃問題，其實在Optaplanner相關的文章中，詳細介紹過關於NPC問題，普通線性規劃問題很多並不是NPC問題，因為對於線性規劃模型，還是有例如單純形法等演算法推算它的最優解的，而不是所有規劃問題的時間複雜度都是O(a^n)或O(n!)的，大家要理解清楚兩者的關係。

我們要求解的問題跟很多運籌學教材或科普書籍上的例子一樣，也是最簡單的在確定的條件約束下，求最大利潤下的產品生產方案問題。例如一家工廠生產兩種產品，產品A與產品B，均需使用到三種資源，資源1、資源2和資源3。其中生產一件產品A，需要5個單位的資源1，4個單位的資源2，3個單位的資源3。生產一件產品B需要3個單位的資源1，8個單位的資源2，5個單位的資源3。一個產品A的利潤是20，一個產品B的利潤是25。庫存中三種資源的存量為：280單位的資源1，580單位的資源2，360單位的資源3.見下表：

求：兩種產品分別生產多少件，才能令到總利潤最大？此時的利潤是多少？

以上問題是典型的線性規劃問題，運籌學的同學可以通過單純形法進行求解，但是這種方法對於沒有運籌學背景的普通工程師來說，困難還是不小。即使我們學會這種辦法，但遇到更複雜問題的時候，對我們來說其挑戰還是相當大。因此，目前市面上，或開源世界裡，提供了很多解決此類規劃問題的開源軟體。但對於非IT人員來說，沒有軟體開發背景，很難利用這些開源軟體工具寫程式求解。因此，一些知名的辦公軟提供了相關的特性，讓非IT專業人員直接使用其規劃功能，輸入數據即可快速求得答案。對各行業的生產、管理活動提供了極大的幫助。下面我們就以Excel和Google Spreadsheet兩種工具中的規劃求解功能，嘗試求解上述問題。

對問題進行數學建模

要解決上述問題，就需要對問題進行線性規劃建模，建立數學模型，以數學工具對問題的約束和目標進行歸納、抽象，用數學語言表達問題的本質意義。對於上面的問題我們的建模如下：假設產品A生產x件，產品B生產y件，才能讓利潤最大化。那麼我們通過對問題的約條件和規劃目標的分析，可以得出以下數學模型。

該模型表示：生產產品A和產品B所需的三種資源的總量，均不能超過每種資源的庫存量；並且產品件數量必須是大於等於0的整數。規劃的目標函數是找出兩種產品的利潤之和的最大值，並計算出獲得該利潤時，兩種產品的產量分別是多少。

對於線性規劃問題，其實可以通過單純形法、對模型進行求解，從而得出z最大時的x與y的值。但此方法需要一定的數學知識，此範圍的知識不在本文的討論範圍內，以後若有機會，我再簡單介紹一下通過單純形法對此模型求解步驟。但本人也不是運籌專業出身，估計也只是班門弄斧；因此，大家可以上網尋找更專業的運籌學資源，了解規劃模型的解法。本文通過Excel下的規劃求解功能，以及Google下的Spreadsheet中的Linear Optimization插件，對該規劃模型進行求解，從而取得該生產安排問題的解。

Microsoft Excel規劃求解

Excel提供了一個非常強大的組件用於解決此類規劃問題，目前我還只嘗試過線性規劃問題，根據其資料顯示，非線性規劃也是可以解的。以後若有機會嘗試一下其它規劃問題再分享給大家。下面逐一展示這組件具體用法給大家。

第一步：添加「規則求解」組件

因為規則求解功能默認不會出現在Excel的常用工具欄中，因此，需要從載入項目中把它載入出來才能使用。在Excel菜單欄中，選擇【文件】->【選項】，在彈出的【Excel選項】窗口中，選擇【載入項】頁簽，在列表中的【非活動應用程式載入項】（意思是說Excel目前有這些功能可以用，但還沒有載入進去，所以不會顯示在工具欄中）的其下方找到【規則求解載入項】，如下圖.

在列表下方的【管理(A)】下拉框中選擇【Excel載入項】，點擊【「轉到…】按鈕，會彈載入項窗口，如下圖。在【可用載入宏(A)】列表中，選中【規劃求解載入項】，點擊確定，窗口關閉。

在Excel的【數據】工具欄的最右側，你會看到【規劃求解】的圖標，即是剛才我們操作完成後載入進來的組件，如下圖。

事實上它是Microsoft提供的一個求解器，該組件對應的文件在C:Program Files (x86)Microsoft OfficerootOffice16LibrarySOLVER此文件夾下。該文件夾下有兩個文件，分別是SOLVER.XLAM和SOLVER32.DLL, SOLVER.XLAM是一個Excel的宏文件，用於實現Excel對求解器核心SOLVER32.DLL的調用，因此SOLVER32.DLL應該就是這個求解器的核心程式動態連接庫。

第二步：將問題填入Excel表並建立各變數之間的關係

完成規劃求解組件載入後，下面就可以將數學模型的各個常量、變數和約束關係填入Excel單元格中；先將兩種產品和三種資源對應的使用數量建立一張二維表，如下表。

通過Excel及規劃求解組件解答此問題步驟如下：

1.填入常量：上表中，產品A對資源1、資源2和資源3的要求量分別是5，4，3(即B2,B3,B4的值)，其單件利潤為20(B5)。 同樣方法將產品B對應的數量填入C２- C5單元格中。另外，對於三種資源的庫存量，將其值填 入D2 – D4中。自此，模型中涉及的常量已經全部填寫進表格。

2.根據數學模型，定義運算關係：本模型中，我們的目標是求得當z最大時變數x,y的值(x,y在運籌學的規劃模型中被稱為 決策變數；在Optaplanner中，它們被稱作規劃變數)。在Excel中每一個決策變數需要確定在一個單元格，以備參與接下來的規劃計算，如上表的B6,C6單元格。在未啟動規劃的時候，這兩個單元格直接填上0作為初始值即可。這兩個代表決策變數的單元格在完成規劃，找到答案後，運算結果值將會被填到對應的單元格中。

確定好這兩個變數後，下一步需要考慮規劃目標，也就是總利潤最大化的目標，也需要為此目標值確定一個單元格，此單元格的值會在規劃完成時，確定了B6和C6兩件單元格的值之後計算出來。根據目標函數z = 20x X 25y的定義，此單元格的公式應為 ：B5 * B6 + C5 * C6，即兩種產品的利潤之和。我們把存儲利潤之和的值定在D7單元格，為了直觀美觀，我們把D7與E7合併。

確定了目標函數值的單元格和計算公式後，下一步需要處理約束條件，也就是產品的資源使用量與庫存的約束關係。對於資源1，我們將E2確定為其資源用量，它計算公式應該是:B2 * B6 + C2 * C6,即兩種產品對該資源的使用量之和。按相同的規則，設置E3 = B3 * B6+ C3* C6, E4 = B4 * B6 + C4 * C6.

第三步：設定規劃求解邏輯參數

通過上述兩個步驟設定後，各個單元格的常量值、決策變數和運算關係已設定好。接下來就可以啟動【規劃求解】插件進行邏輯設定。在【數據】菜單項目中，最右側的【分析】組裡，有一個【規劃求解】圖標，點擊它，即可打開【規劃求解】窗口(如下圖)

以下講解這些參數意義及其設置。

1.【設置目標(T)】項:該項目我們需要選定一個單元格，表示該單元格是本次規劃活動需要計算的目標。通過問題描述和規劃模型，我們得知該問題目標是求利潤的最大值及取得該利潤時兩種產品的產量。也即模型中的目標函數z的最大值，及此時的x,y的值。在上表中D7就是存放這個目標函數的單元格，因此這裡選中D7即可。在參數設置時，都是使用單元格的絕對地址，因此單元格地址前面都有$符號。

2.目標值中【到】項：該項用於設置對於目標函數的取值要求，可以看到它有【最大值】，【最小值】和【目標值】三個選項。其中【最大值】和【最小值】，表示目標函數往最大或最小兩個極值方向求解，即最優解中，D7單元格的值是在滿足約束條件情況下取得的最大值。而【目標值】則表示取得最優解時，目標函數值最等於或最接近於此值。本問題中的目標是求利潤最大，所以我們選擇【最大值】。

3.【通過更改可變單元格(B)】：該項表示在規划過程中求解器，通過改變哪些單元格的值，來獲得結果，直到【目標值】所指的單元格（本例中的D7)中的值達到極值。對應到模型中，也就是x與y兩個決策變數，本例中對應的單元格是B6和C6，分別表示產品A和產品B的產量。因此，選擇B6和C6即可。

4.【遵守約束】：該項內容表示本次規劃需要符合的約束條件，也就是模型中的s.t.部分(s.t. 是subject to的縮寫)和各個不等式和各變數的範圍條件。點擊右側的【添加(A)】按鈕，彈出【添加約束】窗口(如下圖)，可以看到約束的表達方式非常簡單，就是添加左右兩側值的邏輯關係。

　　參照模型中的s.t.部分，和excel中的單元格位置關係，添加它們的關係即可。例如對於資源1，s.t.中的約束條件5x * 3y <= 280, 可參通過選擇操作，添加以下關係: E2 <= D2，表示產品A所需資源量與產品B所需資源量之和，不能大於資源庫存量。按相同的規則設置好資源2和資源3的約束條件。另外對於決策變數x,y，模型中有這兩個變數應為整數，且大於等於0的約束。因此，分別選擇B6和C6，並在條件表達關係選擇int即可。完成後條件約束的內容如上圖中的【遵守約束】列表中的內容。

　　5.【選擇求解方法】：該欄列舉了目前可選擇的三種求解演算法，分別是【單純線性規劃】，即單純形解法，【非線性GRG】和【演化】。具體的求解方法在選擇框下方有簡單解釋，我們選擇默認的【非線性GRG】或【單純形法】即可。

6.【求解】：點擊【求解】按鈕，即會啟動求解器進行規劃求解。完成後會彈出【規劃求解結果】窗口，供進一步操作（例如保存規劃方案等）。與此同時，原來在未求解前，因為產量設置為0，所以所需資源（E列）的三個單格E2,E3,E4,以及總利潤單元格D7的初始值是0。完成規劃後，找到最大利潤下兩種產品的產量(B6,C6)之後，上述原值為0的單元格的值，也隨即被更新為該利潤最大方案時對應的值。如下圖。

　　由結果可知，完成規劃求解後，得到的決策變數值：x=20, y=60, 目標函數z的值為1900，即表示：當產品A生產20個(B6單元格)，產品B生產60(C6單元格)個時，其利潤達到最大值1900(D7單元格)。上述規劃問題得到完美解。下面我們再使用另外一個工具 – Google Spreadsheet中的線性優化插件，求解同樣的問題。

Google Spreadsheet線性優化功能插件

對於規劃問題，微軟和Google通提供了很強大的套件，令到像我這種沒有運籌學背景的普通用戶，可以方便地求解一些規劃問題。在此不得不感嘆一下，在此方面中國類似軟體與國外的差別。曾經有朋友跟我討論過，公司使用的中國某個一線辦公軟體，功能直逼office，辦公中絕大部分情況，這個軟體都能處理，但遇到一些需要進行規劃運算的問題，此軟體則沒有提供類似的功能，不得不求助於Microsoft Excel。

說到這種非專業人員用的規劃求解工具，不得不延伸提一下規劃引擎軟體方面，也存同類問題。目前在中國，如果是針對某一大型公司或項目，只要資源到位，實現一個可用的規劃引擎問題不算大。但涉及要求更高，可用性更強的通用規劃引擎(無論是開源還是商業)中國外的差距就體現出來了。商業求解器領域暫不深入討論，本人專註於開源規劃引擎的應用 研究，近兩三年項目應用或自己學習研究中，曾分析應用過一些開源規劃引擎，除開優化性能和優化結果的品質上的比較；僅就在工程實踐的可用性、易用性上，目前還很難在中國找到一款能跟Optaplanner及Google OR-Tools媲美的開源引擎。先不說可以滿足建模要求的引擎軟體包，就是求解器方面，中國開源項目也寥寥可數。

下面開始對Google Spreadsheet中的Linear Optimization插件的應用進行具體介紹。還是在上面已經建立好的數學模型基礎上，討論通過Google的Linear Optimization求解此模型。在開始之前，需要完成以下準備工作：

1. 解決網路連接問題。這個大家懂的，大家可以自行想辦法解決，如果一些在外資或需要訪問國外網路的機構工作的朋友（如我們辦公室是可能正常合法訪問國外網路），則可以跳過此節。
2. 註冊Google帳號(若你未有Google帳號）。因為Google Docs，Google Spreadsheet均是類似於Microsoft Office的在線文件處理應用服務。無論是哪個Google服務，需要使用必須通過Google帳號。

完成上述前期工作後，即可開始Google Spreadsheet的配置和應用。

Linear Optimization是Google Spreadsheet的一個插件，可以實現對線性規劃模型的求解。默認狀態下，Google Spreadsheet是不包括此插件的，需要使用的話，則需要將其添加Spreadsheet中才能使用。下面將操作步驟列出。

1.創建Spreedsheet文件

　　登錄Google帳號，進入Google Sheets頁面（http://sheets.google.com）。進入後Spreadsheet主頁後，點擊頁面右下角的紅色添加按鈕，創建一個Google Spreadsheet文件。在創建好的文件中，可以將文件命名為「LP_Test」文件即會自動保存到你的Google帳號。如下圖。

2. 添加Linear Optimization插件

　　通過Spreadsheet頁面的Add-ons菜單，將Linear Optimization插件添加到你的帳號上，才能進一步使用該線性優化插件，可以看到還有更多規劃功能的插入可以添加。這也是Google在運籌優化方面的系統架構與Optaplanner存在的差別。我將會有新的一篇文章對比兩個開源規劃引擎這方面的差異，敬請期待。點擊Add-ons -> Get add-ons… 菜單項目，將會彈出【Add-ons】頁面，在頁面上的搜索框中輸入」Linear Optimization」並回車，即可搜索出該插件,並點擊【+FREE】按鈕進行添加。如下圖。

　　在添加過程中，需要你登錄或選擇一個已經登錄的帳號,選擇你已登錄的帳號即可，如下圖

　　選擇或輸入帳號後，會轉到一個Sign in頁面，大概意思是說Linear Optimization將會被添加到指定頁面，點擊頁面底部右側的【Allow】按鈕即可。

3. 創建線性規劃模板

　　添加完成後，在【Add-ons】菜下會出現【Linear Optimization】子菜單項，該子菜單下會有用於設置決策變數、約束和求解的子項。見下圖。

　　選擇【Linear Optimization】菜單下的【Set up optimization sheet】子項，即可在當前Sheet中生成求解模板，模板中包含f了決策變數定義區域、目標函數區域和約束區域。下圖為新創建的線性規劃模板剛創建好的狀態.

4.填入決策變數、約束和目標函數

　　創建好線性規劃模板後，需要將上面已經建立好的數學規劃模型輸入模板中對應的單元格，正確地反映數學模型的意義，才啟動求解器（Google的在線規劃服務，是通過WebAPI提供的，因此其求解器是部署在Google自己的伺服器上）。初學者可以通過Linear Optimization菜單下的子項，來輔助輸入決策變數和約束。選擇Linear Optimization菜單下的【Add Variables…】子項，在頁面的右側會顯示【Describe data】 頁面。該頁面中點擊【Variables】和【Constrains】頁簽分別可以提供定義決策變數(即模型中的x,y)和約束條件(即模型中s.t.部分中的不等式)的輸入元素。以下是【Variables】的各個欄位輸入如下：

　　a. Variable Name: 該欄位表示決策變數，輸入第一個決策變數名x.

　　b. Type: 從我們建立的規劃模型中，知道決策變數x是一個整數，因此Type中選擇Integer,(它默認是Continuous).

　　c. Lower bound, Upper bound:這兩個欄位分別表示約束變數的最大值與最小值（即決策變數的取值範圍），從模型中可以看到它們的最小值是0, 且無最大值限制，因此，Lower bound填上0， Upper bound留空（它提示為Defaults to Infinity,大家應該懂了吧?)。

　　d. Objective coefficient:該欄位表示該決策變數在目標函數中的係數，也就是目標函數表達式中，x前面的常數，從模型的目標函數上可以看到x前面的技術係數為20，因此填入20即可。點擊【Add】按鈕，x的相關值及其在目標函數上的體現將會被填入模板中。以相同的規則填入決策變數y相關的資訊。

　　下面介紹約束的輸入，點擊【Constraints】頁簽，頁面將會展示約束條件填入介面：

　　a. Constraint Name:因為現在我們是新建立約束，因此在下拉框中選擇【New Constraint】, 頁面中將會出現【Constraint Name】、【Lower bound】和【 Upper bound】三個欄位。【Constraint Name】欄位中輸入一個名稱用於標識該約束即可，因為模型中每個不等式是表示一種資源的限制，因此第一個不等式是針對資源1的庫存限制的，我們輸入」Resource1」。

　　b. Lower bound，Lower bound：以模型的s.t.部分中的首個不等式 為例

其實我們根據題意可以把它補充成

也就是說，模型中少了產品A資源用量大於等於０這個限制；其實這樣是不嚴謹的。但因為目標函數是求最大值，因此，大於等於0這個條件不表示出來，也不會影響模型的正確性。但需要在Google的Linear Optimization中表示這個不等式時，必然存在條件才能完整表示，包括以後我們直接使用Google OR-Tools中的線性規劃模組，不等式的必須有明確的範圍才行。根據上面的不等式，我們在【Lower bound】中填入0，【Upper bound】輸入280(即少於等於280)。點【Add】按鈕，首個約束就會被添加到模板中，並添加了範圍限制見下圖紅框內.此時,Resource1這一行(第8行)僅僅表示了式子的值域，具體的式子並未完成。

　　c. Variable Name, Coefficient:上一步僅添加了約束Resource1的基本結構。本步驟將要完成不等式中的式子部分。點擊【Add】後，頁面將會出現【Variable name】下拉框，其中有當前模型的所有決策變數(即本例中的x與y）供選擇。在右則還會出現【Variable coefficient】輸入框，表示你選擇的決策變數在不等式中前面的常數（即技術係數），通過模型我們看到Resource1不等式中x前面的常數是5，因此填入5，並點擊【Add】，此時常數5就會被填入當前約束，x對應列的單元格（即D8單元格)。同樣地，不等式中決策變數y前面的常是3，因此我們在【Variable name】中選擇y，並在【Variable coefficient】中填入3。點擊【Add】即可完成約束Resource1的輸入。同樣的方法輸入資源2和資源3的約束，完成後如下圖

5.求解

　　完成上述步驟之後，我們建立的規劃模型已經全部表達到Linear Optimization模板中，選中【Linear Optimization】菜單下的【Solve】子項，程式將會啟用Google的線性規劃Web服務，對剛才輸入的模型進行求解，並把結果填回表格中，見下圖.

上圖是模型的規劃結果，可以看到，通過這個模型計算出來的最大的利潤是1900(B6單元格)，獲得此利潤時，產品A的產量是20(D6單元格)，產品B的產量是60(E6單元格).

寫在最後

本文通過對一個簡單的線性規劃問題，建立線性規劃模型；並分別通過Excel的規劃求解組件，和Google Spreadsheet下的Linear Optimization插件對模型進行求解，從而得出最優結果。非IT專業人員在實際生產活動中，遇到此類線性規劃問題時，可以通過此方法對問題進行求解。而專業的IT人員，遇到的問題會比本文中的情況複雜得多，通過現成的軟體功能很可能是無法解決，需要通過軟體開發技術，結合規劃引擎進行求解。大家可以參考我之前的Optaplanner系列文章 .

本人近段時間也在研究Google OR-Tools，發現本文用到的Linear Optimization其實是通過將Google OR-Tools的多個運籌求解器，建立在Google自身的伺服器上；再以Web服務方式提供的。在實際軟體項目開發過程中，我們可以繞開Google Spreadsheet服務程式，通過自己的程式調用其運籌優化服務進行求解。當然目前中國的情況來看，通過對它的開源項目Google OR-Tools的引用，直接將其求解器納入我們自己開發的系統中更現實。

我正在撰寫一篇關於Optaplanner與Google OR-Tools的對比文章，通過對比兩個引擎的用法，有針對性的引出對Google OR-Tools的應用，敬請期待，謝謝！