第二章对偶问题ppt课件.ppt

2023/1/11,-第2章 对偶问题-,-1-,第 二 章 线性规划的对偶理论,Duality 对偶Dual Problem 对偶问题 Dual Linear Programming 对偶线性规划Dual Theory 对偶理论,2023/1/11,2,，各生产多少,可获最大利润?,乙方租借设备：甲方以何种价格将设备A、B、C租借给乙方比较合理？请为其定价。,2.1 问题的提出,-第2章 对偶问题-,2023/1/11,3,而就乙方而言，希望甲方的租金收入在满足约束的条件下越小越好，这样双方才可能达成协议。于是得到下述 的线性规划模型：,解：假设A、B、C的单位租金分别为，所以生产产品的资源用于出租时，租金收入应满足：,类似的，生产产品的资源用于出租时，租金收入应满足：,总的租金收入：,-第2章 对偶问题-,思路：就甲方而言，租金收入应不低于将设备用于自己生产时的利润。,原问题的对偶问题,2023/1/11,-第2章 对偶问题-,-4-,例：某企业计划生产甲、乙两种产品，该两种产品均需经 A、B、C、D 四种不同设备加工，按工艺资料规定，在各种不同设备上的加工时间及设备加工能力、单位产品利润如表中所示。问：如何安排产品的生产计划，才能使企业获利最大?,2023/1/11,-第2章 对偶问题-,-5-,1.最大生产利润模型,设 企业生产甲产品为X1件，乙产品为X2件，则 max z=2 X1+3 X2 s.t 2 X1+2 X2 12 X1+2 X2 8 4 X1 16 4 X2 12 X1 0,X2 0,2.资源最低售价模型,(原问题)(对偶问题),设第i种资源价格为yi,（i=1,2,3,4,）则有,min w=12y1+8y2+16y3+12 y4,s.t 2y1+y2+4y3+0 y4 2,2y1+2y2+0y3+4 y4 3,yi 0,(i=1,2,3,4),y1,y2,y3,y4,2023/1/11,-第2章 对偶问题-,-6-,2.2 原问题与对偶问题的关系,一般表示式：原问题：max z=c1 X1+c2 X2+cn Xn s.t a11 X1+a12 X2+a1n Xn b1 a21 X1+a22 X2+a2n Xn b2 am1 X1+am2 X2+amn Xn bm xj 0，j=1,2,n 对偶问题：min w=b1 y1+b2 y2+bm ym s.t a11 y1+a21 y2+am1 ym c1 a12 y1+a22 y2+am2 ym c2 a1n y1+a2n y2+amn ym cn yi 0，(i=1,2,m),2023/1/11,-第2章 对偶问题-,-7-,典式模型对应对偶结构矩阵表示,（1）max z=C X s.t AX b X 0,min w=Y b s.t YA C Y 0,对偶问题,原问题,这是规范形式 的原问题，由此写出其对偶问题如右方所示，那么，当原问题不是规范形式时，应如何写出其对偶问题？可以先将原问题化成规范的原问题，再写出对偶问题。,2023/1/11,-第2章 对偶问题-,-8-,对偶模型其他结构关系,（2）若模型为 max z=C X s.t AX b X 0,max z=C X s.t-AX-b X 0,变形,min w=Y b s.t YA C Y 0,Min w=Y(-b)st.Y(-A)CY 0,令 Y=-Y,对偶问题,对偶变量Y,2023/1/11,-第2章 对偶问题-,-9-,（3）max z=C X s.t AX b X 0,变形,设X=-X,max=-CX st.-AX b X 0,min w=Y b s.t YA C Y 0,则有,min w=Y b s.t-YA-CY 0,2023/1/11,-第2章 对偶问题-,-10-,对偶问题典式：,用矩阵形式表示：（1）max z=C X min w=Y b s.t AX b s.t YA C X 0 Y 0（2）max z=C X min w=Y b s.t AX b s.t YA C X 0 Y 0（3）max z=C X min w=Y b s.t AX b s.t YA C X 0 Y 0,11,等式、无约束情况的对偶：,原问题,对偶问题,12,推导:,原问题化为：,即：,13,根据对称形式的对偶模型,可直接写出上述问题的对偶问题:,14,令，得对偶问题为：,2023/1/11,-第2章 对偶问题-,-15-,原问题与对偶问题关系表,原问题(对偶问题)对偶问题(原问题)目标函数系数 约束右端项 约束右端项 目标函数系数 约束条件系数列向量 A约束条件系数行向量 AT 变量个数约束条件个数max min 变量 x j:约束方程 i:x j 0 x j 无约束=x j 0 约束方程:变量 y i:y i 0=y i 无约束 y i 0,2023/1/11,-第2章 对偶问题-,-16-,2.3 对偶问题的基本性质,Max z=CXMin w=Y b s t.AX b s t.YA C X 0Y 0,(1)弱对偶性：若 X0原问题可行解，Y0对偶问题可行解则 CX0 Y0 b证明：Y0 0，AX0 b，Y0 AX0 Y0 b，而 Y0 A C，CX0 Y0AX0，CX0 Y0 AX0 Y0 b,推论1:原问题任一可行解的目标函数值是其对偶问题目标函数值的下届；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。,推论2:在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；反之不成立。这也是对偶问题的无界性。,2023/1/11,-第2章 对偶问题-,-17-,（2）最优性：,若 X0原问题可行解，Y0对偶问题可行解，且 CX0=Y0 b 则 X0原问题最优解，Y0对偶问题最优解证明：设 X*原问题最优解，Y*对偶问题最优解 则 CX0 CX*Y*b Y0 b 但 CX0=Y0 b，CX0=CX*=Y*b=Y0 b X0=X*，Y0=Y*即 X0原问题最优解，Y0对偶问题最优解证毕。,若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。,2023/1/11,-第2章 对偶问题-,-18-,（3）无界性,若原问题最优解无界，则对偶问题无可行解 证：有性质1，C X0 Y0 b，当 CX0 时，则不可能存在Y0，使得 C X0 Y0 b。注：逆定理不成立，即 如果原问题（对偶问题）无可行解，那么 对偶问题（或原问题）“解无界”不成立。,2023/1/11,-第2章 对偶问题-,-19-,（4）强对偶性（对偶定理）,若原问题有最优解，则对偶问题一定有最优解，且有 z max=w min证：由=C-CB B-1 A 0 令 CBB-1=Y*，得 Y*A C-Y*=-CBB-1 0，Y*0 因此，Y*是对偶问题的可行解，又 CX*=CB(B-1 b)=CB B-1b=Y*b Y*是对偶问题的最优解。,还可推出另一结论：若（LP）与（DP）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。,2023/1/11,-第2章 对偶问题-,-20-,Max z=CX st.AX b X 0,Max z=CX st.AX+Xs=b X 0,标准形,Max z=CBXB+CNXN+0XS st.BXB+NXN+IXS=b，XB,XN,XS 0,改写,B-1存在,Max z=CBXB+CNXN+0XS st.B-1BXB+B-1NXN+B-1I XS=B-1 bXB,XN,XS 0,左乘B-1,LP模型矩阵变换：,|B|0，,（XB+B-1NXN+B-1 XS=B-1 b）,2023/1/11,-第2章 对偶问题-,-21-,单纯形法的矩阵描述：,XB,XN,XS,B,N,I,I,N,B-1,b,b,XS,XB,CB,CN,0,CB,CN,0,=C-CB B-1 A0,0,N,S,xj,cj,pj,0,pj,j,cj,XB=b=B-1 b,N=B-1 N,N=CN-CBB-1 N 0,CB,S=-CB B-1 0,初始表,最终表,A=B N I,2023/1/11,-第2章 对偶问题-,-22-,（5）互补松弛性,n 若 y i*0,则 aij xj*=bi j=1 n 若 a ij xj*bi,则 y i*=0 j=1,n n m m 证：cj x j*=(a ij y i*)xj*=bi y i*j=1 j=1 i=1 i=1,n m m(a ij y i*)xj*-bi y i*=0 j=1 i=1 i=1,m n(a ij xj*-bi）y i*=0 i=1 j=1,当 y i*0,a ij xj*-bi=0,即 a ij xj*=bi,当 a ij xj*-bi 0,y i*=0,j=1,j=1,j=1,n,n,n,2023/1/11,-第2章 对偶问题-,-23-,设X0和Y0分别是P问题 和 D问题 的可行解，则它们分别是最优解的充要条件是：,其中：Xs、Ys为松弛变量,证明：（LP）和（LD）标准化为：,则有:,2023/1/11,-第2章 对偶问题-,-24-,必要性：,则,于是,所以,充分性：若,若 为最优解,所以 为最优解,则,2023/1/11,-第2章 对偶问题-,25,该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知Y*求X*或已知X*求Y*,互补松弛条件,由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：若Y*0，则Xs必为0；若X*0，则Ys必为0 利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。,例 已知线性规划,其对偶问题的最优解为Y*=(0,-2)，求原问题的最优解。,解:对偶问题是,标准化,设原问题最优解为X*(x1，x2，x3)T,由互补松弛性定理可知，X*和 Y*满足：,将Y*带入由方程可知，y3y50，y41。,y2=-20 x50又y4=10 x20,将x2，x5分别带入原问题约束方程中，得：,解方程组得：x1=-5,x3=-1,所以原问题的最优解为,X*=(-5,0,-1)，最优值z=-12,例2:,2023/1/11,-第2章 对偶问题-,-28-,解：对偶问题为,将y1，y2代入，知(2),(3),(4)为严格不等式,x2=x3=x4=0,由y1，y20知原约束为等式:,x=(1,0,0,0,1)T,min W=5,2023/1/11,-第2章 对偶问题-,-29-,（6）单纯形表中的对应关系,原问题与其对偶问题的变量与解的对应关系：在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量。,max z=2 x1+3 x2 min w=12y1+8y2+16y3+12 y4 s.t 2 x1+2 x2 12 s.t 2y1+y2+4y3+0 y4 2 x1+2 x2 8 2y1+2y2+0y3+4 y4 3 4 x1 16 yi 0,i=1,2,3,4 4 x2 12 x1 0,x2 0,-y5-y6-y1-y2-y3-y4,2023/1/11,-第2章 对偶问题-,-30-,原问题最优表,对偶问题最优表,原问题与对偶问题解的对应关系小结,32,原问题的检验数行对应对偶问题的一个基解。,证明：（LP）和（LD）标准化为：,设B是原问题的一个可行基，于是A(B,N)，所以原问题可以改写为：,33,当求得原问题的一个解,其相应检验数为：,相应地对偶问题可表示为：,令，并将它代入上式得：,思考题,判断下列结论是否正确，如果不正确，应该怎样改正？,1）任何线性规划都存在一个对应的对偶线性规划.2）原问题第i个约束是“”约束，则对偶变量yi0.3）互为对偶问题，或者同时都有最优解，或者同时都无最优解.4）对偶问题有可行解，则原问题也有可行解.5）原问题有多重解，对偶问题也有多重解.6）对偶问题有可行解，原问题无可行解，则对偶问题具有无界解.7）原问题无最优解，则对偶问题无可行解.8）对偶问题不可行，原问题可能无界解.9）原问题与对偶问题都可行，则都有最优解.10）原问题具有无界解，则对偶问题不可行.11）对偶问题具有无界解，则原问题无最优解.12）若X*、Y*是原问题与对偶问题的最优解，则X*=Y*.,2023/1/11,-第2章 对偶问题-,-35-,2.4 影子价格(Shadow price),1、对偶变量yi可理解为对一个单位第 i种资源的估价，称为影子价格，但并非市场价格。,假设有原问题和对偶问题如下：,2、对偶变量yi 的值（即影子价格）表示第i种资源数量变化一个单位时，目标函数的增量，是一种边际价格。,对bi求偏导,说明yi的值相当于在资源得到最优利用的生产条件下，bi每增加一个单位时目标函数Z的增量。,2023/1/11,36,资源增加一个单位时，最优解及目标函数值的变化,2023/1/11,-第2章 对偶问题-,-37-,生产过程中如果某种资源 未得到充分利用时，该种资源的影子价格为零；经济解释：资源未用完，再增加对目标函数也无贡献。当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。经济解释：该种资源用尽，再购进用于扩大生产可增加总利润。,在对偶问题的互补松弛性质中有,影子价格是一种机会成本 影子价格是在资源最优利用条件下对单位资源的估价，这种估价不是资源实际的市场价格。因此，从另一个角度说，它是一种机会成本，可用于指导资源的购入与卖出。,若第i 种资源的单位市场价格为mi，则有当yi*mi 时，企业愿意购进这种资源，单位纯利为yi*mi，则有利可图；如果yi*mi，则企业有偿转让这种资源，可获单位纯利miyi*，否则，企业无利可图，甚至亏损。,结论：若yi*mi 则购进资源i，可获单位纯利yi*mi 若yi*mi则转让资源i，可获单位纯利miyi,单纯形表检验数,单纯形表中的检验数与影子价格,其中cj表示第j种产品的价格;表示生产该种产品所消耗的各项资源的影子价格的总和,即产品的隐含成本。,当产值大于隐含成本时，即，表明生产该项产品有利，可在计划中安排；否则，用这些资源生产别的产品更有利，不在生产中安排该产品。,2023/1/11,40,2.5 对偶单纯形法,在单纯形表中，列对应原问题的基可行解，行对应对偶问题的一个基解（不一定可行），当 时，在检验数行就得到对偶问题的基可行解，此时两个问题的目标函数值相等，由最优性条件知，两个问题都达到了最优解。,单纯形法：找一个初始基可行解，保持b列为正，通过迭代找到下一个基可行解，使目标函数值不断增大，当检验数行全部小于等于零时，达到最优解。,41,原问题基可行解 最优解判断,对偶问题的可行解,对偶问题最优解判断,对偶单纯形法基本思路,单纯形法的基本思路：,对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。,找出一个DP的可行基,LP是否可行（XB 0）,保持DP为可行解情况下转移到LP的另一个基本解,最优解,是,否,循环,结束,根据对偶问题的对称性，保持对偶问题的解是可行解，即检验数行非负，而原问题从非可行解开始，逐步迭代到基本可行解，也使原问题和对偶问题达到最优解。,2023/1/11,-第2章 对偶问题-,-43-,2.5 对偶单纯形法,由于单纯表中同时反映原问题与对偶问题的最优解，故可以从求对偶问题最优解角度求解LP模型。,例：,min z=2x1+3x2 max z=-2x1-3x2+0 x3+0 x4 s.t x1+x23 标准化 s.t x1+x2-x3=3 x1+2x2 4 x1+2x2-x4=4 x10,x20 xj 0,(j=1,2,3,4),max z=-2x1-3x2+0 x3+0 x4 s.t-x1-x2+x3=-3-x1-2x2+x4=-4 xj 0,(j=1,2,3,4),2023/1/11,-第2章 对偶问题-,-44-,Cj,x1,x2,x3,x4,XB,b,CB,-1-1 1 0-1-2 0 1,-2-3 0 0,-3-4,x3 x4,00,cj-zj,-2,-3,0,0,-1/2 0 1-1/2 1/2 1 0-1/2,x3 x2,-1 2,cj-zj,-1/2 0 0-3/2,0-3,1 0-2 1 0 1 1-1,x1 x2,21,cj-zj,0 0-1-1,-2-3,列单纯表计算：,2023/1/11,-第2章 对偶问题-,-45-,对偶单纯形法步骤：,1.列初始单纯形表，使得所有检验数j 0；2.出基变量：取min bi0=bl x(l)3.入基变量：min|alk0=xk4.主元素：alk5.迭代：同单纯形法，新单纯表中pk化为单位向量,cj-zj,alj,说明：10 使用对偶单纯形法时，初始表中检验数必须全部为j 0，即使得其对偶问题为可行解，20 为便于说明，这里采取从原问题角度叙述迭代步骤。,2023/1/11,46,1、为何只考虑 行中 的元素对应的变量进基？为使迭代后的基变量取正值。,2、为何采用最小比值规则选择进基变量？为了使得迭代后的多偶问题解仍为可行解（检验数行仍为非正）,3、原问题无可行解的判别准则：当对偶问题存在可行解时，若有某个，而所有，则原问题无可行解，对偶问题目标值无界。因为第r行的约束方程即为：其中，因此不可能存在 使上式成立。也即原问题无可行解。,2023/1/11,-第2章 对偶问题-,-47-,对偶单纯形法的优点：不需要人工变量；对变量较少，而约束条件很多的LP,可以先将其变成LD，再运用对偶单纯形法计算；在灵敏度分析中，有时需要用对偶单纯形法处理简化。,用对偶单纯形法求解LD,LP,LD,最优解=？最优值=？,练习（对偶单纯形法求解）,2023/1/11,-第2章 对偶问题-,-52-,2.6 灵敏度分析,1灵敏度分析的概念：当某一个参数发生变化后，引起最优解如何改变的分析。可以改变的参数有：bi约束右端项的变化，通常称资源的改变；cj 目标函数系数的变化，通常称市场条件的变化；pj 约束条件系数的变化，通常称工艺系数的变化；其他的变化有：增加一种新产品、增加一道新的工序等。,2023/1/11,-第2章 对偶问题-,-53-,2.灵敏度分析的一般步骤：(1)将参数的改变经计算后反映到最终单纯形表中；(2)检查原问题和对偶问题是否仍为可行解；(3)按照下表对应情况，决定下一步骤。,2023/1/11,-第2章 对偶问题-,-54-,3分析原理：借助最终单纯形表，将变化后的结果按下述基本原则反映到最终表中去。,（1）bi变化：（b+b）=B-1（b+b）=B-1 b+B-1 b=b+B-1 b（2）pj变化：（pj+pj）=B-1（pj+pj）=B-1 pj+B-1 pj=pj+B-1 pj（3）cj变化：直接反映到最终表中，计算检验数。（4）增加一个约束方程：直接反映到最终表中。（5）增加新产品：仿照pj变化。,2023/1/11,55,一、C 的变化分析 C的变化只影响检验数。,例、设有如下的线性规划模型试分析 分别在什么范围变化时，最优解不变？,2023/1/11,56,解：问题的最终单纯形表如下：,2023/1/11,57,1、当 变化时，假设，则要使得问题的最优解保持不变，则检验数行 即可，即要求,2、当 变化时，假设，则要使得问题的最优解保持不变，则检验数行 即可，即要求,2023/1/11,58,二、b 的变化分析 b的变化将只影响原问题的基可行解，即最终表中的b列数值。,例、设有如下的线性规划模型试分析 分别在什么范围变化时，最优基不变？,2023/1/11,59,解：将 重新计算后填入问题的最终单纯形表：,1、当 变化时，假设，则问题的解变为填入下表，得,2023/1/11,60,要使得最优基保持不变，则b列数值 即可，即要求,同理可得 的变化范围是：的变化范围是：,2023/1/11,61,三、增加一个变量的变化分析 增加一个变量，在方程组（矩阵A）中就要增加一个系数列，在原来的最终表中也要添加一列，检验数也要计算，其余部分不受影响。如果检验数行仍，则最优解不变，否则继续迭代寻找最优。一般分析步骤：1、计算增加的新变量系数列 在原最终表中的结果；2、计算新变量对应的检验数；3、根据 的符号判断是否仍是最优解，若是，最优解不变；若不是，继续求解。,2023/1/11,62,例、设有如下的线性规划模型现增加变量，其对应系数列为，价值系数，请问最优解是否改变？,解：最终表,2023/1/11,63,新变量的检验数及系数列分别为：,填入表中，易知未达最优，继续迭代求解。,2023/1/11,64,已达最优。最优解为 最优目标值,2023/1/11,65,四、增加一个约束条件的变化分析 增加一个约束条件，相当于增加一道工序。分析方法:1）先将原最优解带入此新约束，若满足条件，说明此约束未起作用，原最优解不变；2）否则，将新约束加入到最终表中，继续分析。,例、在上例中添加新约束，分析最优解的变化情况。解：因为将原最优解 带入此约束，不满足约束，原解已不是最优，继续分析。,2023/1/11,66,6,x,2023/1/11,67,已达最优。最优解为 最优目标值,2023/1/11,-第2章 对偶问题-,-68-,3计算示例：,max z=2 x1+3 x2 s.t 2 x1+2 x2 12 x1+2 x2 8 4 x1 16 4 x2 12 x1 0,x2 0,例：已知某线性规划模型及最终的单纯表如下：,问：（1）若b2增加8个单位，最优解如何变化？（2）若c2还可增加2个单位，最优解如何改变？（3）若引进一个新变量（产品）y，其目标函 数系数为 cy=5，系数列向量为py=3 2 6 3T，问最优解是否会改变？,cj 2 3 0 0 0 0 CB XB b x1 x2 x3 x4 x5 x6,0 x3 0 2 x1 4 0 x6 4 3 x2 2,0 0 1-1-0.25 0 1 0 0 0 0.25 0 0 0 0-2 0.5 1 0 1 0 0.5-0.125 0,cjzj,0 0 0-1.5-0.125 0,2023/1/11,-第2章 对偶问题-,-69-,解：（1）,（b+b）=B-1 b+B-1 b=b+B-1 b=0 4 4 2T+-8 0-16 4 T=-8 4-12 6 T,B-1 b=,1-1-0.25 0 0 0 0.25 0 0-2 0.5 1 0 0.5-0.125 0,0 8 0 0,=,-8 0-16 4,利用对偶单纯形法继续 求最优解。,（2）当cj变化时，=CCB B-1 A，列出单纯形表，重新求出检验数，如表中所示：,（3）增加y时，y=cy-CB B-1 py=5-(0 1.5 0.125 0)3 2 6 3T=1.250 选择y作入基变量，py=B-1 py=-0.5 1.5 2 0.25T,继续迭代：,2023/1/11,-第2章 对偶问题-,-70-,cj 2 3 0 0 0 0 CB XB b x1 x2 x3 x4 x5 x6,0 x3-8 2 x1 4 0 x6-12 3 x2 6,0 0 1-1-0.25 0 1 0 0 0 0.25 0 0 0 0-2 0.5 1 0 1 0 0.5-0.125 0,cjzj,0 0 0-1.5-0.125 0,0 x3-2 2 x1 4 0 x4 6 3 x2 3,0 0 1 0-0.5-0.5 1 0 0 0 0.25 0 0 0 0 1-0.25-0.5 0 1 0 0 0 0.25,cjzj,0 0 0 0-0.5-0.75,0 x5 4 2 x1 3 0 x6 7 3 x2 3,0 0-2 0 1 1 1 0 0.5 0 0-0.25 0 0-0.5 1 0-0.25 0 1 0 0 0 0.25,cjzj,0 0-1 0 0-0.25,返回,右端项变化分析单纯形表：,2023/1/11,-第2章 对偶问题-,-71-,cj 2 5 0 0 0 0 CB XB b x1 x2 x3 x4 x5 x6,0 x3 0 2 x1 4 0 x6 4 5 x2 2,0 0 1-1-0.25 0 1 0 0 0 0.25 0 0 0 0-2 0.5 1 0 1 0 0.5-0.125 0,cjzj,0 0 0-2.5 0.125 0,0 x3 2 2 x1 2 0 x5 8 5 x2 3,0 0 1-2 0 0.5 1 0 0 1 0-0.5 0 0 0-4 1 2 0 1 0 0 0 0.25,cjzj,0 0 0-2 0-0.25,返回,Cj 变化分析单纯形表：,2023/1/11,-第2章 对偶问题-,-72-,cj 2 3 0 0 0 0 5 CB XB b x1 x2 x3 x4 x5 x6 y,0 x3 0 2 x1 4 0 x6 4 3 x2 2,0 0 1-1-0.25 0-0.5 1 0 0 0 0.25 0 1.5 0 0 0-2 0.5 1 2 0 1 0 0.5-0.125 0 0.25,cjzj,0 0 0-1.5-0.125 0 1.25,0 x3 1 2 x1 1 5 y 2 3 x2 1.5,0 0 1-1.5-0.125 0.25 0 1 0 0 1.5-0.125-0.75 0 0 0 0-1 0.25 0.5 1 0 1 0 0.75-0.1875-0.125 0,cjzj,0 0 0-0.25-0.4375-0.625 0,增加新产品（变量y）变化分析单纯形表：,2023/1/11,-第2章 对偶问题-,-73-,2.7 参数线性规划,1.概念：研究目标函数值随某一参数变化的规律及最优解相应的变化。算法：先令变化量=0，当多个参数同时变化时，可以引入一个参数来表示这种变化。如：b列多个值发生变化时，可表示成 再考察随着的增加引起解的变化情况。3.最后，画出目标值随的变化所形成的曲线。,2023/1/11,74,例：求解下述参数线性规划问题:,解：求得 时最终单纯形表并将参数的变化填入表中：,2023/1/11,75,2、是临界点，当 时，所以选择 作为进基变量，迭代一步得到：,1、由表可知，当 时，即 最优解不变。目标函数值是：,2023/1/11,76,3、由上表可知，当 时，即 最优解不变。目标函数值是,4、是临界点，当 时，所以选择 作为进基变量，迭代一步得到：,2023/1/11,77,5、由上表可知，当 时，最优解不再变化。目标函数值是,6、是临界点，当 时，所以选择 作为进基变量，迭代一步得到：,此时无论 如何增加，检验数始终为负，最优解不再变化。目标函数值是,2023/1/11,78,15,24,34,2023/1/11,79,例：某文教用品厂利用原材料白坯纸生产原稿纸、日记本、练习本三种产品，该厂现有工人100人，每天白坯纸供应量限制是3万kg，如果单独生产各种产品时，每人每天生产原稿纸30捆、日记本30打、练习本30箱。已知原材料消耗为每捆原稿纸用白坯纸 公斤，每打日记本用白坯纸 公斤，每箱练习本用白坯纸 公斤。又知每捆原稿纸可盈利2元，每打笔记本盈利3元，每箱练习本盈利1元。试决定（1）在现有生产条件下，工厂盈利最大的生产方案；（2）如果白坯纸的供应数量不变，当工人人数不足时可招收临时工，其工资支出为每人每天40元，问该厂要不要招收临时工，最多招多少？,2023/1/11,80,例：设该厂每天生产原稿纸、日记本、练习本的数量分别是，表示招收临时工的数量。则有下列模 型：,时，得现有条件下的最优生产计划，如下表。,2023/1/11,81,由表中可知，劳动力的影子价格是50元/人（40），所以可以雇用工人扩大生产。将参数 反映到最终表中，得：,2023/1/11,82,要使得最优基不变，须 即，当 时，最优基不变，最优解 目标函数值,当 时，利用对偶单纯形法迭代一步，得结果如下：,2023/1/11,83,由上表可知，当 时，最优解是目标函数值是 变化情况可见图。,2023/1/11,-第2章 对偶问题-,-84-,例：有如下线性规划模型：,max z=2x1+3x2 s.t x1+x23 x1+2x2 4+x10,x20（0）,max z=2x1+3x2+0 x3+0 x4 s.t x1+x2+x3=3 x1+2x2+x4=4 xj 0,(j=1,2,3,4),（1）当=0 时的最优解；（2）当0时，z 值的变化规律。,解：先令=0，有下述模型的标准形,利用单纯形法求解：,2023/1/11,-第2章 对偶问题-,-85-,Cj,x1,x2,x3,x4,XB,b,CB,1 1 1 0 1 2 0 1,2 3 0 0,34,x3 x4,00,cj-zj,2,3,0,0,1/2 0 1-1/2 1/2 1 0 1/2,x3 x2,12,cj-zj,1/2 0 0-3/2,03,1 0 2-1 0 1-1 1,x1 x2,21,cj-zj,0 0-1-1,23,（=0）,2023/1/11,-第2章 对偶问题-,-86-,Cj,x1,x2,x3,x4,XB,b,CB,2 3 0 0,2-1+,x1 x2,23,cj-zj,-1 0-2 1 1 1 1 0,x4 x2,cj-zj,-1 0-3 0,03,0 0-1-1,1 0 2-1 0 1-1 1,（0 3）,当0时，b=B-1b=B-1b(0)T=(-)T，继续迭代如下：（对偶单纯形法）,-2 3,（3）,其变化曲线如下：,2023/1/11,-第2章 对偶问题-,-87-,Z(),0,3,7,9,2023/1/11,-第2章 对偶问题-,-88-,例：,某大学教授利用部分业余时间从事咨询工作。现有三个A、B、C企业欲聘请，各自每小时的咨询费用分别为10，12，16元。教授每月可用于外出咨询的时间为40小时，但对每个企业而言，用于准备的时间与咨询所花的时间的比例分别为0.1，0.5，0.8，教授每月可用于准备的时间应不超过24小时。若假定三个企业每月要求的咨询时间可分别达到80，60，20小时。现问：教授应作何种决策，才能使收益最大？从目前看，教授有许多咨询机会，但可用的外出咨询时间及准备的时间有限，所以可考虑雇用助手（用于帮助准备），但要支付每小时4元的费用，现帮助教授分析一下，它是否该雇用助手，若需雇用，每月应雇用多少时间？,2023/1/11,-第2章 对偶问题-,-89-,设 用于三个企业咨询的时间分别为Ax1，Bx2，Cx3，,Max z=10 x1+12x2+16x3s.t.x1+x2+x340 0.1x1+0.5x2+0.8x324 x180 x2 60 x3 20 x10,x20,x30,+,-4,