A第五章线性规划or1.ppt

第五章线性规划,1运筹学的发展历史（OperationsResearch）第二次世界大战高射炮阵地火力的配置，武器库设置问题等英国雷达、新式武器演示及评价（1938）“作业研究”Erlang1917的排队论；美国数学家G.B.Dantzig的线性规划求解问题（1947）；T.C.Koopmans的运输问题;很多诺贝尔奖金得主的工作与运筹约有关。60年代华罗庚“优选法、统筹方法”，国防科技的计划评审技术。计算机运筹学的发展实际问题的最优与满意解。,2OR的内容和分支,规划论:线性规划、非线性规划、整数规划、动态规划图论与网络分析（哥尼斯堡七桥）排队论（打饭问题）库存理论图与网络计划对策论齐王赛马，矩阵对策决策论“管理就是决策”，决策的原则、决策的方法等多目标规划等,3OR特点,理论和实践，合理利用(人、财物、时、空等信息)寻求满意效果；实践性强，寻最优化的方案；系统的观点，全局性规划，多方法的总和（单个系统而非大系统）。是以定量的模型化方法来描述和解决问题（本质）；应用的普遍性。,运筹学的研究给管理工作带来巨大效益；用数学语言揭示管理过程和规律；用定量的方法来研究管理问题；管理科学包括定性和定量两部分。,5运筹学与管理科学,4基本过程,分析和表达问题；建立模型数学模型,网络模型,图论模型,仿真模型等；求解模型，即寻找方案；检验(对解的最优性进行检验)；方案的分析、评价、实施；,军事运筹学；农业运筹学；交通运输系统运筹学；公共卫生运筹学运筹学与计算机科学运筹学与优化技术之间的关系,6运筹学与控制论（Cybernatics）,优化与控制观点的区别控制论的主要分之控制论与运筹学、管理科学的关系,7运筹学与其它学科的关系,第一节线性规划问题（LinearProgramming）,教学目的：重点引入线性规划问题的模型、几何性质、单纯形解法和线性规划的对偶定理。应理解和掌握线性规划的几何性质和求解原理，能针对实际问题，建立相应的线性规划模型。,重点：线性规划问题的求解方法、解的基本性质以及对偶原理。,难点：线性规划的单纯形法求解思想、矩阵表述、对偶理论以及灵敏度分析,问题1：某工厂计划生产甲、乙两种产品。所需的设备台时及A、B两种原材料消耗，详见下表,该工厂每生产一件甲产品可获利2元，每生产一件乙产品可获利3元，问如何安排生产计划，可使利润最大？,1.1线性规划问题及其数学模型,解：设x1，x2分别为甲、乙产品的数量，则有约束条件x1+2x284x1164x212x10，x20，称x1，x2为决策变量,目标函数maxz=2x1+3x2,问题2：运输问题的运价、产量、销量如下表，如何安排调运，运费最小？,解：设xij为从产地运往销地的物资数量(i=1,2；j=1,2,3),则有目标函数：minz=2x11+x12+3x13+2x21+2x22+4x23约束条件:x11+x12+x13=50 x21+x22+x23=30 x11+x21=40 x12+x22=15x13+x23=25xij0i=1,2；j=1,2,3,总结：线性规划三要素：决策变量、目标函数、约束条件线性规划的特点:目标线性、约束条件为线性不等式或等式,一般情况下，其值均是正的,其中：C价值向量A系数矩阵b资源向量,其它表示形式：形式：max(min)Z=cixjs.taijxj,=,bi，i=1,2,mxj0，j=1,2,n向量形式:max(min)Z=cixjs.tPjxj,=,bi,i=1,2,mxj0，j=1,2,n矩阵形式:max(min)Z=CXs.tAX,=,bX0,线性规划问题模型的标准型,任意线性规划模型转化为标准型的方法,1、目标最小化：minZ=max(Z)=maxZ2、约束条件为不等式：“”引进非负松弛变量xk0,(减去)松弛变量,对应于xk的目标系数取为零。“”引进松弛变量xl0,(加入)松弛变量,对应于xl的目标系数取为零。3、决策变量xk是自由变量(无非负限制)，或xj有上下界限制是可以引进新的变量，转化为变量0形式。例如xk是自由变量，引进xl0,xm0,新变量，令xk=xl-xm，对应的目标系数仍为ck。4、当bi小于零的时候，在等式两边同时乘以-1即可。“小加、大减、一变二”,2.1、图解法:图解法不是解线性规划的主要方法,只是用于说明线性规划解的性质和特点。只能解两个变量问题。（用图解法求解,线性规划不需要化成标准型）图解法的步骤：1、约束区域的确定2、目标函数等值线3、平移目标函数等值线求最优值,2线性规划图解法,线性规划解的几种可能情况1、唯一最优解2、无穷多最优解3、无可行解4、无有限最优解(无界解),例1：maxz=2x1+3x2x1+2x284x116x1，x20,有唯一解,画图步骤：1、约束区域的确定2、目标函数等值线3、平移目标函数等值线求最优值,有无穷多解,两个顶点处达到最优解,例2：,约束条件围不成区域(又称矛盾方程),无可行解,例3：,Maxz=4x1+3x2-3x1+2x26s.t-x1+3x218x1,x20,无有限最优解(无界解),例4：,线性规划的几何特性：,线性规划问题若有最优解,一定在其可行域的顶点达到;有最优解(唯一最优解必在一个顶点达到或无穷多最优解至少在两个顶点达到);无解(可行域为空集或目标函数无有限极值),图解法得出线性规划问题解的几种情况,问题:围成无界区域就不能有唯一解吗?,列向量x=(x1，x2，xm）T为m维列向量。xRn线性相关一组向量v1,vn,如果有一组不全为零的系数1,n,使得:1v1+nvn=0则称v1,vn是线性相关的.线性无关一组向量v1,vn,如果对于任何数1,n,若要满足:1v1+nvn=0,则必有系数1=n=0,(全为零)则称v1,vn线性无关.矩阵A的秩设A为一个mn阶矩阵(m0的数乘（2）式在分别与（1）相加和相减，这样得到(x1-1)P1+(x2-2)P2+(xm-m)Pm=b(x1+1)P1+(x2+2)P2+(xm+m)Pm=b,引理2若K是有界凸集,则任何一点XK可表示为K的顶点的凸组合.证明略。,必要性（基可行解顶点，用反证法）：X不是可行域的顶点,故可在可行域内找到两个不同的点x(1),x(2)，使得x=x(1)+(1-)x(2),0m时,有xj=xj(1)=xj(2)=0,由于x(1),x(2)是可行域的两点.应满足Pjxj(1)=b与Pjxj(2)=b将这两式相减,即得Pj(xj(1)-xj(2)=0因X(1)x(2),所以上式系数(xj(1)-xj(2)不全为零,故向量P1,P2,Pm组线性相关与假设矛盾.即X不是基可行解.,定理3若可行域有界,线性规划问题的目标函数一定可以在其可行域的顶点上达到最优.,证：设X(1),X(2),X(k)是可行域的顶点,若X(0)不是顶点且目标函数在X(0)处达到最优z*=CX(0)(不妨设标准型是z*=maxz),则X(0)可以用顶点表示为X(0)=iX(i)i0,i=1记X(1),X(2),X(k)中使maxCX(i)的顶点为X(m)。于是，由假设CX(0)为最优解，所以CX(0)=CX(m)，即最优解可在顶点X(m)达到。,注：1有时目标函数可能在多个顶点处达到最大值，此时在这些顶点的凸组合处也达到最大值，称这种线性规划问题有无限多个最优解。2若可行域无界，则可能无最优解，也可能有最优解，但若有，必在顶点处取得。,3单纯形法（SimplexMethod）,例子：求解线性规划问题,LP规划问题的最优解，可以从基可行解中找到。图解法有局限性；枚举法计算量大；,3.1单纯形法的引入,解:首先:将该问题化成标准形,第二:找初始可行解(即一个顶点)。系数矩阵A=(p1p2p3p4p5),矩阵形式,因为p3，p4，p5线性独立，故B=(p3,p4,p5)构成一个基底，对应的基变量x3，x4，x5解出来为（用非基变量表示基变量）x3=8-x1-2x2x4=16-4x1(1)x5=12-4x2将(1)代入目标函数中得z=0+2x1+3x2令非基底变量x1=x2=0，则有z=0。这时得到一个基可行解X(0)=(0,0,8,16,12)T-原点,第三:判别从目标函数中得知，非基底变量的系数为正，因此，将非基变量换入基底后可使目标函数增大，转入第四步,第四:换基底(旋转迭代)确定换入变量：由于z=0+2x1+3x2中非基底变量x2系数贡献最大3，故换入基底为x2。换入变量已定，必须从x3，x4，x5换出一个，并且要保证其余均是非负的，即x3，x4，x50。x3=8-2x20 x4=160 x5=12-4x20由此，只要选择x2=min(8/2，-，12/4)=3，对应基底变量x5=0，从而确定用x2和x5对调，即将x5换出。有x3=2-x1+1/2x5x4=16-4x1(2)x2=3-1/4x5,x3+2x2=8-x1x4=16-4x14x2=12-x5用高斯消去法（行变换），得x3=2-x1+1/2x5x4=16-4x1x2=3-1/4x5,将(2)代入目标函数中得z=9+2x1-3/4x5令非基变量为零，又得到另一个基可行解X(1)=(0,3,2,16,0)T顶点Q4返回第三步，可知不是最优解，确定x1为换入变量。由于min(2/1,16/4,-)=2，对应基底变量x3为换出变量，对调整理得,代入目标函数中得z=9+2x1-3/4x5令X1=X5=0，得Z=9，及另一可行解X(1)X(1)=（0，3，2，16，0)T新顶点Q4返回第三步：非基变量x1的系数是正的，还可增大，X(1)不是最优解。重复上述步骤。由于x1的系数是正的，从而x1为转入变量，再由x3=2-x10 x4=16-4x10 x2=30,只要选x1=min2，16/4，-=2上式就成立，因为x1=2时，基变量x3=0，从而由x1换出x3，得x1=2-x3+1/2x54x1+x4=16(3)x2=3-1/4x5高斯消去法（行变换）得,x1=2-x3+1/2x5x4=8-2x5+4x3x2=3-1/4x5,代入目标函数中，得z=13-2x3+1/2x5令非基变量x3=x5=0，又得到另一个基可行解X(2)X(2)=(2,3,0,8,0)T新顶点Q3;同理,返回第三步，再迭代，x5作为转入变量x1=2+1/2x50 x4=8-2x50 x2=3-1/4x50,只要取x5=min-，8/2，12=4就有上式成立。x5=4时，x4=0，故决定用x5换x4x1=4-x4x5=4-1/2x4+2x3x2=2+1/8x41/2x3代入得z=14-3/2x31/8x4，令x3，x4=0得z=14。新基可行解为X(3)=(4,2,0,0,4)T为最优解，新顶点Q2最优目标值z=14。,如下图所示,0,Q4,Q3,第三步：从初始基可行解向相邻的基可行解（顶点）转换，且使目标值有所改善目标函数值增加，重复第二和第三步直到找到最优解。,从实际例子中分析单纯形法原理的基本框架为第一步：将LP线性规划变标准型，确定一个初始可行解（顶点）。第二步：对初始基可行解最优性判别，若最优，停止；否则转下一步。,3.2初始可行基的确定,设线性规划问题：,为了确定初始基可行解，首先要找出初始可行基，其方法如下：从Pj(j=1,2,n)中一般能直接观察到存在一个初始可行基,“小加大减+人造”,约束是形式的不等式，可以利用化标准型的方法，左端加一个松弛变量，经过整理，重新对xj及aij（i=1,2,m；j=1，2，n）进行调整编号，则可得下列方程组,“小加”,x1+a1,m+1xm+1+a1nxn=b1x2+a2,m+1xm+1+a2nxn=b2xm+am,m+1xm+1+amnxn=bmxj0，j=1,2,n,显然得到一个mm单位矩阵,注意：aij和bi已经变化,以B作为可行基，移项整理得x1=b1-a1,m+1xm+1-a1nxnx2=b2a2,m+1xm+1-a2nxnxm=bmam,m+1xm+1-amnxn令xm+1=xm+2=xn=0，可得xi=bi（i=1，2，m）又因bi0，所以得到一个初始基可行解：X（0）=（x1,x2,xm，0,0)T=(b1,b2,bm,0,0)T,对约束条件是“”形式的不等式时，减一个非负的剩余变量（变成标准型），若不存在单位矩阵，则同时加一个非负的人工变量（人造基方法），可以找到一个初始基；等式约束，加人工变量(两阶段法,大M法)。下一节讲。注：松弛变量（剩余变量）、人工变量本身均是非负的。,判别准则？,3.3最优性检验和判别定理,分块矩阵表示：,检验数,基可行解,最优值,定义：为检验数。,证明：构造新的解,验证可行性：因为,每一个aij和bi均带“撇”,3.4基变换换入变量的确定:max(j0)=k,j=m+1,n;xk是换入变量(也可任选).换出变量的确定:确定换出变量的原则是保持解的可行性,就是说要使原基可行解的某一正分量xl变成零,同时保持其它的分量均非负(换基原则)min(bi/aij|aij0)=bl/alk=l,l1,2,m定换出变量(最小比值准则,或准则),3.5旋转运算在确定换入变量xk和换出变量xl以后，要把xk所对应的系数列向量pk变成单位向量，为此,只要对系数矩阵的增广阵进行“行”的初等变换即可。行变换的定义：,较特殊的情况(基矩阵是单位矩阵情形)1.基可行解x1+a1m+1+a1k+a1n=b1xm+amm+1+amk+amn=bm基变量xB=(x1,x2,xm),xN=(xm+1,xm+2,xn);基可行解(b1,bm,0,0)2.检验和判别是最优解,停;否,转下步.3.基变换换入变量:max(j0)=k,j=m+1,n;xk换出变量:min(bi/aij|aij0)=bl/alk=l,l1,2,m(最小比值准则,或准则)pk=(a1k,a2k,amk)T,pl=(0,.,1,0)T,4.旋转:x1.xl.xmxm+1xkxnb1a1m+1a1ka1nb11alm+1alkalnbl1amm+1amkamnbm(第l行)乘1/alk得:(0,0,1/alk,0,0,alm+1/alk,1,aln/alk|bl/alk)(第i行)-(第l行)乘aik)当il得(0,0,aik/alk,0,0,aim+1-alm+1/alkaik,0,ain-aln/alkaikbi-bl/alkaik),x1.xlxmxm+1xkxnb1-a1k/alk.0a1m+10a1nb11/alk0alm+1alkalnbl-amk/alk1amm+10amnbm新基变量xB新非基变量XN新基I新基可行解X(1),4单纯形法的计算步骤和单纯形表总结成“单纯形表格”x1+a1m+1+a1k+a1n=b1xm+amm+1+amk+amn=bm-z+c1x1+cmxm+cm+1xm+1+cnxn=0矩阵形式:-Zx1.xmxm+1xkxnb01a1m+1a1ka1nb10001amm+1amkamnbm1c1cmcm+1cn0,作行变换之后变成01a1m+1a1nb10001amm+1amnbm100cm+1-ciam+1cn-ciain-cibi,对给定的线性规划问题寻优可以用表格进行,即单纯形表如下,得到一个基可行解,z,0,若不是最优解,则有某个非基底变量,x,p,对应的检验,数,p,=(c,p,-z,p,),0,将,x,p,换入基底,目标一定会比原,z,0,要优。取使目标增长最,大的非基底变量进入基底。亦即,确定换入变量：,当,max,（,j,0,）,=,k,，确定,x,k,换入变量,在确定换出变量：当,min,，确定,x,l,换入变量,将交叉元素,（主轴元素）,a,lk,单位化，即乘以初等矩阵。重复上述步骤直到所有的,检验数满足最优条件，得最优解。,将交叉元素（主轴元素）alk单位化，(旋转)x1，xl，xm，xm+1，xk，xnb1a1m+1a1ka1nb11alm+1alkalnbl1amm+1amkamnbm第一步(第l行)乘1/alk得(0,0,1/alk,0,0,alm+1/alk,1,aln/alkbl/alk)第二步(第i行)-(第l行)乘aik/alk当il得(0,0,aik/alk,0,0,aim+1-alm+1/alkaik,0,ain-aln/alkaikbi-bl/alkaik)整理上述例题的求解过程为单纯形表如下,整理上述例题的求解过程为单纯形表如下,1.5单纯形法的进一步讨论,人工变量法（确定初始可行基）：,原约束方程：AX=b,加入人工变量：xn+1，xn+m,人工变量是虚拟变量，加入原方程中是作为临时基变量，经过基的旋转变换，将人工变量均能换成非基变量，所得解是最优解；若在最终表中检验数小于零，而且基变量中还有某个非零的人工变量，原问题无可行解。,1、大M法方法：在约束条件中，加入人工变量后，要求目标函数不受影响？目标函数中人工变量的系数取（-M）。,理由：目标函数实现最大化，就必须将人工变量从基变量中换出，否则目标函数就不可能取得最大化。,例1：用大M法求解如下线性规划问题。,cj,最优解是,目标函数为-2。,2、两阶段法,第一阶段：,建立一个辅助线性规划，并求解，以判断原线性规划是否存在可行解。辅助线性规划问题：目标函数取成所有的人工变量之和，并对目标函数取极小化，约束条件依然为原问题的以单位矩阵作为可行基的标准形的约束条件。所有人工变量都变成非基变量，目标函数最小值为0，原问题存在基可行解。转到第二阶段。若目标函数大于0，至少有一个人工变量不能从基变量中转出，由于它取正值，原问题没有可行解。停止。,第二阶段：,将第一阶段最优表格中去掉人工变量，将目标函数系数换成原问题的目标函数系数，接下去用单纯形法计算，直到得到最优解为止。,例2：同上,第一阶段：求解辅助规划问题,cj,x6，x7是人工变量，第一阶段求解的最优结果是=0，因此得最优解为：,第二阶段：取消人工变量，添入原问题目标函数的系数，求解相应的线性规划。,最优解为：,最优值为：z=-2,两阶段法：辅助规划；去掉人工变量，单纯形法。,对目标函数求max的线性规划问题,用单纯形法计算步骤的框图,第二章对偶理论与灵敏度分析,2.1单纯形法的矩阵描述线性规划Maxz=CXMaxz=CX+0XsAXbAX+IXs=bX0X0,Xs0其中I是mm单位矩阵，松弛变量Xs=(xn+1,xn+2,xn+m)T.设B是一个可行基矩阵，N表示非基底变量的系数矩阵(A，I)(B，N)对应决策变量,对应目标系数,原线性规划可改写为：,约束条件,单纯形表的几个特征:1、检验数:非基底的检验数(等于对应的目标系数)cjzj=(CNCBB-1N)基变量的检验系数为零，即cjzj=CBCBB-1B=0,进一步，非基底变量可分解XN（XN1，Xs），其中XN1表示除去人工变量以后的非基变量；Xs是人工变量，其目标系数为零。,Xs非基底的检验数cjzj=(0CBB-1)=CBB-1所有的检验数可用CCBB-1A与CBB-1表示,这里(B-1b)i是向量(B-1b)中的第i个元素，(B-1Pj)i是向量(B-1Pj)中的第i个元素，j=1,2,n,2、规则的表达形式,3、单纯形表的矩阵表达形式将目标和约束条件改写为：z+CBXB+CN1XN1+0Xs=0，N1,s为非基变量的编号BXB+N1XN1+IXs=bXB为基变量时，经基底转换有XB,z的表达式:XB+B-1N1XN1+B-1Xs=B-1bz+(CN-CBB-1N1)XN1-CBB-1Xs=-CBB-1b用矩阵表示为,分块的系数矩阵可用下列表格形式表示：,一般线性规划问题,初始表,具体对应如下：,1）对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1；2）初始单纯形表中基变量Xs=b，迭代后的表中变为XB=B-1b；3）初始单纯形表中的系数矩阵A，I=B，N，I，迭代后的表中约束系数矩阵为：B-1A，B-1I=B-1B，B-1N，B-1I=I，B-1N，B-1；4）初始单纯形表中变量xj的系数向量为Pj，迭代后为Pj，则有Pj=B-1Pj；,最后表,2改进的单纯形算法,问题原理和计算步骤(见书p50),3线性规划的对偶问题的提出,每个线性规划都有另一个线性规划(对偶问题)与它密切相关，对偶理论揭示了原问题与对偶问题的内在联系。,0,0,76,8,9,40,4,5,36,4,3,.,30,32,max,2,1,2,1,2,1,2,1,2,1,+,+,+,+,=,x,x,x,x,x,x,x,x,t,s,x,x,z,矩阵形式,实际问题提出：某厂生产甲、乙两种产品，产量、利润设备、台时如下模型所示,现在从另一个角度讨论这个问题：另一方面，工厂决定设备转让、收取租金，确定租价。设y1，y2，y3分别为设备A、B、C每台时的租价，同意租让的原则：产品甲租让的租费不低于原利润32元，其余类似。工厂将所有设备台时都出租，其收入和约束为：,矩阵形式,对偶问题或是伴随问题，线性系统的性质,为什么目标最小呢？租金定的越高就不会有人来租，问题就没有实际意义，工厂和接受者都愿意的条件为上述规划问题。其中Y=（y1，y2，y3）。,理论上提出,4线性规划的对偶理论,原问题与对偶问题的数学模型,标准对偶问题,化成对偶问题的标准形1.若原问题的约束条件全部是等式约束,总结：原问题与对偶问题的对应关系,2.其它形式，按线性规划化标准形的方法进行,进一步有,对偶问题的基本性质和基本定理1对称性定理：对偶问题的对偶是原问题证明：,2弱对偶性定理若X（0）和Y（0）分别是原问题和对偶问题的可行解，则有CX（0）Y（0）b,3若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。,证明:因为X（0）是原问题的可行解，故有AX（0）b。又因为Y(0)是对偶问题的可行解，则有Y（0）AX（0）Y（0）b,及Y（0）AC,故CX（0）Y（0）AX（0）Y（0）b亦即CX（0）Y（0）b证毕,4最优性定理若X（0）和Y（0）分别是原问题和对偶问题的可行解，且有CX（0）=Y（0）b,则X（0）和Y（0）分别是原问题和对偶问题的最优解。,证明：设X是原问题任一可行解，Y（0）是对偶问题的可行解，根据弱对偶性定理，有CXY（0）b因为CX（0）=Y（0）b，故CXCX（0），即X（0）是原问题的最优解。设Y为对偶问题的任一可行解，同理有YbY（0）b即Y（0）是对偶问题的最优解。,5对偶定理有一对对偶的线性规划问题，若其中有一个有最优解，则另一个也有最优解，且相应的目标函数值相等。,证明：设X（0）是原问题的最优解，相应的最优基为B,非基变量的检验数为CN-CBB-1N0全体检验数有C-CBB-1A0，即CCBB-1A令Y（0）=CBB-1，则有Y（0）AC即Y（0）是对偶问题的可行解。由于z=CX（0）=CBXB（0）=CBB-1b=Y（0）b（目标值相等）由最优性定理可知Y（0）为对偶问题的最优解。,6互补松弛定理若X（0）和Y（0）分别是原问题和对偶问题的可行解，则X（0）和Y（0）都是最优解的充要条件是Y（0）Xs=0和YsX（0）=0。其中Xs=(xs1,xs2,xsm)T，xs1,xs2,xsm分别是原问题的松弛变量.Ys=(ys1,ys2,ysn)T，ys1,ys2,ysn分别是对偶问题的剩余变量。松弛的含义是如果有某个原始最优解X(0)，使得对某个下标j，满足X(0)j0(对原问题是松的)，那么与之对应的对偶约束在最优的情况下为等式，即ysj=0(对对偶问题是紧的)；如果原始约束在最优情况下对某个下标i满足x(0)si0(对原问题是松的)，那么，对偶最优解中与之对应的y(0)i=0(对偶问题是紧的)。,证明:原问题对偶问题maxz=CXmin=YbAX+Xs=bYA-Ys=CX,Xs0Y,Ys0z=(YA-Ys)X=YAX-YsX=Y(AX+Xs)=YAX+YXs若Y(0)Xs=0和YsX(0)=0,则Y(0)b=Y(0)AX(0)=CX(0)，根据性质4可知X(0),Y(0)为最优解。反之,X(0),Y(0)为最优解,则CX(0)=Y(0)AX(0)=Y(0)b可知必有Y(0)Xs=0和YsX(0)=0。证毕,7原问题的检验数对应对偶问题的一个基本解,XB=B-1b，XN=0检验数为：CN-CBB-1N，-CBB-1令Y=CBB-1得Ys1=0，-Ys2=CN-CBB-1N证毕,min=YbYB-Ys1=CBYN-Ys2=CNY,Ys1，Ys20YS=（YS1，YS2）,证明:原问题对偶问题maxz=CXmin=YbAX+Xs=bYA-Ys=CX,Xs0Y,Ys0,检验数性质：原问题检验数行对应其对偶问题的一个基解,关系如下:,例4已知线性规划问题maxz=x1+x2-x1+x2+x32-2x1+x2-x31x1,x2,x30试用对偶理论证明上述线性规划问题无最优解。,证:首先看到该问题存在可行解，例如X=(0,0,0)而上述问题的对偶问题为min=2y1+y2-y1-2y21y1+y21y1-y20y1,y20由第一约束条件可知对偶问题无可行解，因而无最优解。由此原问题也无最优解。,例5已知线性规划问题min=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x542x1-x2+3x3+x4+x53xj0,j=1,2,3,4,5已知其对偶问题的最优解为y1*=4/5,y2*=3/5；z=5。试用对偶理论找出原问题的最优解.,解:先写出它的对偶问题maxz=4y1+3y22y1+y22y1-y232y1+3y25y1+y223y1+y23y1,y20,将y1*,y2*的值代入上述约束条件，得(2),(3),(4)为严格不等式；由互补松弛性得x2*=x3*=x4*=0因y1,y20，原问题的两个约束条件应取等式，故有x1*+3x5*=42x1*+x5*=3求解后得x1*=1，x5*=1故原问题的最优解为X*=(1,0,0,0,1)T最优值为*=5,5对偶问题的经济解释（影子价格）,由对偶定理知，当达到最优解时有：z=CX（0）=Y（0）b=y1（0）b1+y2（0）b2+ym（0）bm在最优解处，常数项bi的微小改变对目标函数值的影响（在不改变最优基情况下）有,这说明若原问题的bi增加一个单位，则由此引起的最优目标函数值增加量，就等于该约束条件相对应的对偶变量的最优值。因此，最优对偶变量yi的值，就相当于对单位变化的第i种资