第7章整數(shù)線性規(guī)劃

1、第第7章章 整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃 7.1 整數(shù)線性規(guī)劃的分類整數(shù)線性規(guī)劃的分類 全整數(shù)線性規(guī)劃：所有變量均為整數(shù)。全整數(shù)線性規(guī)劃：所有變量均為整數(shù)。 混合整數(shù)線性規(guī)劃：有一些變量是整數(shù)而非全部都是?；旌险麛?shù)線性規(guī)劃：有一些變量是整數(shù)而非全部都是。 0-1整數(shù)線性規(guī)劃：整數(shù)變量只取整數(shù)線性規(guī)劃：整數(shù)變量只取0或或1。 7.2 全整數(shù)線性規(guī)劃的圖解法與計算機解法全整數(shù)線性規(guī)劃的圖解法與計算機解法 (P200)max101528240020004401405,0,zTATATATT A且為整數(shù)7.2.1 LP松弛的圖解法松弛的圖解法 7.2.2 近似整數(shù)解的獲得近似整數(shù)解的獲得T=2, A=3,

2、 z=65T=3, A=3, 不可行不可行T=2, A=4, 不可行不可行 7.2.3 全整數(shù)解的圖解法全整數(shù)解的圖解法 7.2.4 計算機解法計算機解法 7.3 含有含有0-1變量的整數(shù)線性規(guī)劃的應(yīng)用變量的整數(shù)線性規(guī)劃的應(yīng)用 7.3.1 資金預(yù)算資金預(yù)算 愛斯柯德冰箱公司的估計凈現(xiàn)值、資金需求和愛斯柯德冰箱公司的估計凈現(xiàn)值、資金需求和4年內(nèi)的可用資金年內(nèi)的可用資金 （單位：千美元）（單位：千美元） 項目項目可用可用資金資金總額總額工廠擴建工廠擴建倉庫擴建倉庫擴建機器更新機器更新新產(chǎn)品研發(fā)新產(chǎn)品研發(fā)凈現(xiàn)值凈現(xiàn)值90401037第第1年資金需求年資金需求1510101540第第2年資金需求年資金

3、需求20151050第第3年資金需求年資金需求20201040第第4年資金需求年資金需求15541035工廠擴建方案如果通過，工廠擴建方案如果通過，P=1； 如果否決，如果否決，P取取0。倉庫擴建方案如果通過，倉庫擴建方案如果通過，W=1； 如果否決，如果否決，W取取0。機器更新方案如果通過，機器更新方案如果通過，M=1； 如果否決，如果否決，M取取0。新產(chǎn)品研發(fā)方案如果通過，新產(chǎn)品研發(fā)方案如果通過，R=1； 如果否決，如果否決，R取取0。 max904010371510101540201510502020104015541035,0,1zPWMRPWMRPWRPWRPWMRP W M R7.

4、3.2 固定成本核算固定成本核算 RMC問題問題 燃料添加劑燃料添加劑溶劑溶劑地板清潔劑地板清潔劑可用噸數(shù)可用噸數(shù)原料原料 10.40.50.620原料原料20.20.15原料原料30.60.30.321利潤（美元利潤（美元/噸）噸）403050固定成本（美元）固定成本（美元）20050400最大生產(chǎn)量（噸）最大生產(chǎn)量（噸）502540F: 生產(chǎn)的燃料添加劑的噸數(shù)生產(chǎn)的燃料添加劑的噸數(shù)S: 生產(chǎn)的溶劑的噸數(shù)生產(chǎn)的溶劑的噸數(shù)C: 生產(chǎn)的地板清潔劑的噸數(shù)生產(chǎn)的地板清潔劑的噸數(shù)如果生產(chǎn)燃料添加劑，如果生產(chǎn)燃料添加劑，SF=1， 否則，否則，SF=0；如果生產(chǎn)溶劑，則如果生產(chǎn)溶劑，則 SS=1， 否則

5、，否則，SS=0；如果生產(chǎn)地板清潔劑，如果生產(chǎn)地板清潔劑，SC=1， 否則，否則，SC=0。 max403050200504000.40.50.6200.20.150.60.30.321500250400, ,0;,0,1zFSCSFSSSCFSCSCFSCFSFSSSCSCF S CSF SS SC7.3.3 分布系統(tǒng)設(shè)計分布系統(tǒng)設(shè)計 目標工廠目標工廠年固定成本年固定成本（美元）（美元）年生產(chǎn)能力年生產(chǎn)能力（件）（件）底特律底特萊多托萊多30000020000丹佛丹佛37500030000堪薩斯城堪薩斯城50000040000分銷中心分銷中心年需求量（件）年需求量（

6、件）波士頓波士頓30000亞特蘭大亞特蘭大20000休斯敦休斯敦20000馬丁貝克分布系統(tǒng)的單位運輸成本馬丁貝克分布系統(tǒng)的單位運輸成本 工廠地點工廠地點分銷中心分銷中心波士頓波士頓亞特蘭大亞特蘭大休斯敦休斯敦底特律底特律523托萊多托萊多434丹佛丹佛975堪薩斯城堪薩斯城1042圣路易斯圣路易斯84311y 10y 21y 20y 31y 30y 41y 40y 如果在底特律建廠，如果在底特律建廠，否則，否則，如果在托萊多建廠，如果在托萊多建廠，否則，否則，如果在丹佛建廠，如果在丹佛建廠，否則，否則，如果在堪薩斯城建廠，如果在堪薩斯城建廠，否則，否則，11121321222331323341

7、42435152531234111213121222323132333414243451525311213min523434975104284317530037550010020030040030zxxxxxxxxxxxxxxxyyyyxxxyxxxyxxxyxxxyxxxxxx141511222324252132333435312343020200;,0,1ijxxxxxxxxxxxxxy yyy7.3.4 銀行選址銀行選址 俄亥俄州信托公司的擴展區(qū)俄亥俄州信托公司的擴展區(qū) 考慮的郡考慮的郡臨近的郡臨近的郡考慮的郡考慮的郡臨近的郡臨近的郡1 阿什特比拉阿什特比拉2,12,1611 斯塔克斯塔

8、克8,10,13,14,15,18,19,202 萊克萊克1,3,1212 吉奧特吉奧特1,2,3,10,13,163 凱霍加凱霍加2,4,9,10,12,1313 波帝奇波帝奇3,10,11,12,15,164 洛雷恩洛雷恩3,5,7,914 哥倫比亞納哥倫比亞納11,15,205 休倫休倫4,6,715 馬霍寧馬霍寧11,13,14,166 里奇蘭里奇蘭5,7,1716 特蘭伯爾特蘭伯爾1,12,13,157 阿什蘭阿什蘭4,5,6,8,9,17,1817 諾克斯諾克斯6,7,188 韋恩韋恩7,9,10,11,1818 霍姆斯霍姆斯7,8,11,17,199 梅迪納梅迪納3,4,7,8,

9、1019 塔斯卡盧斯塔斯卡盧斯11,18,2010 薩米特薩米特3,8,9,11,12,1320 卡羅爾卡羅爾11,14,1912201212161231211141920min1110,11,2,20jzxxxxxxxxxxxxxxxxj北海岸銀行打算為其全職出納和兼職出納制定一個有效的工作北海岸銀行打算為其全職出納和兼職出納制定一個有效的工作時間表。時間表須能讓銀行有效運作，該銀行周五營業(yè)時間為時間表。時間表須能讓銀行有效運作，該銀行周五營業(yè)時間為上午上午9：00到下午到下午7：00。下表是。下表是 周五各時間段內(nèi)為提供足夠周五各時間段內(nèi)為提供足夠的客戶服務(wù)所需的出納員的數(shù)量。的客戶服務(wù)所

10、需的出納員的數(shù)量。工作時間工作時間出納員數(shù)量出納員數(shù)量工作時間工作時間出納員數(shù)量出納員數(shù)量上午上午9點點上午上午10點點上午上午10點點上午上午11點點上午上午11點點正午正午正午正午下午下午1點點下午下午1點點下午下午2點點648109下午下午2點點下午下午3點點下午下午3點點下午下午4點點下午下午4點點下午下午5點點下午下午5點點下午下午6點點下午下午6點點下午下午7點點64766 每個全職員工從整點開始連續(xù)工作每個全職員工從整點開始連續(xù)工作4小時后，是小時后，是1小時的小時的午餐時間，然后繼續(xù)工作午餐時間，然后繼續(xù)工作3小時。兼職員工從整點開始連續(xù)工小時。兼職員工從整點開始連續(xù)工作作4個

11、小時。全職員工成本每小時個小時。全職員工成本每小時15美元（每天美元（每天105美元），美元），兼職員工成本每小時兼職員工成本每小時8美元（每天美元（每天32美元）。美元）。 構(gòu)建一個整數(shù)規(guī)劃線性模型，以使用最少人力成本并滿構(gòu)建一個整數(shù)規(guī)劃線性模型，以使用最少人力成本并滿足顧客服務(wù)為目標，構(gòu)建一個可行的時間表。足顧客服務(wù)為目標，構(gòu)建一個可行的時間表。123171112121231231231234232345133456124567123567236737min105()32()64810964766,intijzxxxyyxyxxyyxxxyyyxxxyyyyxxyyyyxxyyyyxxyyyyxxxyyyxxyyxyx y第第i點鐘全職員工開始工作的人數(shù)；點鐘全職員工開始工作的人數(shù)；第第i點鐘兼職職員工開始工作的人數(shù)；點鐘兼職職員工開始工作的人數(shù)；ixiy工作時間工作時間臨時工數(shù)量臨時工數(shù)量上午上午9點點上午上午10點點上午上午10點點上午上午11點點上