《理学整数规划》PPT课件.ppt

运筹学运筹学 OPERATIONALOPERATIONAL RESEARCHRESEARCH 广东培正学院 迟彦惠 “四舍五入”取x1=2,x2=7. 3 第五章 整数规划 引例：某厂利用集装箱托运甲、乙两种货物 ，每箱体积重量 、可获利润及托运限制如下 ： 体积重量利润 甲5220 乙4510 托运限制2413 两种货物各托运多少箱使利润最大？ Max Z= 20x1 +10x2 5x1 +4x224 2x1 +5x213 x1 , x20 x2 x1 0 A x1 , x2 为整数 ZA=96 A(4.8, 0 ) Max Z= 20x1 +10x2 5x1 +4x224 2x1 +5x213 x1 , x20 x2 x1 (4.8, 0 ) A ZA=96 x1 , x2 为整数 (4,0) Z=80 (5,0) (4,1) max Z=90 第一节 整数规划的数学模型 一、整数规划问题 整数规划问题（IP）:是指要求部分 或全部决策变量的取值为整数的规划问 题。 松弛问题：不考虑整数条件，由余 下的目标函数和约束条件构成的规划问 题。 重点研究：整数线性规划问题 二、整数线性规划问题的模型 j=1,2,n i=1,2,m xj 中取部分或全部为整数 三、整数规划问题的类型： 1. 纯整数规划问题 minZ= x1 + x2 +x3+x4+x5+x6 +x7+x8 x1 8 x1 + x2 8 x1 + x2+ x3 7 x1+x2+ x3 + x4 1 x2+ x3 + x4 + x5 2 x3+ x4 + x5 +x6 1 x4 + x5 +x6 + x7 5 x5+ x6 + x7 +x8 10 x6 + x7 +x8 10 x7 +x8 6 x8 6 xi 0 (i =1,8)且为整数 2. 0-1型整数线性规划 例2：现有资金总额为B。可供选择的投资项 目有n个，项目j所需投资额和预期收益分别 为aj和cj,此外，因种种原因，有3个附加条件 ：若选择项目1必须同时选择项目2，反之， 不一定；项目3和项目4中至少选择一个；第 三，项目5、6、7中恰好选择两个。应当怎样 选择投资项目，才能使总预期收益最大？ 1 对项目 j 投资 0 对项目 j 不投资 xj= Max Z=cjxj ajxjB x2 x1 x3+ x4 1 x5+ x6 +x7=2 xj=0或1（j=1,2,n） 3. 混合整数规划 例3 工厂A1和A2生产某种物资，由于 该种物资供不应求，还需要建一家工厂。由 两个待选方案A3和A4。物资需求地为 Bj(j=1,2,3,4)。工厂A3和A4的生产费用估计为 1200万元或1500万元。选择哪一个方案才能 使总费用（包括物资运费和新工厂的生产费 用）最小。 B1B2B3B4生产能力 A12934400 A28357600 A37612200 A44525200 需求量350400300150 y 0-1变量 y= 1 若建工厂A3 0 若建工厂A4 设xij为由Ai送往Bj 的物资数量。 则总费用为: min Z=cijxij +1200y+1500(1-y) x11+ x21+ x31+ x41=350 x12+ x22+ x32+ x42=400 x13+ x23+ x33+ x43=300 x14+ x24+ x34+ x44=150 x11+ x12+ x13+ x14=400 x21+ x22+ x23+ x24=600 x31+ x32+ x33+ x34=200y x41+ x42+ x43+ x44=200(1-y) xij0, y=0或1 第二节 解纯整数规划的割平面法 一、基本思想 找到纯整数线性规划的松弛问题，不考 虑整数约束条件，但增加线性约束条件，将 松弛问题的可行域切割一部分，但不切割掉 任何整数解，只切割掉包括松弛问题的最优 解在内的非整数解。 二、割平面求解举例 Max Z=x1+x2 -x1+x21 3x1+x2 4 x1 , x20且为整数 松弛问题 Max Z=x1+x2 -x1+x21 3x1+x2 4 x1 , x20 -x1+x2+x3 =1 3x1+x2 +x4=4 x1 , x20 不考虑整数解约束，解松弛问题的最优单纯形表为 ： CBXBb 1100 x1x2x3x4 0x31-1110 0x443101 -1-100 1x13/410-1/41/4 1x27/4013/41/4 Z=5/2001/21/2 x2+3/4x3+1/4x4=7/4x2-1=3/4-3/4x3-1/4x4 将 -3x3-x4+x5= -3（切割方程） 代入最优表 CBXBb11000 x1x2x3x4x5 1x13/410-1/41/40 1x27/4013/41/40 0x5-300-3-11 Z=5/200-1/2-1/20 1x111001/31/12 1x2101001/4 0x310011-1/3 Z=2000-1/3-1/3 x2-1=3/4-3/4x3-1/4x4 3/4-3/4x3-1/4x40 3-3x3-x403-3x3-x4+x5=0 MaxZ=3x1-x2 3x1-2x23 5x1+4x210 2x1+x25 x1,x20 且为整数 MaxZ=3x1-x2 3x1-2x23 5x1+4x210 2x1+x25 x1,x20 CBXBb11000 x1x2x3x4x5 3x113/7101/702/7 -1x29/701-2/703/7 0x431/700-3/7122/7 Z=5/200-5/70-3/7 x1+1/7x3 + 2/7x5=13/7 x1+1/7x3 + 2/7x5=1+6/7 x1- 1 = 6/7 -（1/7x3 + 2/7x5） 6/7 -（1/7x3 + 2/7x5）0 -1/7x3 - 2/7x5- 6/7 -1/7x3 - 2/7x5- 6/7 -1/7x3 - 2/7x5+x6=- 6/7 CBXBb110000 x1x2x3x4x5x6 3x113/7101/702/70 -1x29/701-2/703/70 0x431/700-3/7122/70 0x6-6/700-1/70-2/71 Z=5/200-5/70-3/70 CBXBb110000 x1x2x3x4x5x6 3x11100001 -1x24/5010-1/40-5/4 0x35/2001-1/20-11/2 0x57/40001/41-3/4 Z=5/200000-17/4 -1/4x4 + 1/4x6-3/4 余下略 第三节 分支定界法 一、基本思想 定界：为求解纯整数规划和混合整数规 划问题(A)，先求出其松弛问题（B）的最优 解，作为问题A的最优目标函数值的上界， 同时选择任意整数可行解作为A的最优目标 函数值的下界。 分支：将应为整数解，但尚是非整数解 之一的决策变量取值分区，并入松弛问题中 ，形成两个分支松弛问题，分别求解。依结 果来调整上下界。 二、举例 例1：A问题为 B问题为 MaxZ=40x1+90x2 9x1+7x256 7x1+20x2 70 x1,x20 x1,x2 都为整数 MaxZ=40x1+90x2 9x1+7x256 7x1+20x2 70 x1,x20 问题B x1=4.81 ,x2=1.82 Z=356 Z=356 Z=0 问题B1 x1=4,x2=2.1 Z=349 问题B 2 x1=5 ,x2=1.57 Z=341 x14 x15 Z=349 Z=0 x22 x23 问题B3 x1=4, x2=2 Z=340 问题B4 x1=1.42 x2=3 Z=327 Z=349 Z=340 x21 x22 问题B5 x1=5.44 x2=1 Z=308 Z*=340 问题B6 无可行 解 第四节 0-1型整数规划 一、0-1变量的概念 0-1变量：一种逻辑变量，常用来表 示系统处于某个特定状态，或者决策时是 否取某个特定方案。 x= 1 当决策取方案P时 0 当决策不取方案P时 二、0-1变量的实际应用 1. 制定相互排斥的计划 例1：投资场所的选定 某公司拟在市东、西、南三区建立门市部，拟 议中有7个位置Ai 可供选择，规定： 在东区，由A1， A2 ，A3三个点中至多选两个 ； 在西区，由A4， A5 两点中至少选择1个； 在南区，由 A6， A7 两点中至少选择1个。 若选择Ai 点，估计设备投资为bi 元，获利ci ,但投资 不能超过B元，如何投资获利最大？ x= 1 当Ai 点被选用时 0 当Ai 点未被选用时 解： Max Z=cixi bixiB x1+ x2 +x32 x4+ x5 1 x6+ x7 1 xj=0或1（i=1,2,n） 2. 相互排斥的约束条件问题 例：集装箱运货（用车运或用船运） 车运体积船运体积重量利润 甲57220 乙43510 托运 限制 244513 两种货物各托运多少箱可以使利润最大？ y= 1 船运 0 车运 解： 5x1+4x224+yM 7x1+3x245+(1-y)M Max Z=20x1+10x2 5x1+4x224+yM 7x1+3x245 +(1-y)M 2x1+5x213 x1, x20 ，y=0或1 x1, x2为整数 y= 1 船运 0 车运 解：x1 ，x2 分别为甲 乙两种货物的托 运数量 3. 固定费用问题 例：有三种资源被用于生产三种产品 ，资源量、产品单件可变费用售价、资源单 耗量及组织三种产品生产的固定费用见下表 。要求制定一个生产计划使总收益为最大。 产品 资源 资源量 A248500 B234300 C123100 单件可变费用456 固定费用100150200 单价81012 设xj 为生产第 j 种产品的产量。y为0-1变量 Max Z=4x1+5x2+6x3-100y1-150y2-200y3 2x1+4x2+8x3500 2x1+3x2+4x3300 x1+2x2+3x3100 x1 M1y1 x2 M2y2 x3 M3y3 xj 0且为整数，j=1,2,3 yj=0或1，j=1,2,3 三、0-1型整数规划的解法 隐枚举法 隐枚举法：不同于穷举法，只检查变 量取值组合的一部分就能找到问题的最优 解。解题关键是寻找可行解，产生过滤条 件。 过滤条件：目标函数值优于计算过的 可行解目标函数值。 maxZ=3X1 -2X2+5X3 X1+ 2X2 - X3 2 X1 + 4X2 +X3 4 X1 + X2 3 4X2 +X3 6 X1 , X2 , X3 = 0 或 1 (x1 , x2 , x3)Z值约束条件 过滤条件 （0，0，0）0 Z0 （0，0，1）5 Z5 （0，1，0）-2 （0，1，1）3 （1，0，0）3 （1，0，1）8 Z8 （1，1，0）1 （1，1，1）6 第五节 指派问题 一、典型的指派问题 某单位需完成n项任务，恰有n个人可 以承担，由于每个人的专长不同，各人完 成任务的效率不同，各人完成一项任务的 同时，不能同时去做其它任务，如何分配 任务会使所需的时间最小或成本最低。 例：有一份中文说明书，需译成英、日 、德、俄四种文字，分别记做E、J、G、R 。现有甲、乙、丙、丁4人，他们将中文说 明书翻译成不同语种的说明书所需的时间如 下，问应指派何人去完成何种工作，使所需 总时间最少？ 任务 人员 EJGR 甲215134 乙1041415 丙9141613 丁78119 指派问题的标准形式 n个人，n件事，第i个人做第j件事的费 用为cij,确定人和事之间一一对应的指派方 案，使完成n件事的总费用最小。 效率 矩阵 或 系数 矩阵 C=(cij)nn= c11 c12 c1n c21 c22 c2n cn1 cn1 cnn C=(cij )nn= 215134 1041415 9141613 78119 二、标准指派问题的数学模型 xij= 1 指派第 i 个人做第 j 件事 0 不指派第 i 个人做第 j 件事 j=1,2,n i=1,2,n xij=1或0 解矩阵：满足约束条件的可行解也 可以写成表格或矩阵的形式，称为解矩阵 。 例： X=(xij )44= 010 0 0001 1 0 0 0 0 0 1 0 三、匈牙利解法 （1）关键性质： 若从指派问题的系数矩阵(cij)nn的某行 或某列各元素中分别减一个常数k, 得到的 新矩阵与原矩阵有相同的最优解。 C=(cij )nn= 215134 1041415 9141613 78119 C=(cij )nn= 215134 1041415 9141613 78119 C=(cij )nn= 01370 6069 0532 0100 匈牙利法的步骤 1.变换系数矩阵 每行减最小数， 没0的列，减最小数 C=(cij )nn= 01370 6069 0532 0100 匈牙利法的步骤 2.寻找独立“0”元素 若有n个，计算结束 若少于n个，转3 C=(cij )nn= 137 669 532 1 匈牙利法的步骤 2.寻找独立“0”元素 若有n个，计算结束 若少于n个，转3 C=(cij )nn= 215134 1041415 9141613 78119 Min Z=c31+c22+c43+c14=4+4+9+11=28 2.寻找独立“0”元素 C=(cij )nn= 4 8 7 15 12 7 9 17 14 10 6 9 12 8 7 6 7 14 6 10 6 9 12 10 6 行减最小数 匈牙利法的步骤 2.寻找独立“0”元素 C=(cij )nn= 0 4 3 11 8 0 2 10 7 3 0 3 6 2 1 0 1 8 0 4 0 3 6 4 0 匈牙利法的步骤 没有零的列减最小数 2.寻找独立“0”元素 若有n个，计算结束 若少于n个，转3 C=(cij )nn= 0 3 0 11 8 0 1 7 7 3 0 2 3 2 1 0 0 5 0 4 0 2 3 4 0 匈牙利法的步骤 是否找到最优指派 3534 3.寻找最少覆盖“0”的直线 0 3 0 11 8 0 1 7 7 3 0 2 3 2 1 0 0 5 0 4 1 2 3 4 0 （1）行或列中只 有一个“0”的元， 作标记，如果其所 在列或行有其它 “0”的，则划去。 （2）如此反复直 到所有行的“0”被 直线覆盖 匈牙利法的步骤 （1）对所有不含0 元素的行打 匈牙利法的步骤 （2）对已打的行 中所有含0元素的 列打 （3）在对已打 的列中含0元素的 行打 直到无法打为止, 3.寻找最少覆盖“0”的直线 0 3 11 8 1 7 7 3 0 2 3 2 1 0 5 0 4 1 2 3 4 匈牙利法的步骤 （4）没打的行画 直线， 对打的列画直线, 3.寻找最少覆盖“0”的直线 0 3 11 8 1 7 7 3 0 2 3 2 1 0 5 0 4 1 2 3 4 0 3 11 8 1 7 7 3 0 2 3