[管理學(xué)]ie10_or12ch3運輸問題4andch4整數(shù)規(guī)劃-文庫吧在線文庫
【正文】 01整數(shù)規(guī)劃 變量只能取 0或 1的整數(shù)線性規(guī)劃 第 27頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強 運籌學(xué) 01規(guī)劃的應(yīng)用 資金需求 ( 1000 $) 項 目 估計現(xiàn)值 第一年 第二年 第三年 第四年 工廠擴建 90 15 20 20 15 銷售網(wǎng)點擴建 40 10 15 20 5 新生產(chǎn)流水線 10 10 0 0 4 新產(chǎn)品研究 37 15 10 10 10 可用資金 40 50 40 35 ?例 1 項目投資預(yù)算 第 28頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強 運籌學(xué) 模型 變量假設(shè) : ????項目沒有選中如果第選中目項第果如iix i 0 1ma x z= 90 x 1 + 40 x 2 + 10 x 3 + 37 x 4. 15 x 1 + 10 x 2 + 10 x 3 + 15 x 4 ≤ 4020 x 1 + 15 x 2 + 1 0 x 4 ≤ 5020 x 1 + 20 x 2 + 1 0 x 4 ≤ 4015 x 1 + 5 x 2 + 4 x 3 + 10 x 4 ≤ 35x 1 , x 2 , x 3 , x 4 , = 0, 1模型 : 第 29頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強 運籌學(xué) 例 2： 一登山隊員做登山準備，他需要攜帶的物品有：食品，氧氣，冰鎬，繩索，帳篷，照相機和通訊設(shè)備，每種物品的重要性系數(shù)和重量如下：假定登山隊員可攜帶最大重量為 25公斤。 第 10頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強 運籌學(xué) 167。 假設(shè)： ，可以從其中幾個產(chǎn)地集中一起運； ，再轉(zhuǎn)運給其他銷地； ，還有幾個中轉(zhuǎn)站，在產(chǎn)地之間、銷地之間或在產(chǎn)地與銷地之間轉(zhuǎn)運。第 1頁 西南科技大學(xué)制造科學(xué)與工程學(xué)院工業(yè)工程與設(shè)計系 石宇強 運籌學(xué) 第 12講 目 錄 轉(zhuǎn)運問題 (補充證明 ) CH4 整數(shù)規(guī)劃 ? 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運價如下表： 解： 把此轉(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 為自身對自身的運量，實際上不進行運作。 分支定界法 混合整數(shù)規(guī)劃的求解 分枝定界方法 分枝： 當(dāng) 不符合整數(shù)要求時，構(gòu)造兩個約束條件： ii bx ?? ? ? ? 1 ??? iiii bxbx 和加入松弛問題分別形成兩個子問題（分枝） 定界： 當(dāng)子問題獲得整數(shù)規(guī)劃的一個可行解，則它的目標函數(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
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1