1、會(huì)計(jì)學(xué)1excel建模整數(shù)建模整數(shù)(zhngsh)規(guī)劃規(guī)劃第一頁，共61頁。第1頁/共61頁第二頁，共61頁。第2頁/共61頁第三頁，共61頁。一般整數(shù)規(guī)劃分類0-1規(guī)劃0-1決策變量固定成本問題整數(shù)規(guī)劃 0-1規(guī)劃輔助0-1變量 產(chǎn)品互斥問題兩個(gè)約束中選一個(gè)約束問題應(yīng)用舉例第3頁/共61頁第四頁，共61頁。第4頁/共61頁第五頁，共61頁。小型飛機(jī)小型飛機(jī)大型飛機(jī)大型飛機(jī)可獲得的總資金可獲得的總資金每架飛機(jī)年利潤每架飛機(jī)年利潤100100萬元萬元500500萬元萬元1 1億元億元每架飛機(jī)采購成本每架飛機(jī)采購成本500500萬元萬元50005000萬元萬元最多購買數(shù)量最多購買數(shù)量2 2沒有限制

2、沒有限制第5頁/共61頁第六頁，共61頁。1212112Max z5550100s.t.2,0 xxxxxx x且為整數(shù)第6頁/共61頁第七頁，共61頁。Excel“Excel“規(guī)劃求解規(guī)劃求解”工具求解整數(shù)規(guī)工具求解整數(shù)規(guī)劃問題采用分支定界法。劃問題采用分支定界法。第7頁/共61頁第八頁，共61頁。第8頁/共61頁第九頁，共61頁。x xng)ng)第9頁/共61頁第十頁，共61頁。第10頁/共61頁第十一頁，共61頁。凈現(xiàn)值（萬元）凈現(xiàn)值（萬元）所需資金（萬元）所需資金（萬元）在長春設(shè)立分公司在長春設(shè)立分公司800800600600在武漢設(shè)立分公司在武漢設(shè)立分公司500500300300在

3、長春建配送中心在長春建配送中心600600500500在武漢建配送中心在武漢建配送中心400400200200第11頁/共61頁第十二頁，共61頁。是非決策問題是非決策問題決策變量決策變量可能取值可能取值在長春設(shè)立分公司？在長春設(shè)立分公司？x10 0或或1 1在武漢設(shè)立分公司？在武漢設(shè)立分公司？x20 0或或1 1在長春建配送中心？在長春建配送中心？x30 0或或1 1在武漢建配送中心？在武漢建配送中心？x40 0或或1 1第12頁/共61頁第十三頁，共61頁。123412343431421234Max z=800 +500+600 +400600 +300+500 +2001000+1s.

4、t. ,0,1xxxxxxxxxxxxxxx x x x第13頁/共61頁第十四頁，共61頁。第14頁/共61頁第十五頁，共61頁。可用資金可用資金（萬元）（萬元）實(shí)際使用實(shí)際使用（萬元）（萬元）建配送中心建配送中心? ?設(shè)立分公司設(shè)立分公司? ?總的凈現(xiàn)值總的凈現(xiàn)值（萬元）（萬元）長春長春武漢武漢長春長春武漢武漢7007005005000 01 10 01 19009008008005005000 01 10 01 19009009009009009000 00 01 11 113001300100010009009000 00 01 11 1130013001100110011001100

5、0 01 11 11 11700170012001200110011000 01 11 11 11700170013001300110011000 01 11 11 11700170014001400140014001 10 01 11 11900190015001500140014001 10 01 11 119001900第15頁/共61頁第十六頁，共61頁。第16頁/共61頁第十七頁，共61頁。0( )00iiiiiiikc xxf xx若若 第17頁/共61頁第十八頁，共61頁。1122Minz()()()s.t. nnf xfxfx給定的線性約束條件1 00 0iiixyx若若1M

6、in() s.t. (1, 2 ,)0 ,1 (1, 2 ,)niiiiiiiizk yc xxM yinyin最 初 給 定 的 線 性 約 束 條 件第18頁/共61頁第十九頁，共61頁。第19頁/共61頁第二十頁，共61頁。1212Max z=3005007001300 xxyy第20頁/共61頁第二十一頁，共61頁。1212121211221212M ax z=300500700130042123218s.t.,0,1xxyyxxxxxMyxMyx xyy且為整數(shù)0第21頁/共61頁第二十二頁，共61頁。第22頁/共61頁第二十三頁，共61頁。12()nyyyk kn (1, 2,)i

7、ixM yin第23頁/共61頁第二十四頁，共61頁。n 決策變量：設(shè)決策變量：設(shè)x1x1、x2x2分別為門分別為門和窗的每周產(chǎn)量。和窗的每周產(chǎn)量。n 輔助輔助0-10-1變量：設(shè)變量：設(shè)y1y1、y2y2分別表分別表示是否生產(chǎn)示是否生產(chǎn)(shngchn)(shngchn)門和窗，門和窗，取取0 0值時(shí)表示不生產(chǎn)值時(shí)表示不生產(chǎn)(shngchn)(shngchn)，取取1 1值時(shí)表示生產(chǎn)值時(shí)表示生產(chǎn)(shngchn)(shngchn)。第24頁/共61頁第二十五頁，共61頁。品互斥）品互斥）n產(chǎn)量產(chǎn)量(chnling)(chnling)xixi非負(fù)、是否非負(fù)、是否生產(chǎn)生產(chǎn)yiyi為為0-10-1

8、變變量量1212121211221212M ax z= 300500421232181s.t., ,0 1xxxxxxyyxM yxM yxxyy0,第25頁/共61頁第二十六頁，共61頁。第26頁/共61頁第二十七頁，共61頁。120 1 y選 擇 約 束 條 件選 擇 約 束 條 件，第27頁/共61頁第二十八頁，共61頁。車間車間單位產(chǎn)品的生產(chǎn)時(shí)間（小時(shí)）單位產(chǎn)品的生產(chǎn)時(shí)間（小時(shí)）每周可獲得的生產(chǎn)時(shí)間每周可獲得的生產(chǎn)時(shí)間（小時(shí)）（小時(shí)）門門窗窗1 11 10 04 42 20 02 212123 33 32 218184 42 24 42828單位利潤（元）單位利潤（元）30030050

9、0500第28頁/共61頁第二十九頁，共61頁。第29頁/共61頁第三十頁，共61頁。12121212Max z=30050042123218s.t. 2428(1)1, 200,1xxxxxxMyxxMyx xy第30頁/共61頁第三十一頁，共61頁。第31頁/共61頁第三十二頁，共61頁。第32頁/共61頁第三十三頁，共61頁。1121212212, ,nnNnNfxxxdfxxxdfxxxd 0 iiiy第 個(gè)約束成立第 個(gè)約束不成立， 1，1121121222121, ,nnNnNNNiifxxxdMyfxxxdMyfxxxdMyyNK第33頁/共61頁第三十四頁，共61頁。約束約束2

10、 2：兩個(gè)工廠中必須選出一個(gè)：兩個(gè)工廠中必須選出一個(gè)專門生產(chǎn)新產(chǎn)品。專門生產(chǎn)新產(chǎn)品。兩個(gè)工廠中各種產(chǎn)品的單位生產(chǎn)兩個(gè)工廠中各種產(chǎn)品的單位生產(chǎn)成本是相同的，但是，由于生產(chǎn)成本是相同的，但是，由于生產(chǎn)設(shè)備的不同設(shè)備的不同(b tn(b tn) )，每單位，每單位產(chǎn)品所需要的生產(chǎn)時(shí)間是不同產(chǎn)品所需要的生產(chǎn)時(shí)間是不同(b tn(b tn) )的。的。第34頁/共61頁第三十五頁，共61頁。工廠工廠單位產(chǎn)品的生產(chǎn)時(shí)間（小時(shí)）單位產(chǎn)品的生產(chǎn)時(shí)間（小時(shí)）每周可獲得的每周可獲得的生產(chǎn)時(shí)間（小時(shí)）生產(chǎn)時(shí)間（小時(shí)）產(chǎn)品產(chǎn)品1 1產(chǎn)品產(chǎn)品2 2產(chǎn)品產(chǎn)品3 31 13 34 42 230302 24 46 62 24

11、040單位利潤（千元）單位利潤（千元）5 57 73 3每周可銷售量每周可銷售量7 75 59 9第35頁/共61頁第三十六頁，共61頁。新產(chǎn)品新產(chǎn)品i i，yi=1yi=1表示生產(chǎn)，表示生產(chǎn)，yi=0yi=0表表示不生產(chǎn)（示不生產(chǎn)（i=1,2,3i=1,2,3）。）。 輔助輔助0-10-1變量：設(shè)變量：設(shè)y=0y=0表示選擇表示選擇工廠工廠1 1，y=1y=1表示選擇工廠表示選擇工廠2 2。第36頁/共61頁第三十七頁，共61頁。123123112233123123123123Max z57327 , 5, 934230s.t. 46240(1),0,0, 10,1xxxyyyxyxyxyx

12、xxMyxxxMyx x xy y yy第37頁/共61頁第三十八頁，共61頁。第38頁/共61頁第三十九頁，共61頁。廣告分配給三種產(chǎn)品，從而能獲得廣告分配給三種產(chǎn)品，從而能獲得最大的利潤。最大的利潤。電視廣告片數(shù)電視廣告片數(shù)利潤（百萬元）利潤（百萬元）產(chǎn)品產(chǎn)品1 1產(chǎn)品產(chǎn)品2 2產(chǎn)品產(chǎn)品3 30 00 00 00 01 11 10 0-1-12 23 32 22 23 33 33 34 4第39頁/共61頁第四十頁，共61頁。第40頁/共61頁第四十一頁，共61頁。112131122232132333112131122232132333112131122232132333Max 33023

13、2411s.t. 1(23 ) (23) (23) 50 1 (,1,2,3)ijzxxxxxxxxxxxxxxxxxxxxxxxxxxxxi j,第41頁/共61頁第四十二頁，共61頁。第42頁/共61頁第四十三頁，共61頁。第43頁/共61頁第四十四頁，共61頁。快遞地點(diǎn)快遞地點(diǎn)可行的路線可行的路線1 12 23 34 45 56 67 78 89 91010A A1 11 11 1B B2 21 12 22 22 2C C3 33 33 33 3D D2 21 11 1E E2 22 23 3F F1 12 2G G3 31 12 23 3H H1 13 31 1I I3 34 42 2

14、時(shí)間時(shí)間( (小時(shí)小時(shí)) )6 64 47 75 54 46 65 53 37 76 6第44頁/共61頁第四十五頁，共61頁。第45頁/共61頁第四十六頁，共61頁。123456789101592469103479168346251781035102471210Min z=647546537611111s.t. 111130,1(1,2,10)ixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxi第46頁/共61頁第四十七頁，共61頁。第47頁/共61頁第四十八頁，共61頁。第48頁/共61頁第四十九頁，共61頁。油田：提供原油(百萬桶)德克薩斯 80加

15、利福尼亞 60阿拉斯加 100中東地區(qū) 120煉油廠：生產(chǎn)石油產(chǎn)品新奧爾良 100查爾斯頓 60西雅圖 80新的煉油廠新的煉油廠 120配送中心：匹茲堡 100亞特蘭大 80堪薩斯城 80舊金山 100備選備選(bi xun)煉油廠地址：煉油廠地址：洛杉磯洛杉磯加爾維斯敦加爾維斯敦圣路易斯圣路易斯第49頁/共61頁第五十頁，共61頁。第50頁/共61頁第五十一頁，共61頁。地點(diǎn)地點(diǎn)每年的運(yùn)營成本（百萬美元）每年的運(yùn)營成本（百萬美元）洛杉磯洛杉磯620620加爾維斯敦加爾維斯敦570570圣路易斯圣路易斯530530第51頁/共61頁第五十二頁，共61頁。油田油田煉油廠煉油廠新奧爾良新奧爾良查爾

16、斯頓查爾斯頓西雅圖西雅圖洛杉磯洛杉磯加爾維斯敦加爾維斯敦圣路易斯圣路易斯德克薩斯德克薩斯2 24 45 53 31 11 1加利福尼亞加利福尼亞5 55 53 31 13 34 4阿拉斯加阿拉斯加5 57 73 34 45 57 7中東地區(qū)中東地區(qū)2 23 35 54 43 34 4第52頁/共61頁第五十三頁，共61頁。煉油廠煉油廠配送中心配送中心匹茲堡匹茲堡亞特蘭大亞特蘭大堪薩斯城堪薩斯城舊金山舊金山新奧爾良新奧爾良6.56.55.55.56 68 8查爾斯頓查爾斯頓7 75 54 47 7西雅圖西雅圖7 78 84 43 3洛杉磯洛杉磯8 86 63 32 2加爾維斯敦加爾維斯敦5 54

17、 43 36 6圣路易斯圣路易斯4 43 31 15 5第53頁/共61頁第五十四頁，共61頁。第54頁/共61頁第五十五頁，共61頁。地點(diǎn)地點(diǎn)運(yùn)輸原油的總成運(yùn)輸原油的總成本（百萬美元）本（百萬美元）運(yùn)輸石油制品運(yùn)輸石油制品的總成本的總成本（十億美元）（十億美元）新煉油廠新煉油廠的運(yùn)營成本的運(yùn)營成本( (百萬美元百萬美元) )總變動(dòng)成總變動(dòng)成本本( (十億美元十億美元) )洛杉機(jī)洛杉機(jī)8808801.571.576206203.073.07加爾維斯敦加爾維斯敦9209201.631.635705703.123.12圣路易斯圣路易斯9609601.431.435305302.922.92最終選擇最終選擇(xunz)了在圣路易斯建造新的煉油廠了在圣路易斯建造新的煉油廠第55頁/共61頁第五十六頁，共61頁。第56頁/共61頁第五十七頁，共61頁。小區(qū)小區(qū)該小區(qū)該小區(qū)800m800m半徑半徑內(nèi)各小區(qū)內(nèi)各小區(qū)A AACEGHIB BBHIC CACGHID DDJE EAEGF FFJKG GACEGH HABCHII IABCHIJ JDFJKLK KFJKLL LJKL第57頁/共61頁第五十八頁，共61頁。