版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
第12講目錄轉(zhuǎn)運(yùn)問(wèn)題(補(bǔ)充證明)CH4整數(shù)規(guī)劃§4.1整數(shù)規(guī)劃問(wèn)題的數(shù)學(xué)模型及解的特點(diǎn)§4.2分支定界法
(第二章習(xí)題講解)§4.30-1整數(shù)規(guī)劃§4.4指派問(wèn)題§4.5應(yīng)用舉例“轉(zhuǎn)運(yùn)問(wèn)題”證明例2、某公司有A1、A2、A3三個(gè)分廠生產(chǎn)某種物資,分別供應(yīng)B1、B2、B3、B4四個(gè)地區(qū)的銷售公司銷售。假設(shè)質(zhì)量相同,有關(guān)數(shù)據(jù)如下表:
試求總費(fèi)用為最少的調(diào)運(yùn)方案。假設(shè):
1.每個(gè)分廠的物資不一定直接發(fā)運(yùn)到銷地,可以從其中幾個(gè)產(chǎn)地集中一起運(yùn);
2.運(yùn)往各銷地的物資可以先運(yùn)給其中幾個(gè)銷地,再轉(zhuǎn)運(yùn)給其他銷地;
3.除產(chǎn)銷地之外,還有幾個(gè)中轉(zhuǎn)站,在產(chǎn)地之間、銷地之間或在產(chǎn)地與銷地之間轉(zhuǎn)運(yùn)。運(yùn)價(jià)如下表:解:把此轉(zhuǎn)運(yùn)問(wèn)題轉(zhuǎn)化為一般運(yùn)輸問(wèn)題:
1、把所有產(chǎn)地、銷地、轉(zhuǎn)運(yùn)站都同時(shí)看作產(chǎn)地和銷地;
2、運(yùn)輸表中不可能方案的運(yùn)費(fèi)取作M,自身對(duì)自身的運(yùn)費(fèi)為0;
3、Ai:產(chǎn)量為20+原產(chǎn)量,銷量為20;Ti
:產(chǎn)量、銷量均為20;Bi:產(chǎn)量為20,銷量為20+原銷量,其中20為各點(diǎn)可能變化的最大流量;
4、對(duì)于最優(yōu)方案,其中xii
為自身對(duì)自身的運(yùn)量,實(shí)際上不進(jìn)行運(yùn)作。擴(kuò)大的運(yùn)輸問(wèn)題產(chǎn)銷平衡與運(yùn)價(jià)表:§4.1整數(shù)規(guī)劃問(wèn)題的數(shù)學(xué)模型及解的特點(diǎn)
整數(shù)線性規(guī)劃問(wèn)題的一般形式例1.某公司擬用集裝箱托運(yùn)甲、乙兩種貨物,這兩種貨物每件的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如表所示。甲種貨物至多托運(yùn)4件,問(wèn)兩種貨物各托運(yùn)多少件,可使獲得利潤(rùn)最大。解:設(shè)x1、
x2分別為甲、乙兩種貨物托運(yùn)的件數(shù),建立模型目標(biāo)函數(shù):Maxz=2x1+3x2
約束條件:
195
x1+273x2≤13654
x1+40x2≤140
x1≤4x1,x2≥0為整數(shù)。貨物每件體積(立方英尺)每件重量(百千克)每件利潤(rùn)(百元)甲乙19527344023托運(yùn)限制1365140
整數(shù)線性規(guī)劃問(wèn)題的分類全整數(shù)線性規(guī)劃混合整數(shù)線性規(guī)劃0-1整數(shù)線性規(guī)劃整數(shù)規(guī)劃與其松弛問(wèn)題當(dāng)放棄整數(shù)約束時(shí)得到的線性規(guī)劃稱為整數(shù)規(guī)劃的松弛問(wèn)題。整數(shù)規(guī)劃的可行域是松弛問(wèn)題的可行域,反之不成立。§4.2分支定界法混合整數(shù)規(guī)劃的求解---分枝定界方法分枝:當(dāng)不符合整數(shù)要求時(shí),構(gòu)造兩個(gè)約束條件:加入松弛問(wèn)題分別形成兩個(gè)子問(wèn)題(分枝)定界:當(dāng)子問(wèn)題獲得整數(shù)規(guī)劃的一個(gè)可行解,則它的目標(biāo)函數(shù)值就構(gòu)成一個(gè)界限例1132X254X1
231S解S得:29/6132X254X1
231S2對(duì)S分枝:構(gòu)造約束:和形成分枝問(wèn)題S1和S2,得解B和CS1SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9132X254X1
231S2對(duì)S1分枝:構(gòu)造約束:和形成分枝問(wèn)題S11和S12,得解DS12S11無(wú)可行解SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11無(wú)可行解S12D:x1=33/14,x2=2Z=61/14132X254X1
231S2對(duì)S12分枝:構(gòu)造約束:和形成分枝問(wèn)題S121和S122,得解E和FS121S122SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11無(wú)可行解S12D:x1=33/14,x2=2Z=61/14S122F:x1=2,x2=2Z=4S121E:x1=3,x2=1Z=4例2用分枝定界法求解:MaxZ=4x1+3x2s.t.
3x1+4x2124x1+2x29x1,x20整數(shù)用單純形法可解得相應(yīng)的松馳問(wèn)題的最優(yōu)解(6/5,21/10)Z=111/10為各分枝的上界。012344321x1x2分枝:X11,x12P1P2兩個(gè)子問(wèn)題:(P1)MaxZ=4x1+3x2s.t.
3x1+4x2124x1+2x29x1,x20,x1
1
,整數(shù)用單純形法可解得相應(yīng)的(P1)的最優(yōu)解(1,9/4)Z=43/4(P2)MaxZ=4x1+3x2s.t.
3x1+4x2124x1+2x29x1,x20,x1
2
,整數(shù)用單純形法可解得相應(yīng)的(P2)的最優(yōu)解(2,1/2)Z=19/2012344321x1x2再對(duì)(P1)分枝:X11(P3)x22(P4)x23P1P2P3P4(P1)兩個(gè)子問(wèn)題:(P3)MaxZ=4x1+3x2s.t.
3x1+4x2124x1+2x29x1,x20,x1
1,x22整數(shù)用單純形法可解得相應(yīng)的(P3)的最優(yōu)解(1,2)Z=10(P1)兩個(gè)子問(wèn)題:(P4)MaxZ=4x1+3x2s.t.
3x1+4x2124x1+2x29x1,x20,x1
1,x23整數(shù)用單純形法可解得相應(yīng)的(P4)的最優(yōu)解(0,3)Z=9X12X2
2X11X23P1:(1,9/4)Z=43/4P4:(0,3)Z=9P2:(2,1/2)Z=19/2P3:(1,2)Z=10P:(6/5,21/10)Z=111/10原問(wèn)題的最優(yōu)解(1,2)Z=10第二章習(xí)題講解(由助教完成)§4.30-1整數(shù)規(guī)劃
1、0-1整數(shù)規(guī)劃變量只能取0或1的整數(shù)線性規(guī)劃2、0-1規(guī)劃的應(yīng)用例1項(xiàng)目投資預(yù)算模型變量假設(shè):模型:例2:一登山隊(duì)員做登山準(zhǔn)備,他需要攜帶的物品有:食品,氧氣,冰鎬,繩索,帳篷,照相機(jī)和通訊設(shè)備,每種物品的重要性系數(shù)和重量如下:假定登山隊(duì)員可攜帶最大重量為25公斤。序號(hào)1234567物品食品氧氣冰鎬繩索帳篷相機(jī)設(shè)備重量55261224重要系數(shù)201518148410解:如果令xi=1表示登山隊(duì)員攜帶物品i,xi=0表示登山隊(duì)員不攜帶物品i,則問(wèn)題表示成0-1規(guī)劃:MaxZ=20x1+15x2+18x3+14x4
+8x5+4x6+10x7s.t.5x1+5x2+2x3+6x4+12x5+2x6+4x725xi=1或xi=0i=1,2,….7背包問(wèn)題(KnapsackProblem)一個(gè)旅行者,為了準(zhǔn)備旅行的必須用品,要在背包內(nèi)裝一些最有用的東西,但有個(gè)限制,最多只能裝b公斤的物品,而每件物品只能整個(gè)攜帶,這樣旅行者給每件物品規(guī)定了一個(gè)“價(jià)值”以表示其有用的程度,如果共有n件物品,第j件物品aj公斤,其價(jià)值為cj.問(wèn)題變成:在攜帶的物品總重量不超過(guò)b公斤條件下,攜帶哪些物品,可使總價(jià)值最大?解:如果令xj=1表示攜帶物品j,xj=0表示不攜帶物品j,則問(wèn)題表示成0-1規(guī)劃:MaxZ=Σcjxjs.t.Σajxjb
xj=0或1例3工廠-銷售點(diǎn)配置問(wèn)題生產(chǎn)廠顧客需求銷售點(diǎn)45DCBA7IIIII213I工廠-銷售點(diǎn)配置問(wèn)題-問(wèn)題描述問(wèn)題:為使經(jīng)營(yíng)成本最低,應(yīng)開設(shè)那些工廠及銷售點(diǎn)?工廠-銷售點(diǎn)配置問(wèn)題-模型參數(shù)工廠-銷售點(diǎn)配置問(wèn)題-模型
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024-2025學(xué)年年七年級(jí)數(shù)學(xué)人教版下冊(cè)專題整合復(fù)習(xí)卷27.3 位似(1)(含答案)-
- 研發(fā)團(tuán)隊(duì)有效管理培訓(xùn)
- 幼兒音樂(lè)教育活動(dòng)的策劃計(jì)劃
- 壬二酸行業(yè)相關(guān)投資計(jì)劃提議
- 自然觀察小班孩子的環(huán)境教育計(jì)劃
- 會(huì)計(jì)、審計(jì)及稅務(wù)服務(wù)相關(guān)行業(yè)投資方案范本
- 制定企業(yè)社會(huì)責(zé)任與人事發(fā)展結(jié)合的計(jì)劃
- 班級(jí)成員角色的明確計(jì)劃
- 社區(qū)小型創(chuàng)業(yè)支持的工作方案計(jì)劃
- 教育管理制度培訓(xùn)
- 美團(tuán)合作協(xié)議書范本(2024版)
- 第21課《小圣施威降大圣》課件 2024-2025學(xué)年統(tǒng)編版語(yǔ)文七年級(jí)上冊(cè)
- AQ/T 2061-2018 金屬非金屬地下礦山防治水安全技術(shù)規(guī)范(正式版)
- 天津市部分區(qū)2022-2023學(xué)年七年級(jí)上學(xué)期期末練習(xí)生物試題
- 小學(xué)三年級(jí)-安全知識(shí)考試試題-(附答案)-
- 醫(yī)院門診醫(yī)生績(jī)效考核標(biāo)準(zhǔn)及評(píng)分細(xì)則
- MOOC 體育保健學(xué)-江西財(cái)經(jīng)大學(xué) 中國(guó)大學(xué)慕課答案
- 廣東省深圳市羅湖區(qū)2022-2023學(xué)年二年級(jí)上學(xué)期數(shù)學(xué)期中復(fù)習(xí)試卷
- 康復(fù)科護(hù)理工作總結(jié)及計(jì)劃
- 基于VMI的庫(kù)存管理
- 建筑工程鋼結(jié)構(gòu)焊接變形的控制措施
評(píng)論
0/150
提交評(píng)論