第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析CjC1 C2 Cj. CnCBXBbx1 x2 xj xnxB1xB2xBnb1b2.bna11 a12 a1j a1na21 a22 a2j a2nan1 an2 anj ann检验数检验数 j设线性规划问题设线性规划问题:目标函数目标函数maxz=CX;约束条件约束条件AXb; Xb; 非负条件非负条件 X0 X0给这线性规划问题的约约束条件加入松给这线性规划问题的约约束条件加入松弛变量以后，得到标准型：弛变量以后，得到标准型： m max z=CX+0Xs;AX+IXX+IXs s=b; X=b; X，X X s s00这里这里I I 是是mmmm单位矩阵。单位矩阵。第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析初始单纯形表和最终单纯形矩阵表示如下初始单纯形表和最终单纯形矩阵表示如下:CjCN CB 00XSb XN XB XSXS b NBI检验数检验数 jCjCN CB 0CBXBb XN XB XSXBB-1bB-1NBB-1B-1检验数检验数 jCN -CB B-1N-CB B-1令非基变量令非基变量=0；由上式得到：；由上式得到：二、改进单纯形法二、改进单纯形法求解线性规划问题的关键是计算求解线性规划问题的关键是计算以下介绍一种比较简便的计算方法以下介绍一种比较简便的计算方法设设mmmm系数矩阵系数矩阵A A，求其逆矩阵。，求其逆矩阵。可以先从第可以先从第1列开始列开始以以为主元素为主元素,进行变换进行变换然后然后构造含有（含有（1 1）列，而其他列都是）列，而其他列都是单位列的矩阵单位列的矩阵可得到：可得到：而后以第而后以第2列的列的为主元素，进行变为主元素，进行变换换然后然后构造含有（含有（2 2）列，而其他列都是）列，而其他列都是单位列的矩阵单位列的矩阵可得到可得到重复以上的步骤，直到获得重复以上的步骤，直到获得求单纯形表的基矩阵的逆矩阵也可以用求单纯形表的基矩阵的逆矩阵也可以用这方法这方法例：用改进单纯形法求解线性规划问题：例：用改进单纯形法求解线性规划问题：第第1步步：确定初始基，初始基变量：确定初始基，初始基变量;确定换入，确定换入，换出变量。换出变量。（1）确定初始基和初始基变量：）确定初始基和初始基变量：（2）计算非基变量的检验数，确定换入）计算非基变量的检验数，确定换入变量。变量。(3)确定换出变量确定换出变量计算：计算：表示选择表示选择0的元素的元素（4）基变换计算）基变换计算将新的基将新的基单位矩阵。计算：单位矩阵。计算：（5）计算非基变量的系数矩阵）计算非基变量的系数矩阵（6）计算）计算RHS第第1步计算结束后的结果步计算结束后的结果第第2步步重复第重复第1步的计算步骤步的计算步骤从新的基，基变量开始。从新的基，基变量开始。计算非基变量的检验数，确定换入变计算非基变量的检验数，确定换入变量。量。(3)确定换出变量确定换出变量计算：计算：表示选择表示选择0的元素的元素计算计算RHS第第2步计算结束后的结果步计算结束后的结果第第3步步从新的基，基变量开始从新的基，基变量开始,重复第重复第1步的计算步骤步的计算步骤.计算非基变量检验数，检查检验数，确计算非基变量检验数，检查检验数，确定换入变量定换入变量(3)确定换出变量确定换出变量计算：计算：表示选择表示选择0的进行计算的进行计算新的基新的基计算计算B逆矩阵逆矩阵计算非基变量的检验数计算非基变量的检验数最优解最优解目标函数的值目标函数的值第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析若若第第一一章章中中例例一一关关于于某某厂厂的的生生产产计计划划问问题题，现现有有另另一一企企业业想想租租赁赁其其设设备备。厂厂方方为为了了在在谈谈判判时时心心中中有有数数，需需掌掌握握设设备备台台时时费费用用的的最最低低价价码码，以以便便衡衡量量对对方方出出价，对出租与否做出抉择。价，对出租与否做出抉择。在在这这个个问问题题上上厂厂长长面面临临着着两两种种选选择择：自自行行生生产产或或出出租设备。首先要弄清两个问题：租设备。首先要弄清两个问题：合理安排生产能取得多大利润合理安排生产能取得多大利润?为保持利润水平不降低，资源转让的最低价格是多少？为保持利润水平不降低，资源转让的最低价格是多少？问题问题的最优解：的最优解：x1=4，x2=2，Z*=14。三、对偶问题的提出三、对偶问题的提出第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析第二个问题：出让定价第二个问题：出让定价假设出租单位设备台时的租金和出让单位原材料假设出租单位设备台时的租金和出让单位原材料A、B所得利所得利润分别为润分别为y1、y2、y3原本用于生产原本用于生产I产品的设备台时，如若出让，不应低于自行生产品的设备台时，如若出让，不应低于自行生产带来的利润，否则宁愿自己生产。于是有产带来的利润，否则宁愿自己生产。于是有y1+4y22同理，对同理，对产品而言，则有产品而言，则有 2y1+4y33设备台时出让的收益（希望出让的收益最少值）设备台时出让的收益（希望出让的收益最少值）min =8y1+16y2+12y3显然还有显然还有 y1，y2，y30第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析对偶问题的最优解：对偶问题的最优解：y1=3/2，y2=1/8，y3=0，W*=14两个问题的目标函数值相等，这不是偶然的，上述两个问题两个问题的目标函数值相等，这不是偶然的，上述两个问题实际上是一个问题的两个方面，如果把前者称为线性规划原实际上是一个问题的两个方面，如果把前者称为线性规划原问题，则后者便是它的对偶问题，反之亦然。问题，则后者便是它的对偶问题，反之亦然。对偶问题的最优解对应于原问题最优单纯型法表中，初始基对偶问题的最优解对应于原问题最优单纯型法表中，初始基变量的检验数的负值。变量的检验数的负值。例例1的对偶问题的数学模型的对偶问题的数学模型min =8y1+16y2+12y3 y1+4y2 2 2y1+4y35 y1，y2，y30 S.t.Max Z=2x1+3x2 x1+2x284x116 4x212 x1 , x2 0第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析原问题与对偶问题的表达形式原问题与对偶问题的表达形式第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析四四线性规划的对偶理论线性规划的对偶理论（一）原问题与对偶问题的关系（一）原问题与对偶问题的关系1 1、标准、标准(max,(max, ) )型的对偶变换型的对偶变换目标函数由目标函数由max型变为型变为min型型对应原问题每个约束行有一个对偶变量对应原问题每个约束行有一个对偶变量yi，i=1,2,m对偶问题约束为对偶问题约束为 型，有型，有n行行原问题的价值系数原问题的价值系数 C 变换为对偶问题的右端项变换为对偶问题的右端项原问题的原问题的右端项右端项 b 变换为对偶问题的变换为对偶问题的价值系数价值系数原问题的技术系数矩阵原问题的技术系数矩阵 A 转置后成为对偶问题的技转置后成为对偶问题的技术系数矩阵术系数矩阵原问题与对偶问题的关系原问题与对偶问题的关系这两个式这两个式子之间的变换子之间的变换关系称为关系称为“对对对对称形式的对偶称形式的对偶称形式的对偶称形式的对偶关系关系关系关系”。 例：写出下面线性规划的对偶问题：例：写出下面线性规划的对偶问题：第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析2、非非标准标准型的对偶变换型的对偶变换 含等式约束时，将等式约含等式约束时，将等式约 束分解为两个不等式束分解为两个不等式 约束条件。约束条件。 第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析按对称形式变换关系可写出它的对偶问题，如上所示。按对称形式变换关系可写出它的对偶问题，如上所示。原问题与对偶问题的关系，归纳如下：（原始对偶表）原问题与对偶问题的关系，归纳如下：（原始对偶表）原问题（或对偶问题）原问题（或对偶问题）对偶问题对偶问题 （或原问题）（或原问题）目标函数目标函数maxz变量变量n个个00无约束无约束目标函数目标函数minw约束条件约束条件n个个约束条件约束条件m个个约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数变量变量m个个00无约束无约束目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析怎样写出非对称形式的对偶问题？怎样写出非对称形式的对偶问题？把一个等式约束写成两个不等式约束，再根据对称形式的对把一个等式约束写成两个不等式约束，再根据对称形式的对把一个等式约束写成两个不等式约束，再根据对称形式的对把一个等式约束写成两个不等式约束，再根据对称形式的对偶关系定义写出；偶关系定义写出；偶关系定义写出；偶关系定义写出；按照按照按照按照原始原始原始原始- - - -对偶表对偶表对偶表对偶表直接写出直接写出直接写出直接写出 。第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析例：试述下列线性规划问题分对偶问题例：试述下列线性规划问题分对偶问题minz=2x1+3x2-5x3 +x4 x1+x2-3x3 +x4 5 2x1+2x3-x4 4 x2+x3 +x4=6 x10;x2,x3 0; x4 无约束无约束Maxz5y14y26y3y12y22y1y333y12y2y35y1y2y31y10，y20，y3无约束无约束第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析练习：练习：练习：练习：写出下面线性规划的对偶规划写出下面线性规划的对偶规划哪一个正确？哪一个正确？前一个。原问题是极小化问题，因此应从原始对偶表的右边往左前一个。原问题是极小化问题，因此应从原始对偶表的右边往左边查！边查！（二）对偶问题的基本性质（二）对偶问题的基本性质1、对称性：、对称性：对偶问题的对偶是原问题。对偶问题的对偶是原问题。2、弱对偶性、弱对偶性若若一对对称形式的对偶线性规划一对对称形式的对偶线性规划一对对称形式的对偶线性规划一对对称形式的对偶线性规划（L） 和和 （D） 均有可行解，分别为均有可行解，分别为 和和 ，则，则C b。证明思路：证明思路：弱对偶性推论：弱对偶性推论：极大化问题极大化问题极大化问题极大化问题的任意一个可行解所对应的目标函数值的任意一个可行解所对应的目标函数值的任意一个可行解所对应的目标函数值的任意一个可行解所对应的目标函数值是其是其是其是其对偶问题对偶问题对偶问题对偶问题最优目标函数值的一个最优目标函数值的一个最优目标函数值的一个最优目标函数值的一个下界下界下界下界。极小化。极小化。极小化。极小化问题的任意一个可行解所对应的目标函数值是其对问题的任意一个可行解所对应的目标函数值是其对问题的任意一个可行解所对应的目标函数值是其对问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个偶问题最优目标函数值的一个偶问题最优目标函数值的一个偶问题最优目标函数值的一个上界上界上界上界。由由（L） 左乘左乘 ，得，得 由由（D） 右乘右乘 ，得，得 第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析如果原如果原max(min)问题为无界解，则其对偶问题为无界解，则其对偶min(max)问题无可行解问题无可行解如果原如果原max(min)问题有可行解，其对偶问题有可行解，其对偶min(max)问问题无可行解，则原问题为无界解题无可行解，则原问题为无界解注注：有可能存在原问题和对偶问题同时无可行解的：有可能存在原问题和对偶问题同时无可行解的情况。情况。3、最优性准则定理最优性准则定理最优性准则定理最优性准则定理 若若若若 、 分别为对称形式对偶线性规划的可行解，分别为对称形式对偶线性规划的可行解，分别为对称形式对偶线性规划的可行解，分别为对称形式对偶线性规划的可行解，且两者目标函数的相应值相等，即且两者目标函数的相应值相等，即且两者目标函数的相应值相等，即且两者目标函数的相应值相等，即C C C C b b b b ，则，则，则，则 ， 分别为原始问题和对偶问题的最优解。分别为原始问题和对偶问题的最优解。分别为原始问题和对偶问题的最优解。分别为原始问题和对偶问题的最优解。第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析证明思路：由弱对偶性和已知条件易证。证明思路：由弱对偶性和已知条件易证。4、主对偶主对偶定理定理如果原问题和对偶问题都有可行解，则它们都有最优如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。解，且它们的最优解的目标函数值相等。证明要点：证明要点：第一部分第一部分第一部分第一部分证明两者均有最优解。证明两者均有最优解。证明两者均有最优解。证明两者均有最优解。由于原始问题和对偶问题由于原始问题和对偶问题均可行均可行均可行均可行，根据弱对偶定理知，根据弱对偶定理知两者两者均有界均有界均有界均有界，于是，于是均有最优解均有最优解均有最优解均有最优解。第第第第二二二二部部部部分分分分证证证证明明明明在在在在达达达达到到到到最最最最优优优优时时时时，两两两两个个个个问问问问题题题题的的的的目目目目标标标标函函函函数值相等。数值相等。数值相等。数值相等。第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析设设X0 为原问题的最优解，它所对应的基矩阵是为原问题的最优解，它所对应的基矩阵是B，X0=B 1b，则其检验数满足，则其检验数满足C CBB 1A 0。令令Y0=CBB 1，则有，则有Y0A C ；而对原问题松弛变量；而对原问题松弛变量的检验数有的检验数有0 CBB 1I 0，即，即Y0 0 。显然显然Y0为对偶问题的可行解。因此有对偶问题目标为对偶问题的可行解。因此有对偶问题目标函数值，函数值，g(Y0)=Y0b=CBB 1b而原问题最优解的目标函数值为而原问题最优解的目标函数值为f(X0)=CX0=CBB 1b故由最优解判别定理可知故由最优解判别定理可知Y0 为对偶问题的最优解。为对偶问题的最优解。证证毕毕。第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析该定理的证明告诉我们一个非常重要的概念：该定理的证明告诉我们一个非常重要的概念：对偶变量对偶变量的最优解等于原问题松弛变量的机会成本的最优解等于原问题松弛变量的机会成本即对偶变量的最优解是原问题资源的即对偶变量的最优解是原问题资源的影子价格影子价格5、互补松弛互补松弛定理定理若若X0, , Y0分别是原问题和对偶问题的可行解。那么分别是原问题和对偶问题的可行解。那么Y0Xs0和和X0Ys0，当且仅当，当且仅当X0, , Y0为最优解。为最优解。证明：证明：1 1） Y0Xs0和和X0Ys0时，时，X0, , Y0为最优解为最优解2 2） 当当X0, , Y0为最优解时，为最优解时， Y0Xs0，X0Ys0第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析例例4 4：已知线性规划问题：已知线性规划问题试用对偶理论证明上述线性规划问题无最优解。试用对偶理论证明上述线性规划问题无最优解。证明：上述问题的对偶问题是：证明：上述问题的对偶问题是：由约束条件可知对偶问题无可行由约束条件可知对偶问题无可行解，而原问题有可行解。故无解，而原问题有可行解。故无最优解。最优解。第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析例例5：已知线性规划问题：已知线性规划问题已知其对偶问题的最优解为已知其对偶问题的最优解为y1*=4/5,y2*=3/5,z=5。试用对偶理论找出问题的最优解。试用对偶理论找出问题的最优解。解：解：第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析这说明这说明yi是右端项是右端项bi每增加一个单位对目标函数每增加一个单位对目标函数Z的贡献。的贡献。对偶变量对偶变量yi在经济上表示原问题第在经济上表示原问题第i种资源的种资源的边际价值边际价值边际价值边际价值。对偶变量的值对偶变量的值yi*所表示的第所表示的第i种资源的边际价值，称为种资源的边际价值，称为影子价值影子价值影子价值影子价值。若原问题的价值系数若原问题的价值系数Cj表示单位产值，则表示单位产值，则yi 称为称为影子价格影子价格影子价格影子价格。若原问题的价值系数若原问题的价值系数Cj表示单位利润，则表示单位利润，则yi 称为称为影子利润影子利润影子利润影子利润。五、对偶问题的经济解释五、对偶问题的经济解释第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析影影子子价价格格不不是是资资源源的的实实际际价价格格，而而是是资资源源配配置置结结构构的的反反映映，是是在在其其它它数数据据相相对对稳稳定定的的条条件件下下某某种种资资源源增增加加一一个个单单位位导导致致的目标函数值的增量变化。的目标函数值的增量变化。对资源对资源i总存量的评估：总存量的评估：购进购进购进购进 or出让出让出让出让对资源对资源i当前分配量的评估：当前分配量的评估：增加增加增加增加 or减少减少减少减少它它表表明明了了当当前前的的资资源源配配置置状状况况，告告诉诉经经营营者者应应当当优优先先增增加加何种资源，才能获利更多。何种资源，才能获利更多。告诉经营者以怎样的代价去取得紧缺资源。告诉经营者以怎样的代价去取得紧缺资源。提示设备出租或原材料转让的基价。提示设备出租或原材料转让的基价。告诉经营者补给紧缺资源的数量，不要盲目大量补给。告诉经营者补给紧缺资源的数量，不要盲目大量补给。借助影子价格进行内部核算。借助影子价格进行内部核算。特别注意特别注意第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析六、对偶单纯形法六、对偶单纯形法基本思路基本思路原单纯型迭代要求每步都是基础可行解原单纯型迭代要求每步都是基础可行解达到最优解时，检验数达到最优解时，检验数cjzj 0(max)或或cjzj 0(min)但对于但对于(min, )型所加的剩余变量无法构成初始基础型所加的剩余变量无法构成初始基础可行解，因此通过加人工变量来解决可行解，因此通过加人工变量来解决大大M法和二阶段法较繁法和二阶段法较繁能否从能否从剩余变量构成的初始基础非可行解出发剩余变量构成的初始基础非可行解出发迭代，迭代，但保证但保证检验数满足最优条件，检验数满足最优条件，cjzj 0(max)或或cjzj 0(min)，保持对偶问题是基可行解，原问题在，保持对偶问题是基可行解，原问题在非可行解的基础上，通过逐步迭代达到基可行解。非可行解的基础上，通过逐步迭代达到基可行解。第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析对偶单纯形的计算步骤如下：对偶单纯形的计算步骤如下：1确定出变量确定出变量找非可行解中最小者，即找非可行解中最小者，即minbi |bi0,可可使使用用原原始始单单纯纯形形法法继继续续迭迭代代求求出出新新的最优解。的最优解。第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析如从最优表中，如从最优表中，C C3 3是非基变量是非基变量x x3 3 的系数，当的系数，当C C3 3变变化时，只会影响到化时，只会影响到 3 3。当当cr是是基基变变量量xr的的价价值值系系数数它它的的变变化化将将影影响所有非基变量的检验数响所有非基变量的检验数，为什麽？，为什麽？当当cr变变化化时时，如如能能保保持持，则则当当前前解解仍仍为为最最优优解解，否否则则可可用用单单纯纯形形法法继继续续迭迭代代求求出出新新的最优解的最优解。将将cr看作待定参数，令看作待定参数，令解这解这n-m个不等式，可算出保持最优解不变个不等式，可算出保持最优解不变时时cr的变化范围的变化范围！第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析例：当例：当c1发生变化时，仍用发生变化时，仍用c1代表代表x1的价值系的价值系数（看成待定参数），原最优表格即为：数（看成待定参数），原最优表格即为：012-1/31/3cjxjCBXBbc13300X1X2X3X4X5c13X1X21210-14/3-1/3-Z-c1-600c1-31-4/3c11/3c1-1第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析令所有检验数小于令所有检验数小于0，得不等式组：，得不等式组：解该不等式组得：解该不等式组得：说明当说明当时，最优解不变。时，最优解不变。当当c13时时,有有,可选可选x3或或x5进基进基,x2出基出基.第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析资源数量资源数量bi变换的分析变换的分析当当bi发生变化时，将影响所有基变量的取值。为什麽？发生变化时，将影响所有基变量的取值。为什麽？因为：因为：因为因为：保保持持B-1b0,当当前前的的基基仍仍为为最最优优基基，最最优优解解的的结结构构不变（取值改变）；不变（取值改变）；（B-1b）i0,当当前前基基为为非非可可行行基基,但但是是仍仍保保持持为为对对偶偶可行基可行基,(为什麽为什麽?),可用对偶单纯形法求出新的最优解；可用对偶单纯形法求出新的最优解；如何求出保持最优基不变的如何求出保持最优基不变的bi的范围的范围?把把bi看作待定参数看作待定参数,令令B-1b0,求解该不等式组即可；求解该不等式组即可； 10-14/3-1/3012-1/31/312X1X22300-1-5/3-1/3-8-Z233000-Z3/19/1111101470139X4X500j23300x1 x2 x3 x4 x5CjbxjXBCB仍然来看上例的最优表格：仍然来看上例的最优表格：原原b1=3，现现用用待待定定参参数数b1代代替替3，则最优表中的解答列应为：则最优表中的解答列应为：若若b1的的变变化化超超出出这这个个范范围围，则则解解答答列列中中至至少少有有一一个个元元素小于素小于0，可用对偶单纯形法迭代求出新的最优解。，可用对偶单纯形法迭代求出新的最优解。7.37.3技术系数技术系数技术系数技术系数ij ij的变化的变化的变化的变化 分两种情况来讨论技术系数分两种情况来讨论技术系数ij的变化，下面以具体例子来说明。的变化，下面以具体例子来说明。例例9分分析析在在原原计计划划中中是是否否应应该该安安排排一一种种新新产产品品。以以第第1章章例例1为为例例。设设该该厂厂除除了了生生产产产产品品，外外，现现有有一一种种新新产产品品III。已已知知生生产产产产品品III，每每件件需需消消耗耗原原材材料料A，B各各为为6kg，3kg，使使用用设设备备2台台时时；每每件件可可获获利利5元元。问问该该厂厂是是否否应应生生产产该该产产品品和和生生产多少产多少?解解分析该问题的步骤是：分析该问题的步骤是：分析该问题的步骤是：分析该问题的步骤是：(1)设设生生产产产产品品II为为x3台台，其其技技术术系系数数向向量量P3=(2,6,3)T，然后计算最终表中对应，然后计算最终表中对应x3的检验数的检验数3=c3-CB-13=5-(1.5,0.125,0)(2,6,3)T=1.250说明安排生产产品说明安排生产产品III是有利的。是有利的。 分析该问题的步骤分析该问题的步骤分析该问题的步骤分析该问题的步骤(2)(2)是：是：是：是： 表表2-13(a)由于b列的数字没有变化，原问题的解是可行解。但检验数行中还有正检验数，说明目标函数值还可以改善。分析该问题的步骤分析该问题的步骤分析该问题的步骤分析该问题的步骤(3)(3)是是是是：(3) (3) 将将x x3 3作作为为换换入入变变量量，x x5 5作作为为换换出出变变量量，进进行行迭迭代代，求求出出最最优优解解。计计算算结结果果见见表表2-13(b)2-13(b)，这这时时得得最最优优解解：x x1 1=1,x=1,x2 2=1.5=1.5，x x3 3=2=2。总总的的利利润润为为16.516.5元元。比比原原计计划增加了划增加了2.52.5元。元。表表2-13(b)2-13(b)例例10 10 分析原计划生产产品的工艺结构发生变化。分析原计划生产产品的工艺结构发生变化。仍以第仍以第1 1章例章例1 1为例，若原计划生产产品为例，若原计划生产产品的工艺结的工艺结构有了改进，这时有关它的技术系数向量变为构有了改进，这时有关它的技术系数向量变为P P1 1=(2,5,2)=(2,5,2)T T，每件利润为，每件利润为4 4元，试分析对原最优计元，试分析对原最优计划有什么影响划有什么影响? ? 解解解解 把改进工艺结构的产品把改进工艺结构的产品把改进工艺结构的产品把改进工艺结构的产品看作产品看作产品看作产品看作产品，设，设，设，设x x x x1 1 1 1为其产量。为其产量。为其产量。为其产量。于是在原于是在原于是在原于是在原计计计计算的最算的最算的最算的最终终终终表中以表中以表中以表中以x x x x1 1 1 1代替代替代替代替x x x x1 1 1 1，计计计计算算算算对应对应对应对应x x x x1 1 1 1的列向量。的列向量。的列向量。的列向量。同时计算出x1的检验数为c1-CBB-1P1=4-(1.5,0.125,0)(2,5,2)T=0.375将以上计算结果填入最终表x1的列向量位置.得表2-14。表表表表2-142-14可见x1为换入变量，x1为换出变量，经过迭代。得到表2-15表表表表2-152-15表表2-152-15表表明明原原问问题题和和对对偶偶问问题题的的解解都都是是可可行行解解。所所以以表表中中的的结结果果已已是是最最优优解解。即即应应当当生生产产产产品品，3.23.2单位；生产产品单位；生产产品，0.80.8单位。可获利单位。可获利15.215.2元。元。注意：注意： 若若碰碰到到原原问问题题和和对对偶偶问问题题均均为为非非可可行行解解时时，就就需需要要引进引进人工变量人工变量后重新求解。后重新求解。例例例例11 11 11 11 假设例假设例假设例假设例10101010的产品的产品的产品的产品的技术系数向量变为的技术系数向量变为的技术系数向量变为的技术系数向量变为P P P P1 1 1 1=(4,5,2)=(4,5,2)=(4,5,2)=(4,5,2)T T T T，而每件获利仍为，而每件获利仍为，而每件获利仍为，而每件获利仍为4 4 4 4元。试问该厂应如何安元。试问该厂应如何安元。试问该厂应如何安元。试问该厂应如何安排最优生产方案排最优生产方案排最优生产方案排最优生产方案? ? ? ?解方法与例方法与例10相同，以相同，以x1代替代替x1，并计算列向量，并计算列向量x1的检验数为c1-CBB-1P1=4-（1.5,0.125,0)(4,5,2)T = -2.625。将这些数字填入最终表1-15的x1列的位置，得到表2-16。表表表表2-162-16将表2-16的x1变换为基变量，替换x1，得表2-17。 从表2-17可见原问题和对偶问题都是非可行解。于是引入人工变量x6。因在表2-17中x2所在行，用方程表示时为0x1+x2+0.5x3-0.4x4+0x5= -2.4表表表表2-172-17引入人工变量引入人工变量x x6 6后，便为后，便为-x-x2 2-0.5x-0.5x3 3+0.4x+0.4x4 4+x+x6 6=2.4=2.4将将x x6 6作作为为基基变变量量代代替替x x2 2，填填入入表表2-172-17，得得到到表表2-182-18。表表表表2-182-18这时可按单纯形法求解。这时可按单纯形法求解。X4为换入变量，为换入变量，x6为换出变量。经基变换运算后，得到表为换出变量。经基变换运算后，得到表2-19的上表。的上表。在表在表2-19的上表中，确定的上表中，确定x2为换入变量，为换入变量，x5为换出变量。经基为换出变量。经基变换运算后，得到表变换运算后，得到表2-19的下表。的下表。此表的所有检验数都为非正，已得最优解。最优生产方案为此表的所有检验数都为非正，已得最优解。最优生产方案为生产产品生产产品，0.667单位；产品单位；产品，2.667单位，可得最大利单位，可得最大利润润10.67元。元。表表表表2-192-19系数阵系数阵A A的元素发生变化：的元素发生变化：（1 1）增加）增加1 1个新变量：相当于系数阵个新变量：相当于系数阵A A增加增加1 1列列如如开开发发出出一一种种新新产产品品，已已知知其其有有关关工工艺艺参参数数（或或消消耗耗的的资资源源量量）和和单单位位产产品品利利润润，设设该该种种产产品品的的产产量量为为x xk k，则则c ck k和和P Pk k已已知知，需需要要进进行行“是是否投产否投产”的决策的决策。如例中欲增加产品如例中欲增加产品D，单件利润，单件利润为为c6=5千元，工时消耗与材料千元，工时消耗与材料消耗为消耗为相相当当于于在在原原始始表表中中增增加加1列列P6，则则在在最最优优表表中中P6应变成应变成相应的检验数：相应的检验数：在此基础上继续迭代，直至求出最优解：在此基础上继续迭代，直至求出最优解：23CBXBcjxjbjX1X2X3X4X5X6X1X2121/(5/3)2/(1/3)-Z-800-1-5/3-1/32/353X6X23/59/53/50-3/54/5-1/51-1/5111/5-3/52/50-Z-42/5-2/50-3/5-11/5-1/5023300510-14/3-1/35/3012-1/31/31/3q-Zq-800-1-5/3-1/32/3-Z-42/52/50-3/5-11/5-1/5023CBXBcjxjbjX1X2X3X4X5X6X1X2121/(5/3)2/(1/3)-Z-800-1-5/3-1/32/353X6X23/59/53/50-3/54/5-1/51-1/5111/5-3/52/50-Z-42/5-2/50-3/5-11/5-1/5023300510-14/3-1/35/3012-1/31/31/3q-Z说说明明新新产产品品D应应于于投投产产，新新的的生生产产计计划划为为X*=(0,9/5,0,0,0,3/5)T,即即生生产产B产产品品5/9吨吨,生生产产D产产品品3/5吨吨,两两种种资资源源全全部部用用完完,可可得得到到最大利润为最大利润为8.4(千元千元)(42/5=8.4)。如如果果算算出出的的60,说说明明新新产产品品D不不宜宜投投产产，否则会使产品总利润下降！否则会使产品总利润下降！(2) (2) 增加增加1 1个约束条件：个约束条件： 相当于系数阵相当于系数阵A A增加增加1 1行行 q 首首先先将将原原最最优优解解代代入入新新增增约约束束检检查查是是否否满满足足？是是，则则说说明明新新增增约约束束不不影影响响最最优解。优解。否则再作下面的讨论：否则再作下面的讨论： 将将新新增增约约束束标标准准化化，添添加加到到原原最最优优表表格中（相当于约束矩阵新增格中（相当于约束矩阵新增1 1行）；行）； 进进行行规规格格化化处处理理用用矩矩阵阵的的行行变变换换将当前基变成单位阵；将当前基变成单位阵； 用适当方法（通常是对偶单纯形法）用适当方法（通常是对偶单纯形法）进行迭代求出新的最优解。进行迭代求出新的最优解。 如如 在在 上上 例例 中中 增增 加加 约约 束束 ：2x2x1 1+2x+2x2 2+x+x3 35,5,当当前前最最优优解解x x1 1=1,x=1,x2 2=2,x=2,x3 3=0=0不不满满足足该该约约束束，将将约约束束条条件件标标准准化化后后加加入入原原最最优优表表格格，进进行行规规格格化化处处理理，然然后后用用对对偶偶单单纯纯形形法法迭迭代代求求出新的最优解：出新的最优解：-ZCBXBcjxjb233005X1X2X3X4X5X6230X1X2X612510-14/3-1/30012-1/31/30221001230X1X2X612-110-14/3-1/30012-1/31/3000-1-20100-1-5/3-1/30比比 值值-15/6-230X1X2X41/313/61/210-5/30-1/32/30113/601/3-1/6001/210-1/2-Z-43/6-43/600-1/60-1/3-5/6-Zq-800-1-5/3-1/30第第8 8节节* * 参数线性规划参数线性规划灵灵敏敏度度分分析析时时，主主要要讨讨论论在在最最优优基基不不变变情情况况下下，确确定定系数系数a aijij，b bi i，c cj j的变化范围。的变化范围。而而参参数数线线性性规规划划是是研研究究这这些些参参数数中中某某一一参参数数连连续续变变化化时时，使使最最优优解解发发生生变变化化的的各各临临界界点点的的值值。即即把把某某一一参参数数作作为为参参变变量量，而而目目标标函函数数在在某某区区间间内内是是这这个个参参变变量量的的线线性性函函数数，含含这这个个参参变变量量的的约约束束条条件件是是线线性性等等式式或或不等式。不等式。因因此此仍仍可可用用单单纯纯形形法法和和对对偶偶单单纯纯形形法法分分析析参参数数线线性性规规划问题。其步骤是：划问题。其步骤是：(1) (1) 对对含含有有某某参参变变量量t t的的参参数数线线性性规规划划问问题题。先先令令t=0t=0，用单纯形法求出最优解；，用单纯形法求出最优解；(2) (2) 用灵敏度分析法，将参变量用灵敏度分析法，将参变量t t直接反映到最终表中；直接反映到最终表中；(3) (3) 当当参参变变量量t t连连续续变变大大或或变变小小时时，观观察察b b列列和和检检验验数数行行各各数数字字的的变变化化。若若在在b b列列首首先先出出现现某某负负值值时时，则则以以它它对对应应的的变变量量为为换换出出变变量量；于于是是用用对对偶偶单单纯纯形形法法迭迭代代一一步步。若若在在检检验验数数行行首首先先出出现现某某正正值值时时，则则将将它它对对应应的的变量为换入变量；用单纯形法迭代一步；变量为换入变量；用单纯形法迭代一步；(4) (4) 在在经经迭迭代代一一步步后后得得到到的的新新表表上上，令令参参变变量量t t继继续续变变大大或或变变小小，重重复复步步骤骤(3)(3)，直直到到b b列列不不能能再再出出现现负负值，检验数行不能再出现正值为止。值，检验数行不能再出现正值为止。8.1 8.1 参数参数c c的变化的变化例例12 12 试试分分析析以以下下参参数数线线性性规规划划问问题题。当当参参数数t0t0时的最优解变化。时的最优解变化。解解解解 将此模型化为标准型将此模型化为标准型将此模型化为标准型将此模型化为标准型令令令令t=0t=0t=0t=0，用单纯形法求解，用单纯形法求解，用单纯形法求解，用单纯形法求解的结果的结果的结果的结果，见表见表见表见表2-202-202-202-20。将将将将c c的变化直接反映到最终表的变化直接反映到最终表的变化直接反映到最终表的变化直接反映到最终表2-202-20中，得表中，得表中，得表中，得表2-212-21。计算t的变化范围当当当当 t t值变化，在值变化，在值变化，在值变化，在4 40 0，即，即，即，即0 0t t9/79/7时，为最优解时，为最优解时，为最优解时，为最优解(2,6,2,0,0)(2,6,2,0,0)T T；当当当当 t t值增大，值增大，值增大，值增大，t t(3/2)/(7/6)=9/7(3/2)/(7/6)=9/7时，时，时，时，在检验数行在检验数行在检验数行在检验数行首先出现首先出现首先出现首先出现4 40 0；表表表表示还可以继续改进。示还可以继续改进。示还可以继续改进。示还可以继续改进。t=9/7t=9/7为第一临界点。当为第一临界点。当为第一临界点。当为第一临界点。当t t9/79/7时，时，时，时，4 40 0，这，这，这，这时时时时x x4 4作为换入变量。用单纯形法迭代一步，得表作为换入变量。用单纯形法迭代一步，得表作为换入变量。用单纯形法迭代一步，得表作为换入变量。用单纯形法迭代一步，得表2-222-22。 当当当当t t t t继续增大继续增大继续增大继续增大t(5/2)/(1/2)=5t(5/2)/(1/2)=5t(5/2)/(1/2)=5t(5/2)/(1/2)=5时，时，时，时，在检验数行在检验数行在检验数行在检验数行首先出现首先出现首先出现首先出现5 5 5 50000，在，在，在，在5 5 5 50000，即，即，即，即9/7t59/7t59/7t59/7t5时，得最优解时，得最优解时，得最优解时，得最优解(4,3,0,6,0) (4,3,0,6,0) (4,3,0,6,0) (4,3,0,6,0) T T 。t=5t=5t=5t=5为第二临界点。当为第二临界点。当为第二临界点。当为第二临界点。当t t t t5 5 5 5时，时，时，时，5 5 5 50 0 0 0，这时，这时，这时，这时x x x x5 5 5 5作为换入变量作为换入变量作为换入变量作为换入变量，用单纯形法迭代一步，得表，用单纯形法迭代一步，得表，用单纯形法迭代一步，得表，用单纯形法迭代一步，得表2-232-232-232-23。t 继续增大时，在检验数行恒有2，30，故当t5时，最优解为(4，0，0，12，6)T。8.2 8.2 参数参数b b的变化分析的变化分析例例13分分析析以以下下线线性性规规划划问问题题，当当t0时时，其其最最优优解解的的变变化范围。化范围。解解 将上述模型化为标准型将上述模型化为标准型将上述模型化为标准型将上述模型化为标准型令令令令t=0t=0，用单纯形法迭代两次，求解，用单纯形法迭代两次，求解，用单纯形法迭代两次，求解，用单纯形法迭代两次，求解的结果的结果的结果的结果，见，见，见，见表表表表2-242-24。将此计算结果反映到最终表将此计算结果反映到最终表将此计算结果反映到最终表将此计算结果反映到最终表2-242-24，得，得，得，得表表表表2-252-25。在表在表在表在表2-252-252-252-25中中中中进行分析进行分析进行分析进行分析 ，当，当，当，当t t t t增大至增大至增大至增大至t2t2t2t2时，时，时，时，则则则则b0b0b0b0；即；即；即；即0t20t20t20t2时，最优解为时，最优解为时，最优解为时，最优解为 (2-t.4,0,0)(2-t.4,0,0)T T。当当当当t t2 2时，则时，则时，则时，则b b1 10 0；故将；故将；故将；故将x x1 1作为换出变量，用对偶单纯形法迭代一步，作为换出变量，用对偶单纯形法迭代一步，作为换出变量，用对偶单纯形法迭代一步，作为换出变量，用对偶单纯形法迭代一步，得表得表得表得表2-262-26结论结论从从表表2-262-26可可见见，当当t t6 6时时，问问题题无无可可行行解解；当当2t62t6时，问题的最优解为时，问题的最优解为(0，6-t，0，-6+3t)T。第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析.已知线性规划问题已知线性规划问题s.t.用单纯形方法求解得最终单纯形如下表用单纯形方法求解得最终单纯形如下表试确定试确定:(1)当目标函数变为当目标函数变为时时,最优解会出最优解会出现什么变化现什么变化?(2)当目标函数变为当目标函数变为时时,在什在什么范围内变化么范围内变化,最优解不变最优解不变?(3)若第若第2个约束条件的右端项增大到个约束条件的右端项增大到32时时,分析最优解的分析最优解的变化变化;(4)若第若第2个约束条件变为个约束条件变为,分析分析在什么范围内变化在什么范围内变化,表中基为最优基表中基为最优基?第二章第二章对偶理论和灵敏度分析对偶理论和灵敏度分析解：解：（1）新解）新解(2)时时,最优解不变最优解不变.（3）最优解为最优解为（4）时时,最优解不变最优解不变.分析下列参数规划问题中当分析下列参数规划问题中当变化时最优解的变化情变化时最优解的变化情况况.1、解：解：