0-1規劃問題的MATLAB标準型
1、在上述模型中,目标函數f 需要 “極小化”,不等式限制形式為 “≤”。假設x為n維設計變量,且線性規劃問題具有不等式限制m1個,等式限制m2個,那麼:c、x均為n維列向量,b為m1維列向量,beq為m2維列向量,A為m1×n維矩陣,Aeq為m2×n維矩陣。
2、如果不滿足标準型的要求,則需要對原問題進行轉化,化為标準型之後才能使用相關函數,标準化的方法和線性規劃中的類似
0-1規劃問題的MATLAB求解函數
MATLAB優化工具箱中求解0-1規劃問題的指令為bintprog
x = bintprog(f)
x = bintprog(f,A,b)
x = bintprog(f,A,b,Aeq,beq)
x = bintprog(f,A,b,Aeq,beq,x0)
x = bintprog(f,A,b,Aeq,Beq,x0,options)
[x,fval] = bintprog(...)
[x,fval,exitflag] = bintprog(...)
[x,fval,exitflag,output] = bintprog(...)
輸入參數
MATLAB工具箱中的bintprog函數在求0-1規劃問題時,提供的參數有如下幾種:
模型參數: x、c、b、beq、A和Aeq
初始解參數:x0
算法控制參數: options,我們可以通過optimset指令對這些具體的控制參數進行設定,其中主要參數的設定方法如下所示:
輸出參數
1、x為0-1規劃問題的最優解
2、fval為0-1規劃問題在最優解x處的函數值
3、exitflag傳回的是bintprog計算終止時的狀态訓示,說明算法終止的原因,其取值和其代表的具體原因如表所示。
4、輸出參數output是一個傳回優化過程中相關資訊的結構變量,它所包含的屬性及屬性代表的意義如表所示。
參數exitflag的實體意義
參數output所包含的資訊
0-1規劃問題的指令詳解
x = bintprog(f) %該函數調用格式求解如下形式的0-1規劃問題
x = bintprog(c,A,b) %該函數調用格式求解如下形式的0-1規劃問題
x = bintprog (c,A,b,Aeq,beq) %該函數調用格式求解如下形式的0-1規劃問題
x = bintprog (c,A,b,Aeq,beq,x0) % 在前一個調用格式的基礎上同時設定求解算法的初始解為x0,
如果初始解x0不在0-1規劃問題的可行域中,算法将采用預設的初始解
x = bintprog (c,A,b,Aeq,beq,x0,options) % 用options指定的優化參數進行最小化.
可以使用optimset來設定這些參數
[x,fval] = bintprog(...) % 在優化計算結束之時傳回整數規劃問題在解x處的目标函數值fval
[x,fval,exitflag] = bintprog(...) % 在優化計算結束之時傳回exitflag值,
描述函數計算的退出條件。
[x,fval,exitflag,output] = bintprog(...)`% 在優化計算結束之時傳回結構變量output
執行個體
c=[20;6;8;9];
A=[-10 -6 -5 -2; -7 -2 -2 -4; -2 -1 -1 -10; 0 1 1 -1];b=[-4;-4;-2;1];
lb=[0;0;0;0];ub=[1;1;1;1];
M=1:4; %均要求為整數變量
Tol=1e-8; %判斷是否整數的誤差限
[x,fval]=intprog(c,A,b,[],[],lb,ub,M,Tol) %調用intprog函數
[x1,fval1]=bintprog(c,A,b) %調用bintprog函數