文档介绍：第八章整數線性規劃
本章內容:
各類型的整數線性規劃模式
全整數規劃問題的圖解法及電腦解
包含0-1變數應用
0-1變數賦予的建模彈性
各類型的整數線性規劃模式
一線性規劃中,所有變數都限定為整數,稱為“全整數線性規劃(all integer linear program)”。下列為一全整數線規劃摸式:
Max 2X1+3X2
. 3X1+3X2≦12
1X2+1X2≦4
1X1+2X2≦6
X1,X2≧0且為整數
刪除整數線性規劃決策變數的「整數」限定後線性規劃問題,稱為
“整數線性規劃的LP寬鬆式(LP Relaxation)”。
一線性規劃中,僅有部份變數被限定為整數稱為混合整數線性規劃(mixed integer linear programming MILP)下列為一混合整數線性規劃模式:
Max 3X1+4X2
. -1X1+2X2≦8
1X2+2X2≦12
2X1+1X2≦16
X1,X2≧0且X2為整數
此例中將“X2為整數”的要求刪去後之線性規劃稱為“混合整數線性規劃的LP寬鬆式”。
在全整數或混合整數線性規劃中,整數值的變數為離散變數(discrete variable),其他變數稱為連續變數(continuous variable)。
一整數規劃中,整數變數只允許0或1稱為0-1或二元(binary)整數規劃。
全整數規劃問題的圖解法及電腦解
例:
東生不動產公司目前有2,000,000元可用來投資出租房屋計劃。公司將投資方案限於在住宅區的別墅及公寓,別墅每棟
282,000元,而目前只有五戶別墅可買得到,每棟公寓售價400,000元,公寓的數量則很多。
公司管理人員每月有140小時間來管理這些投資的不動產。每棟別墅需4小時管理,每棟公寓需40小時。每月利潤,別墅每棟為10,000元,公寓每棟為15,000元,公司要如何分配資金投資到別墅及公寓,以使總利潤最高。
設T=購買別墅棟數 A=購買公寓棟數
線性規劃如下:(金錢以千元為單位)
Max 10T+15A
. 282T+400A≦2000 可用資金
4T+ 40A≦140 管理時間
T ≦5 可購別墅
T,A≧0且為整數
LP寬鬆式的圖解:
最適解為:T=,A=,Z=73,574元,此解不合理,因決策變數非整數。
A
公寓數目
最適LP寬鬆解
T=,A=
管理時間限制
目標函數=
可行區域
可用資金限制
可購別墅限制
T
別墅數目
東生不動產問題寬鬆式的圖解
利用圓整得到整數解:
若將寬鬆式解(T=,A=)“化整”至最“近”的整數值,得解為T=2,A=3,Z=65,000元,此解並非最適解。
全整數問題的圖解
=4,A=2,Z=70,000元,因此以“化整”結果將損失5,000元(=70,000元-65,000元)。
A
注意:黑點表示可行整數解的位置
公寓數目
管理時間限制
目標函數=70
可用資金限制
可行區域
可購別墅限制
T
別墅數目
東生不動產整數問題的圖解
利用LP寬鬆式建立解的界限
整數線性規劃圖解法與線性規劃圖解法相似,首先畫出LP寬鬆式的合理區,然後將合理整數點以黑點標出,爾後即可找出目標函數線上的最適整數解點。
在極大化問題中,整數線性規劃之最適解值與LP寬鬆式之解值的關係有以下的特性:
對極大化的整數線性規劃問題,LP寬鬆解的最適值可做為整數解最適值的上限。而對極小化的整數線性規劃問題,LP寬鬆解的最適值可做為整數解最適值的下限。
由以上特性可知,任何求極大整數或混合整數線性規劃的值,LP寬鬆式解為其上限。
電腦解
包含0-1變數的應用
資本預算
例: