基于Python語言的線性規劃問題求解*

羅云中 何麗紅

（蘭州大學 管理學院 甘肅蘭州 730000）

引言

在現代管理決策中，運籌學是以整體化最優為目標，從系統的觀點出發，在現有有限資源、環境的條件下尋求符合目標要求的最優化行動方案[1]。線性規劃是運籌學中研究最早、發展較快、應用廣泛、方法較成熟的一個重要分支，它是運籌學中最有用、最好用、最常用、最實用的方法，并被廣泛應用于工商企業、軍事部門、政府部門的經營管理、軍事作戰、經濟分析等實踐中，在市場銷售、生產計劃、庫存管理、運輸問題、財政投資、人事管理、項目可行性、工程方案選擇、城市管理等方方面面都能應用到線性規劃的理論和方法[2-4]。

Python由荷蘭人Guido van Rossum發明，由于Python語言簡單、開發速度快、容易上手的特點，自1991年第一版公開發行到2004年開始，Python的使用率呈線性增長，受到編程者的歡迎和喜愛，在2017年度編程語言排行榜中，Python位居第一。Python大量應用于web開發、大數據處理、人工智能、自動化運維開發、云計算、爬蟲和游戲開發等方面，同時也可以應用于運籌學模型，特別是線性規劃模型的求解。

一、線性規劃問題的Python模塊解法

本文以運籌學中套裁下料這一經典線性規劃問題為例，來展示如何運用Python語言的Scipy模塊和Pulp模塊對其進行求解。

1.套裁下料的線性規劃問題描述

套材下料問題一般是已知m種原材料的數量和規格尺寸，需要將原材料按一定的規格尺寸和數量進行裁切，要求所裁的數量不少于所需的數量。通過枚舉法找到所有可能裁切的方法，目標是選擇最優的裁剪方式使所消耗的原材料數量最少。舉例如下。

西蘭物業公司承擔了正大食品在全市92個零售點的肉類、蛋品和蔬菜的運送業務。運送業務要求每天4點鐘開始從總部發貨，送完貨時間必須在7：30前結束（不考慮空車返回時間）。這92個零售點每天需要運送貨物0.5噸，其分布情況為：5公里以內為A區，有36個點，從總部到該區的時間為20分鐘；5公里以上10公里以內為B區，有26個點，從總部到該區的時間為40分鐘；10公里以上為C區，有30個點，從總部到該區的時間為60分鐘；A區各點間運送時間為5分鐘，B區各點間運送時間10分鐘，C區各點間運送時間20分鐘；各區之間運送時間20分鐘。每點卸貨、驗收時間為30分鐘。西蘭物業公司準備購買規格為2噸的運送車輛，每車購價5萬元。請用線性規劃方法確定每天的運送方案，使購買車輛的總費用為最少。

根據題意，枚舉每一種運輸方案，可以得到如表1所示的13種滿足條件的送貨路線，設決策變量xi（i=1，2，…，13）分別表示每一種可能送貨路線所需的車輛數，由此可以得到基本線性規劃模型如下。

表1 西蘭物業公司可能的送貨路線統計

s.t.4x1+3x2+3x3+2x4+2x5+2x6+x7+x8+x9+x10≥36

x2+2x4+x5+2x7+x8+3x9+4x11+3x12+2x13≥26

x3+x5+2x6+x7+2x8+3x10+x12+2x13≥30

xi、2，i=1，2，…，13

這是一個由13個決策變量和3個約束條件構成的線性規劃模型。下面將分別應用Python語言的Scipy和Pulp模塊求解。

2.用Scipy模塊進行求解

利用Scipy模塊求解線性規劃模型，首先需要引入import scipy.optimize.linprog方法來求解線性規劃模型，需要注意的是linprog函數只能用來求解目標函數最小化，且約束條件關系是小于等于型的線性規劃模型。其語法為：scipy.optimize.linprog（c，A_ub=None，b_ub=None，A_eq=None，b_eq=None，bounds=None，method=’interiorpoint’，callback=None，options=None，x0=None）

其中，參數c為目標函數系數組成的一維數組；A_ub為各約束條件關系為不等式時決策變量前的系數組成的二維數組，每個約束條件系數為二維數組中的一個元素；b_ub為約束條件關系為不等式時的右邊常數項組成的一維數組；A_eq為約束條件關系為等式時決策變量前的系數組成的二維數組，b_eq為約束條件關系為等式時的右邊常數項；bounds為決策變量的取值范圍；method為用來求解線性規劃模型的算法，Python提 供highs-ds，highs-ipm，highs，interior-point，revised simplex，simplex等算法，默認是內點法，常用單純型或修正的單純型法。

Scipy模塊求解線性規劃模型的具體過程如下。

第一步：將目標函數最大值問題轉化為最小值，將約束條件關系轉化為小于等于型。

使用scipy.optimize.linprog求解如上套材下料問題時，目標函數是最小化問題，可以直接使用，但約束條件關系為大于等于型，因此需要在不等式兩邊同時乘以“-1”，將約束條件轉化為如下形式[4]：

-x2-2x4-x5-2x7-x8-3x9-4x11-3x12-2x13≤-26

-x3-x5-2x6-x7-2x8-3x10-x12-2x13≤-30

第二步：將目標函數和約束條件寫入Python解釋器。

具體代碼如下，#后面是解釋，程序不執行

#引入模塊scipy和numpy模塊

from scipy import optimize

import numpy as np

針對我國相關文獻的梳理，發現近年來我國對于創新創業人才培養的理論研究還相對薄弱，創新創業實驗班的開展仍處于探索和發展階段，對實驗班創辦的相關研究不夠充足，尚未形成系統的理論體系，研究的重點主要側重在以下方面。

#最小化問題的目標函數系數

c=np.array（[5，5，5，5，5，5，5，5，5，5，5，5，5]）

#約束條件系數，將大于等于轉化為小于等于

A_ub=np.array（[[-4，-3，-3，-2，-2，-2，-1，-1，-1，-1，0，0，0]，

[0，-1，0，-2，-1，0，-2，-1，-3，0，-4，-3，-2]，

[0，0，-1，0，-1，-2，-1，-2，0，-3，0，-1，-2]]）

#約束條件常數項

b_ub=np.array（[-36，-26，-30 ]）

#決策變量的取值范圍

x1=x2=x3=x4=x5=x6=x7=x8=x9=x10=x11=x12=x13=（0，None）

#調用linprog函數

res=optimize.linprog（c，A_ub，b_ub，bounds=（x1，x2，x3，x4，x5，x6，x7，x8，x9，x10，x11，x12，x13），method='revised simplex'）

#輸出求解結果

print（res）

將以上代碼在解釋器中運行后將得到如下結果：

con：array（[]，dtype=float64）

fun：115.0

message：'Optimization terminated successfully.'

nit：1

slack：array（[0.，0.，0.]）

status：0

success：True

x：array（[ 6.5，0.，0.，0.，0.，0.，0.，0.，0.，10.，6.5，0.，0.]）

其中，con是約束條件關系為等號時的左邊實際值和右邊常數項的殘差，fun為最優值，在此題中最小的構成成本為115萬元；message 為算法狀態的描述；nit為循環迭代次數，slack為松弛量/剩余量；status 為0表示成功求得最優解；success算法成功完成時為True；x為最優解，分別對應為x1=6.5，x2=0，x3=0，x4=0，x5=0，x6=0，x7=0，x8=0，x9=0，x10=10，x11=6.5，x12=0，x13=0。

3.用Pulp模塊進行求解

Pulp是應用Python語言編寫的一個開源線性規劃問題求解包，它的主要作用是將優化問題描述為數學模型，生成MPS文件或者LP文件，然后調用LP求解器來進行求解。但Pulp不是Python的默認安裝模塊，需要單獨安裝。Pulp的安裝方式也比較簡單，打開cmd命令框，輸入pip install pulp指令，回車執行安裝，安裝成功后會有success提示。

Pulp模塊求解線性規劃模型的具體過程如下。

第一步：初始化問題類，用pulp.LpProblem確定求解問題并把它命名為prob，給最大化問題傳遞參數LpMaximize，最小化問題傳遞參數LpMaximize。

第二步：定義決策變量pulp.LpVariable，下限值lowBound為0，變量類型為整數LpInteger。

第三步：定義目標函數lpDot（c，x）。

第四步：定義約束條件lpDot（a，x）。

第五步：求解solve。

第六步：輸出求解結果。

Pulp模塊一般需要通過pandas模塊來讀取excel表格中的數據來建立數學模型，將表1保存到excel表格中，并命名為“西蘭送貨.xlsx”，通過pandas模塊將表格讀取為Dataframe，選取不同的數據分別作為目標函數系數c，約束條件系數a，常數項b[5]。

編寫代碼讀入數據，調用pulp模塊并運行。得到結果為最優值115.0，最優解為線路1購買6輛車，線路4購買1輛車，線路10購買10輛車，線路11購買6輛車，能最優化滿足車輛派出和成本最低。pulp模塊可以指定決策變量數據類型，能更好的滿足車輛為整數的條件。

從輸出結果可以看出，最優值為115萬，最優解為線路1購買6輛車，線路4購買1輛車，線路10購買10輛車，線路11購買6輛車。通過Pulp模塊能更好貼切題意，使買入的車輛為整數。

結語

通過Python中兩個模塊對西蘭公司的送貨路線這一典型的套材下料問題的求解，可以看出scipy.optimize.linprog模塊的優點是使用二維數組和一維數組的方式建立數學模型，將數據輸入到excel或數據庫中也能通過Python的程序來讀取，可以處理大型的線性規劃問題。在使用Scipy過程中需要輸入的代碼數量較少，處理過程簡單便捷，輸出結果簡潔明了，對初學者來說十分容易掌握此方法。但該模塊也有明顯的缺點，在處理線性規劃模型時，如果遇到最大化問題需要將目標函數乘以-1來轉化成最小化問題，并且約束條件的約束關系不等式只能是小于等于型，遇到大于等于需要不等式兩邊乘以-1進行轉化；不能通過設定決策變量類型來約束決策變量為整數或二進制，因此該模塊只能處理線性規劃問題，不能處理整數線性規劃問題。

與Scipy模塊相比，Pulp模塊功能十分強大，自帶的線性規劃函數LpVariable在聲明變量時配合編程語言的循環功能，可以便捷地生成大批量的決策變量，利用lpDot函數對變量與系數進行矩陣相乘形成約束條件，內置函數能方便處理大型的線性規劃問題；Pulp模塊配合pandas模塊還能十分方便讀取存儲在Excel或數據庫中的數據來生成數學模型。但Pulp模塊求解后不會自動輸出求解結果，需要格式化輸出最優值和循環遍歷輸出最優解組合[6]。

總而言之，相對其他線性規劃問題的求解軟件，Python語言具有明顯的優勢。首先，其強大的數據處理功能和靈活的處理能力，能特別方便地讀取各種類型的文件。其次，Python語言對變量和約束條件沒有數量限制，計算百萬級的變量和約束條件都十分輕松，只受限于計算機的內存和CPU計算能力。最后，Python語言是開源免費語言，開發者社區龐大，全球有大量開發者參與Python模塊的開發，模塊特別多。因此，將Python語言應用于管理運籌學的教學之中，能極大降低高校教學成本，提升管理運籌學實驗課程教學效果，增強學生編程和靈活處理能力，提升學生培養質量。