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

3、需求20151050第第3年資金需求年資金需求20201040第第4年資金需求年資金需求15541035工廠擴(kuò)建方案如果通過，工廠擴(kuò)建方案如果通過，P=1； 如果否決，如果否決，P取取0。倉庫擴(kuò)建方案如果通過，倉庫擴(kuò)建方案如果通過，W=1； 如果否決，如果否決，W取取0。機(jī)器更新方案如果通過，機(jī)器更新方案如果通過，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利潤(rùn)（美元利潤(rùn)（美元/噸）噸）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è)計(jì)分布系統(tǒng)設(shè)計(jì) 目標(biāo)工廠目標(biāo)工廠年固定成本年固定成本（美元）（美元）年生產(chǎn)能力年生產(chǎn)能力（件）（件）底特律底特萊多托萊多30000020000丹佛丹佛37500030000堪薩斯城堪薩斯城50000040000分銷中心分銷中心年需求量（件）年需求量（

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

7、42435152531234111213121222323132333414243451525311213min523434975104284317530037550010020030040030zxxxxxxxxxxxxxxxyyyyxxxyxxxyxxxyxxxyxxxxxx141511222324252132333435312343020200;,0,1ijxxxxxxxxxxxxxy yyy7.3.4 銀行選址銀行選址 俄亥俄州信托公司的擴(kuò)展區(qū)俄亥俄州信托公司的擴(kuò)展區(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北海岸銀行打算為其全職出納和兼職出納制定一個(gè)有效的工作北海岸銀行打算為其全職出納和兼職出納制定一個(gè)有效的工作時(shí)間表。時(shí)間表須能讓銀行有效運(yùn)作，該銀行周五營業(yè)時(shí)間為時(shí)間表。時(shí)間表須能讓銀行有效運(yùn)作，該銀行周五營業(yè)時(shí)間為上午上午9：00到下午到下午7：00。下表是。下表是 周五各時(shí)間段內(nèi)為提供足夠周五各時(shí)間段內(nèi)為提供足夠的客戶服務(wù)所需的出納員的數(shù)量。的客戶服務(wù)所

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

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