第7章整数线性规划

1、第第7章章 整数线性规划整数线性规划 7.1 整数线性规划的分类整数线性规划的分类 全整数线性规划：所有变量均为整数。全整数线性规划：所有变量均为整数。 混合整数线性规划：有一些变量是整数而非全部都是。混合整数线性规划：有一些变量是整数而非全部都是。 0-1整数线性规划：整数变量只取整数线性规划：整数变量只取0或或1。 7.2 全整数线性规划的图解法与计算机解法全整数线性规划的图解法与计算机解法 (P200)max101528240020004401405,0,zTATATATT A且为整数7.2.1 LP松弛的图解法松弛的图解法 7.2.2 近似整数解的获得近似整数解的获得T=2, A=3,

2、 z=65T=3, A=3, 不可行不可行T=2, A=4, 不可行不可行 7.2.3 全整数解的图解法全整数解的图解法 7.2.4 计算机解法计算机解法 7.3 含有含有0-1变量的整数线性规划的应用变量的整数线性规划的应用 7.3.1 资金预算资金预算 爱斯柯德冰箱公司的估计净现值、资金需求和爱斯柯德冰箱公司的估计净现值、资金需求和4年内的可用资金年内的可用资金 （单位：千美元）（单位：千美元） 项目项目可用可用资金资金总额总额工厂扩建工厂扩建仓库扩建仓库扩建机器更新机器更新新产品研发新产品研发净现值净现值90401037第第1年资金需求年资金需求1510101540第第2年资金需求年资金

3、需求20151050第第3年资金需求年资金需求20201040第第4年资金需求年资金需求15541035工厂扩建方案如果通过，工厂扩建方案如果通过，P=1； 如果否决，如果否决，P取取0。仓库扩建方案如果通过，仓库扩建方案如果通过，W=1； 如果否决，如果否决，W取取0。机器更新方案如果通过，机器更新方案如果通过，M=1； 如果否决，如果否决，M取取0。新产品研发方案如果通过，新产品研发方案如果通过，R=1； 如果否决，如果否决，R取取0。 max904010371510101540201510502020104015541035,0,1zPWMRPWMRPWRPWRPWMRP W M R7.

4、3.2 固定成本核算固定成本核算 RMC问题问题 燃料添加剂燃料添加剂溶剂溶剂地板清洁剂地板清洁剂可用吨数可用吨数原料原料 10.40.50.620原料原料20.20.15原料原料30.60.30.321利润（美元利润（美元/吨）吨）403050固定成本（美元）固定成本（美元）20050400最大生产量（吨）最大生产量（吨）502540F: 生产的燃料添加剂的吨数生产的燃料添加剂的吨数S: 生产的溶剂的吨数生产的溶剂的吨数C: 生产的地板清洁剂的吨数生产的地板清洁剂的吨数如果生产燃料添加剂，如果生产燃料添加剂，SF=1， 否则，否则，SF=0；如果生产溶剂，则如果生产溶剂，则 SS=1， 否则

5、，否则，SS=0；如果生产地板清洁剂，如果生产地板清洁剂，SC=1， 否则，否则，SC=0。 max403050200504000.40.50.6200.20.150.60.30.321500250400, ,0;,0,1zFSCSFSSSCFSCSCFSCFSFSSSCSCF S CSF SS SC7.3.3 分布系统设计分布系统设计 目标工厂目标工厂年固定成本年固定成本（美元）（美元）年生产能力年生产能力（件）（件）底特律底特莱多托莱多30000020000丹佛丹佛37500030000堪萨斯城堪萨斯城50000040000分销中心分销中心年需求量（件）年需求量（

6、件）波士顿波士顿30000亚特兰大亚特兰大20000休斯敦休斯敦20000马丁贝克分布系统的单位运输成本马丁贝克分布系统的单位运输成本 工厂地点工厂地点分销中心分销中心波士顿波士顿亚特兰大亚特兰大休斯敦休斯敦底特律底特律523托莱多托莱多434丹佛丹佛975堪萨斯城堪萨斯城1042圣路易斯圣路易斯84311y 10y 21y 20y 31y 30y 41y 40y 如果在底特律建厂，如果在底特律建厂，否则，否则，如果在托莱多建厂，如果在托莱多建厂，否则，否则，如果在丹佛建厂，如果在丹佛建厂，否则，否则，如果在堪萨斯城建厂，如果在堪萨斯城建厂，否则，否则，11121321222331323341

7、42435152531234111213121222323132333414243451525311213min523434975104284317530037550010020030040030zxxxxxxxxxxxxxxxyyyyxxxyxxxyxxxyxxxyxxxxxx141511222324252132333435312343020200;,0,1ijxxxxxxxxxxxxxy yyy7.3.4 银行选址银行选址 俄亥俄州信托公司的扩展区俄亥俄州信托公司的扩展区 考虑的郡考虑的郡临近的郡临近的郡考虑的郡考虑的郡临近的郡临近的郡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北海岸银行打算为其全职出纳和兼职出纳制定一个有效的工作北海岸银行打算为其全职出纳和兼职出纳制定一个有效的工作时间表。时间表须能让银行有效运作，该银行周五营业时间为时间表。时间表须能让银行有效运作，该银行周五营业时间为上午上午9：00到下午到下午7：00。下表是。下表是 周五各时间段内为提供足够周五各时间段内为提供足够的客户服务所需的出纳员的数量。的客户服务所

10、需的出纳员的数量。工作时间工作时间出纳员数量出纳员数量工作时间工作时间出纳员数量出纳员数量上午上午9点点上午上午10点点上午上午10点点上午上午11点点上午上午11点点正午正午正午正午下午下午1点点下午下午1点点下午下午2点点648109下午下午2点点下午下午3点点下午下午3点点下午下午4点点下午下午4点点下午下午5点点下午下午5点点下午下午6点点下午下午6点点下午下午7点点64766 每个全职员工从整点开始连续工作每个全职员工从整点开始连续工作4小时后，是小时后，是1小时的小时的午餐时间，然后继续工作午餐时间，然后继续工作3小时。兼职员工从整点开始连续工小时。兼职员工从整点开始连续工作作4个

11、小时。全职员工成本每小时个小时。全职员工成本每小时15美元（每天美元（每天105美元），美元），兼职员工成本每小时兼职员工成本每小时8美元（每天美元（每天32美元）。美元）。 构建一个整数规划线性模型，以使用最少人力成本并满构建一个整数规划线性模型，以使用最少人力成本并满足顾客服务为目标，构建一个可行的时间表。足顾客服务为目标，构建一个可行的时间表。123171112121231231231234232345133456124567123567236737min105()32()64810964766,intijzxxxyyxyxxyyxxxyyyxxxyyyyxxyyyyxxyyyyxxyyyyxxxyyyxxyyxyx y第第i点钟全职员工开始工作的人数；点钟全职员工开始工作的人数；第第i点钟兼职职员工开始工作的人数；点钟兼职职员工开始工作的人数；ixiy工作时间工作时间临时工数量临时工数量上午上午9点点上午上午10点点上午上午10点点上午上午11点点上