目标规划培训课程课件

1第三章第三章 运输运输(ynsh)(ynsh)问题问题第四章目标规划第四章目标规划第五章第五章 整数规划整数规划第一页，共一百零三页。销地产地B1B2B3B4产量A116A210A322销量8141214484125210391146811求运费最小的运输求运费最小的运输(ynsh)方案。方案。一、引例一、引例某部门三个工厂生产同一产品的产量、四个销售点的销量(xio lin)及单位运价如下表：第二页，共一百零三页。A1B1B216cijA21012148求最小运费(yn fi)的运输方案？运输运输(ynsh)问题图示：问题图示：产地产地(chnd)销地销地B3B4A32214共产共产48共销共销48第三页，共一百零三页。minZ =4x11+12x12+4x13+11x14+2x21+10 x22+3x23+9x24+8x31+5x32+11x33+6x34x11+x12+x13+x14 =16x21+x22+x23+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其中(qzhng)，第四页，共一百零三页。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个条件(tiojin)线性相关任6个线性无关基变量(binling)6个第五页，共一百零三页。系数矩阵的特点：系数矩阵的特点：(1)约束条件的系数矩阵的元素只有两个：0、1。(2)元素(yun s)xij 对应于每一个变量在前3个约束方程中(第第i个方程中个方程中)出现1次，在后四个约束方程中（第第3+j 个方程中个方程中）也出现1次。(3)产销平衡问题为等式约束。(4)产销平衡问题中各产地产量之和与各销售地点的销量之和相等。(5)运输问题基变量的个数：运输问题基变量的个数：6个第六页，共一百零三页。A1AmB1B2Bna1cijA2a2ambnb2b1求最小运费求最小运费(yn fi)的运输方案的运输方案？二.典型的运输典型的运输(ynsh)(ynsh)问题：问题：产地产地(chnd)销地销地第七页，共一百零三页。销地产地(chnd)B1B2Bn产量(chnling)A1x11x12x1na1A2x21x22x2na2Amxm1xm2xmnam销量(xio lin)b1b2bnc11c12cm1c21c22c2nc1ncmncm2第八页，共一百零三页。i=1,2,mj=1,2,nxij 0典型运输典型运输(ynsh)问题的数学模型问题的数学模型: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第九页，共一百零三页。三、运输三、运输(ynsh)问题数学模型的特点：问题数学模型的特点：1.运输问题一定有最优解；2.运输问题约束条件的系数矩阵的特点：(1)约束条件的系数矩阵的元素只有两个：0、1。(2)元素 xij 对应于每一个变量在前m个约束方程中(第i个方程中)出现一次，在后n个约束方程中（第m+j 个方程中）也出现一次。(3)产销平衡问题为等式约束。(4)产销平衡问题中各产地产量之和与各销售地点的销量之和相等。3.运输问题基变量的个数：运输问题基变量的个数：m+n-1个第十页，共一百零三页。设对偶变量向量(xingling)为 Y=(u1,u2,um,v1,v2,vn)对偶规划为 ui+vjcijui、vj 无约束i=1,2,3 m，j=1,2,3 n第十一页，共一百零三页。产销(chnxio)平衡问题总产量=总销量即产销不平衡(pnghng)问题总产量总销量总产量总销量(xio lin):总产量P2 P3 Pn 相对优先：目标具有相同的优先因子，但他们的重要程度用权数表示第三十九页，共一百零三页。目标函数：目标函数：通过各目标约束的正、偏差(pinch)变量和赋于相应的优先等级来构造的。决策者的要求是尽可能从某个方向缩小偏离目标的数值。于是，目标规划的目标函数应该是求极小：1）要求恰好达到目标(mbio)值，即相应目标(mbio)约束的正、负偏差变量都要尽可能地小。这时取2)要求(yoqi)不超过目标值，即使相应目标约束的正偏差变量要尽可能地小。这时取3)要求不低于目标值，即使相应目标约束的负偏差变量要尽可能地小。这时取其基本形式有以下三种：第四十页，共一百零三页。建模步骤(bzhu)1.列出全部的约束条件2.把要达到指标的约束不等式加上正、负偏差变量后，化为目标约束等式3.对目标赋予相应的优先因子4.对同一级优先因子中的各偏差变量，若重要程度不一样，可根据题意赋予不同的加权系数5.构造一个按优先因子及加权系数对应(duyng)的目标偏差量所要实现最小化的目标函数。第四十一页，共一百零三页。例例5.25.2：已知某实际问题已知某实际问题(wnt)(wnt)(wnt)(wnt)的线性规划模型为的线性规划模型为在此基础上考虑：在此基础上考虑：1.Z的值不低于的值不低于1900 2.资源资源1必须全部必须全部(qunb)利用利用资源资源资源资源(zy(zy(zy(zyun)un)un)un)1 1资源资源2 2优先因子优先因子P1：约束转换约束转换P2：无级别：无级别：目标目标minf=第四十二页，共一百零三页。转化(zhunhu)后的模型为s.t.目标目标(mbio)minf =第四十三页，共一百零三页。例4.3：某公司生产两种产品A和B，每周生产线运行时间为60h，生产一台A、B产品分别需要4h、6h。根据市场预测，A、B产品平均销售量分别为每周9台、8台，销售利润分别为12万元、1 8万元。在制定生产计划时，经理考虑下述4项目标：首先，产量不能超过市场预测的销售量；其次，尽量不加班；第三，希望总利润最大；最后，要尽可能满足市场需求；当不能满足时，市场认为B产品的重要性是A产品的2倍。试建立这个问题的数学模型。分析(fnx)：设决策变量为x1、x2分别为产品A，B的产量。把4个目标表示为不等式：第一个目标为：x19，x28;第二个目标为：4x1+6x260；第三个目标为：希望总利润最大，要表示成不等式需要找到一个目标上界，这里可以估计为252(=12*9+18*8)，于是有12x1+18x2=252；第四个目标为：x19，x28。第四十四页，共一百零三页。目标(mbio)约束：根据(gnj)决策者的考虑知：第二(d r)优先级要求 第三优先级要求第四优先级要求这里，当不能满足市场需求时，市场认为B产品的重要性是A产品的2倍，即减少B产品其影响是A产品的2倍，因此引入2:1的权系数。第一优先级要求第四十五页，共一百零三页。综合上述分析，可得到下列目标(mbio)规划模型：取P=1000 100 10 1第四十六页，共一百零三页。考虑目标(mbio)规划数学模型的一些特点，作以下规定：1）目标函数为求最小化2）非基变量检验数中含有不同等级的优先因子，即j=kjpj ，p1p2pk；从每个检验数的整体看：检验数的正、负首先决定于p1的系数。若a1j0，j0 则此检验数的正、负就决定于p2的系数a2j的正负，依次类推。3)目标规划使用单纯形法求解，di-，di+视为普通变量。P1P2 PL 解目标(mbio)规划的单纯形第四十七页，共一百零三页。例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+=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-2x2+d1-d1+=0 4x1+4x2+d2-d2+=36 6x1+8x2+d3-d3+=48 x1，x2，x2，di-，di+0,i=1,2,3第五十一页，共一百零三页。CBXBbx1x2p1p2p3x36003648514610-24801000-100001000-10000100-100p1 0P3-10-620-8000100000010000001P1P2p3解:初始(ch sh)单纯形表为：x31000000第五十二页，共一百零三页。CBXBbx1x2p1p2p3x36003648010020-21220-51-4-65-146001000-100001000-100 0P300000-2010600-6000010000001P1P2p3x31000000 x1第五十三页，共一百零三页。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 00000000106000000010001000P1P2p3x31000000 x1x2三个目标(mbio)均达到第五十四页，共一百零三页。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 00000000106000000010001000P1P2p3x31000000 x1x2第五十五页，共一百零三页。CBXBbx1x2p1p2p3x320848010010/34/3-4/310/3000-10001001000-10-5/61/6-2/31/600 00000000106000000010001000P1P2p3x31000000 x15/6-1/62/3-1/6第五十六页，共一百零三页。l优先目标规划：按照目标先后顺序，逐一满足优先级较高的目标，最终得到一个满意解；等级森严，可能高级目标偏差小，后边的目标偏差比较大分多步进行(jnxng)建模和求解l加权目标规划：各目标没有很明确的优先级，所有的偏差都有相应的权数以偏差加权和为目标函数，求最小值一步建模和求解。第五十七页，共一百零三页。加权目标(mbio)规划：minZ=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+=48 x1，x2，x2，di-，di+0,i=1,2,3第五十八页，共一百零三页。第五章第五章 整数整数(zhngsh)(zhngsh)规划规划1整数规划(guhu)的数学模型及其解的特点2解纯整数规划的割平面法3 分枝定界法4 01 型整数规划5 指派问题第五十九页，共一百零三页。本章要求理解整数规划(guhu)的含义掌握分枝定界法的思想和方法掌握0-1变量的含义和用法掌握指派问题的算法第六十页，共一百零三页。第五章第五章 整数整数(zhngsh)(zhngsh)规划规划1整数规划的数学模型及其解的特点2解纯整数规划的割平面(pngmin)法3 分枝定界法4 01 型整数规划5 指派问题第六十一页，共一百零三页。一、整数规划(guhu)问题整数规划问题（IP）:是指要求部分或全部决策变量的取值为整数的规划问题。模型模型(mxng(mxng)为为j=1,2,mxj 中取部分(b fen)或全部为整数松弛问题：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题。第六十二页，共一百零三页。整数线性规划问题分为以下几种类型：纯整数规划问题（pure integer linear programming）:是指全部决策变量的取值为整数的线性规划问题。混合整数规划问题(mixed integer linear programming):是指决策变量中有一部分必须取整数值，另一部分可以不取整数的线性规划问题。（如：奖金(jingjn)人数及其奖金(jingjn)数额之决策）0-1型整数规划问题(zero-one integer linear programming)是指决策变量只能取0或1的整数线性规划问题。第六十三页，共一百零三页。二、应用(yngyng)案例上班时间安排投资(tu z)组合问题运输问题背包问题第六十四页，共一百零三页。例例1.某服务(fw)部门各时段（每2h为一时段）需要的服务(fw)员人数见下表。按规定，服务(fw)员连续工作8h（即4个时段）为一班。现要求安排服务(fw)员的工作时间，使服务(fw)部门服务(fw)员总数最少。9810服务员最少数目(shm)321时段411513687583设设 在第j班开始上班的服务员人数(rn sh)为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+x5 13x3+x4+x5 8x4+x5 5x5 3xi 0,且为整数(zhngsh)问题(wnt)的数学模型为整数(zhngsh)规划第六十六页，共一百零三页。10530511111231000010=101100015=81110018=91111018=110111113=13001118=8000115=5000015=3第六十七页，共一百零三页。证券投资证券投资：把一定的资金投入到合适(hsh)的有价证券上以规避风险并获得最大的利润项目投资项目投资：财团或银行把资金投入到若干项目中以获得中长期的收益最大。投资(tu z)问题例2：现有资金(zjn)总额为B。可供选择的投资项目共n个，项目j所需投资额和预期收益分别为aj和cj（j=1n)。此外由于种种原因，有三个附加条件：（1）若选择项目一，必须选项目二，反之不一定。（2）项目3和项目4中至少选择一个；（3）项目5、6、7中恰好选择两个。问：应当怎样选择投资项目，才能使总预期收益最大？第六十八页，共一百零三页。模 型 约束(yush)目标(mbio)总收益最大变量每个项目(xingm)是否投资(1)选1必选2(2)3、4中必选一(3)5、6、7中恰选两个(4)总金额不超过限制0-1规划模型第六十九页，共一百零三页。投资问题（二）投资问题（二）某公司在今后(jnhu)五年内对以下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%，此项投资金额不限。该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大?第七十页，共一百零三页。解：解：1)设xiA、xiB、xiC、xiD(i 1，2，3，4，5)分别表示第 i 年年初给项目A，B，C，D的投资额；建立如下的决策建立如下的决策(juc)变量：变量：第1年 第2年 第3年 第4年 第5年 A x1A x2A x3A x4A B x3B C x2C D x1D x2D x3D x4D x5D 约束条件：约束条件：第1年：年初10万元，D项目在年末可收回投资，故第一年年初应把全部(qunb)资金投出去，x1A+x1D=10；第2年：A的投资第二年末才收回，故第二年年初的资金为1.06x1D第3年：年初资金：1.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）关于项目的投资额规定的处理）关于项目的投资额规定的处理(chl)：设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年投资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）目标）目标(mbio)函数及模型：函数及模型：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+x4D=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 个人.目标目标(mbio)：使得完成 n 项任务的总的效率最高。这就是指派问题。例1有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。指派指派(zhpi)(zhpi)问题问题第七十四页，共一百零三页。Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24 +26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.t.x11+x12+x13+x14=1 (甲只能干一项工作(gngzu)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解解：第七十五页，共一百零三页。销地产地B1B2B3B4产量/年A12934400A28357600A37612200A44525200需求量/年350400300150工厂(gngchng)A3或A4开工后，每年的生产费用估计分别为1200万元或1500万元。现要求决定应该建厂A3还是A4，才能使今后每年的总费用最少。选场问题选场问题例：例：两生产地、四需求地、供不应求，需再建一厂。有两个(lin)建厂方案。各厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij见表：第七十六页，共一百零三页。设xij 表示(biosh)由Ai运往Bj的物资数量，i,j=14x11+x12+x13+x14 =400 x21+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+x43 =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;x13+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,混合(hnh)整数规划第七十八页，共一百零三页。背包(bibo)(knapsack)问题背景旅行背包：旅行背包：容量一定容量一定(ydng)(ydng)的背包里装尽可能的多的物的背包里装尽可能的多的物品品 一位旅行者出发前准备在自己的背包里携带必需的物品,已知可供选择的物品有n种,第j种物品的重量为aj公斤,其价值为cj,若背包所带物品的总重量不得(bu de)超过b公斤,问他应如何选择所带物品，以使总价值最大。第七十九页，共一百零三页。则背包则背包(bibo)问题的数学模型如下：问题的数学模型如下：解：设解：设第八十页，共一百零三页。实 例一一个(y)徒步旅行者要在背包中选择一些有价值的物品携带，他最多携带115kg的物品、现共有5件物品，分别重54kg、34kg、57kg、45kg、19kg，其价值依次为7、5、9、6、3.问该旅行者携带哪些物品，使总价值最大？第八十一页，共一百零三页。实实 例二例二某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升。根据需要列出需带物品清单(qngdn)：必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）；10件可带可不带物品，如果不带将在目的地购买，通过网络查询知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表试给出一个合理的安排方案把物品放在三个旅行包里.物品物品12345678910体积体积200350500430320120700420250100价格价格1545100705075200902030第八十二页，共一百零三页。解：变量变量:xij为第i个物品(wpn)是否放在第j个包裹中 约束约束(yush):包裹容量(rngling)限制必带物品限制选带物品限制 目标函数目标函数:未带物品购买费用最小未带物品购买费用最小第八十三页，共一百零三页。模模 型型第八十四页，共一百零三页。固定成本问题例例 高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用(fi yong)，每种容器售出一只所得的利润分别为 4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用(fi yong)：小号是l00万元，中号为 150 万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。资源小号容器中号容器大号容器金属板（吨）248劳动力（人月）234机器设备（台月）123第八十五页，共一百零三页。解：这是一个整数规划的问题。设x1，x2，x3 分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有(zhyu)在生产该种容器时才投入，为了说明固定费用的这种性质，设 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第八十六页，共一百零三页。分布系统设计分布系统设计例例 某企业在 A1 地已有一个工厂(gngchng)，其产品的生产能力为 30 千箱，为了扩大生产，打算在 A2，A3，A4，A5地中再选择几个地方建厂。已知在 A2，A3，A4，A5地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外，A1产量及A2，A3，A4，A5建成厂的产量，那时销地的销量以及产地到销地的单位运价(每千箱运费)如下表所示。销地 产地B1B2B3产量(千吨)A184330A252310A343420A497530A5104240销量(千吨)302020问应该在哪几个地方(dfng)建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小?第八十七页，共一百零三页。解：解：设 xij为从Ai 运往Bj 的运输量(单位千箱)，yk=1(当Ak 被选中时)或0（当Ak 没被选中时),k=2,3,4,5这可以表示(biosh)为一个整数规划问题：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+x51=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。第八十八页，共一百零三页。例.用隐枚举法求解(qi ji)第八十九页，共一百零三页。旅行售货员旅行售货员(货郎担货郎担)问题（问题（TSP）有一旅行团从v0出发要游遍城市v1,v2，vn，已知从vi到vj的旅费(lfi)为cij,应如何安排行程是总费用最小？第九十页，共一百零三页。20个城市个城市(chngsh)哈密顿图：不重复的走遍所有哈密顿图：不重复的走遍所有(suyu)(suyu)的点再返回出发点的点再返回出发点。第九十一页，共一百零三页。分分 析析变量是否(sh fu)从i 第个城市（出）到第j个城市（进）目标(mbio)总费用最小 约束每个城市(chngsh)只能离开一次、到达一次第九十二页，共一百零三页。数学模型数学模型每座城市恰好出一次每座城市恰好出一次每座城市恰好进一次每座城市恰好进一次直接从直接从vi进入进入(jnr)vj 其它其它第九十三页，共一百零三页。三、整数规划与松弛问题(wnt)的联系（1）松弛问题（一般线性规划问题）可行解集为一凸集，即任意可行解的图组合仍为可行解。整数规划问题的可行解是松弛问题可行解集的一个子集，但任意两个可行解的凸组合不一定为整数解，故不一定为可行解（2）整数规划问题的可行解一定是松弛问题的可行解，故整数规划最优值不会优于松弛问题的最优值。（3）一般的，松弛问题的最优解不会恰好是整数，故不是整数规划问题的最优解。不可用四舍五入法或去尾法对线性规划的非整数解加以处理来解决整数规划。第九十四页，共一百零三页。整数规划问题整数规划问题(wnt)的求解方法：的求解方法：目前，常用的求解整数规划的方法有：目前，常用的求解整数规划的方法有：割平面法、分支割平面法、分支(fnzh)定界法和完全枚举定界法和完全枚举法法第九十五页，共一百零三页。321(一）整数(zhngsh)规划图解法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且为整数(zhngsh)A*第九十六页，共一百零三页。第二节第二节 解纯整数规划解纯整数规划(guhu)的割平的割平面法面法模型模型(mxng(mxng)为为xj 取整数(zhngsh)一、基本思想找到纯整数线性规划的松弛问题，不考虑整数约束条件，但增加线性约束条件，将松弛问题的可行域切割一部分，但不切割掉任何整数解，只切割掉包括松弛问题的最优解在内的非整数解。设xij,aij,bj全为整数第九十七页，共一百零三页。33分枝分枝(fn zh)(fn zh)定界定界法法 分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件，则求出整数规划的上下界 增加约束条件，把相应的线性规划的可行(kxng)域分成子区域（称为分枝）再求解这些子区域上的线性规划问题 不断缩小整数规划的上下界的距离，最后得整数规划的最优解。分枝定界法是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。第九十八页，共一百零三页。例1 用分枝定界法求解整数(zhngsh)规划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）。第九十九页，共一百零三页。(三三)将一个线性规划问题将一个线性规划问题(wnt)(wnt)分为两支，并求解。分为两支，并求解。可由x12或x13中取值。将线性规划1分解为两支，如下：线性规划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第一百页，共一百零三页。(四四)修改整数规划的最优目标修改整数规划的最优目标(mbio)函数的上下界。函数的上下界。经分析，将上界z*=14.66修改为z*=14.58，z*=13。(五五)在线性规划在线性规划2和线性规划和线性规划3中选择一个上界最大的线性规划，即线性规划中选择一个上界最大的线性规划，即线性规划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*=14，z*=14,都取线性规划2，4，5中的整数可行解的目标函数值的最大值。性质2：当整数规划的最优目标函数值的上界z*等于其下界z*时，该整数规划的最优解已经被求出。这个(zh ge)整数的最优解即为其目标函数值取此下界的对应线性规划的整数可行解。第一百零二页，共一百零三页。用图表示例的求解过程(guchng)与求解结果线性规划线性规划(xin xn u hu)1Z1=14.66X1=2.44X2=3.26z*=13,=13,z*=14.66 线性规划线性规划(xin xn u hu)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第一百零三页，共一百零三页。