第三章目标规划和整数规划.pptVIP

第三章目标规划和整数规划 3.1 目标规划 3.2 整数规划 匈牙利法的具体步骤： 练习： 例2.1 胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子售价30元/个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4个小时，油漆工2小时。生产一个椅子需要木工3个小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？ 纯整数规划 数学模型： 例 一登山队员做登山准备，他需要携带的物品及每件物品的重要系数、重量如下表，假定登山队员可携带的最大重量为25千克，问该队员该携带那些物品 1 2 3 4 5 6 7 序号 物品 食品 氧气 冰镐 绳索 帐篷 照相器材 通讯设备 重量ai（千克） 5 5 2 6 12 2 4 重要系数ci 20 15 18 14 8 4 10 1 0 带第i个物品 不带第i个物品 Z表示总重要系数 0-1规划 混合型 6个人应聘4份工作，由于个人的技术专长不同，他们承担各项工作所获得的收益如下表，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总收益最大的指派方案。 工作 人 收益 1 2 3 4 1 2 3 4 5 6 3 5 4 5 6 7 6 8 8 9 8 10 10 10 9 11 12 11 10 12 13 12 11 13 分派方案： 第3个人第2项工作 第4个人第3项工作 第5个人第1项工作 第6个人第4项工作 第1、2个人没工作 [ ] OR 最优解X*=（4，1）；Z（X*）=14 3.2.4 0-1规化 3．2．4．1 0-1规划问题及其数学模型 3．2．4．2 0-1规划的隐枚举解法 例 MaxZ（X）=3x1-2x2+5x3 x1 +2x2 - x3 ≤2 ① x1 +4x2 + x3 ≤ 4 ② x1 + x2 ≤3 ③ 4x2 + x3 ≤ 6 ④ x1,x2,x3 =0 或 1 解：首先通过试探的方法找出一个可行解 X =（x1,x2,x3 ）=（1，0，0） Z（X）= 3x1-2x2+5x3 = 3 增加约束： 3x1-2x2+5x3 ≥3 ⊙（称为过滤条件） OR 例 MaxZ（X）=3x1-2x2+5x3 x1 +2x2 - x3 ≤2 ① x1 +4x2 + x3 ≤ 4 ② x1 + x2 ≤3 ③ 4x2 + x3 ≤ 6 ④ x1,x2,x3 =0 或 1 6 2 6 N 8 0 2 1 Y 1 1 N 3 1 1 1 0 Y 3 1 5 N 5 -1 1 0 1 Y 5 -2 N 0 N 将不满足过滤条件的X全部过滤掉，见下表 3 8 OR 改进过滤条件： -2x2+3x1+5x3 ≥5 ⊙ 改进过滤条件： -2x2+3x1+5x3 ≥8 ⊙ 注意： （1）为进一步减少计算工作量，可及时改进过滤条件。 （2）价值系数按递增排列， 如 MaxZ（X）=-2x2+3x1+5x3 X*=(1,0,1) Z=8 OR Operational Research 3．2．5分派问题（Assignment problem） 一般描述: 有n项任务,指派n个人(广义)去完成,第i个人完成第j项 任务的效率为Cij(i=1,2,…,n;j=1,2,…,n)；要求每个人只 能承担一项任务,并且每一项任务都有一个人个来承担；问 如何分派可以使总的效率达到最高。（Cij）为效率矩阵。 3．2．5．1建立数学模型 引入0-1变量 效率矩阵: xij= 0