第八章蓑教规 §1整数规划的图解法 §2整数规划的计算机求解 §3整数规划的应用 §4整数规划的分枝定界法
第八章 整数规划 §1 整数规划的图解法 §2整数规划的计算机求解 §3整数规划的应用 §4整数规划的分枝定界法
§1整数规划的图解法 例1.某工厂在计划期内要安排甲、乙两种仪器设备的生产,已知生产仪器设备 需要A、B两种材 乙 资源限制 料的消耗以及资 材料A 2 源的限制,如右 材料B 0 表 单件获利1万元1万元 问题:工厂应分 别生产多少件甲、乙种仪器设备才 能使工厂获利最多? 解 目标函数:Maxz=x1+x2 约束条件:st 3x+2x=10 3X1+2x2<10 2x x1,x2≥0为整数 不考虑整数约束得到最优解: X1=1.667,X2=2.5 4.167 x1+2x2=6 考虑整数约束得到最优解: X1=2,x2=2; 4 整数规划的最优目标值小于相应 目标函数 等值线 线性规划的最优目标值(相当于附加一个约束) 图6.4.1
§1 整数规划的图解法 例1. 某工厂在计划期内要安排甲、乙两种仪器设备的生产，已知生产仪器设备 需要A、B两种材 料的消耗以及资 源的限制，如右 表。 问题：工厂应分 别生产多少件甲、乙种仪器设备才 能使工厂获利最多？ 甲 乙 资源限制 材料 A 3 2 10 材料 B 0 2 5 单件获利 1 万元 1 万元 解、 目标函数： Max z = x1 + x2 约束条件： s.t. 3 x1 + 2 x2 ≤ 10 2 x2 ≤ 5 x1，x2 ≥ 0 为整数 不考虑整数约束得到最优解： x1 =1.667， x2 = 2.5；z = 4.167 考虑整数约束得到最优解： x1 = 2， x2 = 2； z = 4 整数规划的最优目标值小于相应 线性规划的最优目标值(相当于附加一个约束)
§2蓬数规划的计算机求解 例2: 例2: Maxz=15x1+10x2+7x3 Max z= 15x+ 10xo t 7x s. t 5x1-10x2+7x3≤8 5x1-10x2+7x3≤8 6 4 22 +8x2≤12 6x1+4x2+ x2 8X2≤12 3x1+2x2+2x3≤10 3x1+2x2+2x3≤10 x1,x2,x3≥0为整数 x1,X2,X2≥0 x3为整数x1为0-1变量 用《管理运筹学》软件求解得: 0 X3 用《管理运筹学》软件求解得: 0
§2整数规划的计算机求解 例2： Max z = 15x1 + 10x2 + 7x3 s.t. 5x1 - 10x2 + 7x3 ≤ 8 6x1 + 4x2 + 8x3 ≤ 12 -3x1 + 2x2 + 2x3 ≤ 10 x1,x2,x3 ≥ 0 为整数 例2： Max z = 15x1 + 10x2 + 7x3 s.t. 5x1 - 10x2 + 7x3 ≤ 8 6x1 + 4x2 + 8x3 ≤ 12 -3x1 + 2x2 + 2x3 ≤ 10 x1,x2,x3 ≥ 0 x3 为整数 x1 为0-1变量 用《管理运筹学》软件求解得： x1 = 0 x2 = 3 x3 = 0 z = 30 用《管理运筹学》软件求解得： x1 = 1 x2 = 1.5 x3 = 0 z = 30
§3数规划的应用(1) 、投资场所的选择 例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部,拟议中有10个 位置A(=1,2,3,…,10)可供选择,考虑到各地区居民的消费水平及居民居住密集 度,规定 在东区由A1,A2,A3三个点至多选择两个; 在西区由A4,A5两个点中至少选一个 在南区由A6,A7两个点中至少选一个 在北区由A3,A,A10三个点中至少选两个 A各点的设备投资及每 AIA2A3 A4 A, A8 A 年可获利润由于地点不同都是[投资额10012015080709080140160180 不一样的,预测情况见右表所L利润36405022203025485861 示(单位:万元)。但投资总额不能超过720万元,问应选择哪几个销售点,可使年利润为最 大 解:设:0-1变量x=1(A点被选用)或0(A1点没被选用)。 这样我们可建立如下的数学模型 axz=36x1+40x2+50x3+22x4+20x+30x6+25x2+48X8+58形+61x1o s.t.100x1+120x2+150x3+80x1+70x5+90x6+80x2+140x+160x+180x0≤720 X x8+x+x10≥2 x1≥0x1为0--1变量,i=1,2,3,…,10
§3整数规划的应用(1) 一、投资场所的选择 例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个 位置 Aj (j＝1，2，3，…，10)可供选择，考虑到各地区居民的消费水平及居民居住密集 度，规定： 在东区由A1 ， A2 ，A3 三个点至多选择两个； 在西区由A4 ， A5 两个点中至少选一个； 在南区由A6 ， A7 两个点中至少选一个； 在北区由A8 ， A9 ， A10 三个点中至少选两个。 Aj 各点的设备投资及每 年可获利润由于地点不同都是 不一样的，预测情况见右表所 示 (单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最 大? A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 投资额 100 120 150 80 70 90 80 140 160 180 利润 36 40 50 22 20 30 25 48 58 61 解：设：0--1变量xi = 1 (Ai 点被选用）或0 (Ai 点没被选用）。 这样我们可建立如下的数学模型： Max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10 s.t. 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10 ≤ 720 x1 + x2 + x3 ≤ 2 x4 + x5 ≥ 1 x6 + x7 ≥ 1 x8 + x9 + x10 ≥ 2 xj ≥ 0 xj 为0--1变量，i = 1,2,3,……,10
§3数规划的应用(2) 固定成本问题 例5.高压容器公司制造小、中、大三种尺寸的金属容器,所用资源为金属板、劳动力和机 器设备,制造一个容器所需的各种资源的数量如右 资源 小号容器中号容器大号容器 表所示。不考虑固定费用,每种容器售出一只所得金属板(吨 的利润分别为4万元、5万元、6万元,可使用的金 劳动力(人月) 机器设备(台月) 221 432 843 属板有500吨,劳动力有300人月,机器有100台月, 此外不管每种容器制造的数量是多少,都要支付一笔固定的费用:小号是100万元,中号为150 万元,大号为200万元。现在要制定一个生产计划,使获得的利润为最大。 解:这是一个整数规划的问题。 设x1,x2,x3分别为小号容器、中号容器和大号容器的生产数量 各种容器的固定费用只有在生产该种容器时才投入,为了说明固定费用的这种性质,设 =1(当生产第i种容器,即x1>0时)或0(当不生产第i种容器即x1=0时) 引入约束x1≤My,i=1,2,3,M充分大,以保证当y=0时,x1=0。 这样我们可建立如下的数学模型: axz=4x1+5x2+6x3-1 150y2-200 t.2x1+4x2+8x3≤500 2x1+3x2+4x3≤300 x1+2x2+3x3≤100 x1≤My,i=1,2,3,M充分大 x≥0y1为0--1变量,i=1,2,3
二、固定成本问题 例5．高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机 器设备，制造一个容器所需的各种资源的数量如右 表所示。不考虑固定费用，每种容器售出一只所得 的利润分别为 4万元、5万元、6万元，可使用的金 属板有500吨，劳动力有300人月，机器有100台月， 此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为 150 万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。 解：这是一个整数规划的问题。 设x1，x2， x3 分别为小号容器、中号容器和大号容器的生产数量。 各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设 yi = 1(当生产第 i种容器, 即 xi ＞ 0 时) 或0（当不生产第 i种容器即 xi = 0 时） 引入约束 xi ≤ M yi ，i =1，2，3，M充分大，以保证当 yi = 0 时，xi = 0 。 这样我们可建立如下的数学模型： Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3 s.t. 2x1 + 4x2 + 8x3 ≤ 500 2x1 + 3x2 + 4x3 ≤ 300 x1 + 2x2 + 3x3 ≤ 100 xi ≤ M yi ，i =1，2，3，M充分大 xj ≥ 0 yj 为0--1变量，i = 1,2,3 §3整数规划的应用(2) 资源 小号容器 中号容器 大号容器 金属板（吨） 2 4 8 劳动力（人月） 2 3 4 机器设备（台月） 1 2 3
§3数规划的应用(3) 、指派问题 有n项不同的任务,恰好n个人可分别承担这些任务,但由于每人特长不同,完成各 项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务,怎样把n项任务指派 给n个人,使得完成n项任务的总的效率最高,这就是指派问题。 例6.有四个工人,要分别指派他们完 工作 成四项不同的工作,每人做各项工作所消 工人 18 耗的时间如右表所示,问应如何指派工作, 才能使总的消耗时间为最少。 甲乙丙丁 16 19 解:引入0—1变量x1,并令 x=1(当指派第i人去完成第j项工作时)或0(当不指派第i人去完成第j项工作时) 这可以表示为一个0-1整数规划问题 Minz=15x1+18x12+21x13+24x14+19x21+23x2+22x23+18x2+26x31+17x32+16x3+19x34+19x41 +21x42+23x43+17x4 s.t.x1+x12+x3+x14=1(甲只能干一项工作 x2+x2+x23+x24=1(乙只能干一项工作 x31+x2+x3+x34=1(丙只能干一项工作 x1+x42+x43+x4=1(丁只能干一项工作 x1+x21+x31+x41=1(A工作只能一人干 x12+x2+x2+x42=1(B工作只能一人干 x13+x23+x3+x43=1(C工作只能一人干 x14+x2+x34+x4=1(D工作只能一人干 x1;为0--1变量, ***求解可用《管理运筹学》软件中整数规划方法
例6．有四个工人，要分别指派他们完 成四项不同的工作，每人做各项工作所消 耗的时间如右表所示，问应如何指派工作， 才能使总的消耗时间为最少。 解：引入0—1变量 xij，并令 xij = 1(当指派第 i人去完成第j项工作时)或0（当不指派第 i人去完成第j项工作时)． 这可以表示为一个0--1整数规划问题： Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x44 s.t. x11+ x12+ x13+ x14= 1 (甲只能干一项工作) x21+ x22+ x23+ x24= 1 (乙只能干一项工作) x31+ x32+ x33+ x34= 1 (丙只能干一项工作) x41+ x42+ x43+ x44= 1 (丁只能干一项工作) x11+ x21+ x31+ x41= 1 ( A工作只能一人干) x12+ x22+ x32+ x42= 1 ( B工作只能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干) xij 为0--1变量，i,j = 1,2,3,4 * * * 求解可用《管理运筹学》软件中整数规划方法。 §3整数规划的应用(3) 工作 工人 A B C D 甲 15 18 21 24 乙 19 23 22 18 丙 26 17 16 19 丁 19 21 23 17 三、指派问题 有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由于每人特长不同，完成各 项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把 n 项任务指派 给 n 个人，使得完成 n 项任务的总的效率最高，这就是指派问题
§3数规划的应用(4) 四、分布系统设计 例7.某企业在A地已有一个工厂,其产品的生产能力为销地B.B.B产量(千吨 30千箱,为了扩大生产,打算在A2,A2,A,A地中再 选择几个地方建厂。已知在A2,A3,A4,A3地建厂的固 10 定成本分别为175千元、300千元、375千元、500千元,另 外,A产量及A2,A,A4,A3建成厂的产量,那时销地 1042 40 的销量以及产地到销地的单位运价(每千箱运费)如右表所示。 销量(千吨) a)问应该在哪几个地方建厂,在满足销量的前提下,使得其总的固定成本和总的运输费用之和最小? b)如果由于政策要求必须在A2,A3地建一个厂,应在哪几个地方建厂? 解:a)设x为从A运往B的运输量(单位千箱),=1(当A1被选中时)或0(当A1没被选中时) 这可以表示为一个整数规划问题 Minz=175y2+300y3+375y4+500y+8x1+4x12+3x13+5x2+2x2+3x23+4x1+3x32+4x3+9x1+7x42+5x43+10x5 其中前4项为固定投资额,后面的项为运输费用 s.t.x1+x12+x13≤30(A1厂的产量限制) x21+x2+x23≤10y2(A2厂的产量限制) b)增加约束:y2+y=1 x3+x32+x3≤20y3(A3厂的产量限制 x1+x2+x9≤30y4(A4厂的产量限制 x51+x52+x53≤40y5(A5厂的产量限制) x1计+x2+x31+x41+x51=30(B1销地的限制) x12+x2+x32+x2+xB2=20(B2销地的限制) x13+x2+x3+x3+x53=20(B3销地的限制) x1;≥0为0--1变量,i=1,2,3,4,5;j=1,2,3 ***求解可用《管理运筹学》软件中整数规划方法
四、分布系统设计 例7．某企业在A1 地已有一个工厂，其产品的生产能力为 30 千箱，为了扩大生产，打算在 A2，A3，A4，A5地中再 选择几个地方建厂。已知在 A2 ，A3，A4，A5地建厂的固 定成本分别为175千元、300千元、375千元、500千元，另 外，A1产量及A2，A3，A4，A5建成厂的产量，那时销地 的销量以及产地到销地的单位运价(每千箱运费)如右表所示。 a) 问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小? b) 如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂? 解： a) 设 xij为从Ai 运往Bj 的运输量(单位千箱)， yi = 1(当Ai 被选中时)或0（当Ai 没被选中时)． 这可以表示为一个整数规划问题： Min z = 175y2+300y3+375y4+500y5+ 8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41 +7x42+5x43+10x51 +4x52+2x53 其中前4项为固定投资额，后面的项为运输费用。 s.t. x11+ x12+ x13 ≤ 30 ( A1 厂的产量限制) x21+ x22+ x23 ≤ 10y2 ( A2 厂的产量限制) b）增加约束：y2+y3=1 x31+ x32+ x33 ≤ 20y3 ( A3 厂的产量限制) x41+ x42+ x43 ≤ 30y4 ( A4 厂的产量限制) x51+ x52+ x53 ≤ 40y5 ( A5 厂的产量限制) x11+ x21+ x31+ x41 + x51 = 30 ( B1 销地的限制) x12+ x22+ x32+ x42 + x52 = 20 ( B2 销地的限制) x13+ x23+ x33+ x43 + x53 = 20 ( B3 销地的限制) xij ≥ 0 yi为0--1变量，i = 1,2,3,4,5；j = 1,2,3 * * * 求解可用《管理运筹学》软件中整数规划方法。 §3整数规划的应用(4) 销地 产地 B1 B2 B3 产量(千吨) A1 8 4 3 30 A2 5 2 3 10 A3 4 3 4 20 A4 9 7 5 30 A5 10 4 2 40 销量(千吨) 30 20 20
S3数规划的应用(5) 五、投资问题 例8.某公司在今后五年内考虑给以下的项目投资。已知: 项目A:从第一年到第四年每年年初需要投资,并于次年末回收本利115%,但要求第一年投资最低金额 为4万元,第二、三、四年不限 项目B:第三年初需要投资,到第五年未能回收本利128%,但规定最低投资金额为3万元,最高金额为5 万元 项目C:第二年初需要投资,到第五年未能回收本利140%,但规定其投资额或为2万元或为4万元或为6 万元或为8万元 项目D:五年内每年初可购买公债,于当年末归还,并加利息6%,此项投资金额不限 该部门现有资金10万元,问它应如何确定给这些项目的每年投资额,使到第五年末拥有的资金本利总额 为最大? 解:1)设x1A、x1B、xC、xD(i=1,2,3,4,5)分别表示第i年年初给项目A,B,C,D的投资额 设yv,yB,是0-1变量,并规定取1时分别表示第i年给A、B投资,否则取0(i=1,2,3,4,5) 设y是非负整数变量,并规定:2年投资C项目8万元时,取值为4 2年投资C项目6万元时,取值为3; 2年投资C项目4万元时,取值为2 2年投资C项目2万元时,取值为1 2年不投资C项目时,取值为0 这样我们建立如下的决策变量 第1年第2年第3年第4年第5年 A XI X4 B C xc(=20000yxC) D
§3整数规划的应用(5) 五、投资问题 例8．某公司在今后五年内考虑给以下的项目投资。已知： 项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%，但要求第一年投资最低金额 为4万元，第二、三、四年不限； 项目B：第三年初需要投资，到第五年未能回收本利128％，但规定最低投资金额为3万元，最高金额为5 万元； 项目 C：第二年初需要投资，到第五年未能回收本利140%，但规定其投资额或为2万元或为4万元或为6 万元或为8万元。 项目 D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。 该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额 为最大? 解：1) 设xiA、xiB、xiC、xiD ( i ＝1，2，3，4，5)分别表示第 i 年年初给项目A，B，C，D的投资额； 设yiA， yiB，是0—1变量，并规定取 1 时分别表示第i 年给A、B投资，否则取0（ i = 1, 2, 3, 4, 5）。 设yiC 是非负整数变量，并规定：2年投资C项目8万元时，取值为4； 2年投资C项目6万元时，取值为3； 2年投资C项目4万元时，取值为2； 2年投资C项目2万元时，取值为1； 2年不投资C项目时， 取值为0； 这样我们建立如下的决策变量： 第1年 第2年 第3年 第4年 第5年 A x1A x2A x3A x4A B x3B C x2C (=20000y2C) D x1D x2D x3D x4D x5D
§3数规划的应用(6) 2)约束条件: 第 年初有100000元,D项目在年末可收回投资,故第一年年初应把全部资金投出去,于是x1A+x1D 100000; 第二年:A次年末才可收回投资故第二年年初的资金为1.06x10,于是xA+2C+x2D=1.06x10 第三年:年初的资金为1.15x1+1.06x0,于是x3+x32+x3D=1.15x1A+1.06x20 第四年:年初的资金为1.15x21+1.06x0,于是x+xD=1.152+1.06xa0 第五年:年初的资金为1.15x3+1.06x0,于是x=1.15x3+1.06x0 关于项目A的投资额规定:x1≥40000%A,x1A≤200000%A,200000是足够大的数 关于项目B的投资额规定:x3≥3000038,AB≤500004≥ 保证当1A=0时,xA=0;当yA=1时,x1A≥40000 保证当3B=0时,x3B=0;当y3B=1时,50000xB≥ 30000 关于项目C的投资额规定:x2C=20000yc,yc=0,1,2,3,4。 3)目标函数及模型: Maxz=1.15x4+1.40xc+1.28x+1.06 x1A+x1D=100000 x2A+x2c+x2D=1.06x1; X3 1.15x1a+1.06 X4 15x2+1.06 X5D=1.15x3A+1.06x x1A≥40000 X1A≤2000001A, XB≥30000%8, X3≤50000%B xac=20000 y2c 五A,y1B=0或1,i=1,2,3,4,5 2C=0, 2,3,4 x1A,x1B,xc,xiD≥0(i=1、2、3、4、5)
§3整数规划的应用(6) 2）约束条件： 第一年：年初有100000元，D项目在年末可收回投资，故第一年年初应把全部资金投出去，于是 x1A+ x1D = 100000； 第二年：A次年末才可收回投资故第二年年初的资金为1.06x1D，于是x2A+x2C+x2D = 1.06x1D； 第三年：年初的资金为 1.15x1A+1.06x2D，于是 x3A+x3B+x3D = 1.15x1A+ 1.06x2D； 第四年：年初的资金为 1.15x2A+1.06x3D，于是 x4A + x4D = 1.15x2A+ 1.06x3D； 第五年：年初的资金为 1.15x3A+1.06x4D，于是 x5D = 1.15x3A+ 1.06x4D； 关于项目A的投资额规定: x1A ≥ 40000y1A ，x1A ≤ 200000y1A ，200000是足够大的数； 保证当 y1A = 0时， x1A = 0 ；当y1A = 1时，x1A ≥ 40000 。 关于项目B的投资额规定: x3B ≥ 30000y3B ，x3B ≤ 50000y3B ； 保证当 y3B = 0时， x3B = 0 ；当y3B = 1时，50000 ≥ x3B ≥ 30000 。 关于项目C的投资额规定: x2C = 20000y2C ，y2C = 0，1，2，3，4。 3）目标函数及模型： Max z = 1.15x4A+ 1.40x2C+ 1.28x3B + 1.06x5D s.t. x1A+ x1D = 100000； x2A+x2C+x2D = 1.06x1D； x3A+x3B+x3D = 1.15x1A+ 1.06x2D； x4A+x4D = 1.15x2A+ 1.06x3D； x5D = 1.15x3A+ 1.06x4D； x1A ≥ 40000y1A ， x1A ≤ 200000y1A ， x3B ≥ 30000y3B ， x3B ≤ 50000y3B ； x2C = 20000y2C ， yiA， yiB = 0 或 1，i = 1,2,3,4,5 y2C = 0，1，2，3，4 xiA ，xiB ，xiC ，xiD ≥ 0 ( i = 1、2、3、4、5）
§4蓬数规划的分枝定界法(1) 问题(A)Minz=c1x1+c2x2+.+cnx 记问题(B)为去掉整数约束的问题(A) s.t. auX+an x,+...+ain,=b a21x1+a22×x2+…+a2Xn=b2 mi,+am2 x2+.+amn,= b x2,….,xn≥0为整数 在分枝定界法过程中求解问题(B),应有以下情况之一: ①(B)无可行解,则(A)亦无可行解,停止对此问题的计算 ②(B)有最优解,并满足整数约束,即同时为(A)的最优解,那么z同时是当前问题(A)最优 目标值的上界 和下界。停止对这个问题的计算; ③(B)有最优解ⅹ及最优值z但不符合整数条件。这时得到当前问题(A)最优目标值的一个下 界z=z,于是通过以下判断可对此问题进一步计算。 分枝定界法的计算过程 1、对原问题(A),求解松弛问题(B)。根据上面分析,若出现情况①,②则停机。若情况③ 发生,得到(A问题最优值的一个下界。我们任找(A)问题的一个可行解,那么对应的目标 函数值是(A)最优值的一个上界z。即得到z<z<z。(注:找(A问题的可行解往往需 要较大的计算量,这时可简单记z=+∞,而先不必费很大力量去求较好的上界。从以下 分析可以看到,找到一个好的最优目标值上界,将对算法的快速求得目标非常有效。), 转2,进行以下一般步的迭代;
§4整数规划的分枝定界法(1) 问题（A） Min z = c1 x1 + c2 x2 + … + cn xn 记 问题（B）为去掉整数约束的问题（A） s.t. a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a22 x2 + … + a2n xn = b2 …… …… am1 x1 + am2 x2 + … + amn xn = bm x1 ，x2 ，… ，xn ≥ 0 为整数 在分枝定界法过程中求解问题(B)，应有以下情况之一： ①(B)无可行解，则(A)亦无可行解，停止对此问题 的计算； ②(B)有最优解，并满足整数约束，即同时为(A)的最优解，那么z *同时是当前问题(A)最优 目标值的上界 和下界。停止对这个问题的计算； ③(B)有最优解 x 及最优值 z 但不符合整数条件。这时得到当前问题(A)最优目标值的一个下 界 z ＝z ,于是通过以下判断可对此问题进一步计算。 分枝定界法的计算过程： 1、对原问题(A)，求解松弛问题(B)。根据上面分析，若出现情况①，②则停机。若情况③ 发生，得到(A)问题最优值的一个下界。我们任找(A)问题的一个可行解，那么对应的目标 函数值是(A)最优值的一个上界 z¯ 。即得到 z ＜ z * ＜z¯。(注：找(A)问题的可行解往往需 要较大的计算量，这时可简单记 z¯＝+，而先不必费很大力量去求较好的上界。从以下 分析可以看到，找到一个好的最优目标值上界，将对算法的快速求得目标非常有效。)， 转2，进行以下一般步的迭代；