[管理學(xué)]ie10_or12ch3運(yùn)輸問題4andch4整數(shù)規(guī)劃-wenkub
2023-03-06 11:13:14 本頁面
【正文】 ? 167。 指派問題 ? 167。 B 1 B 2 B 3 B 4 產(chǎn)量A 1 3 1 1 3 10 7A 2 1 9 2 8 4A 3 7 4 10 5 9銷量 3 6 5 6 和 = 2 0運(yùn)價(jià)如下表： 解： 把此轉(zhuǎn)運(yùn)問題轉(zhuǎn)化為一般運(yùn)輸問題： 把所有產(chǎn)地、銷地、轉(zhuǎn)運(yùn)站都同時看作產(chǎn)地和銷地； 運(yùn)輸表中不可能方案的運(yùn)費(fèi)取作 M，自身對自身的運(yùn)費(fèi)為 0； Ai： 產(chǎn)量為 20+原產(chǎn)量， 銷量為 20； Ti ： 產(chǎn)量、銷量均為 20； Bi： 產(chǎn)量為 20， 銷量為 20 +原銷量，其中 20為各點(diǎn)可能變化的最大流量； 對于最優(yōu)方案，其中 xi i 為自身對自身的運(yùn)量，實(shí)際上不進(jìn)行運(yùn)作。 解： 設(shè) x1 、 x2分別為甲、乙兩種貨物托運(yùn)的件數(shù)，建立模型 目標(biāo)函數(shù)： Max z = 2x1 +3 x2 約束條件： 195 x1 + 273 x2 ≤1365 4 x1 + 40 x2 ≤140 x1 ≤4 x1， x2 ≥ 0 為整數(shù)。 分支定界法 混合整數(shù)規(guī)劃的求解 分枝定界方法 分枝： 當(dāng) 不符合整數(shù)要求時，構(gòu)造兩個約束條件： ii bx ?? ? ? ? 1 ??? iiii bxbx 和加入松弛問題分別形成兩個子問題（分枝） 定界： 當(dāng)子問題獲得整數(shù)規(guī)劃的一個可行解，則它的目標(biāo)函數(shù)值就構(gòu)成一個界限 例 1 ?????????????????取整數(shù)2121212121, 0,3121451149x ..xz m axxxxxxxxtsx1 3 2 X 2 5 4 X 1 2 3 1 )310,23(AS 解 S得： 941 310,23 : 21???zxxA29/6 1 3 2 X 2 5 4 X 1 2 3 1 )310,23(AS2 對 S分枝： 構(gòu)造約束： 21 ?x和 11 ?x形成分枝問題 S1和 S2，得解 B和 C S1 )37,1(C )923,2(B941923 )。( 3 , 1 : ?zES122 )2,2(F4)。 第 30頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計(jì)系 石宇強(qiáng) 運(yùn)籌學(xué) 序號 1 2 3 4 5 6 7 物品 食品 氧氣 冰鎬 繩索 帳篷 相機(jī) 設(shè)備 重量 5 5 2 6 12 2 4 重要系數(shù) 20 15 18 14 8 4 10 第 31頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計(jì)系 石宇強(qiáng) 運(yùn)籌學(xué) 解： 如果令 xi=1表示登山隊(duì)員攜帶物品 i， xi=0表示登山隊(duì)員不攜帶物品 i，則問題表示成 01規(guī)劃 : Max Z= 20x1+15x2 +18x3 +14x4 +8x5 +4x6 +10x7 . 5x1 + 5x2 +2x3 +6x4 +12x5 +2x6 +4x7 ?25 xi=1或 xi=0 i=1,2,… .7 第 32頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計(jì)系 石宇強(qiáng) 運(yùn)籌學(xué) 背包問題 ( Knapsack Problem) 一個旅行者 ,為了準(zhǔn)備旅行的必須用品 ,要在背包內(nèi)裝一些最有用的東西 ,但有個限制 ,最多只能裝 b公斤的物品 ,而每件物品只能整個攜帶 ,這樣旅行者給每
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1