摘要：目前使用Python求解混合整數規劃問題的執行個體大多使用了cplex庫。本文基于教材上的混合整數規劃和0-1整數規劃兩道例題，嘗試使用Python語言予以解決，得到的答案與教材上一緻。現将有關求解過程及代碼附上，以期對運籌學初學者有所裨益。
關鍵詞：整數規劃； 0-1規劃； cplex；Python
0.例題
目标函數：
M a x z = 3 x 1 + x 2 + 3 x + 3 \ Max \ z=3x_1+x_2+3x+3 Max z=3x1+x2+3x+3
限制條件： { − x 1 + 2 x 2 + x 3 ≤ 4 4 x 2 − 3 x 3 ≤ 2 x 1 − 3 x 2 + 2 x 3 ≤ 3 x 1 , x 2 , x 3 ≥ 0 x 1 為 整 數 x 3 為 0 − 1 變 量 \left\{\begin{aligned} -x_1+2x_2+x_3\leq 4 \\ 4x_2-3x_3\leq 2\\ x_1-3x_2+2x_3\leq3\\ x_1,x_2,x_3\geq 0\\ x_1為整數\\ x_3為0-1變量\\ \end{aligned}\right. ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧−x1+2x2+x3≤44x2−3x3≤2x1−3x2+2x3≤3x1,x2,x3≥0x1為整數x3為0−1變量
1.Python代碼
#導入cplex
import cplex
from cplex.exceptions import CplexError
my_obj=[3.0,1.0,3.0]#目标函數系數
my_ctype='ICI'#目标函數變量的類型，一般就是C,整數類型就是I就是integer
my_ub=[cplex.infinity, cplex.infinity,1]#變量的限制條件上限
my_lb=[0,0,0]#變量的限制條件下限
my_colnames=['x1','x2','x3']#column names列向量的名字
my_rhs=[4.0,2.0,3.0]#限制條件的值相當于b
my_rownames=['r1','r2','r3']#row names行向量的名字
#是限制條件的形式，L為小于号“less-than”,大于号是‘G’，即'greater than'
my_sense='LLL'
def populatebyrow(prob):
#設定目标函數類型：求max or min
prob.objective.set_sense(prob.objective.sense.maximize)
#設定（增加）變量，明确目标函數，限制條件上限、下限，變量類型，還有變量名稱
prob.variables.add(obj=my_obj,lb=my_lb,ub=my_ub,types=my_ctype,
names=my_colnames)
#對應的限制方程
rows=[[['x1','x2','x3'],[-1.0,2.0,1.0]],
[['x2','x3'],[4.0,-3.0]],
[['x1','x2','x3'],[1.0,-3.0,2.0]]]
#設定（增加）限制條件
prob.linear_constraints.add(lin_expr=rows, senses=my_sense,
rhs=my_rhs,names=my_rownames)
#初始化模型
my_prob=cplex.Cplex()
#計算
handle=populatebyrow(my_prob)
#求解
my_prob.solve()
#輸出結果
print(my_prob.solution.get_objective_value())
x = my_prob.solution.get_values()
print(x)
2.結果
可以看到，求得最優解: z = 16.25 ; x 1 = 4.0 , x 2 = 1.25 , x 3 = 1.0 \ z=16.25; \ x_1=4.0, x_2=1.25, x_3=1.0 z=16.25; x1=4.0,x2=1.25,x3=1.0
3.求解0-1規劃問題
（1）例題
某公司計劃在市區的東、南、西、北四個區建立銷售門市部，拟議有10個位置 A i j ( j = 1 , 2 , . . . , 10 ) \ A_{ij}(j=1,2,...,10) Aij(j=1,2,...,10)可供選擇，考慮到各地居民消費水準及居民居住密集度，規定：
（1）在東區由 A 1 , A 2 , A 3 \ A_1,A_2,A_3 A1,A2,A3三個點中至多選擇兩個；
（2）在西區由 A 4 , A 5 \ A_4,A_5 A4,A5兩個點中至少選擇一個；
（3）在南區由 A 6 , A 7 \ A_6,A_7 A6,A7兩個點中至少選擇一個；
（4）在北區由 A 8 , A 9 ， A 10 \ A_8,A_9，A_{10} A8,A9，A10三個點中至少選擇兩個。
| A 1 \ A_1 A1 | A 2 \ A_2 A2 | A 3 \ A_3 A3 | A 4 \ A_4 A4 | A 5 \ A_5 A5 | A 6 \ A_6 A6 | A 7 \ A_7 A7 | A 8 \ A_8 A8 | A 9 \ A_9 A9 | A 10 \ A_{10} A10 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 投資額 | 100 | 120 | 150 | 80 | 70 | 90 | 80 | 140 | 160 | 180 |
| 利潤 | 36 | 40 | 50 | 22 | 20 | 30 | 25 | 48 | 58 | 61 |
A j \ A_j Aj各點的裝置投資及每年可獲利潤由于地點不同而不同，預測情況如上表，但總投資金額不超過720萬元，問應該選擇哪幾個銷售點，可使利潤最大。
（2）求解
解：設 0 − 1 \ 0-1 0−1變量 x i = 1 ( A i 點 被 選 用 ) \ x_i=1(A_i點被選用) xi=1(Ai點被選用)或 x i = 0 ( A i 點 未 被 選 用 ) \ x_i=0(A_i點未被選用) xi=0(Ai點未被選用)，建立數學模型如下：
目标函數：
M a x z = 36 x 1 + 40 x 2 + 50 x 3 + 22 x 4 + 20 x 5 + 30 x 6 + 25 x 7 + 48 x 8 + 58 x 9 + 61 x 10 \ Max\ z=36x_1+40x_2+50x_3+22x_4+20x_5+30x_6+25x_7+48x_8+58x_9+61x_{10} Max z=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10
限制條件： { 100 x 1 + 120 x 2 + . . . + 160 x 9 + 180 x 10 ≤ 720 x 1 + x 2 + x 3 ≤ 2 x 4 + x 5 ≥ 1 x 6 + x 7 ≥ 1 x 8 + x 9 + x 10 ≥ 2 1 ≥ x i ≥ 0 , i = 1 , 2 , . . . , 10 x i 為 0 − 1 變 量 , i = 1 , 2 , . . . , 10 \left\{\begin{aligned} 100x_1+120x_2+...+160x_9+180x_{10} \leq 720 \\ x_1+x_2+x_3 \leq 2\\ x_4+x_5 \geq 1\\ x_6+x_7 \geq 1\\ x_8+x_9+x_{10} \geq 2\\ 1 \geq x_i \geq 0, i=1,2,...,10\\ x_i為0-1變量,i=1,2,...,10\\ \end{aligned}\right. ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧100x1+120x2+...+160x9+180x10≤720x1+x2+x3≤2x4+x5≥1x6+x7≥1x8+x9+x10≥21≥xi≥0,i=1,2,...,10xi為0−1變量,i=1,2,...,10
(3)代碼
import cplex
from cplex.exceptions import CplexError
my_obj=[36.,40.,50.,22.,20.,30.,25.,48.,58.,61.]
my_ctype='IIIIIIIIII'
my_ub=[1,1,1,1,1,1,1,1,1,1]
my_lb=[0,0,0,0,0,0,0,0,0,0]
my_colnames=['x1','x2','x3','x4','x5','x6','x7','x8','x9','x10']
my_rhs=[720,2,1,1,2]
my_rownames=['r1','r2','r3','r4','r5']
my_sense='LLGGG'
def populatebyrow(prob):
prob.objective.set_sense(prob.objective.sense.maximize)
prob.variables.add(obj=my_obj, lb=my_lb, ub=my_ub,
types=my_ctype, names=my_colnames)
rows=[[['x1','x2','x3','x4','x5','x6','x7','x8','x9','x10'],[100.0,120.0,150.0,80.0,70.0,90.0,80.0,140.0,160.0,180.0]],
[['x1','x2','x3'],[1.0,1.0,1.0]],
[['x4','x5'],[1.,1.]],
[['x6','x7'],[1.,1.]],
[['x8','x9','x10'],[1.,1.,1.]]]
prob.linear_constraints.add(lin_expr=rows, senses=my_sense,
rhs=my_rhs,names=my_rownames)
my_prob=cplex.Cplex()
handle=populatebyrow(my_prob)
my_prob.solve()
print(my_prob.solution.get_objective_value())
x = my_prob.solution.get_values()
print(x)
（4）結果
4.說明
（1）以上兩個例題均來自韓伯棠老師主編的《管理運籌學》（第四版）教材中，韓老師授課十分有趣、清楚，是初學運籌學者比較好的入門課程。
（2）網上有很多關于cplex的說明，本人了解不全，很多設定還搞不清楚，請各位批評指正。