第7章--整数线性规划ppt课件.ppt

《第7章--整数线性规划ppt课件.ppt》由会员分享，可在线阅读，更多相关《第7章--整数线性规划ppt课件.ppt（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目第第7章章 整数线性规划整数线性规划 7.1 整数线性规划的分类整数线性规划的分类 全整数线性规划：所有变量均为整数。全整数线性规划：所有变量均为整数。混合整数线性规划：有一些变量是整数而非全部都是。混合整数线性规划：有一些变量是整数而非全部都是。0-1整数线性规划：整数变量只取整数线性规划：整数变量只取0或或1。7.2 全整数线性规划的图解法与计算机解法全整数线性规划的图解法与计算机解法(P200)认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫

2、工作高度重视，已经展开了“精准扶贫”项目7.2.1 LP松弛的图解法松弛的图解法 7.2.2 近似整数解的获得近似整数解的获得T=2,A=3,z=65T=3,A=3,不可行不可行T=2,A=4,不可行不可行 认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目7.2.3 全整数解的图解法全整数解的图解法 7.2.4 计算机解法计算机解法 认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目7.3 含有含有0-1变量的整数线性规划的应用变量的整数线性规划的应用 7.

3、3.1 资金预算资金预算 爱斯柯德冰箱公司的估计净现值、资金需求和爱斯柯德冰箱公司的估计净现值、资金需求和4年内的可用资金年内的可用资金（单位：千美元）（单位：千美元）项项目目可用可用资资金金总额总额工厂工厂扩扩建建仓库扩仓库扩建建机器更新机器更新新新产产品研品研发发净现值净现值90401037第第1年年资资金需求金需求1510101540第第2年年资资金需求金需求20151050第第3年年资资金需求金需求20201040第第4年年资资金需求金需求15541035工厂扩建方案如果通过，工厂扩建方案如果通过，P=1；如果否决，如果否决，P取取0。仓库扩建方案如果通过，仓库扩建方案如果通过，W=1

4、；如果否决，如果否决，W取取0。机器更新方案如果通过，机器更新方案如果通过，M=1；如果否决，如果否决，M取取0。新产品研发方案如果通过，新产品研发方案如果通过，R=1；如果否决，如果否决，R取取0。认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目7.3.2 固定成本核算固定成本核算 RMC问题问题 燃料添加燃料添加剂剂溶溶剂剂地板清地板清洁剂洁剂可用吨数可用吨数原料原料 10.40.50.620原料原料20.20.15原料原料30.60.30.321利利润润（美元（美元/吨）吨）403050固定成本（美元）固定成本（美元）

5、20050400最大生最大生产产量（吨）量（吨）502540F:生产的燃料添加剂的吨数生产的燃料添加剂的吨数S:生产的溶剂的吨数生产的溶剂的吨数C:生产的地板清洁剂的吨数生产的地板清洁剂的吨数如果生产燃料添加剂，如果生产燃料添加剂，SF=1，否则，否则，SF=0；如果生产溶剂，则如果生产溶剂，则 SS=1，否则，否则，SS=0；如果生产地板清洁剂，如果生产地板清洁剂，SC=1，否则，否则，SC=0。认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目7.3.3 分布系统设计分布系统设计 目目标标工厂工厂年固定成本年固定成本（美元

6、）（美元）年生年生产产能力能力（件）（件）底特律底特律17500010000托莱多托莱多30000020000丹佛丹佛37500030000堪堪萨萨斯城斯城50000040000分分销销中心中心年需求量（件）年需求量（件）波士波士顿顿30000亚亚特特兰兰大大20000休斯敦休斯敦20000马丁贝克分布系统的单位运输成本马丁贝克分布系统的单位运输成本 工厂地点工厂地点分分销销中心中心波士波士顿顿亚亚特特兰兰大大休斯敦休斯敦底特律底特律523托莱多托莱多434丹佛丹佛975堪堪萨萨斯城斯城1042圣路易斯圣路易斯843认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫

7、工作高度重视，已经展开了“精准扶贫”项目如果在底特律建厂，如果在底特律建厂，否否则则，如果在托莱多建厂，如果在托莱多建厂，否否则则，如果在丹佛建厂，如果在丹佛建厂，否否则则，如果在堪如果在堪萨萨斯城建厂，斯城建厂，否否则则，认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目7.3.4 银行选址银行选址 俄亥俄州信托公司的扩展区俄亥俄州信托公司的扩展区 考考虑虑的郡的郡临临近的郡近的郡考考虑虑的郡的郡临临近的郡近

8、的郡1 阿什特比拉阿什特比拉2,12,1611 斯塔克斯塔克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 霍姆斯霍姆

9、斯7,8,11,17,199 梅迪梅迪纳纳3,4,7,8,1019 塔斯卡塔斯卡卢卢斯斯11,18,2010 萨萨米特米特3,8,9,11,12,1320 卡卡罗罗尔尔11,14,19认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国家对扶贫工作高度重视，已经展开了“精准扶贫”项目北海岸银行打算为其全职出纳和兼职出纳制定一个有效的工作北海岸银行打算为其全职出纳和兼职出纳制定一个有效的工作时间表。时间表须能让银行有效运作，该银行周五营业时间为时间表。时间表须能

10、让银行有效运作，该银行周五营业时间为上午上午9：00到下午到下午7：00。下表是。下表是 周五各时间段内为提供足够周五各时间段内为提供足够的客户服务所需的出纳员的数量。的客户服务所需的出纳员的数量。工作时间工作时间出纳员数量出纳员数量工作时间工作时间出纳员数量出纳员数量上午上午9点点上午上午10点点上午上午10点点上午上午11点点上午上午11点点正午正午正午正午下午下午1点点下午下午1点点下午下午2点点648109下午下午2点点下午下午3点点下午下午3点点下午下午4点点下午下午4点点下午下午5点点下午下午5点点下午下午6点点下午下午6点点下午下午7点点64766 每个全职员工从整点开始连续工作

11、每个全职员工从整点开始连续工作4小时后，是小时后，是1小时的小时的午餐时间，然后继续工作午餐时间，然后继续工作3小时。兼职员工从整点开始连续工小时。兼职员工从整点开始连续工作作4个小时。全职员工成本每小时个小时。全职员工成本每小时15美元（每天美元（每天105美元），美元），兼职员工成本每小时兼职员工成本每小时8美元（每天美元（每天32美元）。美元）。构建一个整数规划线性模型，以使用最少人力成本并满构建一个整数规划线性模型，以使用最少人力成本并满足顾客服务为目标，构建一个可行的时间表。足顾客服务为目标，构建一个可行的时间表。认识到了贫困户贫困的根本原因，才能开始对症下药，然后药到病除。近年来国

12、家对扶贫工作高度重视，已经展开了“精准扶贫”项目第第i点钟全职员工开始工作的人数；点钟全职员工开始工作的人数；第第i点钟兼职职员工开始工作的人数；点钟兼职职员工开始工作的人数；工作时间工作时间临时工数量临时工数量上午上午9点点上午上午10点点上午上午10点点上午上午11点点上午上午11点点正午正午正午正午下午下午1点点下午下午1点点下午下午2点点下午下午2点点下午下午3点点下午下午3点点下午下午4点点下午下午4点点下午下午5点点下午下午5点点下午下午6点点下午下午6点点下午下午7点点6 6 63 3 05 2 20 0 61 4 10 0 06 6 60 0 00 0 00 0 0总成本合计总成本合计 672多个最优解多个最优解