8第八章__整数规划.pptVIP

第八章 整数规划 整数规划的难度远大于一般线性规划 整数规划模型的类型 纯整数规划模型 混合整数规划模型 0-1整数规划模型 纯整数规划模型 混合整数规划模型 0-1整数规划模型 二、整数规划实际应用 投资场所的选择 固定成本问题 指派问题 分布系统设计 投资问题 人力资源分配问题 投资组合问题 应急设施选址问题 背包问题 1、投资场所的选择 例1、京城畜产品公司计划在市区的东南西北四区建立销售门市部，拟议中有10个位置Ai（i=1,2…,10）可供选择，各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况如表所示。 考虑到各地区居民的消费水平及居民居住密集度，规定： 在东区由A1, A2, A3三个点至多选择两个； 在西区A4, A5两个点中至少选一个； 在南区由A6, A7两个点中至少选一个； 在北区由A8, A9, A10三个点中至少选两个； 投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大？ 解：设 1 当Ai点被选用 xi= 0 当Ai点没被选用 maxZ=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10 ≤720 x1+x2+x3 ≤2 s.t. x4+x5 ≥1 x6+x7 ≥1 x8+x9+x10 ≥2 xi≥0且xi为0-1变量(i=1,2,…10) 2、固定成本问题 例2、高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量、不考虑固定费用，每种容器售出一只所得的利润、所用资源的数量、不管每种容器制造的数量是多少，都要支付的固定费用如表。现在要制定一个生产计划，使获得的利润为最大。 3、指派问题 例3、有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如表所示，问如何分配任务使完成四项任务的总工时耗费最少？ 指派问题的通用数学模型如下： 4、分布系统设计 例4、某企业在A1地已有一个工厂，其产品的生产能力为30千箱，为了扩大生产，打算在A2 A3 A4 A5地中再选择几个地方建厂。已知A1地的产量、 A2 A3 A4 A5建成厂的产量、那时销售地的销量、产地到销售地的单位运价、在地建厂的固定成本等如表。 （1）问应该在哪几个地方建厂，在满足销售量的前提下，使得其固定成本和总的运输费用之和最小； （2）如果由于政策要求必须在A2 A3地建一个厂，问在哪几个地方建厂？ 5、投资问题 某公司在今后四年内考虑以下四个投资项目选择问题： 项目甲：第二年初需投资，到第四年年末收回本利180%； 要求最大投资额为8万元； 项目乙：从第一年到第三年，每年年初需投资，并于次年年 末收回本利120%； 项目丙：从第一年开始每年年初可购买公债，于当年年末归 还，并加息10%； 项目丁：第一年初需投资，到第二年年末收回本利135%； 第三年初又投资，到第四年年末收回本利130% 此外，为了使每年项目之间保持平衡性，要求每年年末回收的资金全部投资到第二年年初, 该部门现有投资资金30万元。应如何确定这些项目在各年的投资额，使该公司在第四年年末拥有资金的本利总额达到最大？试建立该问题的线性规划模型。 解： 根据题意，可假设如下决策变量： 第一年 第二年 第三年 第四年 项目甲： x12 项目乙： x21 x22 x23 项目丙： x31 x32 x33 x34 项目丁： x41 x43 maxZ=180%x12+120%x23+110%x34+130%x43. x21+ x31+ x41 =30 x12+x22+x32 =110%x31 s.t.