基于Python語言的線性規(guī)劃問題求解*

羅云中 何麗紅

（蘭州大學(xué) 管理學(xué)院 甘肅蘭州 730000）

引言

在現(xiàn)代管理決策中，運(yùn)籌學(xué)是以整體化最優(yōu)為目標(biāo)，從系統(tǒng)的觀點(diǎn)出發(fā)，在現(xiàn)有有限資源、環(huán)境的條件下尋求符合目標(biāo)要求的最優(yōu)化行動(dòng)方案[1]。線性規(guī)劃是運(yùn)籌學(xué)中研究最早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個(gè)重要分支，它是運(yùn)籌學(xué)中最有用、最好用、最常用、最實(shí)用的方法，并被廣泛應(yīng)用于工商企業(yè)、軍事部門、政府部門的經(jīng)營管理、軍事作戰(zhàn)、經(jīng)濟(jì)分析等實(shí)踐中，在市場銷售、生產(chǎn)計(jì)劃、庫存管理、運(yùn)輸問題、財(cái)政投資、人事管理、項(xiàng)目可行性、工程方案選擇、城市管理等方方面面都能應(yīng)用到線性規(guī)劃的理論和方法[2-4]。

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

一、線性規(guī)劃問題的Python模塊解法

本文以運(yùn)籌學(xué)中套裁下料這一經(jīng)典線性規(guī)劃問題為例，來展示如何運(yùn)用Python語言的Scipy模塊和Pulp模塊對(duì)其進(jìn)行求解。

1.套裁下料的線性規(guī)劃問題描述

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

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

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

表1 西蘭物業(yè)公司可能的送貨路線統(tǒng)計(jì)

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

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

2.用Scipy模塊進(jìn)行求解

利用Scipy模塊求解線性規(guī)劃模型，首先需要引入import scipy.optimize.linprog方法來求解線性規(guī)劃模型，需要注意的是linprog函數(shù)只能用來求解目標(biāo)函數(shù)最小化，且約束條件關(guān)系是小于等于型的線性規(guī)劃模型。其語法為：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）

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

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

第一步：將目標(biāo)函數(shù)最大值問題轉(zhuǎn)化為最小值，將約束條件關(guān)系轉(zhuǎn)化為小于等于型。

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

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

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

第二步：將目標(biāo)函數(shù)和約束條件寫入Python解釋器。

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

#引入模塊scipy和numpy模塊

from scipy import optimize

import numpy as np

針對(duì)我國相關(guān)文獻(xiàn)的梳理，發(fā)現(xiàn)近年來我國對(duì)于創(chuàng)新創(chuàng)業(yè)人才培養(yǎng)的理論研究還相對(duì)薄弱，創(chuàng)新創(chuàng)業(yè)實(shí)驗(yàn)班的開展仍處于探索和發(fā)展階段，對(duì)實(shí)驗(yàn)班創(chuàng)辦的相關(guān)研究不夠充足，尚未形成系統(tǒng)的理論體系，研究的重點(diǎn)主要側(cè)重在以下方面。

#最小化問題的目標(biāo)函數(shù)系數(shù)

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

#約束條件系數(shù)，將大于等于轉(zhuǎn)化為小于等于

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]]）

#約束條件常數(shù)項(xiàng)

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

#決策變量的取值范圍

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

#調(diào)用linprog函數(shù)

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'）

#輸出求解結(jié)果

print（res）

將以上代碼在解釋器中運(yùn)行后將得到如下結(jié)果：

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是約束條件關(guān)系為等號(hào)時(shí)的左邊實(shí)際值和右邊常數(shù)項(xiàng)的殘差，fun為最優(yōu)值，在此題中最小的構(gòu)成成本為115萬元；message 為算法狀態(tài)的描述；nit為循環(huán)迭代次數(shù)，slack為松弛量/剩余量；status 為0表示成功求得最優(yōu)解；success算法成功完成時(shí)為True；x為最優(yōu)解，分別對(duì)應(yīng)為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模塊進(jìn)行求解

Pulp是應(yīng)用Python語言編寫的一個(gè)開源線性規(guī)劃問題求解包，它的主要作用是將優(yōu)化問題描述為數(shù)學(xué)模型，生成MPS文件或者LP文件，然后調(diào)用LP求解器來進(jìn)行求解。但Pulp不是Python的默認(rèn)安裝模塊，需要單獨(dú)安裝。Pulp的安裝方式也比較簡單，打開cmd命令框，輸入pip install pulp指令，回車執(zhí)行安裝，安裝成功后會(huì)有success提示。

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

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

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

第三步：定義目標(biāo)函數(shù)lpDot（c，x）。

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

第五步：求解solve。

第六步：輸出求解結(jié)果。

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

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

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

結(jié)語

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

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

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