第四章整數線性規劃4.1汽車生產計劃問題4.2分派問題4.3選課策略y問題二：某廠每日8小時的產量不低于1800件。為了進行質量控制，計劃聘請兩種不同水平的檢驗員。一級檢驗員的標準為：速度25件/小時，正確率98%，計時工資4元/小時；二級檢驗員的標準為：速度15小時/件，正確率95%，計時工資3元/小時。檢驗員每錯檢一次，工廠要損失2元。為使總檢驗費用最省，該工廠應聘一級、二級檢驗員各幾名？解設需要一級和二級檢驗員的人數分別為x1、x2人,則應付檢驗員的工資為：因檢驗員錯檢而造成的損失為：故目標函數為：約束條件為：且x1、x2均為整數編寫M文件xxgh4.m如下：c=[40;36];A=[-5-3];b=[-45];Aeq=[];beq=[];vlb=zeros(2,1);vub=[9;15];%調用linprog函數：[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)ToMatlab(xxgh4)結果為：x=9.00000.0000fval=360即只需聘用9個一級檢驗員。

注：本問題應還有一個約束條件：x1、x2取整數。故它是一個整數線性規劃問題。這里把它當成一個線性規劃來解，求得其最優解剛好是整數：x1=9，x2=0，故它就是該整數規劃的最優解。若用線性規劃解法求得的最優解不是整數，將其取整后不一定是相應整數規劃的最優解，這樣的整數規劃應用專門的方法求解。例1汽車廠生產計劃汽車廠生產三種類型的汽車，已知各類型每輛車對鋼材、勞動時間的需求，利潤及工廠每月的現有量。小型中型大型現有量鋼材（噸）1.535600勞動時間（小時）28025040060000利潤（萬元）234制訂月生產計劃，使工廠的利潤最大。設每月生產小、中、大型汽車的數量分別為x1,x2,x3汽車廠生產計劃模型建立

小型中型大型現有量鋼材1.535600時間28025040060000利潤234線性規劃模型(LP)模型求解

3）

模型中增加條件：x1,x2,x3

均為整數，重新求解。

x=64.5161167.74190.0000f=632.2581結果為小數，怎么辦？1）舍去小數：取x1=64，x2=167，算出目標函數值z=629，與LP最優值632.2581相差不大。2）試探：如取x1=65，x2=167；x1=64，x2=168等，計算函數值z，通過比較可能得到更優的解。但必須檢驗它們是否滿足約束條件qiche1.m注意：IP不能用Matlab軟件直接求解整數規劃(IntegerProgramming,簡記IP)模型求解

怎么辦？算法：1、割平面法 2、分支定界法 3、全枚舉法（應用較廣泛）全枚舉法一般步驟：1、確定決策變量數量和變化范圍；2、用for-end語句作決策變量的整型參數變化的循環，若有多個決策變量則要實現多重循環；3、用if-end語句作不等式約束和等式約束條件是否滿足的判斷；4、符合約束條件的一組決策變量，則進行目標函數計算，并進行存儲，否則跳過5、用函數max或min語句，搜索目標函數的最大值或最小值及相應的決策變量。注意：當決策變量變化范圍較大時，運行速度較慢qiche2.mqiche2.cIP的最優解x1=64，x2=168，x3=0，最優值z=632注意：對于本題來說，決策變量的變化范圍很大，故程序運行速度較慢。分派問題若干項任務分給一些候選人來完成，每人的專長不同，完成每項任務取得的效益或需要的資源就不同，如何分派任務使獲得的總效益最大，或付出的總資源最少。若干種策略供選擇，不同的策略得到的收益或付出的成本不同，各個策略之間有相互制約關系，如何在滿足一定條件下作出決擇，使得收益最大或成本最小。丁的蛙泳成績退步到1’15”2；戊的自由泳成績進步到57”5,組成接力隊的方案是否應該調整？如何選拔隊員組成4100米混合泳接力隊?例2混合泳接力隊的選拔

甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”45名候選人的百米成績窮舉法：組成接力隊的方案共有5!=120種。目標函數若選擇隊員i參加泳姿j的比賽，記xij=1,否則記xij=0

0-1規劃模型

cij(秒)~隊員i第j種泳姿的百米成績約束條件每人最多入選泳姿之一

ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每種泳姿有且只有1人用MATLAB優化工具箱解線性規劃命令：x=bintprog（c，A，b，Aeq,beq,x0）注意：若沒有不等式：存在，則令A=[]，b=[].模型：minz=cX

X為0或1模型求解

MIN66.8x1+57.2x2+78x3+70x4+67.4x5+……+58.6x16+53x17+59.4x18+57.2x19+62.4x20SUBJECTTOx1+x6+x11+x16<=1

……x5+x10+x15+x20<=1x1+x2+x3+x4+x5=1

……x16+x17+x18+x19+x20=1設X11=X1,X12=X2,,X13=X3,X14=X4,X15=X5,,X21=X6X22=X7,X23=X8,,X24=X9,X25=X10,X31=X11,,X32=X12X33=X13,X34=X14,X35=X15,X41=X16,X42=X17,X43=X18,,X44=X19,X45=X20模型求解

最優解：x2=x8=x14=x16=1,其它變量為0;成績為253.2(秒)=4’13”2Youyong.m

甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”4甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.為了選修課程門數最少，應學習哪些課程？

例3選課策略要求至少選兩門數學課、三門運籌學課和兩門計算機課課號課名學分所屬類別先修課要求1微積分5數學

2線性代數4數學

3最優化方法4數學；運籌學微積分；線性代數4數據結構3數學；計算機計算機編程5應用統計4數學；運籌學微積分；線性代數6計算機模擬3計算機；運籌學計算機編程7計算機編程2計算機

8預測理論2運籌學應用統計9數學實驗3運籌學；計算機微積分；線性代數0-1規劃模型

決策變量

目標函數

xi=1~選修課號i的課程（xi=0~不選）

選修課程總數最少約束條件最少2門數學課，3門運籌學課，2門計算機課。

課號課名所屬類別1微積分數學2線性代數數學3最優化方法數學；運籌學4數據結構數學；計算機5應用統計數學；運籌學6計算機模擬計算機；運籌學7計算機編程計算機8預測理論運籌學9數學實驗運籌學；計算機先修課程要求最優解：

x1=x2=x5=x6=x7=x8=1,其它為0；6門課程，總學分210-1規劃模型

約束條件x3=1必有x1=x2=1模型求解xuanke.m課號課名先修課要求1微積分

2線性代數

3最優化方法微積分；線性代數4數據結構計算機編程5應用統計微積分；線性代數6計算機模擬計算機編程7計算機編程

8預測理論應