excel建模整数规划学习教案

1、会计学1excel建模整数建模整数(zhngsh)规划规划第一页，共61页。第1页/共61页第二页，共61页。第2页/共61页第三页，共61页。一般整数规划分类0-1规划0-1决策变量固定成本问题整数规划 0-1规划辅助0-1变量 产品互斥问题两个约束中选一个约束问题应用举例第3页/共61页第四页，共61页。第4页/共61页第五页，共61页。小型飞机小型飞机大型飞机大型飞机可获得的总资金可获得的总资金每架飞机年利润每架飞机年利润100100万元万元500500万元万元1 1亿元亿元每架飞机采购成本每架飞机采购成本500500万元万元50005000万元万元最多购买数量最多购买数量2 2没有限制

2、没有限制第5页/共61页第六页，共61页。1212112Max z5550100s.t.2,0 xxxxxx x且为整数第6页/共61页第七页，共61页。Excel“Excel“规划求解规划求解”工具求解整数规工具求解整数规划问题采用分支定界法。划问题采用分支定界法。第7页/共61页第八页，共61页。第8页/共61页第九页，共61页。x xng)ng)第9页/共61页第十页，共61页。第10页/共61页第十一页，共61页。净现值（万元）净现值（万元）所需资金（万元）所需资金（万元）在长春设立分公司在长春设立分公司800800600600在武汉设立分公司在武汉设立分公司500500300300在

3、长春建配送中心在长春建配送中心600600500500在武汉建配送中心在武汉建配送中心400400200200第11页/共61页第十二页，共61页。是非决策问题是非决策问题决策变量决策变量可能取值可能取值在长春设立分公司？在长春设立分公司？x10 0或或1 1在武汉设立分公司？在武汉设立分公司？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页。可用资金可用资金（万元）（万元）实际使用实际使用（万元）（万元）建配送中心建配送中心? ?设立分公司设立分公司? ?总的净现值总的净现值（万元）（万元）长春长春武汉武汉长春长春武汉武汉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且为整数0第21页/共61页第二十二页，共61页。第22页/共61页第二十三页，共61页。12()nyyyk kn (1, 2,)i

7、ixM yin第23页/共61页第二十四页，共61页。n 决策变量：设决策变量：设x1x1、x2x2分别为门分别为门和窗的每周产量。和窗的每周产量。n 辅助辅助0-10-1变量：设变量：设y1y1、y2y2分别表分别表示是否生产示是否生产(shngchn)(shngchn)门和窗，门和窗，取取0 0值时表示不生产值时表示不生产(shngchn)(shngchn)，取取1 1值时表示生产值时表示生产(shngchn)(shngchn)。第24页/共61页第二十五页，共61页。品互斥）品互斥）n产量产量(chnling)(chnling)xixi非负、是否非负、是否生产生产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页。车间车间单位产品的生产时间（小时）单位产品的生产时间（小时）每周可获得的生产时间每周可获得的生产时间（小时）（小时）门门窗窗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第 个约束成立第 个约束不成立， 1，1121121222121, ,nnNnNNNiifxxxdMyfxxxdMyfxxxdMyyNK第33页/共61页第三十四页，共61页。约束约束2

10、 2：两个工厂中必须选出一个：两个工厂中必须选出一个专门生产新产品。专门生产新产品。两个工厂中各种产品的单位生产两个工厂中各种产品的单位生产成本是相同的，但是，由于生产成本是相同的，但是，由于生产设备的不同设备的不同(b tn(b tn) )，每单位，每单位产品所需要的生产时间是不同产品所需要的生产时间是不同(b tn(b tn) )的。的。第34页/共61页第三十五页，共61页。工厂工厂单位产品的生产时间（小时）单位产品的生产时间（小时）每周可获得的每周可获得的生产时间（小时）生产时间（小时）产品产品1 1产品产品2 2产品产品3 31 13 34 42 230302 24 46 62 24

11、040单位利润（千元）单位利润（千元）5 57 73 3每周可销售量每周可销售量7 75 59 9第35页/共61页第三十六页，共61页。新产品新产品i i，yi=1yi=1表示生产，表示生产，yi=0yi=0表表示不生产（示不生产（i=1,2,3i=1,2,3）。）。 辅助辅助0-10-1变量：设变量：设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页。广告分配给三种产品，从而能获得广告分配给三种产品，从而能获得最大的利润。最大的利润。电视广告片数电视广告片数利润（百万元）利润（百万元）产品产品1 1产品产品2 2产品产品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页。快递地点快递地点可行的路线可行的路线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、时间时间( (小时小时) )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中东地区 120炼油厂：生产石油产品新奥尔良 100查尔斯顿 60西雅图 80新的炼油厂新的炼油厂 120配送中心：匹兹堡 100亚特兰大 80堪萨斯城 80旧金山 100备选备选(bi xun)炼油厂地址：炼油厂地址：洛杉矶洛杉矶加尔维斯敦加尔维斯敦圣路易斯圣路易斯第49页/共61页第五十页，共61页。第50页/共61页第五十一页，共61页。地点地点每年的运营成本（百万美元）每年的运营成本（百万美元）洛杉矶洛杉矶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中东地区中东地区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页。地点地点运输原油的总成运输原油的总成本（百万美元）本（百万美元）运输石油制品运输石油制品的总成本的总成本（十亿美元）（十亿美元）新炼油厂新炼油厂的运营成本的运营成本( (百万美元百万美元) )总变动成总变动成本本( (十亿美元十亿美元) )洛杉机洛杉机8808801.571.576206203.073.07加尔维斯敦加尔维斯敦9209201.631.635705703.123.12圣路易斯圣路易斯9609601.431.435305302.922.92最终选择最终选择(xunz)了在圣路易斯建造新的炼油厂了在圣路易斯建造新的炼油厂第55页/共61页第五十六页，共61页。第56页/共61页第五十七页，共61页。小区小区该小区该小区800m800m半径半径内各小区内各小区A AACEGHIB BBHIC CACGHID DDJE EAEGF FFJKG GACEGH HABCHII IABCHIJ JDFJKLK KFJKLL LJKL第57页/共61页第五十八页，共61页。