《目标规划培训课程bmlm.pptx》由会员分享，可在线阅读，更多相关《目标规划培训课程bmlm.pptx（103页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1第三章第三章 运输问题运输问题第四章目标规划第四章目标规划第五章第五章 整数规划整数规划4125210391146811求运费最小的运输方案。求运费最小的运输方案。一、引例一、引例某部门三个工厂生产同一产品的产量、四个销售点的销量及单位运价如下表：A1B1B216cijA21012148求最小运费的运输方案？运输问题图示：运输问题图示：产地产地销地销地B3B4A32214共产共产48共销共销48minZ =4x11+12x12+4x13+11x14+2x21+10 x22+3x23+9x24+8x31+5x32+11x33+6x34x11+x12+x13+x14 =16x21+x22+x23
2、+x24 =10 x31+x32+x33+x34 =22x11+x21+x31 =8x12+x22+x32 =14x13+x23+x33 =12x14+x24+x34=14 xij 0i=1,2,3j=1,2,3,4xij 0其中，x11 x12 x13 x14 x21 x22 x23 x24 x31 x32 x33 x34 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 13个4个t1t2t3t4t5t6t77个条件线性相关任6个线性无关基变量6个系数矩阵的特点：系数矩阵的特点：(1)约束条件的系数矩阵的元素只有两个：0、1。(2)元素 xij 对应
3、于每一个变量在前3个约束方程中(第第i个方程中个方程中)出现1次，在后四个约束方程中（第第3+j 个方程中个方程中）也出现1次。(3)产销平衡问题为等式约束。(4)产销平衡问题中各产地产量之和与各销售地点的销量之和相等。(5)运输问题基变量的个数：运输问题基变量的个数：6个A1AmB1B2Bna1cijA2a2ambnb2b1求最小运费的运输方案？求最小运费的运输方案？二.典型的运输问题：典型的运输问题：产地产地销地销地 销地产地B1B2Bn产量A1x11x12x1na1A2x21x22x2na2Amxm1xm2xmnam销量b1b2bnc11c12cm1c21c22c2nc1ncmncm2i
4、=1,2,mj=1,2,nxij 0典型运输问题的数学模型典型运输问题的数学模型:x11 x12 x1n x21 x22 x2n xm1 xm2 xmn1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1mnm*n三、运输问题数学模型的特点：三、运输问题数学模型的特点：1.运输问题一定有最优解；2.运输问题约束条件的系数矩阵的特点：(1)约束条件的系数矩阵的元素只有两个：0、1。(2)元素 xij 对应于每一个变量在前m个约束方程中(第i个方程中)出现一次，在后n个约束方程中（第m+j 个方程中）也出现一次。(3)产销平衡问题为等式约束。(4)产销平衡问题中各产地产量之和与各销售
5、地点的销量之和相等。3.运输问题基变量的个数：运输问题基变量的个数：m+n-1个设对偶变量向量为 Y=(u1,u2,um,v1,v2,vn)对偶规划为 ui+vjcijui、vj 无约束i=1,2,3 m，j=1,2,3 n 产销平衡问题总产量=总销量即产销不平衡问题总产量总销量总产量总销量:总产量P2 P3 Pn 相对优先：目标具有相同的优先因子，但他们的重要程度用权数表示 目标函数：目标函数：通过各目标约束的正、偏差变量和赋于相应的优先等级来构造的。决策者的要求是尽可能从某个方向缩小偏离目标的数值。于是，目标规划的目标函数应该是求极小：1）要求恰好达到目标值，即相应目标约束的正、负偏差变量
6、都要尽可能地小。这时取2)要求不超过目标值，即使相应目标约束的正偏差变量要尽可能地小。这时取3)要求不低于目标值，即使相应目标约束的负偏差变量要尽可能地小。这时取其基本形式有以下三种：建模步骤1.列出全部的约束条件2.把要达到指标的约束不等式加上正、负偏差变量后，化为目标约束等式3.对目标赋予相应的优先因子4.对同一级优先因子中的各偏差变量，若重要程度不一样，可根据题意赋予不同的加权系数5.构造一个按优先因子及加权系数对应的目标偏差量所要实现最小化的目标函数。例例5.25.2：已知某实际问题的线性规划模型为已知某实际问题的线性规划模型为在此基础上考虑：在此基础上考虑：1.Z的值不低于的值不低于
7、1900 2.资源资源1必须全部利用必须全部利用资源资源资源资源1 1 1 1资源资源资源资源2 2 2 2优先因子优先因子P1：约束转换约束转换P2：无级别：无级别：目标目标minf=转化后的模型为s.t.目标目标minf =例4.3：某公司生产两种产品A和B，每周生产线运行时间为60h，生产一台A、B产品分别需要4h、6h。根据市场预测，A、B产品平均销售量分别为每周9台、8台，销售利润分别为12万元、1 8万元。在制定生产计划时，经理考虑下述4项目标：首先，产量不能超过市场预测的销售量；其次，尽量不加班；第三，希望总利润最大；最后，要尽可能满足市场需求；当不能满足时，市场认为B产品的重要
8、性是A产品的2倍。试建立这个问题的数学模型。分析：设决策变量为x1、x2分别为产品A，B的产量。把4个目标表示为不等式：第一个目标为：x19，x28;第二个目标为：4x1+6x260；第三个目标为：希望总利润最大，要表示成不等式需要找到一个目标上界，这里可以估计为252(=12*9+18*8)，于是有12x1+18x2=252；第四个目标为：x19，x28。目标约束：根据决策者的考虑知：第二优先级要求 第三优先级要求第四优先级要求这里，当不能满足市场需求时，市场认为B产品的重要性是A产品的2倍，即减少B产品其影响是A产品的2倍，因此引入2:1的权系数。第一优先级要求综合上述分析，可得到下列目标
9、规划模型：取P=1000 100 10 1考虑目标规划数学模型的一些特点，作以下规定：1）目标函数为求最小化2）非基变量检验数中含有不同等级的优先因子，即j=kjpj ，p1p2pk；从每个检验数的整体看：检验数的正、负首先决定于p1的系数。若a1j0，j0 则此检验数的正、负就决定于p2的系数a2j的正负，依次类推。3)目标规划使用单纯形法求解，di-，di+视为普通变量。P1P2 PL 解目标规划的单纯形例4.1minZ=P1 d1-，P2 d2+，P3 d3-5x1+10 x2+x3 =60 x1-2x2+d1-d1+=0 4x1+4x2+d2-d2+=36 6x1+8x2+d3-d3+
10、=48 x1，x2，x2，di-，di+0,i=1,2,3第一步：minZ=P1 d1-5x1+10 x2+x3 =60 x1-2x2+d1-d1+=0 4x1+4x2+d2-d2+=36 6x1+8x2+d3-d3+=48 x1，x2，x2，di-，di+0,i=1,2,3第二步minZ=P1 d1-，P2 d2+5x1+10 x2+x3 =60 x1-2x2+d1-d1+=0 4x1+4x2+d2-d2+=36 6x1+8x2+d3-d3+=48 x1，x2，x2，di-，di+0,i=1,2,3第三步minZ=P1 d1-，P2 d2+，P3 d3-5x1+10 x2+x3 =60 x1
11、-2x2+d1-d1+=0 4x1+4x2+d2-d2+=36 6x1+8x2+d3-d3+=48 x1，x2，x2，di-，di+0,i=1,2,3CBXBbx1x2p1p2p3x36003648514610-24801000-100001000-10000100-100p1 0P3-10-620-8000100000010000001P1P2p3解:初始单纯形表为：x31000000CBXBbx1x2p1p2p3x36003648010020-21220-51-4-65-146001000-100001000-100 0P300000-2010600-6000010000001P1P2p3
12、x31000000 x1CBXBbx1x2p1p2p3x31224/536/512/50100000112/5-2/5-3/10-1-2/52/53/10001000-10-11/10-3/51/201-1/103/5-1/2000 00000000106000000010001000P1P2p3x31000000 x1x2三个目标均达到CBXBbx1x2p1p2p3x31224/536/512/50100000112/5-2/5-3/10-1-2/52/53/10001000-10-11/10-3/51/201-1/103/5-1/2000 0000000010600000001000100
13、0P1P2p3x31000000 x1x2CBXBbx1x2p1p2p3x320848010010/34/3-4/310/3000-10001001000-10-5/61/6-2/31/600 00000000106000000010001000P1P2p3x31000000 x15/6-1/62/3-1/6l优先目标规划：按照目标先后顺序，逐一满足优先级较高的目标，最终得到一个满意解；等级森严，可能高级目标偏差小，后边的目标偏差比较大分多步进行建模和求解l加权目标规划：各目标没有很明确的优先级，所有的偏差都有相应的权数以偏差加权和为目标函数，求最小值一步建模和求解。加权目标规划：minZ=P
14、1 d1-+P2 d2+P3 d3-5x1+10 x2+x3 =60 x1-2x2+d1-d1+=0 4x1+4x2+d2-d2+=36 6x1+8x2+d3-d3+=48 x1，x2，x2，di-，di+0,i=1,2,3第五章第五章 整数规划整数规划1整数规划的数学模型及其解的特点2解纯整数规划的割平面法3 分枝定界法4 01 型整数规划5 指派问题本章要求理解整数规划的含义掌握分枝定界法的思想和方法掌握0-1变量的含义和用法掌握指派问题的算法第五章第五章 整数规划整数规划1整数规划的数学模型及其解的特点2解纯整数规划的割平面法3 分枝定界法4 01 型整数规划5 指派问题一、整数规划问题
15、整数规划问题（IP）:是指要求部分或全部决策变量的取值为整数的规划问题。模型为模型为j=1,2,mxj 中取部分或全部为整数松弛问题：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题。整数线性规划问题分为以下几种类型：纯整数规划问题（pure integer linear programming）:是指全部决策变量的取值为整数的线性规划问题。混合整数规划问题(mixed integer linear programming):是指决策变量中有一部分必须取整数值，另一部分可以不取整数的线性规划问题。（如：奖金人数及其奖金数额之决策）0-1型整数规划问题(zero-one integer
16、linear programming)是指决策变量只能取0或1的整数线性规划问题。二、应用案例上班时间安排投资组合问题运输问题背包问题例例1.某服务部门各时段（每2h为一时段）需要的服务员人数见下表。按规定，服务员连续工作8h（即4个时段）为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少。9810服务员最少数目321时段411513687583设设 在第j班开始上班的服务员人数为xj.j=18注意：在第j班开始上班的服务员在3班后下班。MinZ=x1+x2+x3+x4+x5+x6+x7+x8x1 10 x1+x2 8x1+x2+x3 9x1+x2+x3+x4 11x2+x3+x4+
17、x5 13x3+x4+x5 8x4+x5 5x5 3xi 0,且为整数问题的数学模型为整数规划证券投资证券投资：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润项目投资项目投资：财团或银行把资金投入到若干项目中以获得中长期的收益最大。投资问题例2：现有资金总额为B。可供选择的投资项目共n个，项目j所需投资额和预期收益分别为aj和cj（j=1n)。此外由于种种原因，有三个附加条件：（1）若选择项目一，必须选项目二，反之不一定。（2）项目3和项目4中至少选择一个；（3）项目5、6、7中恰好选择两个。问：应当怎样选择投资项目，才能使总预期收益最大？模 型 约束 目标总收益最大变量每个项目
18、是否投资(1)选1必选2(2)3、4中必选一(3)5、6、7中恰选两个(4)总金额不超过限制0-1规划模型投资问题（二）投资问题（二）某公司在今后五年内对以下4个项目投资。已知：项目A：从第1-4年每年年初需要投资，于次年末回收本利115%，但要求第一年投资最低金额为4万元，第2-4年不限；项目B：第3年初需要投资，到第5年末能回收本利128，但规定最低投资金额为3万元，最高金额为5万元；项目 C：第2年初需要投资，到第5年末能回收本利140%，但规定其投资额或为2万元或为4万元或为6万元或为8万元。项目 D：5年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。该部门现有资金
19、10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大?解：解：1)设xiA、xiB、xiC、xiD(i 1，2，3，4，5)分别表示第 i 年年初给项目A，B，C，D的投资额；建立如下的决策变量：建立如下的决策变量：第1年 第2年 第3年 第4年 第5年 A x1A x2A x3A x4A B x3B C x2C D x1D x2D x3D x4D x5D 约束条件：约束条件：第1年：年初10万元，D项目在年末可收回投资，故第一年年初应把全部资金投出去，x1A+x1D=10；第2年：A的投资第二年末才收回，故第二年年初的资金为1.06x1D第3年：年初资金：1.
20、15x1A+1.06x2D，第4年：年初资金：1.15x2A+1.06x3D，第5年：年初资金：1.15x3A+1.06x4D，x3A+x3B+x3D=1.15x1A+1.06x2D；x4A+x4D=1.15x2A+1.06x3D；x5D=1.15x3A+1.06x4D。2）关于项目的投资额规定的处理：）关于项目的投资额规定的处理：设yiA，yiB，是01变量，规定第 i 年给A、B投资时取 1，否则取 0（i=1,2,3,4,5）。设yiC 是非负整数变量：第2年不投资C项目时，取0；第2年投资C项目2万元时，取1；第2年投资C项目4万元时，取2；第 2年投资C项目6万元时，取3；第2年投资
21、C项目8万元时，取4；关于项目A第一年投资额规定:x1A 4y1A，x1A 10y1A；保证当 y1A=0时，x1A=0；当y1A=1时，x1A 4。关于项目B的投资额规定:x3B 3y3B，x3B 5y3B；保证当 y3B=0时，x3B=0；当y3B=1时，5 x3B 3。关于项目C的投资额规定:x2C=2y2C，y2C=0，1，2，3，4。3）目标函数及模型：）目标函数及模型：Max z=1.15x4A+1.40 x2C+1.28x3B+1.06x5D s.t.x1A+x1D=10；x2A+x2C+x2D=1.06x1D；x3A+x3B+x3D=1.15x1A+1.06x2D；x4A+x4
22、D=1.15x2A+1.06x3D；x5D=1.15x3A+1.06x4D；x1A 4y1A，x1A 10y1A，x3B 3y3B，x3B 5y3B；x2C=2y2C，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）问题问题：有 n 项不同的任务，恰好 n 个人可分别承担这些任务。由于每人特长不同，完成各项任务的效率也不同。现假设必须指派每个人去完成一项任务，怎样把 n 项任务指派给 n 个人.目标：目标：使得完成 n 项任务的总的效率最高。这就是指派问题。例1有四个工人，要分别指派他们完成四项不同的工
23、作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。指派问题指派问题Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24 +26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.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
24、+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解解：工厂A3或A4开工后，每年的生产费用估计分别为1200万元或1500万元。现要求决定应该建厂A3还是A4，才能使今后每年的总费用最少。选场问题选场问题例：例：两生产地、四需求地、供不应求，需再建一厂。有两个建厂方案。各厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij见表：设xij 表示由Ai运往Bj的物资数量，i,j=14x11+x12+x13+x14 =400 x21+
25、x22+x23+x24 =600 x31+x32+x33+x34 =200 x11+x21+x31 =350 x12+x22+x32 =400 x13+x23+x33 =300 x14+x24+x34=150 xij 0minZ=2x11+9x12+3x13+4x14+8x21+3x22+5x23+7x24+7x31+6x32+x23+2x34+1200建建A3,总费用为：总费用为：x11+x12+x13+x14 =400 x21+x22+x23+x24 =600 x41+x42+x43+x44 =200 x11+x21+x41 =350 x12+x22+x42 =400 x13+x23+x4
26、3 =300 x14+x24+x44=150 xij 0minZ=2x11+9x12+3x13+4x14+8x21+3x22+5x23+7x24+4x41+5x42+2x43+5x44+1500建建A4,总费用为：总费用为：x11+x12+x13+x14 =400 x21+x22+x23+x24 =600 x31+x32+x33+x34 =200yx41+x42+x43+x44 =200(1-y)x11+x21+x31 =350y;x11+x21+x41 =350(1-y);x12+x22+x32 =400y;x12+x22+x42 =400(1-y);x13+x23+x33 =300y;x1
27、3+x23+x43 =300(1-y);x14+x24+x34=150y;x14+x24+x44=150(1-y)xij 0y=0,1 minZ=2x11+9x12+3x13+4x14+8x21+3x22+5x23+7x24 +y(7x31+6x32+x23+2x34+1200)+(1-y)(4x41+5x42+2x43+5x44+1500)y=建A3建A4minZ=2x11+9x12+3x13+4x14+8x21+3x22+5x23+7x24 +7x31+6x32+x23+2x34+y1200+4x41+5x42+2x43+5x44+1500(1-y)1,0,混合整数规划背包(knapsac
28、k)问题背景旅行背包：旅行背包：容量一定的背包里装尽可能的多的物品容量一定的背包里装尽可能的多的物品 一位旅行者出发前准备在自己的背包里携带必需的物品,已知可供选择的物品有n种,第j种物品的重量为aj公斤,其价值为cj,若背包所带物品的总重量不得超过b公斤,问他应如何选择所带物品，以使总价值最大。则背包问题的数学模型如下：则背包问题的数学模型如下：解：设解：设实 例一一个徒步旅行者要在背包中选择一些有价值的物品携带，他最多携带115kg的物品、现共有5件物品，分别重54kg、34kg、57kg、45kg、19kg，其价值依次为7、5、9、6、3.问该旅行者携带哪些物品，使总价值最大？实实 例二
29、例二某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升。根据需要列出需带物品清单：必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）；10件可带可不带物品，如果不带将在目的地购买，通过网络查询知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表试给出一个合理的安排方案把物品放在三个旅行包里.物品物品12345678910体积体积200350500430320120700420250100价格价格1545100705075200902030解：变量变量:xij为第i个物品是否放在第j个包裹中
30、约束约束:包裹容量限制必带物品限制选带物品限制 目标函数目标函数:未带物品购买费用最小未带物品购买费用最小模模 型型固定成本问题例例 高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为 4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为 150 万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。解：这是一个整数规划的问题。设x1，x2
31、，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-200y3s.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分布
32、系统设计分布系统设计例例 某企业在 A1 地已有一个工厂，其产品的生产能力为 30 千箱，为了扩大生产，打算在 A2，A3，A4，A5地中再选择几个地方建厂。已知在 A2，A3，A4，A5地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外，A1产量及A2，A3，A4，A5建成厂的产量，那时销地的销量以及产地到销地的单位运价(每千箱运费)如下表所示。问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小?解：解：设 xij为从Ai 运往Bj 的运输量(单位千箱)，yk=1(当Ak 被选中时)或0（当Ak 没被选中时),k=2,3,4,5这可以
33、表示为一个整数规划问题：Min z=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10 x51+4x52+2x53其中前4项为固定投资额，后面的项为运输费用。s.t.x11+x12+x13 30 (A1 厂的产量限制)x21+x22+x23 10y2 (A2 厂的产量限制)x31+x32+x33 20y3 (A3 厂的产量限制)x41+x42+x43 30y4 (A4 厂的产量限制)x51+x52+x53 40y5 (A5 厂的产量限制)x11+x21+x31+x41+x5
34、1=30 (B1 销地的限制)x12+x22+x32+x42+x52=20 (B2 销地的限制)x13+x23+x33+x43+x53=20 (B3 销地的限制)xij 0，i=1,2,3,4,5；j=1,2,3，yk 为0-1变量，k=2,3,4,5。例.用隐枚举法求解旅行售货员旅行售货员(货郎担货郎担)问题（问题（TSP）有一旅行团从v0出发要游遍城市v1,v2，vn，已知从vi到vj的旅费为cij,应如何安排行程是总费用最小？20个城市个城市哈密顿图：不重复的走遍所有的点再返回出发点哈密顿图：不重复的走遍所有的点再返回出发点哈密顿图：不重复的走遍所有的点再返回出发点哈密顿图：不重复的走遍
35、所有的点再返回出发点。分分 析析变量是否从i 第个城市（出）到第j个城市（进）目标总费用最小 约束每个城市只能离开一次、到达一次数学模型数学模型每座城市恰好出一次每座城市恰好出一次每座城市恰好进一次每座城市恰好进一次直接从直接从vi进入进入vj 其它其它三、整数规划与松弛问题的联系（1）松弛问题（一般线性规划问题）可行解集为一凸集，即任意可行解的图组合仍为可行解。整数规划问题的可行解是松弛问题可行解集的一个子集，但任意两个可行解的凸组合不一定为整数解，故不一定为可行解（2）整数规划问题的可行解一定是松弛问题的可行解，故整数规划最优值不会优于松弛问题的最优值。（3）一般的，松弛问题的最优解不会恰
36、好是整数，故不是整数规划问题的最优解。不可用四舍五入法或去尾法对线性规划的非整数解加以处理来解决整数规划。整数规划问题的求解方法：整数规划问题的求解方法：目前，常用的求解整数规划的方法有：目前，常用的求解整数规划的方法有：割平面法、分支定界法和完全枚举法割平面法、分支定界法和完全枚举法321(一）整数规划图解法x2x1 1 2 3 4 5 6 7（4,2)(18/7,19/7)x1+2x2=8-2x1+3x2=3Max z=x1+4x2s.t.-2x1+3x23 x1+2x28x1,x2 0且为整数A*第二节第二节 解纯整数规划的割平面法解纯整数规划的割平面法模型为模型为xj 取整数一、基本思
37、想找到纯整数线性规划的松弛问题，不考虑整数约束条件，但增加线性约束条件，将松弛问题的可行域切割一部分，但不切割掉任何整数解，只切割掉包括松弛问题的最优解在内的非整数解。设xij,aij,bj全为整数33分枝定界法分枝定界法 分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件，则求出整数规划的上下界 增加约束条件，把相应的线性规划的可行域分成子区域（称为分枝）再求解这些子区域上的线性规划问题 不断缩小整数规划的上下界的距离，最后得整数规划的最优解。分枝定界法是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。例1 用分枝定界法求解整数规
38、划Max 2x1+3x2s.t.195x1+273x21365 4x1+40 x2140 x1 4 x1,x2 0且x1,x2为整数解:(一)先求出以下线性规划的解：Max 2x1+3x2 s.t.195x1+273x21365 4x1+40 x2140 x1 4 x1,x2 0 得z1=14.66,x1=2.44,x2=3.26(二)求最优目标函数值初始上界z*和下界z*。分析后，知道 z*=14.66，由观察法得下界z*=13（x1=2,x2=3）。(三三)将一个线性规划问题分为两支，并求解。将一个线性规划问题分为两支，并求解。可由x12或x13中取值。将线性规划1分解为两支，如下：线性规
39、划2：Max 2x1+3x2 s.t.195x1+273x21365 4x1+40 x2140 x1 4 x1 2 x1,x2 0 解得z2=13.90,x1=2,x2=3.30 线性规划3：Max 2x1+3x2 s.t.195x1+273x21365 4x1+40 x2140 x1 4 x1 3 x1,x2 0 解得z3=14.58,x1=3,x2=2.86(四四)修改整数规划的最优目标函数的上下界。修改整数规划的最优目标函数的上下界。经分析，将上界z*=14.66修改为z*=14.58，z*=13。(五五)在线性规划在线性规划2和线性规划和线性规划3中选择一个上界最大的线性规划，即线性规
40、划中选择一个上界最大的线性规划，即线性规划3，进行分支。，进行分支。线性规划3分解为线性规划4和线性规划5，如下：线性规划4：Max 2x1+3x2 s.t.195x1+273x21365 4x1+40 x2140 x1 4 x1 3 x2 2 x1,x2 0 解得z4=14,x1=4,x2=2 线性规划5：Max 2x1+3x2 s.t.195x1+273x21365 4x1+40 x2140 x1 4 x1 3 x2 3 x1,x2 0 无可行解(六六)进一步修改整数规划最优目标函数值的上下界。进一步修改整数规划最优目标函数值的上下界。从线性规划2，4，5中修改上下界。分析后，可得z*=1
41、4，z*=14,都取线性规划2，4，5中的整数可行解的目标函数值的最大值。性质2：当整数规划的最优目标函数值的上界z*等于其下界z*时，该整数规划的最优解已经被求出。这个整数的最优解即为其目标函数值取此下界的对应线性规划的整数可行解。用图表示例的求解过程与求解结果线性规划线性规划1Z1=14.66X1=2.44X2=3.26z*=13,=13,z*=14.66 线性规划线性规划2Z2=13.90X1=2X2=3.30线性规划线性规划3Z3=14.58X1=3X2=2.86线性规划线性规划4Z4=14.00X1=4X2=2线性规划线性规划5无可行解无可行解X12X13X22X23z*=13,=13,z*=14.58 z*=14,=14,z*=14图图8-28-2