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

第二讲对偶理论与灵敏度分析第1页，课件共66页，创作于2023年2月

【例1】某企业用四种资源生产三种产品，工艺系数、资源限量及价值系数如下表：

建立总收益最大的数学模型。

产品资源ABC资源限量Ⅰ986500Ⅱ547450Ⅲ832300Ⅳ764550单件产品利润1008070线性规划的对偶模型DualmodelofLP线性规划的对偶模型第2页，课件共66页，创作于2023年2月【解】设x1，x2，x3分别为产品A，B，C的产量，则线性规划数学模型为：

现在从另一个角度来考虑企业的决策问题。假如企业不考虑自己生产产品，而将现有的资源标价出售，

问题：决策者应怎样给定资源一个合理的价格？线性规划的对偶模型DualmodelofLP第3页，课件共66页，创作于2023年2月设y1，y2，y3及y4分别表示四种资源的单位增值价格(售价＝成本＋增值)，总增值最低可用minw=500y1+450y2+300y3+550y4

表示。企业生产一件产品A用了四种资源的数量分别是9，5，8和7个单位，利润是100,企业出售这些数量的资源所得的利润不能少于100，即同理，对产品B和C有线性规划的对偶模型DualmodelofLP第4页，课件共66页，创作于2023年2月称上述线性规划模型是前面生产计划模型的对偶线性规划模型,这一问题称为对偶问题。生产计划的线性规划问题称为原始线性规划问题或原问题。价格不可能小于零，即有yi≥0(i=1,…,4),从而企业的资源价格模型为线性规划的对偶模型DualmodelofLP第5页，课件共66页，创作于2023年2月注：以上两问题是同一组数据参数，只是位置有所不同，所描述的问题实际上是从两个不同的角度去描述。原始线性规划问题考虑的是充分利用现有资源，以产品数量和单位产品的利润来决定企业的总利润，没有考虑资源的价格，实际上在构成产品的利润中，不同的资源对利润的贡献也不同，它是企业生产过程中一种隐含的潜在价值，经济学中称为影子价格。线性规划的对偶模型DualmodelofLP第6页，课件共66页，创作于2023年2月第7页，课件共66页，创作于2023年2月线性规划问题(2.2)就是原线性规划问题(2.1)的对偶线性规划问题，反之，(2.2)的对偶问题就是(2.1)．原问题与对偶问题有如下关系(假设原问题(2.1))：(1)原问题的约束个数(不含非负约束)等于对偶变量的个数(2)原问题的目标函数系数对应于对偶问题的右端项(3)原问题的右端项对应于对偶问题的目标函数系数(4)原问题的约束矩阵转置就是对偶问题系数矩阵(5)原问题求最大，对偶问题是求最小(6)原问题不等式约束符号为“≤”,对偶问题不等式约束符号为“≥”线性规划的对偶模型DualmodelofLP第8页，课件共66页，创作于2023年2月

【例2】写出该线性规划的对偶问题【解】线性规划的对偶模型DualmodelofLP第9页，课件共66页，创作于2023年2月线性规划问题的规范形式(或叫对称形式)：定义：

目标函数求极大值时，所有约束条件为≤号，变量非负；

目标函数求极小值时，所有约束条件为≥号，变量非负。

注：

(1)线性规划规范形式与标准型是两种不同形式，但可以相互转换。(2)规范形式的线性规划问题的对偶仍然是规范形式．线性规划的对偶模型DualmodelofLP第10页，课件共66页，创作于2023年2月对于一般的线性规划问题：其中为矩阵，为维列向量，为维向量，为维列向量(i=1,2,3;j=1,2)且令，此问题可化为线性规划的对偶模型DualmodelofLP第11页，课件共66页，创作于2023年2月用分别表示以上四组约束的对偶问题，则原问题的对偶问题是第12页，课件共66页，创作于2023年2月令，整理得对偶问题为

将原问题与对偶问题的对应关系列于表2。第13页，课件共66页，创作于2023年2月原问题(或对偶问题)对偶问题(或原问题)

目标函数max目标函数系数(资源限量)约束条件系数矩阵A(AT)

目标函数min资源限量(目标函数系数)约束条件系数矩阵AT(A)变量n个变量第j个变量≥0第j个变量≤0第j个变量无约束约束n个约束第j个约束为≥第j个约束为≤第j个约束为=约束m个约束第i个约束≤第i个约束≥第i个约束为=变量m个变量第i个变量≥0第i个变量≤0第i个变量无约束

表2线性规划的对偶模型DualmodelofLP第14页，课件共66页，创作于2023年2月【例3】写出下列线性规划的对偶问题

【解】=≥≤≤y1≤0，y2≥0，y3无约束线性规划的对偶模型DualmodelofLP第15页，课件共66页，创作于2023年2月对偶问题是(记为DP)：这里A是m×n矩阵,X是n×1列向量,Y是1×m行向量。【性质1】

对称性:

对偶问题的对偶是原问题。

设原问题是(记为LP)：对偶性质Dualproperty对偶性质【性质2】

弱对偶性:

设X*、Y*分别为LP(max)与

DP(min)的可行解，则第16页，课件共66页，创作于2023年2月对偶性质Dualproperty由这个性质可得到下面几个结论：

(LP)的任一可行解的目标值是(DP)的最优值下界；(DP)的任一可行解的目标是(LP)的最优值的上界；

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

(3)若原问题可行且另一个问题不可行，则原问题具有无界解。

注意:上述结论(2)及(3)的条件不能少。一个问题无可行解时，另一个问题可能有可行解(此时具有无界解)也可能无可行解。第17页，课件共66页，创作于2023年2月例如：无可行解，而对偶问题有可行解，由结论(3)知必有无界解。对偶性质Dualproperty第18页，课件共66页，创作于2023年2月【性质3】最优准则定理:

设X*与Y*分别是(LP)与(DP)的可行解，则X*、Y*是(LP)与(DP)的最优解当且仅当CX*=Y*b.对偶性质Dualproperty【性质4】对偶性：若互为对偶的两个问题其中一个有最优解，则另一个也有最优解，且最优值相同。另一结论：若(LP)与(DP)都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。【性质5】互补松弛定理:

设X*、Y*分别为(LP)与(DP)的可行解，XS和YS分别是它们的松弛变量的可行解，则X*和Y*是最优解当且仅当YSX*=0和

Y*XS=0第19页，课件共66页，创作于2023年2月性质5告诉我们已知一个问题的最优解时求另一个问题的最优解的方法，即已知Y*求X*或已知X*求Y*。Y*

XS=0和YSX*

=0两式称为互补松弛条件。将互补松弛条件写成下式由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：对偶性质Dualproperty第20页，课件共66页，创作于2023年2月(1)当yi*>0时，,反之当,时yi*=0；利用上述关系，建立对偶问题(或原问题)的约束线性方程组，方程组的解即为最优解。【例4】已知线性规划的最优解是,求对偶问题的最优解。对偶性质Dualproperty第21页，课件共66页，创作于2023年2月【解】对偶问题是因为x1≠0，x2≠0，所以对偶问题的第一、二个约束的松弛变量等于零，即解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为Y=(1，1)，最优值w=26。对偶性质Dualproperty第22页，课件共66页，创作于2023年2月【例5】已知线性规划的对偶问题的最优解为Y=(0，－2)，求原问题的最优解。【解】对偶问题是对偶性质Dualproperty第23页，课件共66页，创作于2023年2月解方程组得：x1=－5,x3=－1,所以原问题的最优解为X=(－5，0，－1)T，最优值Z=－12。因为y2≠0，所以原问题第二个松弛变量=0，由y1=0、y2=2知，松弛变量故x2=0，则原问题的约束条件为线性方程组：对偶性质Dualproperty第24页，课件共66页，创作于2023年2月【例6】证明该线性规划无最优解：【证】容易看出X=(4，0，0)是一可行解。对偶问题将三个约束的两端分别相加得,而第二个约束有y2≥1,矛盾，故对偶问题无可行解，因而原问题具有无界解，即无最优解。对偶性质Dualproperty第25页，课件共66页，创作于2023年2月【性质6】LP(max)的检验数的相反数对应于DP(min)的一组基本解，其中第j个决策变量xj的检验数的相反数对应于(DP)中第j个松弛变量的解，第i个松弛变量的检验数的相反数对应于第i个对偶变量yi的解。反之，(DP)的检验数(注意：不乘负号)对应于(LP)的一组基本解。对偶性质Dualproperty注：应用性质6的前提是线性规划为规范形式，而性质1-5则对所有形式线性规划有效。第26页，课件共66页，创作于2023年2月根据对偶性质；可将原问题与对偶问题解的对应关系列表如下：一个问题max另一个问题min有最优解有最优解性质4无无最优解无最优解性质4最优无界解(有可行解)无可行解性质2解无可行解无界解(有可行解)应用已知最优解通过解方程求最优解性质5已知检验数检验数乘以－1求得基本解性质6对偶性质Dualproperty第27页，课件共66页，创作于2023年2月影子价格因为原问题和对偶问题的最优值相等，将线性规划的目标函数表达成资源的函数，故有即yi是第i种资源的变化率，说明当其它资源供应量bk(k≠i)不变时，bi增加一个单位时目标值Z增加yi个单位．对偶性质Dualproperty第28页，课件共66页，创作于2023年2月正确理解影子价格，利用影子价格作下列经济活动分析:调节生产规模．例如，目标函数Z表示利润(或产值)当第i种资源的影子价格大于零(或高于市场价格)时，表示有利可图，企业应购进该资源扩大生产规模，当影子价格等于零(或低于市场价格)，企业不能增加收益，这时应将资源卖掉或出让，缩小生产规模。生产要素对产出贡献的分解．通过影子价格分析每种资源获得多少产出．例如，企业获得100万元的利润，生产过程中产品的直接消耗的资源有材料A、材料B、设备和工时，这些资源各产生多少利润，由影子价格可以大致估计出来。对偶性质Dualproperty第29页，课件共66页，创作于2023年2月由性质2.5知，第i个松弛变量大于零时第i个对偶变量等于零，并不能说明该资源在生产过程中没有作出贡献，只能理解为第i种资源有剩余时再增加该资源量不能给企业带来利润或产值的增加．影子价格是企业生产过程中资源的一种隐含的潜在价值，表明单位资源的贡献，与市场价格是不同的两个概念．同一种资源在不同的企业、生产不同的产品或在不同时期影子价格都不一样．例如，某种钢板市场价格是每吨8000元，一个企业用来生产汽车，另一个企业用来生产空调外壳，每吨钢板的产值是不一样的．对偶性质Dualproperty第30页，课件共66页，创作于2023年2月影子价格是一个变量．由的含义知影子价格是一种边际产出，与bi的基数有关，在最优基B不变的条件下yi不变，当某种资源增加或减少后，最优基B可能发生了变化，这时yi的值也随之发生变化．对偶性质Dualproperty第31页，课件共66页，创作于2023年2月

对偶单纯形法对于任何一个可行基B,为原问题的一个基可行解，单纯形法是从一个基可行解到另一个相邻的基可行解，直到基B满足

为止。对偶单纯形法DualSimplexMethod单纯形法首先化问题为标准型：第32页，课件共66页，创作于2023年2月对偶单纯形法DualSimplexMethod原始单纯形法的思想：

从满足可行性条件的一个基可行解(即基B满足)出发，经过换基运算迭代到另一个基可行解，直到找到满足最优性条件()的基可行解，这就是原问题的最优解。－CBB－1bC-CBB－1AλB-1bB-1AXBbX对于任意基B,对应的单纯形表为第33页，课件共66页，创作于2023年2月若上表为最优单纯形表，则下列两个式子同时成立：对偶单纯形法DualSimplexMethod问题：可否从满足条件(2)的基出发去找原问题的最优解？对偶单纯形法思想：从满足条件(2)的基(一般称为正则基)B出发，经过换基运算到另一个正则基，即一直保证条件(2)成立，直到找到一个满足条件(1)的正则基。－CBB－1bC-CBB－1AλB-1bB-1AXBX第34页，课件共66页，创作于2023年2月对偶单纯形法的计算步骤：(1)将线性规划的约束化为等式，找出一个正则基，即全部检验数λj≤0（max）或λj≥0（min）,求出其对应的基本解，当基本解可行时，则达到最优解；若基本解不可行，即有某个基变量的解bi<0，则进行换基计算；(2)换基计算(i)先确定出基变量:

l行对应的变量出基；(ii)再选进基变量:求最小比值(3)求新的基本解，用初等变换将主元素alk化为l,k列其它元素化为零，得到新的基本解，转到第(1)步重复运算。对偶单纯形法DualSimplexMethod第35页，课件共66页，创作于2023年2月【例7】用对偶单纯形法求解【解】先将约束不等式化为等式，再两边同乘以(－1)，得到x4、x5为基变量，用对偶单纯形法，迭代过程如表2-7所示。对偶单纯形法DualSimplexMethod第36页，课件共66页，创作于2023年2月XBx1x2x3x4x5b表(1)x4x5-1-1[-1]1-141001－5→－3λj41↑300表2-7对偶单纯形法DualSimplexMethod最优解：X＝(4，1，0)T；Z=17表(2)x2x51[-2]1013-11015－8→λj3↑0210表(3)x2x101105/2-3/2-1/2-1/21/2－1/214λj0013/25/23/2第37页，课件共66页，创作于2023年2月

线性规划的灵敏度分析也称为敏感性分析，它是研究和分析数据(cj，bi，aij)的波动对最优解的影响程度，主要研究下面两个方面：(1)当模型中这些数据有一个或几个发生变化时，最优解有什么变化，或这些数据在什么范围内变化时，原最优解或最优基不变；(2)若最优解或最优基发生变化后，如何求出新的最优基或最优解。灵敏度分析灵敏度分析

SensitivityAnalysis第38页，课件共66页，创作于2023年2月

设线性规划

其中Am×n，线性规划有最优解，设基B为最优基，则有灵敏度分析

SensitivityAnalysis求解思路：将变化后的数据代入上述公式，看看可行性条件与最优性条件是否依然成立：若成立，则还是最优解；若不成立，则利用单纯形法或对偶单纯形法可求出变化后的最优解。第39页，课件共66页，创作于2023年2月价值系数cj的变化分析为使最优解不变，求cj的变化范围灵敏度分析

SensitivityAnalysis由最优性条件可知，当目标函数系数发生变化时，有可能引起检验数的变化，从而影响最优性条件是否满足？要使最优解不变，即当cj变化为

后，检验数仍然是小于等于零，即这时分cj是非基变量和基变量的系数两种情况讨论。第40页，课件共66页，创作于2023年2月(1)cj是非基变量xj的系数即cj的增量不超过cj的检验数的相反数时，最优解不变，否则最优解就要改变。所以

(2)ci是基变量xi的系数

因ci∈CB

，故每个检验数λj中含有,当ci变化为ci＋Δci

后λj同时变化，这时灵敏度分析

SensitivityAnalysis第41页，课件共66页，创作于2023年2月令要使得所有，则有灵敏度分析

SensitivityAnalysis第42页，课件共66页，创作于2023年2月要使得所有，则有只要求出上限δ2及下限δ1就可以求出Δci的变化区间灵敏度分析

SensitivityAnalysis第43页，课件共66页，创作于2023年2月资源限量bi变化分析为了使最优基B不变，求bi的变化范围。

设br的增量为Δbr,b的增量为原性规划的最优解为X，基变量为XB=B－1b，要使最优基B不变，即要求而灵敏度分析

SensitivityAnalysis第44页，课件共66页，创作于2023年2月因为灵敏度分析

SensitivityAnalysis第45页，课件共66页，创作于2023年2月所以

令灵敏度分析

SensitivityAnalysis第46页，课件共66页，创作于2023年2月因而要使得所有必须满足这个公式与求的上、下限的公式类似，比值的分子都小于等于零，分母是B－1中第r列的元素，大于等于比值小于零的最大值，小于等于比值大于零的最小值。当某个时，可能无上界或无下界。灵敏度分析

SensitivityAnalysis第47页，课件共66页，创作于2023年2月约束系数的灵敏度分析1、非基变量的系数列向量发生变化则改变后只影响的检验数，而对其他的检验数没有影响由于是对偶可行解，要使最优基B不变，则必须有灵敏度分析

SensitivityAnalysis第48页，课件共66页，创作于2023年2月当中只有第i个分量发生变化灵敏度分析

SensitivityAnalysis第49页，课件共66页，创作于2023年2月2、基变量的系数列向量发生变化当最优基B的列向量发生变化时，也发生变化，从单纯形表可知，几乎所有位置都受到影响，故很难给出变化范围的一般公式，在实际问题中往往重新计算。3、增加新的决策变量假设增加一个新变量，其对应的目标函数系数为，在约束函数中对应的列向量，在最优单纯形表中增加一列相应的检验数为

若，则原问题最优解不变若，则以为新的进基变量，可用单纯形法继续迭代。灵敏度分析

SensitivityAnalysis第50页，课件共66页，创作于2023年2月4、增加新的约束条件(i)若在原问题中增加一个新的不等式约束条件先将原问题的最优解代入新的约束条件中，若满足，则原最优解是新问题的最优解，否则需将新约束加入原问题，具体做法：(1)引入松弛变量，新约束成为(2)在单纯形表中增加一行一列，并以为基变量，下面的系数为，注意在单纯形表中的列向量是单位向量，而原来的m个基变量对应的列向量可能不是单位向量，故应先做初等变换，然后继续迭代求解。灵敏度分析

SensitivityAnalysis第51页，课件共66页，创作于2023年2月(ii)若在原问题中增加一个新的等式约束条件先将原问题的最优解代入新的约束条件中，若满足，则原最优解不变，否则在新约束引入人工变量，再用大M法求解新问题。灵敏度分析

SensitivityAnalysis第52页，课件共66页，创作于2023年2月注：由以上讨论可知，当某些参数变化时，并不一定要用单纯形法重新计算，而可从原最优单纯形表出发，做适当修改，再根据具体情况求得新最优解，其步骤如下：(1)修改原最优单纯形表，以反映参数的变化。(2)检验以上修改是否使最优解发生变化，即以下式子是否成立：(3)若满足可行性而不满足最优性，则用单纯形法求解；若满足最优性而不满足可行性，则用对偶单纯形法求解。(4)若可行性与最优性都不满足，则引入人工变量后重新求解；若最优性与可行性都满足，则最优基不变。灵敏度分析

SensitivityAnalysis第53页，课件共66页，创作于2023年2月【例8】考虑下列线性规划求出最优解后，分别对下列各种变化进行灵敏度分析，求出变化后的最优解。综合应用灵敏度分析

SensitivityAnalysis第54页，课件共66页，创作于2023年2月(2)改变目标函数x3的系数为c3=1;(3)改变x2的系数为(4)改变约束(1)为(5)增加新约束(1)改变右端常数为:第55页，课件共66页，创作于2023年2月【解】加入松弛变量x4、x5、x6，用单纯形法计算，最优表如2－10所示。表2－10Cj2-14000bCBXBx1x2x3x4x5x64x305/711/73/7022x112/70－1/74/7010x60－200－111λj0－31/70－2/7－20/70

最优解X=(1，0，2，0，0，1)T

，最优值Z=10灵敏度分析

SensitivityAnalysis第56页，课件共66页，创作于2023年2月最优基矩阵及其逆(1)基变量的解为基本解不可行，将求得的XB代替表2－10中的常数项，用对偶单纯形法求解，其结果见表2－11所示。灵敏度分析

SensitivityAnalysis第57页，课件共66页，创作于2023年2月表2－11Cj2－14000bCBXBx1x2x3x4x5x64x305/711/73/7022/72x112/70－1/74/706/70x60[－2]00－11－2λj0－31/70－2/7－20/70

4x30011/71/145/1417/72x1100－1/73/71/74/7－1x201001/2－1/21λj000－2/7－9/14－31/14

灵敏度分析

SensitivityAnalysis第58页，课件共66页，创作于2023年2月最优解(2)由表2－10容易得到基变量x3的系数c3的增量变化范围是而c3=1不在允许的变化范围之外，故表2－10的解不是最优解。非基变量的检验数x4进基，用单纯形法计算，得到表2－12灵敏度分析

SensitivityAnalysis第59页，课件共66页，创作于2023年2月表2－12XBx1x2x3x4x5x6

bx305/71[1/7]3/702x112/70－1/74/701x60－200－111λj0－16/701/7－11/70

x405713014x11110103x60－200－111λj0－3－10－20

最优解为X=(3，0，0，14，0，1)T，最优值Z=6。灵敏度分析

SensitivityAnalysis第60页，课件共66页，创作于2023年2月(3)这时目标函数的系数和约束条件的系数都变化了，同样求出λ2判别最优解是否改变。x2进基，计算结果如表2－13所示灵敏度分析

SensitivityAnalysis第61页，课件共66页，创作于2023年2月表2－13Cj234000bCBXBx1x2x3x4x5x64x30011/73/7022x11－10－1/74/7010x60[3]00－111λj050－2/7－20/70

4

x3001