[管理學(xué)]ie10_or12ch3運輸問題4andch4整數(shù)規(guī)劃-展示頁
2025-02-28 11:13本頁面
【正文】 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 )。 整數(shù)規(guī)劃的可行域是松弛問題的可行域，反之不成立。 解： 設(shè) x1 、 x2分別為甲、乙兩種貨物托運的件數(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ī)劃問題的數(shù)學(xué)模型及解的特點 整數(shù)線性規(guī)劃問題的一般形式 m a x ( m i n ) z c x c x c xn n? ? ? ?1 1 2 2 ???????????????????????mnmnmmnnnnbxaxaxabxaxaxabxaxaxats).().().(..22112222212111212111??????中部分或全部取整數(shù)nxxx , 11 ?例 1. 某公司擬用集裝箱托運甲、乙兩種貨物，這兩種貨物每件的體積、重量、可獲利潤以及托運所受限制如表所示。 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運價如下表： 解： 把此轉(zhuǎn)運問題轉(zhuǎn)化為一般運輸問題： 把所有產(chǎn)地、銷地、轉(zhuǎn)運站都同時看作產(chǎn)地和銷地； 運輸表中不可能方案的運費取作 M，自身對自身的運費為 0； Ai： 產(chǎn)量為 20+原產(chǎn)量， 銷量為 20； Ti ： 產(chǎn)量、銷量均為 20； Bi： 產(chǎn)量為 20， 銷量為 20 +原銷量，其中 20為各點可能變化的最大流量； 對于最優(yōu)方案，其中 xi i 為自身對自身的運量，實際上不進(jìn)行運作。假設(shè)質(zhì)量相同，有關(guān)數(shù)據(jù)如下表： 試求總費用為最少的調(diào)運方案。 指派問題 ? 167。 分支定界法 ? 167。第 1頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強 運籌學(xué) 第 12講 目 錄 轉(zhuǎn)運問題 (補充證明 ) CH4 整數(shù)規(guī)劃 ? 167。 ? 167。 01整數(shù)規(guī)劃 ? 167。 應(yīng)用舉例 第 2頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強 運籌學(xué) ?“ 轉(zhuǎn)運問題 ” 證明 第 3頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強 運籌學(xué) 例 某公司有 A A A3三個分廠生
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1