第二章线性规划的对偶理论与灵敏度分析课件

§2线性规划的对偶理论与灵敏度分析§2-1线性规划的对偶问题对偶:在不同的领域有着不同的诠释。在词语中，它是一种修辞方法，两个字数相等、结构相似的语句表现相关或相反的意思。在数学上表现为数式或图形的对称,命题或结构的对应

§2线性规划的对偶理论与灵敏度分析§2-1线性规划的11.对偶问题的提出例1第一章例1中美佳公司利用该公司资源生产两种家电产品时,其线性规划问题为1.对偶问题的提出例1第一章例1中美佳公司利用该2

假定有某个公司想把美佳公司的资源买过来，它至少应付出多大代价，才能使美住公司愿意放弃生产活动，出让自己的资源。美佳公司愿意让自己资源的条件是，出让代价应不低于用同等数量资源由自己组织生产活动时获取的赢利。1.对偶问题的提出假定有某个公司想把美佳公司的资源买过来，它至少应付出3用y1，y2，y3代表单位时间设备A、设备B和调试工序的出让代价，为使美佳公司愿意出让自己的资源（出售资源后所得不应比生产产品所得少），则：

收购美佳公司应付出的代价为（总的收购价越小越好）：15y1+24y2+5y31.对偶问题的提出用y1，y2，y3代表单位时间设备A、设备B和调试工序的出让41.对偶问题的提出1.对偶问题的提出5)2(LPïîïíì³³++³+++=0,,12526st.

52415min32132132321yyyyyyyyyyyw比较LP1和LP2)2(LPïîïíì³³++³+++=0,,12526st.6对偶问题minW=Y’b

A’Y

C’Y0maxZ=CX

AX

bX0原问题每个线性规划问题都存在一个与其对应的对偶问题对偶问题minW=Y’bmaxZ=CX原问题72.对偶问题的一般形式2.对偶问题的一般形式8矩阵形式表示原－对偶问题原问题(P) 对偶问题(D)价格系数—————— 资源向量资源向量—————— 价格系数最大化—————— 最小化变量个数—————— 约束个数约束个数—————— 变量个数约束系数行 ————— 约束系数列互称对偶问题对应关系：矩阵形式表示原－对偶问题原问题(P) 对偶93.非对称形式的原－对偶问题关系3.非对称形式的原－对偶问题关系10第二章线性规划的对偶理论与灵敏度分析课件11第二章线性规划的对偶理论与灵敏度分析课件12对偶变换的规则约束条件的类型与非负条件对偶非标准的约束条件类型对应非正常的非负条件对偶变换的规则约束条件的类型与非负条件对偶13练习：练习：14矩阵形式表示原－对偶问题原问题(P) 对偶问题(D)价格系数—————— 资源向量资源向量—————— 价格系数最大化—————— 最小化变量个数—————— 约束个数约束个数—————— 变量个数约束系数行 ————— 约束系数列互称对偶问题对应关系：矩阵形式表示原－对偶问题原问题(P) 对偶15对偶变换的规则约束条件的类型与非负条件(非负约束)对偶非标准的约束条件类型对应非正常的非负条件对偶变换的规则约束条件的类型与非负条件(非负约束)对偶16§2-2对偶问题的基本性质1.对称性：一个线性规划的对偶问题的对偶问题即是原问题2.弱对称性：假定X是原规划（P）的任一可行解，Y是对偶规划（D）的任一可行解，则有CX≤bTY3.无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解§2-2对偶问题的基本性质1.对称性：一个线性规174.设X是原问题的可行解，Y是对偶问题的可行解，当CX＝bTY时，X，Y皆为最优解。5.强对偶性原规划有最优解，则对偶规划也有最优解，且最优值相同。6.互补松弛性(松紧定理)在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值非0，则该约束取严格等式，如果约束条件取严格不等式，其对应的对偶变量一定为0。§2-2对偶问题的基本性质4.设X是原问题的可行解，Y是对偶问题的可行解，当CX18原问题与对偶问题最终单纯型表的比较原问题与对偶问题最终单纯型表的比较19第二章线性规划的对偶理论与灵敏度分析课件20在最优解的单纯型表中，原问题虚变量(松弛或剩余)的检验数对应对偶问题实变量(对偶变量)的最优解，原问题实变量(决策变量)的检验数对应对偶问题虚变量(松弛或剩余变量)的最优解。在最优解的单纯型表中，原问题虚变量(松弛或剩余)的检21例：min

=2x1+3x2+5x3+2x4+3x5其对偶解y1﹡=4/5y2﹡=3/5Z﹡=5用对偶理论求(P)的最优解x1+x2+2x3+x4+3x542x1-x2+3x3+x4+x53

xi0(i=1…5)(P)对偶性质的应用例：min=2x1+3x2+5x3+2x4+3x522解：(D)为maxZ

=4y1+3y2y1+2y22①y1-y23②2y1+3y25③y1+y22④3y1+y23⑤y1,

y20其对偶解y1﹡=4/5y2﹡=3/5解：(D)为maxZ=4y1+3y2其对偶解y1﹡=23将y1﹡，y2﹡代入，知②,③,④为严格不等式∴x2=x3=x4=0∴x

=(1,0,0,0,1)T

Z=5由y1﹡，y2﹡﹥0知原约束为等式

x1+3x5=42x1+x5=3将y1﹡，y2﹡代入，知②,③,④为严格不等式∴x24§2—3影子价格§2—3影子价格25

当线性规划原问题求得最优解xj*时，其对偶问题也得到最优解yi*，且式中bi*是线性规划原问题约束条件的右端项，代表第i种资源的拥有量；对偶变量yi*的意义代表在资源最优利用条件下对单位第i种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，这个概念在西方经济学中称为影子价格当线性规划原问题求得最优解xj*时，其对偶问题26影子价格提供的信息1.影子价格可以告诉决策者，增加哪一种资源对增加效益最有利。影子价格提供的信息1.影子价格可以告诉决策者，增加哪一种资27第二章线性规划的对偶理论与灵敏度分析课件28

资源1影子价格为0，增加与否对总利润没有影响。 资源2影子价格为1，增加一个单位，总利润增加1， 资源3影子价格为3，增加一个单位，一产品产量34件，二产品产量12，总利润218，增加3，资源3对目标函数贡献最大， 资源3售价 <3购入生产获利 >3卖出获利资源1影子价格为0，增加与否对总利润没有影响。292.影子价格可以告诉决策者，用多大代价增加资源才是合算——机会成本。如：资源3的影子价格为3，即增加一个单位的会使收益增加3，获取资源3的代价<3，就可以获利。3.影子价格告诉决策者，资源利用程度对线性规划问题的求解是确定资源的最优分配方案，对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及资源的最有效利用。影子价格不为零，则该资源已消耗完毕；影子价格为零，则该资源没有充分利用2.影子价格可以告诉决策者，用多大代价增加资源才是合算——30§2－4对偶单纯形法§2－4对偶单纯形法31第二章线性规划的对偶理论与灵敏度分析课件32对某标准形式的线性规划问题当所有检验数小于等于零（cj-zj≤0），bi≥0；此线性规划问题取得最优解。若存在bi<0,则用对偶单纯形法进行求解。对某标准形式的线性规划问题当所有检验数小于等33应用对偶单纯形法进行求解时，bi的值不要求为正。单纯形法计算的前提是bi的值总保持非负，对偶单纯形法计算的前提是检验数总保持非正。应用对偶单纯形法进行求解时，bi的值不要求34对偶单纯形法基本步骤max型(min型)(1)、确定初始基Bo,作初始表，使全部σj

0(0)(2)、检验：若B-1b0，是最优。否则转（3）(b)l=min{(b)i}----xl出基b<0(3)、基变换，先确定出基变量xl对偶单纯形法基本步骤max型(min型)(1)、确35再确定换入基变量①若Xl所在行的alj全0，停，原问题无可行解。②若Xl行的alj有alj<0,则求θ=min{}=σjσkaljalkalj<0

Xk为换入变量(4)、以alk为主元，换基迭代再确定换入基变量①若Xl所在行的alj全036第二章线性规划的对偶理论与灵敏度分析课件37第二章线性规划的对偶理论与灵敏度分析课件38第二章线性规划的对偶理论与灵敏度分析课件39第二章线性规划的对偶理论与灵敏度分析课件40

对偶单纯形法的局限性主要是，对大多数线性规划问题，很难找到一个初始可行基，因而这种方法在求解线性规划问题时很少单独应用.对偶单纯形法的局限性主要是，对大多数线性规划问题，很41§2-5灵敏度分析§2-5灵敏度分析42

灵敏度是指对系统或事物因周围条件变化显示出来的敏感程度。在线性规划问题中，假定aij,bi,cj是己知常数。但实际上这些数往往是一些估计和预测的数字，如随市场条件变化，cj值就会变化。aij随工艺技术条件的改变而改变，而bi值是根据资源投入后能产生多大经济效果来决定的一种决策选择。

§2-5灵敏度分析灵敏度是指对系统或事物因周围条件变化显示出来的敏感程43

当这些参数中的一个或几个发生变化时，问题的最优解会有什么变化，或者这些参数在一个多大范围内变化时，问题的最优解不变。这就是灵敏度分析所要研究解决的问题。

当线性规划问题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。可以用单纯形法从头计算，以便得到新的最优解。这样做很麻烦，而且也没有必要。可以把发生变化的个别系数，经过一定计算后直接填入最终计算表中，并进行检查和分析，§2-5灵敏度分析当这些参数中的一个或几个发生变化时，问题的最优44LP的灵敏度分析的步骤：⑴分析问题，建立适当的LP模型；⑵求解LP模型；

⑶将参数的改变通过计算反映到最终单纯形表上；(4)检查原问题是否仍为可行解；(5)检查对偶问题是否仍为可行解LP的灵敏度分析的步骤：(4)检查原问题是否仍为可行解；45第二章线性规划的对偶理论与灵敏度分析课件46初始基变量在最终单纯形表中对应的系数矩阵初始基变量在最终单纯形表中对应的系数矩阵471.分析Cj变化方法：

cj

的变化只影响检验数的变化，只需要计算变化后的检验数，并反映到最终单纯形表中。

1.分析Cj变化方法：48第二章线性规划的对偶理论与灵敏度分析课件49第二章线性规划的对偶理论与灵敏度分析课件50为使原线性规划问题的解仍为最优解，应有为使原线性规划问题的解仍为最优解，应有512.分析bi变化

右端项b的变化在实际问题中反映为可用资源数量的变化，b的变化反映到最终单纯形表中将引起b列数字的变化，出现两种情况：(1)变换后所有b的值依然为非负，问题的最优基不变，变换后的b列值为最优解。(2)变换后b存在负值，用对偶单纯形法迭代，继续寻找最优解。2.分析bi变化右端项b的变化在实际问题中反52第二章线性规划的对偶理论与灵敏度分析课件53第二章线性规划的对偶理论与灵敏度分析课件54第二章线性规划的对偶理论与灵敏度分析课件55第二章线性规划的对偶理论与灵敏度分析课件56第二章线性规划的对偶理论与灵敏度分析课件573.增加一个变量xn+1方法：问题：所加的变量是否最优（新产品是否投产），即增加是否有利？原最优解不变，按单纯形法继续迭代计算，3.增加一个变量xn+1方法：问题：所加的变量是否最优（新58第二章线性规划的对偶理论与灵敏度分析课件59第二章线性规划的对偶理论与灵敏度分析课件60第二章线性规划的对偶理论与灵敏度分析课件614.分析参数aij的变化aij的变化使线性规划的约束系数矩阵A发生变化。若变量xj在最终单纯形表中为非基变量，其约束条件中系数aij的变化分析，相当于增加一种新产品。4.分析参数aij的变化aij的变化使线性规62若变量xj在最终单纯形表中为基变量，则aij的变化将使B和B-1发生变化，因此有可能出现原问题和对偶问题均为非可行解的倩况。出现这种倩况，需引进人工变量先将原问题的解转化为可行解，再用单纯形法求解。4.分析参数aij的变化若变量xj在最终单纯形表中为基变量，则aij的63例8在美佳公司中，若家电Ⅱ每件需设备A,B和调试工时变为8h、4h、1h，该产品的利润变为3元/件，重新确定公司最优生产计划。解先将生产工时变化后的新家电Ⅱ看作是一种新产品，生产量为x´2，例8在美佳公司中，若家电Ⅱ每件需设备A,B和调试工时变为864第二章线性规划的对偶理论与灵敏度分析课件65原问题与对偶问题均为非可行解，故先设法使原问题变为可行解。原问题与对偶问题均为非可行解，故先设法使原问题变为可行解。66第二章线性规划的对偶理论与灵敏度分析课件67用单纯形法计算得最优生产计划:每天生产家电11/4件Ι,15/8件新家电Ⅱ用单纯形法计算得最优生产计划:每天生产家电11/4件Ι,1685.增加一个约束条件的分析

增加一个约束条件在实际问题中相当于增添一道工序。分析的方法是先将原问题最优解的变量值代人新增的约束条件，如满足，说明新增的约束末起到限制作用，原最优解不变。否则，将新增的约束直接反映到最终单纯形表中再进一步分析。5.增加一个约束条件的分析增加一69例9以美佳公司为例，设家电Ⅰ，Ⅱ经调试后，还需要经过一道环境试验工序，家电Ⅰ每件须环境试验3h，家电Ⅱ每件2h，又环境试验工序每天生产能力为12h.试分析增加该工序后的美佳公司最优生产计划。3×7/2+2×3/2=27/2>12原问题最优解不是本例的最优解例9以美佳公司为例，设家电Ⅰ，Ⅱ经调试后，还需要经过一道70x1、x2列不是单位向量，故需进行初等变换，x1、x2列不是单位向量，故需进行初等变换，71第二章线性规划的对偶理论与灵敏度分析课件72用对偶单纯形法迭代计算得用对偶单纯形法迭代计算得73第二章线性规划的对偶理论与灵敏度分析课件74允许的增量和