运筹学讲义-单纯形方法

单击此处编辑母版样式,单击此处编辑幻灯片母版样式,第二层,第三层,第四层,第五层,*,*,运筹学,耿修林,9/14/2024,1,五 、 单纯形方法,（一）单纯形方法的初步讨论,1、单纯形方法的基本思想,从可行域中的一个基本可行解出发，判断它是否已是最优解，若不是，寻找下一个基本可行解，并使目标函数得到改进，如此迭代下去，直到找出最优解或判定问题无界为止。,从另一个角度说，就是从可行域的某一个极点出发，迭代到另一个极点，并使目标函数的值有所改善，直到找出有无最优解时为止。,9/14/2024,2,五 、 单纯形方法,（一）单纯形方法的初步讨论,2、单纯形方法：消去法,例求解线性规划模型,解：第一步，将线性规划模型标准化：,Max Z=50x,1,+30x,2,+0x,3,+0x,4,st 4x,1,+3x,2,+x,3,=120,2x,1,+x,2,+ +x,4,=50,x,1, x,2, x,3,x,4,0,9/14/2024,3,2、单纯形方法：消去法,第二步，寻找初始可行解。变量x,3,、,x,4,对应的列,向量A,3、,A,4,可作为初始可行基，那么X,3,、X,4,为基,变量，X,1,、X,2,为非基变量，用非基量表示基变量， 则有：,Max Z=50x,1,+30x,2,+0x,3,+0x,4,st x,3,=120- 4x,1,-3x,2,x,4,=50 -2x,1,-x,2,x,1, x,2, x,3,x,4,0,令x,1,、 x,2,=0，得到基本可行解 X=（0，0，120，50）。,文本,文本,文本,文本,文本,文本,文本,文本,9/14/2024,4,五、 单纯形方法,2、单纯形方法：消去法,第三步，判断目标函数是否达到了最优。,第四步，选取入基变量。确定x,1,为 基变量， x,2,仍为非基变量。,第五步，选取出基变量。,x,3,=120- 4x,1,-3x,2,0,x,4,=50 -2x,1,-x,2,0,解不等式得：x,1,25 ，只有当x,1,=25时， x,4,恰好等于0，所以x,4,确定为出基变量。于是新的典则方程为：,x,1,=25 -,0.5x,2,-,0.5 x,4,x,3,=20 - x,2,+ 2,x,4,9/14/2024,5,（一）单纯形方法的初步讨论,第六步，产生新的基本可行解及目标函数值。令x,2 、,x,4,等于0，得到x,1,=25， x,3,=20，于是新的基本可行解为X=（25，0，20，0），目标函数值为Z=1250。,第七步，判定目标函数值是否得到了最优。根据分析目前的方案还不是最优的。重复第四、五、六步， x,2,入基， x,3,出基，建立新的典则方程：,x,1,=15+ 0.5 x,3,-1.5 x,4,x,2,=20 - 2 x,3,+ 2 x,4,令非基变量x,3,、 x,4,等于0，得到新的基本可行解X=（15，20，0，0），目标函数值为1350。,问题求解完成。,9/14/2024,6,五、 单纯形方法,（二）单纯形方法的矩阵描述,1、线性规划的典则形式：,Max Z=C,B,B,-1,b+(C,N,-C,B,B,-1,N)X,N,St X,B,=B,-1,b-B,-1,NX,N,X,B, X,N,0,2、判别向量与判别数：,（a）=C,N,-,C,B,B,-1,A为对应基B的所有X的判别向量，其中任一分量,j,=c,j,-C,B,B,-1,A,j,为变量x,j,关于基B的判别数，j=1,2, -, n。,9/14/2024,7,五、 单纯形方法,2、判别向量与判别数：,（b）,N,=C,N,-C,B,B,-1,N为对应基B的所有非基变量X,N,的判别向量，其中任一分量,j,=c,j,-C,B,B,-1,A,j,为非基变量x,j,关于基B的判别数，j=m+1,m+2, -, n。,（c）所有基变量的判别向量是零向量，所有基变量的判别数是0（为什么？）。,3、最优解的判定：,（a）如果所有的检验数都小于0，则当前解为最优解。,9/14/2024,8,五、 单纯形方法,3、最优解的判定：,（b）如果至少存在一个检验数大于0，且该检验数对应的列向量中至少有一个正分量，则需要继续进行迭代寻找最优解。,（c）如果至少存在一个检验数大于0，且该检验数对应的列向量的所有分量都小于0，则线性规划问题不存在有界最优解。,9/14/2024,9,五、 单纯形方法,（三）单纯形方法：表上作业法,1、单纯形表的构造,方法1：C-C,B,B,-1,A=(C,B,C,N,)-C,B,B,-1,(B,N),=(0,C,N,-C,B,B,-1,N),两边同乘上X得：,（C-C,B,B,-1,A）X= (0,C,N,-C,B,B,-1,N)X，化简得：,Z=C,B,B,-1,b+(,C,N,-C,B,B,-1,N,),X,N,构造联立方程：,Z+,(,C,B,B,-1,A- C,),X,=C,B,B,-1,b,B,-1,AX =B,-1,b,9/14/2024,10,五、 单纯形方法,1、单纯形表的构造,这样得到单纯形表：,9/14/2024,11,五、 单纯形方法,1、单纯形表的构造,方法2：,X,B=,B,-1,b-B,-1,NX,N,，则有：,X,B,+B,-1,N X,N,=B,-1,b,又 Z=C,B,B,-1,b+(C,N,-C,B,B,-1,N)X,N,，于是：,Z+（C,B,B,-1,N-C,N,）X,N,=C,B,B,-1,b，这样得：,Z+（C,B,B,-1,N-C,N,）X,N,=C,B,B,-1,b,X,B,+B,-1,N X,N,=B,-1,b,构造单纯形表：,9/14/2024,12,五、 单纯形方法,（三）单纯形方法：表上作业法,1、表上作业的步骤：,第一步，将线性规划问题进行标准化处理。,第二步，确定初始基本可行解与初始可行基。,第三步，编制单纯形计算表。,第四步，计算检验数，判断线性规划问题是否有最优解。,第五步，确定入基变量。一是最大检验数准则，二是最,小下标准则。,第六步，确定出基变量。最小检验数对应的基变量出基。,第七步，编制新的单纯形表。重复以上的第四七步，,直到能够确定线性规划问题是否有最优解为止。,9/14/2024,13,五、 单纯形方法,2、单纯形方法：表上作业法,应用举例,求解下列线性规划问题：,Min Z=X,1,-3X,2,S.t. 2X,1,+4X,2,6,-X,1,+3X,2,5,X,1, X,2,0,解： 第一步，将上述问题进行标准化处理：,9/14/2024,14,五、 单纯形方法,应用举例,Max Z=-X,1,+3X,2,S.t. 2X,1,+4X,2,+X,3,=6,-X,1,+3X,2,+ X,4,=5,X,1,X,2,X,3,X,4,0,第二步，确定初始基本可行解与初始基本可行基。,初始可行基： B=（A,3,A,4,）,初始可行解： X=（0，0，6，5）,9/14/2024,15,五、 单纯形方法,应用举例,第三步，构造单纯形表：,-1,3,0,0,C,B,X,B,B,-1,b,X,1,X,2,X,3,X,4,检验数,0,X,3,6,2,4,1,0,3/2,0,X,4,5,-1,3,0,1,5/3,检验数,0,-1,3,0,0,9/14/2024,16,五、 单纯形方法,应用举例,第四步，计算检验数并判断是否是最优解。检验数列在初始单纯形表中的最后一行。,第五步，确定入基变量。 对应的检验数最大，所以确定X,2,为入基变量。,第六步，确定出基变量。计算的检验数列在初始单纯形表中的最后一列。根据出基变量的判别准则，应确定X,3,出基。,9/14/2024,17,五、 单纯形方法,-1,3,0,0,C,B,X,B,B,-1,b,X,1,X,2,X,3,X,4,检验数,3,X,2,1.5,0.5,1,0.25,0,0,X,4,0.5,-2.5,0,-0.75,1,检验数,4.5,-2.5,-0.75,0,第七步，构造新的单纯形表：,9/14/2024,18,五、 单纯形方法,应用举例,第八步，判定迭代到这一步是否应该停止。,因为所有的非基变量的检验数都为负数，因此可以判断迭代到此步的基是最优基，目标函数值为Z=4.5，最优解为X=（0，1.5，0，0）。原问题的最优解为X=（0，1.5，0，0），目标函数值为Z=-4.5。,9/14/2024,19,五、 单纯形方法,（四）确定初始基本可行解的方法,1、对于约束方程中都是小于等于0，并且约束方程右边项皆大于0的情况，只要引进松弛变量即可得到单位阵的初始可行基。,2、如果约束方程都是等于某些值的情况，此时需要引进人工变量才能构造出单位阵的初始可行基和初始可行解。,3、如果约束方程中有大于某些值的情况，则需要引进剩余变量并同时引进人工变量，才能构造出单位阵的初始可行基和初始可行解。,9/14/2024,20,六、 线性规划的其他解法,（一）人工变量消除法M法,1、M法的含义：,通过引进人工变量，构造一个辅助的线性规划问题，然后由辅助的线性规划问题找出原问题的第一个初始可行基，在此基础上，利用单纯形方法求出原问题的最优解。,9/14/2024,21,六、 线性规划的其他解法,（一）人工变量消除法M法,2、M法的辅助线性规划问题：,原问题：,Max z=c,1,x,1,+c,2,x,2,+c,n,x,n,s.t. a,11,x,1,+a,12,x,2,+a,1n,x,n,=b,1,a,21,x,1,+ a,22,x,2,+ +a,2n,x,n,=b,2,a,m1,x,1,+a,m2,x,2,+a,mn,x,n,=b,m,x,1,x,2,x,n,0,9/14/2024,22,六、线性规划的其他解法,（一）人工变量消除法M法,2、M法的辅助线性规划问题：,Max z=c,1,x,1,+c,2,x,2,+c,n,x,n,-MX,n+1,-MX,n+2,-MX,n+m,s.t. a,11,x,1,+a,12,x,2,+a,1n,x,n,+X,n+1,=b,1,a,21,x,1,+a,22,x,2,+ +a,2n,x,n,+,X,n+2,=b,2,a,m1,x,1,+a,m2,x,2,+ +a,mn,x,n,+X,n+m,=b,m,x,1,x,2,x,n,0,9/14/2024,23,六、线性规划的其他解法,3、M法的解题步骤,（1）把原线性规划问题进行标准化处理。,（2）引进人工变量，构造辅助线性规划问题。,（3）运用单纯形方法，把人工变量全部剔除出基变量。,（4）在得到的原问题的初始可行基的基础上，运用单纯形方法进行迭代。,（5）直到能够判断原问题有无最优解时为止。,9/14/2024,24,六、线性规划的其他解法,4、M法解的判定,（1）经过若干次迭代后，基变量中无人工变量，则说明原问题有基本可行解。,（2）经过若干次迭代后，基变量中仍有人工变量，并且全部检验数皆小于0，则表明原问题无可行解。,9/14/2024,25,六、线性规划的其他解法,（二）人工变量消除法两阶段法,1、含义：在原来问题引入人工变量后分两个阶段求解线性规划问题的方法。其中，第一阶段在原来问题中引入人工变量，设法构造一个单位阵的初始可行基，另外在目标函数中令非人工变量的系数全部为0，人工变量的系数为1，构造一个新的辅助目标函数。在此基础上，建立辅助线性规划问题。然后运用单纯形方法求解，直到辅助目标函数为0时为止。第二阶段重新回到原来的问题，以第一阶段得到的可行基为初始可行基，运用单纯形方法以求出原来问题的解。,9/14/2024,26,六、 线性规划的其他解法,（二）人工变量消除法两阶段法,2、两阶段法的辅助问题：,原问题：,Max z=c,1,x,1,+c,2,x,2,+c,n,x,n,s.t. a,11,x,1,+a,12,x,2,+a,1n,x,n,=b,1,a,21,x,1,+ a,22,x,2,+ +a,2n,x,n,=b,2,a,m1,x,1,+a,m2,x,2,+a,mn,x,n,=b,m,x,1,x,2,x,n,0,9/14/2024,27,六、线性规划的其他解法,（二）人工变量消除法两阶段法,2、两阶段法的辅助问题：,辅助问题：,Min Z,/,=X,n+1,+X,n+2,+X,n+m,s.t. a,11,x,1,+a,12,x,2,+a,1n,x,n,+X,n+1,= b,1,a,21,x,1,+ a,22,x,2,+ +a,2n,x,n,+ X,n+2,=b,2,a,m1,x,1,+a,m2,x,2,+a,mn,x,n,+ X,n+m,=b,m,x,1,x,2,，,x,n,0,X,n+1,，X,n+2,，,，X,n+m,0,9/14/2024,28,六、线性规划的其他解法,（二）人工变量消除法两阶段法,3、解的判断：,（1）辅助问题的目标函数值Z,/,0。,（2）假定B为辅助问题最优基，此时若辅助问题的目标函数值Z,/,0，则原问题无解。,证明（请同学们自己做一做）。,（3）辅助问题在最优基B下目标函数的值Z,/,=0，此时有两种情况：第一种情况，若辅助问题的最优基B对应的基变量中无人工变量，则该最优基也是原问题的可行基，这时候只要在单纯形表中去掉人工变量所在的列和最后一行，即可得到原问题的初始可行单纯形表。,9/14/2024,29,六、 线性规划的其他解法,（二）人工变量消除法两阶段法,3、解的判断：,（3）第二种情况，若辅助问题最优基B对应的基变量中还有人工变量，即存在：,y,r,+a,/,rk,y,k,+a,/,rj,x,j,=0,这时需要进行讨论：,第一，若a,/,rj,=0，即有：,y,r,+a,/,rk,y,k,=0,则表明原问题中的第r个约束是多余的，可以从辅助问题单纯形表中，直接划掉这一行。,第二，若a,/,rj,中至少有一个不等于0，则需要以之为转轴元素再进行迭代，直到化为第一种情况为止。,9/14/2024,30,（三） 退化、循环及其处理方法,1、退化问题,在约束系数矩阵A=(a,ij,),mn,（,mn）中，若,R（A） m，则称该线性规划问题是退化的。,2、退化迭代的特点,（1）退化解的基变量中至少有一个取值为0。,（2）退化迭代中基在不断变化但解始终不变。,（3）退化迭代不会引起目标函数值的改进。,3、防止循环迭代的方法,（1）摄动法,（2）字典顺序法,（3）最小下标法,9/14/2024,31,（三） 退化、循环及其处理方法,4、退化问题的单纯形摄动方法,（1）原理,对退化的线性规划问题的右边项作微小的扰动，以避免因退化而引起的循环。,（2）应用举例,9/14/2024,32,七、 电子表格建模及其求解,见Excel中的演示,9/14/2024,33,案例讨论,9/14/2024,34,第四讲 线性规划建模,第一节 线性规划建模的几个问题,第二节 常见的线性规划模型,第三节 案例讨论,9/14/2024,35,第一节 线性规划建模的有关问题,一、线性规划建模的要求与思路,1、要求：繁简适当，要能够反映实际问题的主要因素，得出结论和产生效益。,2、思路,：首先将实际问题简化得能比较容易地建立一个粗略的、可以使用的模型；在这个基础上考虑加进先前被省略掉的一些因素，改进已建立的模型；重复这个过程直到能建立符合要求的模型为止。,9/14/2024,36,第一节 线性规划建模的有关问题,二、线性规划建模的一般过程,1、明确决策变量,2、确定目标函数,3、确立约束方程,4、给出变量取值的限制,9/14/2024,37,第一节 线性规划建模的有关问题,三、参数资料的来源,1、统计资料,2、会计核算资料,3、工程分析,4、实验研究,5、合理规定等,9/14/2024,38,第二节 常见的线性规划模型,一、配料问题,假设有n种原料，已知每种原料都含有m种成分，又已知每种原料的单位成分含量为a,ij,（i=1,2, ,m,j=1,2, ,n）。现欲用这n种原料配制成一种产品，要求单位产品的各种成分的含量为b,i,，如果每种原料的单价为c,j,。问如何配料才能使产品的生产成本最低。,9/14/2024,39,第二节 常见的线性规划模型,二、资源利用问题,生产n种产品，每种产品都要经过m道工序，其中，第j种产品在第i道工序上加工所需要的工时为a,ij,（i=1,2, ,m,j=1,2, ,n）,第i道工序可提供的工时最多为b,i,，第j种产品的单位利润为c,j,。问如何规划各种产品的数量，使获得的利润最大。,9/14/2024,40,第二节 常见的线性规划模型,三、运输问题:,某种物资有m个产地、n个需地，产地产量、需地的需求量及由产地到需地的单位运价如下：,运价,（C）,需求地（B）,产量,（a）,1,2,n,产地,1,11,12,1n,1,2,21,22,2n,2,m,m1,m2,mn,M,需求量（b）,1,2,n,9/14/2024,41,第二节 常见的线性规划模型,三、运输问题：,问如何设计运输方案，才能使运输成本达到最小。,（1）产销平衡 （2）产大于销,（3）产小于销 （4）运力限制等,9/14/2024,42,第二节 常见的线性规划模型,四、投资问题：,设有n个投资项目可供选择，C,j,表示,第j个投资项目的收益率，a表示第i种资源,用于第j个项目的投资数量，b表示第i种资,源的数量，问如何进行投资才能使投资总,收益率最大。,9/14/2024,43,第二节 常见的线性规划模型,五、混合问题：,某石油公司用A、B、C三种原料混合成普通汽油（R）、高级汽油（P）和低铅汽油（L）3种成品出售。3种原料的单位成本及每月最大购入量：,原料 单位成本 最大购入量,A a 100,B b 150,C c 50,9/14/2024,44,第二节 常见的线性规划模型,五、混合问题：,每千克成品油的售价为：普通汽油为d元，高级汽油为e元，低铅汽油为f元。,低铅汽油每月最多销售50吨。,各种汽油的规格如下：,普通汽油R：A少于20%、C不多于30%；,高级汽油P：A不少于40%、B不少于己于10%且不多于20%、C不多于10%；,低铅汽油：B不少于30%。,试建立线性规划模型。,9/14/2024,45,第二节 常见的线性规划模型,六、下料问题：,用某种材料切割m种毛坯，根据经验，单位材料上有n种不同的下料方案，每种下料方案可得各种毛坯数量及每种毛坯的需求量为：,C,下料方案,需求量,B1,B2,.,Bn,毛,坯,名,称,A1,A2,Am,11,12,.,1n,b1,21,22,.,2n,b2,.,.,.,.,m1,m2,.,mn,bm,9/14/2024,46,第二节 常见的线性规划问题,六、下料问题：,问应该怎样安排下料方案，才能是材料的消耗最省。,9/14/2024,47,第二节 常见的线性规划问题,七、分派问题：,设有n件工作B1，B2，.，Bn，分,派给n个人A1，A2，An去做，每,人只做一件工作且每件工作只安排一人,做，Ai完成Bj的工时为Cij。问应如何分,派才能使总工时最省。,9/14/2024,48,第二节 常见的线性规划模型,八、生产进度问题：,某企业生产一种季节性很强的产品，产品只能在k个月内销售，同时生产也要在这些月内进行。除正常生产时间生产外，也可以加班生产，产品在正常生产时间每月最多能生产A个单位，单位成本为a元，加班生产每月最多能生产B个单位，单位成本为b元。当月生产未及时销售出去的需贮存，库存容量为C，贮存费为单位产品c元，k个月的需求量分别为O1、O2,.,Ok。试建立线性规划模型，使得总的生产费用最低。,9/14/2024,49,第四讲 线性规划对偶理论及其应用,第一节 线性规划的对偶问题,一、问题的提出,二、原问题与对偶问题的关系：,（1）原问题求极大（小）对偶问题求极小（大）,（2）原问题目标函数的系数变成对偶问题的约束方程的右边项，同样，对偶问题目标函数的系数是原问题的约束方程的右边项,（3）原问题的变量的个数、主约束的个数分别等于对偶问题的主约束个数和变量的个数,（4）原问题的约束系数矩阵与对偶问题的约束系数矩阵存在转置关系,9/14/2024,50,第一节 线性规划的对偶问题,二、原问题与对偶问题的关系,（5）在原极小问题中的“大于等于”、“小于等于”、“等于”约束，分别与对偶问题中变量的“大于等于0”、“小于等于0”、“无约束”相对应。反之，在原极小问题中的变量“大于等于0”、“小于等于0”、“无约束”分别对应着对偶问题约束中的“小于等于”、“大于等于”、“等于”。,9/14/2024,51,第一节 线性规划的对偶问题,三、原问题与对偶问题的转换,举例说明。,9/14/2024,52,第二节 线性规划的对偶理论,一、原问题与对偶问题是相互对称的。,二、弱对偶定理：,原问题的目标函数值以对偶问题的目标函数值为上界，对偶问题的目标函数值以原问题的目标函数值为下界。,三、无界性定理：,若原问题（对偶问题）为无界解，则对偶问题（原问题）无可行解。,9/14/2024,53,第二节 线性规划的对偶理论,四、最优解性质定理：,X,*,、Y,*,分别是原问题与对偶问题的可行解，若有CX,*,=Y*,b,存在，则X,*,、Y,*,分别是原问题与对偶问题的最优解。,五、对偶定理：,若原问题有最优解，那么对偶问题也有最优解，且目标函数的值相等。,六、互补松弛性定理：,X,*,、Y,*,分别是原问题和对偶问题的可行解，若Y,*,Xs=Ys X,*,，当且仅当X,*,、Y,*,为最优解。,9/14/2024,54,第三节 互补松弛性定理的应用,一、关于互补松弛性定理的几个重要的推论,二、互补松弛定理的应用,应用举例,Max 2X,1,+4X,2,+X,3,+X,4,St X,1,+3X,2,+X,4,8,2X,1,+X,2,6,X,2,+X,3,+X,4,6,X,1,+X,2,+X,3,9,X,1,、X,2、,X,3,、X,4,0,9/14/2024,55,第三节 互补松弛性定理的应用,二、互补松弛定理的应用,其最优解为X=（2，2，4，0），目标函数值为16。试运用互补松弛定理求对偶问题的最优解。,9/14/2024,56,第三节 互补松弛定理的应用,三、对偶解的解释,1、对偶解与影子价格,2、检验数与边际贡献,9/14/2024,57,第四节 对偶单纯形方法,一、对偶单纯形方法的基本思想,从对偶问题的可行解和原问题的不可行解出发，进行换基迭代，一旦当原问题的解也变成可行解时，这时的解就是原问题的最优解。,二、对偶单纯形方法与原单纯形方法的区别,1、原单纯形方法从可行解和对偶问题不可行解出发，直到所有的检验数皆小于等于0，而对偶单纯形方法则从对偶可行解和原问题不可行解出发，直到原问题的解也变成可行。,9/14/2024,58,第四节 对偶单纯形方法,二、对偶单纯形方法与原单纯形方法的区别,2、最优解的判定标准不一样。,3、确定出入基变量的顺序不同。原单纯形方法，先确定入基变量后再确定出基变量，而对偶单纯形方法先确定出基变量后确定入基变量。,4、确定出入基变量的方法不同。,9/14/2024,59,第四节 对偶单纯形方法,三、对偶单纯形方法的解的判定,1、B,-1,b,0，表明已求出了原问题的最优解。,2、 B,-1,b,中至少有一个负分量，且该负分量所在行的各元素都是非负数，则问题无最优解。,3、 B,-1,b,中至少有一个负分量，且该负分量所在行的元素中存在负数，则需要继续迭代。,9/14/2024,60,第四节 对偶单纯形方法,四、对偶单纯形算法的过程,1、对问题进行标准化处理,2、确定一个初始的对偶可行解,3、编制对偶单纯形表,4、判定目标函数是否达到最优,5、换基迭代，直到能判定问题有无最优解时为止。,五、应用举例,9/14/2024,61,第五节 敏感性分析,一、敏感性分析的含义,由于受到政策、价格、工艺水平、资源贮备、设备更新等若干因素的影响，线性规划模型中的参数C、A、,b,经常会发生变化，那么C、A、,b,在什么样的范围内变化，才不会导致已求出的最优基的改变，这就是敏感性分析所要解决的问题。,9/14/2024,62,第五节 敏感性分析,二、目标函数系数C变化的敏感性分析,1、单个目标函数系数C,j,变化的情况,（1）C,j,为非基变量的目标函数系数,（2） C,j,为基变量的目标函数系数,2、多个目标函数系数变化的情况,（1）变化的目标函数系数都是非基变量,（2）变化的目标函数系数中有一个是基变量，其他的是非基变量,（3）变化的目标函数系数中有多于一个基变量,9/14/2024,63,第五节 敏感性分析,三、右边项发生变化的敏感性分析,1、单个右边项发生变化,2、多个右边项发生变化,四、增加新变量的敏感性分析,在原问题中增加新变量，会导致约束系数矩阵的列向量增加，同时也会增加检验数的个数。如果增加新变量后，新变量的检验数仍小于0，则最优解保持不变，否则最优解会发生变化。,五、增加新约束的敏感性分析,1、如果原问题的最优解满足新约束条件，则最优解保持不变。,2、如果原问题的最优解不满足新约束条件，则需要寻找新的最优解。,9/14/2024,64,第六讲 整数规划,第一节 概述,一、概念,对决策变量的取值有整数限制的规划问题，称为整数规划。,二、整数规划的分类,1、线性整数规划与非线性整数规划,2、纯整数规划与混合整数规划,9/14/2024,65,第一节 概述,三、线性整数规划的模型,Max Z=CX,St AX(=、),b,X0,且取整数,9/14/2024,66,第一节 概述,四、整数线性规划与一般线性规划的关系,1、对整数线性规划的整数约束的放松，便得到一般的线性规划，反之，对一般线性规划增加变量取整的要求，则便变成整数线性规划。因此，整数线性规划的约束比一般线性规划的约束更紧。,2、整数线性规划的可行域是一般线性规划问题可行域的子集。,3、整数线性规划问题的目标函数值以一般线性规划问题目标函数值为界，即整数线性规划问题的最优值，不可能优于一般线性规划问题的最优值。,9/14/2024,67,第二节整数线性规划的几个典型模型,一、背包问题,一个背包的容积为V，现有n种物品待装，物品的重量为w,j,，体积为v,j,j=1,2, ,n，问如何配装才能使得既不超过背包的容量，又能装入的物品重量最大。,二、工厂的选址问题,有n城市1,2, ,n，需要某种物资的数量分别为d,1, d,2, ,d,n,，现欲打算建造m座工厂，假设在城市j建厂，规模为s,j,，需要投资为f,j,，从城市i到城市j的单位运输费用为c,ij,，问m座工厂应分设在何处比较合适。,9/14/2024,68,第二节整数线性规划的几个典型模型,三、加工问题,有m台同类型的机床，有n种零件要在这些机床上进行加工，设加工的时间分别是a,1,a,2,a,n,，问如何分配才能使各机床的总加工任务相等，或尽可能均衡。,四、旅游推销问题,一个旅游推销商从家门口A,0,出发，经过预先确定的村子A1，A2，An，然后回到家，假定村子Ai到村子Aj的距离为dij,问如何确定一条行走路线，经过所有要去的村庄，且使总的行走路程最短。,9/14/2024,69,第三节 分枝定界法,一、“公理”,1、对一个整数线性规划问题，如果不考虑变量取整的要求，由此求得的整数最优解X，也一定是整数线性规划问题的最优解。,2、对于一个整数非线性规划问题，如果不考虑变量取整的要求，由此求得的非整数最优解，则一定可以断定整数线性规划问题的最优解不会好于非整数最优解。,3、在求解的过程中最先出现的整数解，不会好于最优整数解。,9/14/2024,70,第三节 分枝定界法,二、分枝定界的含义,1、分枝的含义。,按“公理”的要求，对一般线性规划的可行域进行分解。,2、定界的含义,通过分枝不断调整整数最优解的上下界。,9/14/2024,71,第三节 分枝定界法,三、分枝定界法的解题思路,1、对于给定的整数线性规划问题，先不考虑变量取整的要求，把它当作一般的线性规划问题来处理，并求其最优解，如果该最优解都是整数，则同时也就得到了整数线性规划问题的最优解，问题求解到此为止。,2、若由一般线性规划求出的最优解不是整数解，假定基变量X,k,=b,/,k,不是整数，那么作如下处理:b,/,k,b,/,k,b,/,k,+1。,3、构造两个新的约束方程，并把它们分别加到问题中去，形成两个整数规划问题。,9/14/2024,72,第三节 分枝定界法,两个新的约束方程为：,X,k,b,/,k, X,k,b,/,k,+1,两个新的整数规划问题为：,（I） Max Z=CX （II） Max Z=CX,St AX(=、),b,St AX(=、),b,X,k,b,/,k, X,k,b,/,k,+1,X0,且取整数 X0,且取整数,9/14/2024,73,第三节 分枝定界法,4、分别按一般线性规划求解这两个整数规划，直到能够确定整数规划的最优解或能够判定其无最优解时为止。,9/14/2024,74,第三节 分枝定界法,分枝定界法解的判定标准,（I） （II） 说明,无可行解 无可行解 整数规划无解,无可行解 整数解 （ II）的解为最优解,无可行解 非整数最优解 对（II）继续求解,整数解 整数解 较优解为最优整数解,整数解且,目标函数,优于（II） 非整数 （I）的解为最优解,整数解 非整数解且,目标函数优于（I） 只对（II）继续求解（I）的解为最优解,9/14/2024,75,第三节 分枝定界法,五、分枝定界法的应用,求解下列规划问题：,Max Z=6x,1,+4x,2,st 2x,1,+4x,2,13,2x,1,+x,2,7,x,1,、,x,2,0且取整数,9/14/2024,76,第四节 割平面法,一、割平面法的基本思想,解整数规划时，先不考虑变量取整的要求，把它当作一般的线性规划问题来处理，假定X为一般规划问题的最优解，如果X是整数，则得到整数规划的最优解，如果X不是整数，则构造一个约束方程，使X不满足该方程，但原问题的所有整数可行解却满足该方程，然后再解增加约束后的线性规划问题，直到求出最优解为止。,9/14/2024,77,第四节 割平面法,二、割平面构造问题,三、应用举例,9/14/2024,78,