第二章对偶理论与灵敏度分析

第二章对偶理论与灵敏度分析课件第1页，课件共133页，创作于2023年2月本章重点1、掌握写出对偶问题的方法，原问题与其对偶问题的对应关系2、掌握对偶问题的基本理论和性质3、理解影子价格的定义和意义4、理解并掌握对偶单纯形方法的思想和步骤5、掌握线性规划灵敏度分析(1)资源数量bi

发生变化的分析(2)目标函数中价值系数cj发生变化的分析难点难点第2页，课件共133页，创作于2023年2月XBXNXSbXBBNIbCCBCN00了解----单纯形的矩阵描述XS为松弛变量第3页，课件共133页，创作于2023年2月XBXNXSbXBIB－1NB－1B－1b

N0CN－CBB－1N－CBB－1－CBB－1b单纯性法计算时，总选取单位矩阵I为初始基，对应基变量为XS,设迭代若干步后，基变量变为XB,XB在初始单纯性表中的系数矩阵为B。则该步的单纯性表中由XB

系数组成的矩阵为单位矩阵I，对应XS的系数矩阵在新表中应为B-1

Y=CBB-1称为单纯性乘子（对偶变量）第4页，课件共133页，创作于2023年2月2.3对偶问题提出

例2.2：某公司在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及AB两种原材料的消耗如表所示，该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元，问应该如何安排计划使该工厂获利最多？

举例2第5页，课件共133页，创作于2023年2月Chapter2灵敏度分析

先根据图表来列出模型

MaxZ=2X1+3X2

X1+2X2≤8

4X1≤16

4X2≤12

X1,X2≥0

举例第6页，课件共133页，创作于2023年2月设用y1,y2,y3分别表示出租单位设备台时的租金和出让单位原材料A,B的附加额.

现在从另一个角度来考虑企业的决策问题。假如企业自己不生产产品，而将现有的资源转让或出租给其它企业，那么资源的转让价格是多少才合理？合理的价格应是对方用最少的资金购买本企业的全部资源，而本企业所获得的利润不应低于自己用于生产时所获得的利润。这一决策问题可用下列线性规划数学模型来表示。第7页，课件共133页，创作于2023年2月他在做定价决策时,作如下比较:若用一个单位设备台时和4个单位原材料A可以生产一件产品I,可获利2元,那么生产每件产品I的设备台时和原材料出租和出让的所有收入应不低于生产一件产品I的利润,这就有y1+4y2≥2第8页，课件共133页，创作于2023年2月

同理将生产每件产品II的设备台时和原材料的出租和出让的所有收入应不低于生产一件产品II的利润,这就有2y1+4y3≥3

把工厂所有设备台时和资源都出租和出让,其收入为

f=8y1+16y2+12y3第9页，课件共133页，创作于2023年2月从工厂决策者的角度来看，f当然是越大越好,但从接受者眼光来说f是越少越好,所以工厂决策者只可以在满足≥ 所有产品的利润条件下,使其总收入尽可能的小.因此第10页，课件共133页，创作于2023年2月我们称这个线性规划问题为线性规划问题（这称为原问题）的对偶问题。各模型中有关数据的“位置”示意图如下。

矩阵A矩阵AT第11页，课件共133页，创作于2023年2月对偶问题提出例2.3某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。第12页，课件共133页，创作于2023年2月表2.3第13页，课件共133页，创作于2023年2月不难得出下面一对对偶问题。原问题

第14页，课件共133页，创作于2023年2月对偶问题

不少于甲产品的利润不少于乙产品的利润第15页，课件共133页，创作于2023年2月例2.4：资源利用问题考虑：资源拥有者为了实现一定的收入目标，将其所拥有的资源出售，给每一种资源如何定价？

第16页，课件共133页，创作于2023年2月解：表示出售单位数量的第i种资源的价格。资源拥有者在做出售资源的决策时，考虑出售资源的收入不应该低于生产所获得的收入，则有：第17页，课件共133页，创作于2023年2月如果资源拥有者将所有资源出售，则他得到的总收入

f=第18页，课件共133页，创作于2023年2月资源拥有者出售每一种资源的最低估价，可通过求解线性规划问题而得到。第19页，课件共133页，创作于2023年2月对同一个资源利用问题，从不同的角度考虑，可以得到两个相互联系的线性规划模型，这就是线性规划的对偶问题。第20页，课件共133页，创作于2023年2月由上面的例子我们可以知道原问题与对偶问题的关系1．线性规划问题是对称形式

Maxz=CXMinf=Ybs.t.Ax≤bs.t.YA≥c

x≥0y≥0“Max--≤”“Min--≥”原问题与对偶问题的关系第21页，课件共133页，创作于2023年2月互为转置列向量行向量n个变量n个约束第22页，课件共133页，创作于2023年2月例2.5写出下述问题的对偶问题第23页，课件共133页，创作于2023年2月解：上述问题的对偶问题为第24页，课件共133页，创作于2023年2月(1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，≤”和“min，≥”相对应。如上面例题所示一对对称形式的对偶规划之间具有下面的对应关系第25页，课件共133页，创作于2023年2月(2)从约束系数矩阵看：一个模型中为Ａ，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。(3)从数据b、C的位置看：在两个规划模型中，b和C的位置对换。(4)两个规划模型中的变量皆非负。第26页，课件共133页，创作于2023年2月补充例子原问题：第27页，课件共133页，创作于2023年2月对偶问题：第28页，课件共133页，创作于2023年2月Chapter2灵敏度分析2.线性规划问题是非对称形式

对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。（1）将模型统一为“max，≤”或“min，≥”的形式，对于其中的等式约束按下面（2）、（3）中的方法处理；第29页，课件共133页，创作于2023年2月（2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；（3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。综上所述，线性规划的原问题和对偶问题的关系，其变换形式归纳为表2.5第30页，课件共133页，创作于2023年2月原问题（或对偶问题）对偶问题（或原问题）目标函数max目标函数min约束条件m个m个变量≤≥0≥≤0=无约束变量n个n个约束条件≥0≥≤0≤无约束=约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项第31页，课件共133页，创作于2023年2月下面我们以一个例子说明上述关系写出下述线性规划问题的对偶问题第32页，课件共133页，创作于2023年2月为了写出对偶问题，思路是先将其转化为对称形式，为此（1）约束条件（1a）两端同乘以-1；（2）约束条件（3a）变换为和

（3）令

（4）第33页，课件共133页，创作于2023年2月则线性规划变换成如下的对称形式第34页，课件共133页，创作于2023年2月令对应上述4个约束的对偶变量分别为写出对偶问题第35页，课件共133页，创作于2023年2月再令将（3b）和（4b）合并，（2b）两端同乘以-1，于是有第36页，课件共133页，创作于2023年2月例2.6写出下述线性规划问题的对偶问题

第37页，课件共133页，创作于2023年2月第38页，课件共133页，创作于2023年2月补充例题写出下述线性规划问题的对偶问题第39页，课件共133页，创作于2023年2月解：对偶问题为第40页，课件共133页，创作于2023年2月

小练习写出下列问题的对偶问题第41页，课件共133页，创作于2023年2月作业：2.1（1）（2）（3）第42页，课件共133页，创作于2023年2月2.4对偶问题的基本性质

【性质1】

对称性

对偶问题的对偶是原问题。(P)(D)

MaxZ=CXMinf=Ybs.t.AX≤bs.t.YA≥CX≥0Y≥0“Max--≤”“Min--≥”

第43页，课件共133页，创作于2023年2月

【证】因为X*、Y*是可行解，故有AX*≤b,X*≥0及Y*A≥C，Y*≥0,将不等式AX*≤b两边左乘Y*，得Y*AX*≤Y*b再将不等式Y*A≥C两边右乘X*，得CX*≤Y*AX*故CX*≤Y*AX*≤Y*b这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都不会大于求最小值的线性规划的任一目标值，不能理解为原问题的目标值不超过对偶问题的目标值。【性质2】弱对偶性设X*、Y*分别为LP(max)与DP(min)的可行解，则第44页，课件共133页，创作于2023年2月由这个性质可得到下面几个结论：(1)（LP）的任一可行解的目标值是（DP）的最优值下界；（DP）的任一可行解的目标是（LP）的最优值的上界；

(2)在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解；

(3)若原问题可行且另一个问题不可行，则原问题具有无界解。第45页，课件共133页，创作于2023年2月【性质3】最优准则定理设X*与Y*分别是（LP）与（DP）的可行解，则当X*、Y*是（LP）与（DP）的最优解当且仅当CX*=Y*b.【证】若X*、Y*为最优解，B为（LP）的最优基，则有Y*=CBB－1，并且当CX*=Y*b时，由性质1，对任意可行解有即Y*b是（DP）中任一可行解的目标值的下界，CX*是（LP）中任一可行解的目标值的上界，从而X*、Y*是最优解。第46页，课件共133页，创作于2023年2月【性质4】线性规划的对偶原理（1）若原问题有最优解，那么对偶问题也有最优解，而且二者最优值相等。（强对偶性）（2）若原问题（对偶问题）的解为无界解，则其对偶问题（原问题）无可行解。（无界性）注：这个问题的性质不存在逆。(看后面例子)第47页，课件共133页，创作于2023年2月【证】（1）设（LP）有最优解X0,那么对于最优基B必有C-CBB-1A≤0与－CBB-1≤0，即有Y°A≥C与Y°≥0，这里Y°=CBB-1

，从而Y°是可行解，对目标函数有由性质3知Y°是最优解。（2）由弱对偶性，显然得注：这个问题的性质不存在逆第48页，课件共133页，创作于2023年2月例如下述一对问题两者皆无可行解。

原问题（对偶问题）对偶问题（原问题）

minw=-x1-x2maxz=y1+y2

x1–x2≥1 y1-y2≤

-1-x1+x2≥1 -y1+y2≤-1x1,x2≥0y1,y2≥0由性质4还可推出另一结论：若（LP）与（DP）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。第49页，课件共133页，创作于2023年2月【性质5】互补松弛定理设X0、Y0分别为（LP）与（DP）的可行解，XS和YS分别是（LP）与（DP）对应的松弛变量向量，则X0和Y0是最优解当且仅当YSX0=0和

Y0XS=0【证】设X°和Y°是最优解,由性质3，CX0=Y0b，由于XS和YS是松弛变量，则有AX0＋XS＝bY0A－YS=C将第一式左乘Y0，第二式右乘X0得Y0AX0＋Y0XS＝Y0bY0AX0－YSX0=CX0第50页，课件共133页，创作于2023年2月显然有Y0XS=－YSX0又因为Y°、Xs、Ys、X°≥0，所以有Y°XS=0和YSX°=0成立。反之，当Y°XS=0和YSX°=0时，有Y°AX°＝Y°bY°AX°=CX°显然有Y0b=CX°,由性质3知X°与Y°是（LP）与（DP）的最优解。证毕。第51页，课件共133页，创作于2023年2月性质5告诉我们已知一个问题的最优解时求另一个问题的最优解的方法，即已知Y*求X*或已知X*求Y*。Y*

XS=0和YSX*

=0两式称为互补松弛条件。将互补松弛条件写成下式由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：其中第52页，课件共133页，创作于2023年2月(1)当yi*>0时，,反之当时yi*=0；利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。性质5的结论和证明都是假定（P）与（D）为对称形式，事实上对于非对称形式，性质5的结论仍然有效。注：上述针对对称形式证明的对偶问题的性质，同样适应于非对称形式。第53页，课件共133页，创作于2023年2月【补充例题】已知线性规划的最优解是求对偶问题的最优解。【解】对偶问题是下面举例说明互补松弛条件的应用第54页，课件共133页，创作于2023年2月解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为Y=（1，1），最优值w=26。因为X1≠0，X2≠0，所以对偶问题的第一、二个约束的松弛变量等于零，即第55页，课件共133页，创作于2023年2月【性质6】假设原问题是：maxz=CX;AX+Xs=b;X>=0它的对偶问题是：minf=Yb;YA-Ys=C;Y>=0则原问题单纯形表的检验数行对应其对偶问题的一个基解。其对应关系见如下表第56页，课件共133页，创作于2023年2月-0

N-Y-这里是对应于原问题中基变量XB

剩余变量，是对应于原问题中非基变量XN剩余变量.-第57页，课件共133页，创作于2023年2月一个问题max另一个问题min有最优解有最优解性质4无无最优解无最优解性质4最优无界解（有可行解）无可行解性质2解无可行解无界解（有可行解）应用已知最优解通过解方程求最优解性质5已知检验数检验数乘以－1求得基本解性质6对于这六个对偶性质，这些性质是研究原问题与对偶问题解的对应关系；下表也许对您了解这些性质有帮助。第58页，课件共133页，创作于2023年2月例2.7：判断下例说法是否正确，为什么？A如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解B如果线性规划的对偶问题无可行解，则原问题也一定无可行解。C在互为对偶的一对原问题和对偶问题中，不管原问题是求极大或者极小，原问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数值。

第59页，课件共133页，创作于2023年2月解：A不对。因为原问题为无界解时（它当然有可行解），其对偶问题无可行解。B此句为A的逆否命题，所以也不对。C不对。因为哪个问题是原问题，哪个问题是对偶问题是相对而言的。

第60页，课件共133页，创作于2023年2月例2.8已知线性规划问题

试用对偶理论证明上述线性规划问题有无界解（即有可行解但无最优解）。第61页，课件共133页，创作于2023年2月证明：所给问题的对偶问题为第62页，课件共133页，创作于2023年2月显然约束条件中与矛盾，即此对偶问题无可行解，因此所给原问题无最优解，它只可以是无界解或者无可行解。然而X=（0，0，0）显然是它的可行解，因此它必定有无界解。第63页，课件共133页，创作于2023年2月

补充例题给出线性规划（1）写出对偶问题（2）用对偶理论证明上述线性规划目标函数值无界第64页，课件共133页，创作于2023年2月解：（1）对偶问题为第65页，课件共133页，创作于2023年2月上述对偶问题中,

则与对偶问题的第一个约束条件矛盾，所以对偶问题无可行解，因而原问题无最优解，它只可以是无界解或者无可行解，然而x=(10,4,2)显然是他的可行解，因而它必定有无界解。第66页，课件共133页，创作于2023年2月例2.9已知线性规划问题已知其对偶问题的最优解为试用对偶理论找出原问题的最优解。第67页，课件共133页，创作于2023年2月解：先写出它的对偶问题

第68页，课件共133页，创作于2023年2月将的值代入约束条件，得到(2),(3),(4)为严格不等式;由互补松弛性得到因为;原问题的两个约束条件的松弛变量由互补松弛性得到为0，因此两个约束条件应该取等式,所以有第69页，课件共133页，创作于2023年2月求解后得到所以原问题的最优解为X=(1,0,0,0,1)T第70页，课件共133页，创作于2023年2月

补充例题:

已知原问题的最优解为X*=（0,0,4），Z=12,试求对偶问题的最优解。第71页，课件共133页，创作于2023年2月解:对偶问题为将X*=（0,0,4）代入原问题中，有下式：第72页，课件共133页，创作于2023年2月Chapter2灵敏度分析所以，根据互补松弛条件，必有y*1=y*2=0，代入对偶问题约束（3）式，y3=3。因此，对偶问题的最优解为

Y*=（0,0,3），W=12。第73页，课件共133页，创作于2023年2月因为原问题和对偶问题的最优值相等，将线性规划的目标函数表达成资源的函数，故有即yi是第i种资源的变化率，称yi是第i种资源的边际价格，说明当其它资源供应量bk(k≠i)不变时，bi增加一个单位时目标值Z增加yi个单位．2.5影子价格第74页，课件共133页，创作于2023年2月

影子价格(Shadowprice):

原始线性规划问题考虑的是充分利用现有资源，以产品的数量和单位产品的收益来决定企业的总收益，没有考虑到资源的价格，但实际在构成产品的收益中，不同的资源对收益的贡献也不同，它是企业生产过程中一种隐含的潜在价值，经济学中称为影子价格，即对偶问题中的决策变量yi的值。对偶变量yi

就是第i个约束的影子价格（边际价格）第75页，课件共133页，创作于2023年2月Chapter2灵敏度分析影子价格是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。若x*,y*

分别为（LP）和（DP）的最优解，那么，cT

x*=bT

y*

。根据f=bTy*=b1y1*+b2y2*+

+bmym*

可知

f/

bi

=

yi*

yi*

表示bi

变化1个单位对目标f

产生的影响，称yi*

为bi的影子价格。

注意：若B

是最优基，y*=CBB-1

为影子价格向量。第76页，课件共133页，创作于2023年2月Chapter2灵敏度分析影子价格的经济含义

(1)影子价格是对现有资源实现最大效益时的一种估价企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。第77页，课件共133页，创作于2023年2月Chapter2灵敏度分析（2）影子价格表明资源增加对总效益产生的影响。根据推论“设x0和y0分别为原规划（P）和对偶规划（D）的可行解，当cx0=bTy0时，x0、y0分别是两个问题的最优解”可知，在最优解的情况下，有关系

因此，可以将z*看作是bi,i=1,2，…,m的函数，对bi求偏导数可得到

这说明，如果右端常数增加一个单位，则目标函数值的增量将是第78页，课件共133页，创作于2023年2月Chapter2灵敏度分析（3）根据对偶问题的互补松弛性质中时；当时，，这表明生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。

第79页，课件共133页，创作于2023年2月（4）影子价格是企业生产过程中资源的一种隐含的潜在价值，表明单位资源的贡献，与市场价格是不同的两个概念．同一种资源在不同的企业、生产不同的产品或在不同时期影子价格都不一样．例如，某种钢板市场价格是每吨8000元，一个企业用来生产汽车，另一个企业用来生产空调外壳，每吨钢板的产值是不一样的．（5）影子价格是一个变量．由的含义知影子价格是一种边际产出，与bi的基数有关，在最优基B不变的条件下yi不变，当某种资源增加或减少后，最优基B可能发生了变化，这时yi的值也随之发生变化．第80页，课件共133页，创作于2023年2月根据对偶问题的性质，因为当即有即其对偶问题的解为可行解，由此对偶问题和原问题均为最优解。反之，如果存在一个对偶问题的可行基B，即对这时只要有即原问题的解也为可行解，即两者均为最优解。否则，保持对偶可行性，进行迭代2.6对偶单纯形法第81页，课件共133页，创作于2023年2月设原问题是（记为LP）：对偶问题是（记为DP）：对偶单纯形法的条件是：初始表中对偶问题可行，即极大化问题时

，极小化问题时。第82页，课件共133页，创作于2023年2月对偶单纯形法的基本思想是：从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。如果得到的基本解的分量皆非负则该基本解为最优解。第83页，课件共133页，创作于2023年2月Chapter2对偶单纯形法在什么情况下使用：应用前提：有一个基，其对应的基满足:

①单纯形表的检验数行全部非正（对偶可行）；②变量取值可有负数（非可行解）。注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。第84页，课件共133页，创作于2023年2月这样的优点在于，一是当问题的模型中存在“>=”的约束条件时，不需要引入人工变量，只要在约束条件方程的两边乘以“-1”后加入松弛变量，再按单纯形法求解。二是当约束条件方程个数m大于变量个数n的时候，将原问题变换成对偶问题求解，计算量一般会小些。第85页，课件共133页，创作于2023年2月Chapter2对偶单纯形法求解线性规划问题步骤：

1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2；

2.若b’≥0,则得到最优解,停止;否则,若有bi<0,

3.换出变量：设min{bi|bi<0}=bk，则选k行的基变量为换出变量.第86页，课件共133页，创作于2023年2月4.若所有akj’≥0(j=1,2,…,n)，则原问题无可行解,停止;否则,若有akj<0则选

=min{

j/akj┃akj<0}=

r/akr

那么xr

为换入变量,转5；

5.以akr’为主元,作矩阵行变换使其变为1,该列其他元变为0（旋转变换）,转2。第87页，课件共133页，创作于2023年2月例2.10求线性规划第88页，课件共133页，创作于2023年2月解：引入松弛变量将上述问题转化为得对偶单纯形表2.7第89页，课件共133页，创作于2023年2月表2.7此时基本解为X=(0,0,0,0,-2,-3),不可行，转第二步。因为min{-2,-3}=-3,所以x6为换出变量，又因为Min{-2/-2,-5/-1}=1,所以x1为换入变量。得到新的单纯形表2.8第90页，课件共133页，创作于2023年2月表2.8此时基本解为X=(3/2,0,0,0,-1/2,0),不可行，转第二步。因为-1/2<0,所以x5为换出变量，又因为Min{-4/(-5/2),{-4/(-5/2),{-9/(-5/2),{-1/(-1/2)}=8/5,所以x2和x3

都可以作为换入变量。任选其中一个x2，做线性变换得到新的单纯形表2.9第91页，课件共133页，创作于2023年2月表2.9得到一个基本解为X=(8/5,1/5,0,0,0,0)T,因解是可行的，所以满足最优检验下的基本可行解因而也是最优解。

第92页，课件共133页，创作于2023年2月Chapter2从以上求解过程中我们可以看到，对偶单纯形法有以下的优点：

1)初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。

2)当变量多于约束条件，对于这样的线性规划问题，用对偶单纯形法计算可以减少计算工作量，因此对于变量较少，而约束条件很多的线性规划问题，可以首先将它变换成为对偶问题，然后用对偶单纯形法来求解。

第93页，课件共133页，创作于2023年2月3)在灵敏度分析中，有时需要使用对偶单纯形法，这样可以使问题处理简化。对偶单纯形法的局限在于：对于大多数的线性规划问题，很难找到一个初始可行基，因而这个方法在求解线性规划问题时很少单独应用。第94页，课件共133页，创作于2023年2月从几何图形上看单纯性和对偶单纯性的区别已知Q2为最优解点x1x2O4

Q2(4,2)Q1Q3Q43ABC单纯形法：OQ1O2

或OQ4O3O2

对偶单纯性法：ABQ2

或BQ2注意：对偶单纯形对迭代点的要求---对偶可行性

第95页，课件共133页，创作于2023年2月（1）用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解；（2）初始表中一定要满足对偶问题可行，也就是说检验数满足最优判别准则；（3）对偶单纯形法与普通单纯形法的换基顺序不一样，普通单纯形法是先确定进基变量后确定出基变量，对偶单纯形法是先确定出基变量后确定进基变量；（4）对偶单纯形法在确定出基变量时，若不遵循

规则，任选一个小于零的bi对应的基变量出基，不影响计算结果，只是迭代次数可能不一样．

应当注意：第96页，课件共133页，创作于2023年2月2.7灵敏度分析

系数br、cj变化，最优解的最优性、可行性是否变化？

系数在什么范围内变化，最优解或最优性不变？

如何求新的最优解？本节重点第97页，课件共133页，创作于2023年2月例2.2第98页，课件共133页，创作于2023年2月1.求解此线性规划的解2.当C2=2时，新的线性规划问题的解3.当C2=5时，新的线性规划问题的解4.当b1=9时，新的线性规划问题的解5.当b1=12时，新的线性规划问题的解第99页，课件共133页，创作于2023年2月灵敏度分(SensitivityAnalyisi),就是分析研究LP模型参数aij,br,cj

的取值变化对最优解和最优基的影响。它在应用线性规划解决实际问题的过程中是非常有用的。实际LP问题的最优解，是在模型参数区某一组定值的基础上获得的，而这些定值往往是一些预测和估计的数字，因此或者有一定的误差，或者可能变动。如市场条件出现了变动，cj的值就会发生变化；aij是随着工艺技术条件的改变而改变的，而br

值则是根据资源投入后能产出多大经济效果来决定的一种决策选择。

第100页，课件共133页，创作于2023年2月因此就会产生以下问题：当这些参数中的一个或几个发生了变化时，问题的最优解会有什么变化，或者这些参数在一个多大的范围内变化时，问题的最优解不变。这就是我们学习灵敏度分析所要研究解决的问题。当然通过上面的学习我们知道：当线性规划问题中的一个或者几个参数变化时，可以用单纯形法从头计算，看最优解有无变化，但是这样做既麻烦又没有必要。第101页，课件共133页，创作于2023年2月因为我们知道单纯形法的迭代运算是从一组基向量变换为另一组基向量，表中每步迭代得到的数字只随基向量的不同选择而改变，因此有可能把个别参数的变化直接在计算得到最优解的单纯形表上面反映出来，这样就不需要从头计算了，而直接对计算得到的最优解的单纯形表进行审查，看一些数字变化后，是否满足最优解的条件，如果不满足的话，再从这个表开始进行迭代计算，求出最优解。第102页，课件共133页，创作于2023年2月Chapter2灵敏度分析灵敏度分析的步骤可以归纳如下：1)将参数的改变计算反映到最终单纯形表上来;具体的计算方法是，按照相关公式计算出由参数的变化而引起的最终单纯形表上有关数字的变化；2)检查原问题是否仍为可行解;3)检查对偶问题是否仍为可行解;4)我们可以按照书中表中罗列的几种情况得出结论和决定继续计算的步骤第103页，课件共133页，创作于2023年2月第104页，课件共133页，创作于2023年2月第105页，课件共133页，创作于2023年2月Chapter2灵敏度分析2.7.1资源数量br发生变化的分析资源数量变化是指系数br发生了变化，br变化为br’=br+br，并假设规划问题的其它系数都没有发生变化。根据讨论，最优解的基变量xB=B-1b.这样使得最终表中原问题的解相应的变化为XB’=B-1（b+

b）其中，

b=（0，…,

br,0,…,0）T1、资源系数br的灵敏度变化分析第106页，课件共133页，创作于2023年2月根据讨论，只要保持B-1(b+

b)≥0，最终表中检验数不变，则最优基不变，但最优解的值变化，XB’=B-1(b+

b)为新的最优解；否则，需要利用对偶单纯形法继续计算。

为了使最优基B不变，求br的变化范围。第107页，课件共133页，创作于2023年2月第108页，课件共133页，创作于2023年2月B-1的第r列第109页，课件共133页，创作于2023年2月这个时候在最终表里面求得的b列的所有元素

i=1,2,…，m。由此可得

由此可得，最优基不变（检验数不变）的条件是

第110页，课件共133页，创作于2023年2月例题:

问题：某公司在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及AB两种原材料的消耗如表所示，该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元，问应该如何安排计划使该工厂获利最多？

III资源限制设备128台时原料A4016公斤原料B0412公斤单位利润23第111页，课件共133页，创作于2023年2月Chapter2灵敏度分析第112页，课件共133页，创作于2023年2月Chapter2灵敏度分析最终单纯形表为:若该厂又从别处抽出4台时用于生产I、II，求这时该厂生产产品I,II的最优方案。第113页，课件共133页，创作于2023年2月

这里各列分别对应b1、b2、b3

的单一变化下面给出最优基不变时，△b1

的变化范围

第114页，课件共133页，创作于2023年2月B=（x1x5x2)可得△b1≥-2/0.5=-4,△b1≤-4/-2=2由公式知△b1变化范围[-4,2],显然b1变化范围[4,10]因此，当△b1=4时，最优基发生变化，需要用对偶单纯形法继续求解第115页，课件共133页，创作于2023年2月解：先计算B-1△b将这个结果放到最终表中得第116页，课件共133页，创作于2023年2月第117页，课件共133页，创作于2023年2月表中b列中有负数，故可用对偶单纯形法求最优解。最优解见下表

第118页，课件共133页，创作于2023年2月即该厂最优生产方案应改为生产产品I为4件，生产产品II为3件，获利17元。从最优表中看出x3=2,即设备有2小时未被利用。第119页，课件共133页，创作于2023年2月2.7.2价值系数cj的变化分析当目标系数cj变化时，可能引起检验数的变化，从而影响最优性条件是否满足。为了方便起见，分别就对应的是非基变量与基变量两中情况来讨论最优解不变的条件。第120页，课件共133页，创作于2023年2月（1）当cj是非基底变量xj的系数，检验数为或当cj变化

cj后，检验数要小于或等于零，即只要

j’

≤0,即

cj≤-

j，则最优解不变；否则，将最优单纯形表中的检验数

j用

j’取代，继续单纯形法的表格计算。第121页，课件共133页，创作于2023年2月Chapter2灵敏度分析例题:

Maxz=-2x1-3x2-4x3

S.t.

-x1-2