0-1型整數(shù)規(guī)劃

1.介紹：0-1型整數(shù)規(guī)劃是整數(shù)規(guī)劃中的特殊情況，通過引入0-1變量$x_j$來描述約束條件，一般用于指派選擇問題這一類的具有相互排斥的約束條件的規(guī)劃問題，其中$x_j$取1表示起作用或者被選擇，取0反之。

比如有兩種運輸方式可供選擇，但只能選其一。車運輸約束條件為$5x_1+4x_2\le 24$，船運輸?shù)募s束條件為$7x_1+3x_2\le 45$。這兩種約束條件是互相排斥的，所以我們引入一個0-1變量：
$$y=\{\begin{array}{l}1,采取船運，\\ 0,采取車運.\end{array}$$
那么就可以改寫約束條件為：
$$\begin{gathered} ?\begin{array}{l}5x_1+4x_2\le 24+yM,\\ 7x_1+3x_2\le 45+(1?y)M,\\ y=0或1.\end{array} \\ 式中M為充分大的數(shù) \end{gathered}$$
而如果有m個互相排斥的約束條件：$a_{i1}{x}_1+?+a_{in}{x}_n\le b_i,i=1,2,?,m。$

那么將引入m個0-1變量：
$$y_i=\{\begin{array}{l}1,第i個約束起作用，\\ 0，第i個約束不起作用.\end{array}$$
則可以得出：
$$\begin{gathered} a_{i1}{x}_1+?+a_{in}{x}_n\le b_i+(1?y_i)M,i=1,2,?,m, \\ {y}_1+?+y_m=1, \end{gathered}$$
這樣就實現(xiàn)了多取一的情況,有點像學(xué)數(shù)電里的選擇器。

2.固定費用問題(Fixed Cost Promblem)

某工廠為了生產(chǎn)某種產(chǎn)品，有幾種不同的生產(chǎn)方式可供選擇，如選定的生產(chǎn)方式投資高(選購自動化程度高的設(shè)備)，由于產(chǎn)量大，因而分配到每件產(chǎn)品的變動成本就降低；反之，如選定的生產(chǎn)方式投資低，將來分配到每件產(chǎn)品的變動成本可能增加。所以必須全面考慮。設(shè)有三種方式可供選擇，令

? $$\begin{gathered} j=1,2,3分別表示三種方式; \\ {x}_j表示采用第j種方式時的產(chǎn)量; \\ {c}_j表示采用第j種方式時每件產(chǎn)品的變動成本； \\ {k}_j表示采用第j種方式時的固定成本 \end{gathered}$$

所以采用各種生產(chǎn)方式的總成本分別為：
$$P_j=\{\begin{array}{l}{k}_j+c_j{x}_j,當(dāng)x_j>0,\\ 0,當(dāng)x_j=0,j=1,2,3\end{array}$$
再引入0-1變量$y_j$:
$$y_j=\{\begin{array}{l}1,當(dāng)采用第j種生產(chǎn)方式，即x_j>0時\\ 0,當(dāng)不采用第j種生產(chǎn)方式，即x_j=0時\end{array}$$
于是目標(biāo)函數(shù)可以表示為:
$$\begin{gathered} minz=(k_1{y}_1+c_1{x}_1)+(k_2{x}_2+c_2{x}_2)+(k_3{y}_3+c_3{x}_3) \\ s.t.y_j\epsilon \le x_{j}M,j=1,2,3, \\ 式中：\epsilon 為充分小的常數(shù)；M為充分大的常數(shù) \end{gathered}$$
PS:其實可以理解取了充分大充分小的常數(shù)之后，這個約束條件便會失去約束作用，自然不被選擇。比如小于充分大后，其最大值就等于沒有設(shè)限

3.指派問題的數(shù)學(xué)模型

擬分配n人去做n項工作，每人做且僅做一項工作，若分配第i人去做第j項工作，需花費$c_{ij}$單位時間，問應(yīng)如何分配工作才能使工人花費的總時間最少？給出指派問題的系數(shù)矩陣C=($c_{ij}$)

引入0-1變量
$$x_{ij}=\{\begin{array}{l}1,第i人做第j項工作\\ 0,第i人不做第j項工作\end{array}$$
所以可得出模型為：
$$\begin{gathered} min\sum _{i?1}^n\sum _{j=1}^n{c}_{ij}{x}_{ij}, \\ s.t.?\begin{array}{l}{\sum }_{j=1}^n{x}_{ij}=1,\\ {\sum }_{i=1}^n{x}_{ij}=1,\\ x_{ij}=0或1\end{array} \end{gathered}$$
例1.投資問題：有600萬元投資5個項目，如下表：

項目投資額項目收益約束條件

一	210	160	1.項目一、二、三中選一項
二	300	210	2.項目三、四中選一項
三	150	60	3.項目五以項目一為先驗條件
四	130	80
五	260	180

即可求得模型：
$$\begin{gathered} maxz=160x_1+210x_2+60x_3+80x_4+180x_5 \\ s.t.?\begin{array}{l}210x_1+300x_2+150x_3+130x_4+260x_5\le 600,\\ x_1+x_2+x_3=1,\\ x_3+x_4=1,\\ x_5\le x_1\\ x_1,x_2,x_3,x_4,x_5=0或1\end{array} \end{gathered}$$
非標(biāo)準(zhǔn)型的指派模型

1.如果是最大化指派問題，則需要先把指派矩陣中的最大值m-$c_{ij}$?形成新的指派系數(shù)?。

2.如果人數(shù)和工作數(shù)不等，則哪個少就增加哪個的虛擬對象，并設(shè)代價為0

3.如果一個人可做多分工作，則多創(chuàng)造幾個相同的人

4.某工作不能某人做，則將代價設(shè)置為足夠大

匈牙利算法

第一步：從指派矩陣c中的每一行減去當(dāng)前行的最小元素，再從每一列減去當(dāng)前列的最小元素

第二步：進行試指派，尋求最優(yōu)解。從只有一個0的行(列)開始，標(biāo)記當(dāng)前0，劃去當(dāng)前0所在的列(行)的所有0，反復(fù)進行直到盡可能多的0被標(biāo)記。若仍有未被標(biāo)記或者劃掉的0，且同行(列)至少有兩個0，則從0最少的行(列)開始，比較這與行所有0元素的列中0元素的數(shù)量，標(biāo)記該行0元素最少的列對應(yīng)的0，劃掉同行同列的0，直到所有0都被標(biāo)記或者劃掉，若標(biāo)記0的數(shù)目等于階數(shù)，則找到了最優(yōu)解，否則進行第三步，但是第三步老折騰了，所以如果需要進行第三步，建議放棄改用MATLAB求解。

整數(shù)線性規(guī)劃的MATLAB求解

Matlab求解混合整數(shù)線性規(guī)劃的命令為：

[x,fval] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)

標(biāo)準(zhǔn)數(shù)學(xué)模型如下：
$$\begin{gathered} min{f}^{T}x, \\ s.t.?\begin{array}{l}x(intcon)為整數(shù)\\ Ax\le b,\\ Aeq\le beq,\\ lb\le x\le ub.\end{array} \\ 其中intcon的意義為整數(shù)約束變量的位置，基本上有n個決策變量則取[1,2,?,n] \end{gathered}$$
例2.求解下列指派問題，已知指派矩陣為：
$$?\begin{array}{ccccc}3& 8& 2& 10& 3\\ 8& 7& 2& 9& 7\\ 6& 4& 2& 7& 5\\ 8& 4& 2& 3& 5\\ 9& 10& 6& 9& 10\end{array}?$$
解：這里需要把二維決策變量$x_{ij}(i,j=1,?,5)$變?yōu)橐痪S決策變量$y_k(k=1,?,25)$

然后依據(jù)[x,fval] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)抽取參數(shù)：
$$\begin{gathered} c=?\begin{array}{ccccc}3& 8& 2& 10& 3\\ 8& 7& 2& 9& 7\\ 6& 4& 2& 7& 5\\ 8& 4& 2& 3& 5\\ 9& 10& 6& 9& 10\end{array}? \\ intcon=[1,2,?,25] \\ Aeq=?\begin{array}{ccc}0& ?25行?& 0\\ ?& & ?\\ 10列& & ?\\ ?& & ?\\ 0& ?& 0\end{array}? \\ beq=[1,?10列?,1{]}^T \\ lb為25行1列的0 \\ ub為25行1列的1 \end{gathered}$$
轉(zhuǎn)化為代碼如下：

c = [3 8 2 10 3;8 7 2 9 7;6 4 2 7 5;8 4 2 3 5;9 10 6 9 10];%錄入指派矩陣 c = c(:);%將矩陣抽為一維 a = zeros(10,25);%這里a取十行是指行有五個加上列有五個 intcon = 1:25; for i = 1:5a(i,(i - 1)*5+1:5*i) = 1;%將所有的行和所有的列相加取值為一a(5 + i,i:5:25) = 1; end b = ones(10,1); lb = zeros(25,1); ub = ones(25,1); x = intlinprog(c,intcon,[],[],a,b,lb,ub); x = reshape(x,[5,5])

結(jié)果如下圖：

總結(jié)

以上是生活随笔為你收集整理的0-1型整数规划—MATLAB数学建模的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。