




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
第
3
章Integer
ProgrammingI
P整數規劃3.1整數規劃問題及其建模3.2分支定界法3.3割平面法3.40-1型整數線性規劃的解法3.5指派問題第3章整數規劃第3章整數規劃2基本概念整數規劃:變量取整數的線性規劃;純整數規劃:所有變量都取整數的線性規劃;混合整數規劃:部分變量取整數的線性規劃;0-1規劃:所有變量都取0、1兩個值的規劃;0-1混合規劃:部分變量取0、1兩個值的規劃。1、0-1變量的應用
例1:某油田在10個有油氣構造處要選擇若干個鉆探采油,設第j個構造開采時需投資aj元,投產后預計年收益為cj元,若該油田投資的總限額為b元,問:應選擇哪幾個構造開采最為有利?設xj=10---選擇開采第j個構造---不選擇開采第j個構造maxz=Σcjxjj=110∑ajxjbxj=0或1(j=1,2,---,10)j=110-----年總收益----投資額限制3.1
整數規劃問題及其建模
例2:上述例題中,如果在開采中需用電力,解決的方案或由電網供電或由自備的柴油機發電。已知第j個構造開采時每天耗電量為dj度,電網每天供電量限制為f度。當使用自備柴油機發電時,每度電平均耗油0.3公斤,而柴油供應量限額為每天p公斤。試在模型中表示出該限制條件。采用電網供電:∑djxjf采用自備柴油機發電:∑0.3djxjpj=110j=110+(1-y1)M+(1-y2)My1+y2=1y1,y2=0或1M-----非常大的正數例3:若在開采時還需滿足下述條件:(a)若開采8號,則必須同時開采6號;(b)若開采5號,則不許開采3號;(c)2號和4號至少開采一個;(d)8號與7號必須同時開采;(e)1號、4號、6號、9號開采時不能超過兩個,試表示上述約束條件。(a)當x8=1x6=1,x6≠0當x8=0x6=1,x6=0∴x8
x6
(b)當x5=1x3=0,x3≠1當x5=0x3=0,x3=1∴
x5+x3
1(c)x2+x4
1(d)x8=x7(e)x1+x4+x6+x9
2例4:兩組條件滿足其中一組若x14,則x21,否則(x14),則x23。設yi=10第i組條件起作用第i組條件不起作用則i=1,2x14+(1-y1)Mx21-(1-y1)MM——充分大正數x14-(1-y2)Mx23+(1-y2)My1+y2=1y1,y2=0或1例3-1考慮固定成本的最小生產費用問題
在最小成本問題中,設第j種設備的固定成本為
,運行的變動成本為
,則生產成本與設備運行時間的關系為:設第j種設備運行每小時可以生產第i種產品
件,而第i種產品的定貨為
件。要滿足定貨同時使設備運行的總成本最小的問題為:9混合0-1規劃線性規劃與整數規劃的關系10線性規劃整數規劃X*=(13/5,19/5)Z*=89/5=17.8X*=(5,3)Z*=17一、引例
某廠擬用集裝箱托運甲、乙兩種貨物,每箱的體積、重量、可獲利潤及托運時所受的限制如下表所示,問如何托運能使總收益最大?貨物體積(米3/箱)重量(噸/箱)利潤(千元/箱)甲乙2 2 33 1 214 米3 9噸托運限制3.2分支定界法建模:解:設托運甲貨物x1箱,乙貨物x2箱Maxz=3x1+2x2 2x1+3x214 2x1+x29 x10,x20,且為整數24624(3.25,2.5)x1x22x1+3x2=142x1+x2=93x1+2x2=624624(3.5,2)x1x22x1+3x2=142x1+x2=93x1+2x2=6(2.5,3)24624(4,1)x1x22x1+3x2=142x1+x2=93x1+2x2=6(2.5,3)(3,2)分枝定界法:L0:z0=14.75x1=3.25,x2=2.5L1:z1=14.5L2:z2=13.5L3:z3=13L4:z4=14x1=3.5,x2=2x1=2.5,x2=3x1=3,x2=2x1=4,x2=1x2≤2x2≥3x1≤3x1≥4基本思想分支(Branch)定界(Bound)3.2分支定界法(B&B)第3章整數規劃xr≤Irxr≥Ir+1例3-2
用分枝定界法求解以下整數規劃先求得相應的線性規劃的最優解,為3.2分支定界法(B&B)第3章整數規劃1819Sub-6無可行解原問題Sub-2Sub-1Sub-3Sub-4Sub-5Sub-7Sub-9Sub-8Sub-10無可行解x2≤2x2≥3x1≤5x1≥5x2≤1x2≥2x1≤4x1≥6x2≤0x2≥1圖3-3.探索過程示意圖×√√3.3.1割平面法基本思想3.3
割平面法第3章整數規劃20設放棄變量整數要求得到的線性規劃的最優單純形表如下:設其中基變量Xr的值br不是整數,以I表示整數,以F表示正的真分數,令yrj=Irj+
Frj(0≤
Frj<1)
br=Ir+Fr
(0<
Fi
<1)將上面兩式代入約束r中,得3.3
割平面法第6章整數規劃21改寫成因此對于整數可行解,約束(3-2)可以寫成更嚴格的不等式這就是源于第r行的割平面。
⑴線性規劃的任何整數可行解都滿足這個約束;未切割掉任何一個整數解。
⑵線性規劃的非整數最優解不滿足這個約束。切割掉了非整的LP解X;(3-4)3.3
割平面法第3章整數規劃22
2°
若Xk的分量全為整數,則Xk即為原問題的最優解,停止計算;
否則根據Xk的一個非整分量所在單純形表的那一行,譬如第i行,構造源于第
i行的割平面(3-4)
,并給它引入一個弛變量xn+k+1,得Frjxj+
xn+k+1
=-Frj=m+1
-
3°
把這個新約束添到最優單純形表的倒第2行,并增加一列(即
xn+k+1列),用對偶單純形法繼續迭代,求得一個新解Xk+1,令k:=k+1,返2°。
3.3.2割平面法基本步驟
1°
用單純形法求解IP的伴隨LP問題,得到其解X0,令k=0;n3.3
割平面法第6章整數規劃23
minz=3x1+4x23x1+x2≥4x1+2x2≥4
x1,
x2≥0
x1,
x2為整數s.t.例3-3
試用割平面法求解以下整數規劃:解求解線性規劃得最優單純形表選擇一個非整數的基變量,例如x2=8/5,構造約束條件(3-4)3.3割平面法第3章整數規劃24用對偶單純形法,x5離基,x3進基,已獲得整數的最優解:X*=(2,1)Z*=10第6章整數規劃25
maxz=
x1+x22x1+x2≤54x1-x2≥2
x1,
x2≥0
x1,
x2為整數s.t.
maxz=
x1+x2
2x1+x2+x3=5
-4x1+x2+x4
=
-2
x1,
x2,x3,
x4≥
0s.t.例:
試用割平面法求解:解
標準化并獲取排列陣:第6章整數規劃26
cj
基
解
x1
x2x3
x4
1
1
00序號
2
110x3x4
5-2
-
4
1
0100
0
1
1
00-
4
4
0
3/2
1
1/2x3x1
01
1/21
-1/4
0-1/4
1/2
0
5/4
0
1/43/211
x2x17/6
1
0
1/6
-1/6
8/3
0
1
2/3
1/323/60
0
-5/6
-1/6(a)(b)(c)
源于第一行構造割平面:-
(x3+
x4)≤0232313
-
x3-
x4+
x5=
-232313①等價于x2
≤2
2
00
21
-3110
3/2101/2
0-1/2x2x1x4(b)cj
基
解
x1
x2x3
x4x5
1
1
00
0序號
x2x1x5
23/6
0
0
5/6
1/6
0-2/30
0-2/3
-1/31-1/3110
7/61
0
1/6-1/6
0
8/30
1
2/3
1/3
0(a)
2
01
001
7/2
00
1/2
0
1/2第6章整數規劃28源于第二行構造割平面:-
(x3+
x5)≤0121212
-
x3-
x5+
x6=
-121212X1*=
(1,2)TX2*=
(2,1)Tz*
=
3②
等價于
x1+x2
≤3cj
基
解
x1x2
x3x4x5
x63
5
00
0
0
0
1
0
0
1
0x2x1
x4
x6
23/2
2
1
01/2
0
-1/2
01100
0
0
2
1
-3
07/2
0
01/2
0
1/2
0-1/2
0
0-1/2
0-1/2
1-1/2x2x1
x4
x3
1
0
0
1
0
1-2
0
0
0
0
1
-5
4
1
1
0
0
0
-1
1
2
0
1
0
0
10
3
0
0
0
0
01110010
11
22x1x2A(7/6,8/3)①x2
≤
2B(1,2)C(3/2,2)②x1
+
x2
≤
3
11
22x1x2B(1,2)C(3/2,2)D(2,1)隱枚舉法(ImplicitEumeration)例3-4用隱枚舉法求解下列問題
④③①②可行解:X=(1,0,0),Z=3
增加過濾條件(filteringconstraint)
◎3.40-1型整數規劃的解法第3章整數規劃303.40-1型整數規劃的解法第3章整數規劃313.5指派問題及匈牙利算法(AssignmentProblem)一、問題的提出和數學模型例:有一份說明書,要分別譯成英、日、德、俄四種文字,交與甲、乙、丙、丁四個人去完成,因各人專長不同,他們完成翻譯不同文字所需要的時間(小時)如表所示。規定每項工作只能交與其中的一個人完成,每個人只能完成其中的一項工作。問:如何分配,能使所需的總時間最少?甲乙丙丁工作人譯英文譯日文譯德文譯俄文2109715414813141611415139建立模型:設xij=10譯英文:x11+x12+x13+x14=1譯日文:x21+x22+x23+x24=1譯德文:x31+x32+x33+x34=1譯俄文:x41+x42+x43+x44=1甲:x11+x21+x31+x41=1乙:x12+x22+x32+x42=1丙:x13+x23+x33+x43=1丁:x14+x24+x34+x44=1xij=0或1(i=1,2,3,4;j=1,2,3,4)Minz=aijxij (aij---效率)i=1j=144若第i項工作交與第j個人完成若第i項工作不交與第j個人完成分配問題一般數學模型結構:
設有m項工作要交與m個人完成,其中第i項工作交與第j個人完成時所需花費的時間為
aij。規定每項工作只能交與其中的一個人完成,而每個人只能完成其中的一項工作。問:如何分配,可使所需的總時間最少?Minz=aijxijst.xij=1xij=1i=1j=1j=1i=1mmmmxij=0或1(i=1,2,···,m;j=1,2,···,m)(i=1,2,···,m)(j=1,2,···,m)二、匈牙利法:基本思想:(0)564(0)563(0)(0)562
克尼格定理(konig):如果從效率矩陣[aij]的每一行元素中分別減去(或加上)一個常數ui,從每列中分別減去(或加上)一個常數vj,得到一個新的效率矩陣[bij],其中bij=aij-ui-vj,則以[bij]為效率矩陣的最優解等價于以[aij]為效率矩陣的最優解.證明:以[aij]為效率矩陣的目標函數值:z0=aijxij以[bij]為效率矩陣的目標函數值:z=bijxijmmi=1j=1i=1j=1mm∵
bij=aij-ui-vj∴z=(aij-ui-vj)xij=aijxij-uixij-vjxij
=z0-uixij-
vjxijmmmmmmmmmm=z0-ui-vj=z0-constantmmi=1j=1i=1j=1i=1j=1i=1j=1i=1j=1j=1i=1i=1j=1mm三、步驟⑴使每行、每列都出現0元素方法:每行減該行最小元素;2109715414813141611415139-2-4-11-4min0875110104235001195min-0-0-5-0082511054230001145-2-2 -2+2+2080311032450001123每列減該列最小元素。⑵尋找位于不同行不同列的0元素準則:A)從第一行開始,若只有一個0,則記(0),同時作直線覆蓋該列的元素。否則,轉下行;B)從第一列開始,若只有一個0,則記(0),同時作直線覆蓋該行的元素。否則,轉下列;C)重復A)、B),至再找不出這樣的0元素,轉D)D)可能出現三種情況: ①每行均有(0)元素,則在有(0)位置構成最優解中xij=1; ②多于兩行和兩列存在未被直線覆蓋的0元素,即存在0元素的閉回路,則沿回路頂點每間隔一個0記(),同時作直線覆蓋該列的元素;③所有0元素均有直線覆蓋,但記(0)的個數<m個,轉⑶。000000⑶迭代,尋找新的位于不同行不同列的0元素a)從未被直線覆蓋的元素中找出一個最小的元素amin; b)對行,若無直線覆蓋,則-amin;
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024-2025學年高中物理 第二章 機械波 2 波速與波長、頻率的關系教學設計3 教科版選修3-4
- 7.2 運動的快慢 速度(教學設計)-2024-2025滬粵版物理八年級下冊
- 遠東宏信租賃鑄劍培訓
- 九年級英語下冊 Unit 1 Asia Integrated skill and Study skills教學設計 (新版)牛津版
- 2024-2025學年高中歷史 第五單元 第2課 拿破侖帝國的建立與封建制度的復辟教學設計1 新人教版選修2
- 七年級地理下冊 第八章 第四節 澳大利亞教學設計 (新版)新人教版
- 2019商務星球版七年級下冊地理6.1《世界第一大洲》教學設計
- Unit 2 Know your body 第3課時(教學設計)-2024-2025學年外研版(三起)(2024)英語三年級下冊
- 月嫂上崗技巧培訓課件
- 2023八年級英語下冊 Module 2 Experiences Unit 2 They have seen the Pyramids第三課時教學設計 (新版)外研版
- 河南鄭州大學第二附屬醫院招聘筆試真題2024
- 《中國腦卒中防治報告(2023)》
- 吉林省吉林市2024-2025學年高三下學期3月三模試題 政治 含答案
- 五下語文期中復習知識點
- 浙江省溫州市2025屆高三下學3月二模試題 英語 南瓜雕刻比賽故事續寫 講義
- 縣人民醫院開展產前篩查技術服務可行性研究報告
- 中央2025年中國日報社及所屬事業單位招聘國內高校應屆生筆試歷年參考題庫附帶答案詳解
- 小紅書運營:小紅書賬號運營培訓課件
- 2022年陜西省普通高校職業教育單獨招生統一考試英語試題及答案
- 大健康特色產業園項目商業計劃書
- 2025年上半年上海青浦新城發展(集團)限公司自主招聘9名易考易錯模擬試題(共500題)試卷后附參考答案
評論
0/150
提交評論