第7章整数线性规划

第7章整数线性规划7.1整数线性规划的分类全整数线性规划：所有变量均为整数。混合整数线性规划：有一些变量是整数而非全部都是。0-1整数线性规划：整数变量只取0或1。7.2全整数线性规划的图解法与计算机解法(P200)7.2.1LP松弛的图解法7.2.2近似整数解的获得 T=2,A=3,z=65 T=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年资金需求20151050第3年资金需求20201040第4年资金需求15541035工厂扩建方案如果通过，P=1； 如果否决，P取0。仓库扩建方案如果通过，W=1；如果否决，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固定成本（美元）20050400最大生产量（吨）502540F:生产的燃料添加剂的吨数S:生产的溶剂的吨数C:生产的地板清洁剂的吨数如果生产燃料添加剂，SF=1，否则，SF=0；如果生产溶剂，则SS=1，否则，SS=0；如果生产地板清洁剂，SC=1，否则，SC=0。7.3.3分布系统设计目标工厂年固定成本（美元）年生产能力（件）底特莱多30000020000丹佛37500030000堪萨斯城50000040000分销中心年需求量（件）波士顿30000亚特兰大20000休斯敦20000马丁贝克分布系统的单位运输成本工厂地点分销中心波士顿亚特兰大休斯敦底特律523托莱多434丹佛975堪萨斯城1042圣路易斯843如果在底特律建厂，否则，如果在托莱多建厂，否则，如果在丹佛建厂，否则，如果在堪萨斯城建厂，否则，7.3.4银行选址俄亥俄州信托公司的扩展区考虑的郡临近的郡考虑的郡临近的郡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霍姆斯7,8,11,17,199梅迪纳3,4,7,8,1019塔斯卡卢斯11,18,2010萨米特3,8,9,11,12,1320卡罗尔11,14,19北海岸银行打算为其全职出纳和兼职出纳制定一个有效的工作时间表。时间表须能让银行有效运作，该银行周五营业时间为上午9：00到下午7：00。下表是周五各时间段内为提供足够的客户服务所需的出纳员的数量。工作时间出纳员数量工作时间出纳员数量上午9点~上午10点上午10点~上午11点上午11点~正午正午~下午1点下午1点~下午2点648109下午2点~下午3点下午3点~下午4点下午4点~下午5点下午5点~下午6点下午6点~下午7点64766每个全职员工从整点开始连续工作4小时后，是1小时的午餐时间，然后继续工作3小时。兼职员工从整点开始连续工作4个小时。全职员工成本每小时15美元（每天105美元），兼职员工成本每小时8美元（每天32美元）。构建一个整数规划线性模型，以使用最少人力成本并满足顾客服务为目标，构建一个可行的时间表。——第i点钟全职员工开始工作的人数；——第i点钟兼职职员工开始工作的人数；工作时间临时工数量上午9点~上午10点上午10点~上午11点上午11点~正午正午~下午1点下午1点~下午2点下午2点~下午3点下午3点~下午4点下午4点~下午5点下午5点~下午6点下午6点~下