【學界|編碼】整數規劃求解方法大全（附Lingo代碼）

07-09

來自專欄『運籌OR帷幄』大數據人工智慧時代的運籌學

文章作者： @張敬信 （哈工大數學博士哈爾濱商業大學教師）
責任編輯： @文雨之 （東北大學系統工程博士生）
本篇文章是由以上作者在知乎的優秀文章(原文鏈接:【優化演算法】03. 整數規劃), 通過『運籌OR帷幄』責任編輯整理而成。
歡迎原鏈接轉發，轉載請前往 @留德華叫獸 的主頁獲取信息，盜版必究。
敬請關注和擴散本專欄及同名公眾號，會邀請全球知名學者陸續發布運籌學、人工智慧中優化理論等相關乾貨、知乎Live及行業動態：『運籌OR帷幄』大數據人工智慧時代的運籌學

全部變數限制為整數的規劃問題，稱為純整數規劃；部分變數限制為整數的規劃問題，稱為混合整數規劃；變數只取0或1的規劃問題，稱為0-1整數規劃。

整數規劃問題，建議使用Lingo軟體求解。常用的整數規劃問題解法有：

（1）分枝定界法：可求純或混合整數線性規劃。

（2）割平面法：可求純或混合整數線性規劃。

（3）隱枚舉法：用於求解0-1整數規劃，有過濾法和分枝法。

（4）匈牙利法：解決指派問題（0-1規劃特殊情形）。

（5）蒙特卡羅法：求解各種類型規劃。

1、分枝定界法

分支定界法的基本思想是：設有最大化的整數規劃問題A，先解與之相應的線性規劃問題B，若B的最優解不符合A的整數條件，那麼B的最優目標函數必是A的最優目標函數z*的上界，記作z2, 而A的任意可行解的目標函數值將是z*的一個下界z1, 分支定界法就是將B的可行域分成子區域（稱為分支）的方法，逐步減小z2和增大z1，最終求到z*。

例1 分枝定界法原理示例：

$max z=5x_1+8x_2$

$mathrm{s.~ t.} quad x_1+x_2 leq 6$ $(P_0)$

$~~~~~~~~~ 5x_1+9x_2 leq 45$

$x_i geq 0, , x_i in mathbb{Z} quad i=1,,2$

Lingo代碼：

model:max=5*x1+8*x2;x1+x2<6;5*x1+9*x2<45;@gin(x1);@gin(x2);end

運行結果：

Global optimal solution found.

Objective value: 40.00000

Variable Value

X1 0.000000

X2 5.000000

2、0-1整數規劃

變數 $x_i$ 只能取值 $0,,1$ , 該約束條件可表示為：

$0leq x leq 1, quad x_i in mathbb{N} qquad ext{或} qquad x_i(x_i-1)=0$

1. 隱枚舉法

例2 求解下列0-1規劃問題：

$max z=3x_1-2x_2+5x_3$

$mathrm{s.~t.} quad x_1+2x_2-x_3 leq 2 qquad qquad (a)$

$x_1+4x_2+x_3 leq 4 qquad qquad (b)$

$x_1+x_2 leq 3 qquad qquad qquad ~~ (c)$

$4x_2+x_3 leq 6 qquad qquad ~~~~~~ (d)$

求解思路：

(1) 先試探性地求一個可行解，易看出 $(x_1,,x_2,,x_3)=(1,,0,,0)$ 滿足約束條件，故是一個可行解，相應的目標函數值為 $z=3$ .

(2) 由於是求極大值，故目標值 $z<3$ 的解，不必檢驗是否滿足約束條件即可刪除，於是可增加一個約束條件（稱為過濾條件）：

$3x_1-2x_2+5x_3 geq 3 qquad qquad ~(e)$

(3)用全部枚舉法，3個變數共 $2^3=8$ 種可能的組合，用過濾條件（並計算目標函數值，不斷改進過濾條件）篩選每個可能的組合，最終得到問題的最優解。

隱枚舉法求解過程如下表所示：

從而得到最優解為 $(1,,0,,1)$ , 最優值為 $z^*=8$ 。

Lingo代碼：

model:max=3*x1-2*x2+5*x3;x1+2*x2-x3<2;x1+4*x2+x3<4;x1+x2<3;4*x2+x3<6;@bin(x1);@bin(x2);@bin(x3);end

運行結果：Global optimal solution found.

Objective value: 8.000000

Variable Value

X1 1.000000

X2 0.000000

X3 1.000000

2. 指派問題

指派問題可以描述為整數規劃問題，暫略（放圖論部分）

3、蒙特卡羅法（隨機取樣法）

前面的方法，主要是針對線性整數規劃而言，對於非線性整數規劃沒有通用的有效解法。

整數規劃由於限制變數是整數，增加了求解難度，但整數解是有限個，所以可以採用枚舉法。當枚舉個數很多時，顯性枚舉是不現實的，但利用蒙特卡羅隨機取樣法，在一定的計算量下是可以得到滿意解的。

例3 求解如下非線性整數規劃問題：

$max z=x_1^2 + x_2^2 +3x_3^2 +4x_4^2+2x_5^2 - 8x_1 - 2x_2 - 3x_3 -x_4 - 2x_5$

$mathrm{s. ~t.} quad x_1+x+2+x_3+x_4+x_5 leq 400$

$x_1+2x_2+2x_3+x_4+6x_5 leq 800$

$2x_1+x_2+6x_3 leq 200$

$x_3+x_4+5x_5 leq 200$

$0 leq x_i leq 99, quad i=1,, cdots, , 5$

若用顯枚舉法，共需 $100^5=10^{10}$ 個點，計算量非常大。但用蒙特卡羅法隨機計算 $10^6$ 個點，便可找到滿意解。

Matlab代碼：

目標函數：

function [f,g]=fun1(x)f=x(1)^2+x(2)^2+3*x(3)^2+4*x(4)^2+2*x(5)^2-8*x(1)-2*x(2)-3*x(3)-x(4)-2*x(5);g(1)=sum(x)-400;g(2)=x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800;g(3)=2*x(1)+x(2)+6*x(3)-200;g(4)=x(3)+x(4)+5*x(5)-200;

主程序：

rand(state,sum(clock));p0=0;ticfor i=1:10^6 x=99*rand(5,1); x1=floor(x); x2=ceil(x); [f,g]=fun5(x1); if sum(g<=0)==4 if p0<=f x0=x1; p0=f; end end [f,g]=fun5(x2); if sum(g<=0)==4 if p0<=f x0=x2; p0=f; end endendx0, p0toc

運行結果（注意由於是隨機取樣，故每次的運行結果可能不一樣）：

x0 = 43 94 1 99 5

p0 = 49298

Elapsed time is 45.494952 seconds.

Lingo代碼：

model:sets:row/1..4/:b;col/1..5/:c1,c2,x;link(row,col):a;endsetsdata:c1=1,1,3,4,2;c2=-8,-2,-3,-1,-2;a=1 1 1 1 11 2 2 1 62 1 6 0 00 0 1 1 5;b=400,800,200,200;enddatamax=@sum(col:c1*x^2+c2*x);@for(row(i):@sum(col(j):a(i,j)*x(j))<b(i));@for(col:@gin(x));@for(col:@bnd(0,x,99));end

運行結果：Local optimal solution found.

Objective value: 51568.00

Variable Value

X( 1) 50.00000

X( 2) 99.00000

X( 3) 0.000000

X( 4) 99.00000

X( 5) 20.00000

4、混合整數規劃（配送選址問題）

物流配送中心選址問題，是在給定某一地區所有備選點的地址集合中選出一定數目的地址建立配送中心，從而建立一系列的配送區域，以實現選出點建立的配送中心與各需求點和工廠(供貨點)形成的配送系統總物流費用最小。例如，如圖1所示。

總費用=運輸費用+配送費用+倉儲費用+固定成本

設有 $m$ 個供應工廠， $n$ 個客戶， $l$ 個備選配送中心；

$p_k$ 表示第 $k$ 個工廠的產量 ( $k=1,,cdots,,m$ );

$d_j$ 表示第 $j$ 個客戶的需求量 ( $j=1,,cdots,,n$ );

$g_i$ 表示第 $i$ 個配送中心的單位管理成本 ( $i=1,,cdots,,l$ );

$f_i$ 表示建立第 $i$ 個配送中心的固定成本；

$z_i$ 指示是否選中第 $i$ 個配送中心， $1$ 表示選中， $0$ 表示未選中；

$z_{max}$ 表示配送中心的最大限制數目；

$c_{ki}$ 表示第 $k$ 個供應工廠到第 $i$ 個配送中心的運輸單價；

$h_{ij}$ 表示第 $i$ 個配送中心到第 $j$ 個客戶的配送單價；

$w_{ki}$ 表示第 $k$ 個供應工廠到第 $i$ 個配送中心的運量；

$x_{ij}$ 表示第 $i$ 個配送中心到第 $j$ 個客戶的運量。

則配送選址問題數學模型的一般形式如下：

$min quad sum_{k=1}^m sum_{i=1}^l c_{ki}w_{ki} + sum_{i=1}^l sum_{j=1}^n h_{ij}x_{ij} + sum_{i=1}^l sum_{k=1}^m g_i w_{ki} + sum_{i=1}^l f_i z_i$

$mathrm{s.~t.} quad sum_{i=1}^l w_{ki} leq p_k, quad k=1,, cdots, , m$ (運出量不大於生產量)

$sum_{j=1}^n x_{ij} = sum_{k=1}^m w_{ki}, quad i=1, , cdots, , l$ (運入量不等於運出量)

$sum_{i=1}^l x_{ij} geq d_j, quad , j=1, , cdots, , n$ (運入量不小於需求量)

$sum_{k=1}^m w_{ki} leq a_i z_i, , quad i = 1, , cdots, , l$ (運入量不大於倉庫容量)

$sum_{i=1}^l z_i leq z_{max}$ (選取配送中心不超過最大限制數目)

例4 設有4個備選物流配送中心地址，6個工廠為其供貨，6個客戶需要產品，最多設置3個物流配送中心。工廠到物流配送中心的運輸價格見表2，物流配送中心到客戶的運輸價格見表3，工廠的總生產能力見表4，物流配送中心的固定成本、單位管理成本，及容量見表5，客戶的需求量見表6：

Lingo代碼：

model:sets:factory/p1..p6/:p;warhouse/w1..w4/:a,f,g;customer/c1..c6/:d;tr/tr1..tr4/:z;link1(factory,warhouse):c,w;link2(warhouse,customer):h,x;endsetsdata:p=40000,50000,60000,70000,60000,40000;a=70000,60000,70000,50000;f=500000,300000,400000,400000;g=3,2,5,4;d=10000,20000,10000,20000,30000,10000;c = 6 54 22 3 4 96 8 7 57 4 2 34 2 5 13 4 1 7;H = 3 27 4 7 56 1 4 2 5 32 4 5 3 6 85 6 3 7 4 6;enddatamin=@sum(link1(k,i):c(k,i)*w(k,i))+@sum(link2(i,j):h(i,j)*x(i,j))+@sum(link1(k,i):g(i)*w(k,i))+@sum(warhouse(i):f(i)*z(i));@for(factory(k):@sum(link1(k,i):w(k,i))<=p(k));@for(warhouse(i):@sum(link2(i,j):x(i,j))=@sum(link1(k,i):w(k,i)));@for(customer(j):@sum(link2(i,j):x(i,j))>=d(j));@for(warhouse(i):@sum(link1(k,i):w(k,i))<=(a(i)*z(i)));@sum(tr(i):z(i))<=3;@for(tr(i):@bin(z));end

運行結果：Global optimal solution found.

Objective value: 1480000

Variable Value

Z(TR2) 1.000000

Z(TR4) 1.000000

W( P1,W4) 40000.00

W( P5,W2) 60000.00

X( W2,C2) 20000.00

X( W2,C3) 10000.00

X( W2,C4) 20000.00

X( W2,C6) 10000.00

X( W4,C1) 10000.00

X( W4,C5) 30000.00

結果表明，最小物流成本為1480000；最優方案是選擇2號和4號備選地址作為物流配送中心；由工廠1向4號配送中心供應40000，由工廠5向2號配送中心供應60000；配送中心2分別向客戶2、3、4、6供貨20000、10000、20000、10000，配送中心4分別向客戶1、5供貨10000、30000。

主要參考文獻：

吳剛, 張敬信等. 數學建模與數學實驗，北京: 中國商業出版社，2017
卓金武等. Matlab在數學建模中的應用，北京：北京航空航天大學出版社，2011
謝金星，薛毅. 優化建模與LINDO/LINGO軟體，北京：清華大學出版社，2006
司守奎，孫璽菁. 數學建模演算法與應用，北京：國防工業出版社，2013

註：掃描文末二維碼關注『運籌OR帷幄』微信公眾號，後台回復「運籌學」，免費獲取海量學習資料。

如果你是運籌學/人工智慧碩博或在讀，請在下圖的公眾號後台留言：「加微信群」。系統會自動辨認你的關鍵字，並提示您進一步的加群要求和步驟，邀請您進全球運籌或AI學者群（群內學界、業界大佬雲集）。

同時我們有：【運籌學|優化愛好者】【供應鏈|物流】【人工智慧】【數據科學|分析】千人QQ群，想入群的小夥伴可以關注下方公眾號點擊「加入社區」按鈕，獲得入群傳送門。

學術界|工業界招聘、徵稿等信息免費發布，請見下圖：