对偶规划与灵敏度分析

对偶规划与灵敏度分析1第1页，课件共60页，创作于2023年2月

对偶理论是线性规划的重要内容之一。对应于每个线性规划问题都伴生一个相应的线性规划问题。

原问题和对偶问题紧密关联，它们不但有相同的数据集合，相同的最优目标函数值，而且在求得一个线性规划的最优解的同时，也同步得到对偶线性规划的最优解。由对偶问题引伸出来的对偶解还有着重要的经济意义，是研究经济学的重要概念和工具之一。

2第2页，课件共60页，创作于2023年2月对偶问题的提出例1、某工厂生产甲,乙两种产品，这两种产品需要在A,B,C三种不同设备上加工。每吨甲、乙产品在不同设备上加工所需的台时，它们销售后所能获得的利润，以及这三种设备在计划期内能提供的有限台时数均列于表。试问如何安排生产计划，即甲,乙两种产品各生产多少吨，可使该厂所获得利润达到最大。§1

对偶线性规划设备每吨产品的加工台时可供台时数甲乙ABC359448364076利润（元/吨）32303第3页，课件共60页，创作于2023年2月

假设计划期内甲乙两种产品各生产吨，设备每吨产品的加工台时可供台时数甲乙ABC359448364076利润（元/吨）3230用图解法或单纯形法可求得最优解(元)即在计划期内甲产品生产吨，乙产品生产8吨，可以使总利润达到最大，为元。4第4页，课件共60页，创作于2023年2月

现在从另一个角度来考虑该工厂的生产问题:假设该厂的决策者打算不再自己生产甲,乙产品，而是把各种设备的有限台时数租让给其他工厂使用，这时工厂的决策者应该如何确定各种设备的租价。设分别为设备A，B，C每台时的租价，约束条件：把设备租出去所获得的租金不应低于利用这些设备自行生产所获得的利润目标函数：所获租金总额尽量少．5第5页，课件共60页，创作于2023年2月由此可得两个对称的线性规划：6第6页，课件共60页，创作于2023年2月矩阵形式：7第7页，课件共60页，创作于2023年2月可以得到另一个线性规划：称之为原线性规划问题的对偶问题，

对偶线性规划考虑如下具有不等式约束的线性规划问题8第8页，课件共60页，创作于2023年2月9第9页，课件共60页，创作于2023年2月10第10页，课件共60页，创作于2023年2月11第11页，课件共60页，创作于2023年2月

若令线性规划标准型的对偶规划为：

线性规划问题标准型的对偶问题考虑一个标准形式的线性规划问题由于任何一个等式约束都可以用两个不等式约束等价地表示，所以标准形线性规划问题可等价表示为：它的对偶规划为：12第12页，课件共60页，创作于2023年2月对偶线性规划的求法

从任何一个线性规划出发，都可以求出相应的对偶规划，在实际求解过程中，通常不通过求标准型，而是利用如下反映原始问题与对偶问题对应关系的原始─对偶表：

目标函数变量系数约束条件右端项约束条件右端项目标函数变量系数

约束条件个数：n个变量个数：n个变量个数：m个约束条件个数：m个目标函数minW目标函数maxZ对偶问题（或原问题）原问题（或对偶问题）13第13页，课件共60页，创作于2023年2月解：对偶规划：例2写出下列线性规划的对偶问题14第14页，课件共60页，创作于2023年2月例3写出下列线性规划的对偶问题解：上述问题的对偶规划：15第15页，课件共60页，创作于2023年2月

本节讨论几条重要的对偶定理，这些定理揭示了原始问题的解和对偶问题的解之间的基本关系。定理1：（对合性）对偶问题的对偶是原问题。证明：设原问题为对偶问题为改写对偶问题为对偶问题的对偶为§2

对偶定理16第16页，课件共60页，创作于2023年2月

定理2：弱对偶定理

若是原（极小化）问题的可行解，是对偶（极大化）问题的可行解，那么

证明：因为是对偶问题的可行解，所以满足约束条件又因为是原问题的可行解，可得，,所以。注：原（极小化）问题的最优目标函数值以对偶问题任一可行解的目标函数值为下界。对偶（极大化）问题的最优目标函数值以原问题任一可行解的目标函数值为上界。

推论1：如果原问题没有下界（即minZ→－∞），则对偶问题不可行。如果对偶问题没有上界（即maxW→＋∞），则原问题不可行。

若原问题与对偶问题之一无界，则另一个无可行解。17第17页，课件共60页，创作于2023年2月证明：由弱对偶定理，对于原始问题的所有可行解，都有因此是原问题的最优解。同理，对于对偶问题的所有可行解，都有所以是对偶问题的最优解。推论2：最优性定理

若是原问题的可行解，是对偶问题的可行解，而且两者的目标函数值相等，即，则和分别是原问题和对偶问题的最优解。18第18页，课件共60页，创作于2023年2月证明：设是原问题(min)的最优解，则对应的基Ｂ必有。若定义，则，

因此为对偶问题的可行解，而且，由最优性定理，是对偶问题的最优解。

定理3:

强对偶定理如果原问题（min)与对偶问题(max)之一有最优解，那么另一个也有最优解，而且目标函数值相等。19第19页，课件共60页，创作于2023年2月证明：设满足原问题(min)的最优性条件，则对应的基Ｂ必有。若定义，则，

因此为对偶问题的基本可行解。

定理4：设满足原问题(min)的最优性条件的一个基本解，则其对应的线性规划问题(min)的检验数对应对偶问题的一个基本可行解。20第20页，课件共60页，创作于2023年2月原问题与对偶问题可能出现的情况（1）两者都有最优解，且最优值相等；（2）一个有可行解，但无界，则另一个无可行解；（3）两者都无可行解。21第21页，课件共60页，创作于2023年2月定理5：互补松弛定理

如果分别是原问题(min)和对偶问题（max)的可行解，那么和为最优解的充要条件是

通常称为互补松弛条件。证明：充分性必要性22第22页，课件共60页，创作于2023年2月例5、已知线性规划问题:其对偶问题的最优解。试用互补松弛定理找出原问题的最优解。解：原问题的对偶问题为：由对偶问题最优解可知，由互补松弛定理，解方程组所以原问题最优解23第23页，课件共60页，创作于2023年2月

假设计划期内甲乙两种产品各生产吨，设备每吨产品的加工台时可供台时数甲乙ABC359448364076利润（元/吨）3230用图解法或单纯形法可求得最优解(元)即在计划期内甲产品生产吨，乙产品生产8吨，可以使总利润达到最大，为元。例１：对偶最优解的经济解释—影子价格

24第24页，课件共60页，创作于2023年2月25第25页，课件共60页，创作于2023年2月

由强对偶定理可知，如果原问题有最优解，那么对偶问题也有最优解，而且它们的目标函数值相等，即有：其中是线性规划原问题约束条件的右端数据向量，它代表各种资源的拥有量。为对偶问题最优解，它代表在资源最优利用条件下对各种单位资源的估价，这种估计不是资源的市场价格，而是根据资源在生产中所作出的贡献（如创造利润，产值等）而作出估价，为区别起见，称之为影子价格(shadowprice)。26第26页，课件共60页，创作于2023年2月

影子价格的大小客观地反映了各种不同资源在系统内的稀缺程度。如果第i种资源供大于求，即在达到最优解时，该种资源没有用完，或松弛变量，由互补松弛定理，在对偶最优解中，第i种资源的影子价格。反之如果第i种资源的影子价格，那么由互补松弛定理，原问题的第i个约束为严格等式，即，这表明第i种资源已经用完，成为稀缺资源。

资源的影子价格同时也是一种机会成本，在市场经济的条件下，当某种资源的市场价格低于影子价格时，企业应买进这种资源用于扩大生产；相反当某种资源的市场价格高于影子价格时，企业应卖出这种资源。随着资源的买进卖出，企业资源的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。

27第27页，课件共60页，创作于2023年2月设备每吨产品的加工台时可供台时数甲乙ABC359448364076利润（元/吨）3230例１：对偶最优解其中为设备A的影子价格，在资源最优利用的条件下，设备A每增加一个单位台时，可以使总利润增加元。若设备Ａ可供台时数＝３７，则28第28页，课件共60页，创作于2023年2月§3对偶单纯形法

单纯形法是以保持原问题可行为条件，即不论进行怎样的基变换，常数列必须保持非负。利用对偶问题的对称性，我们从另一个角度来考虑求解原问题最优解的方法，这种方法以保持对偶问题可行为条件，即不论进行何种基变换，必须保持所有的检验数非负，同时取消原问题必须可行的要求，即取消常数列的非负限制，通过基变换使原问题在非可行解的基础上逐步转换成基本可行解，一旦原问题的基本解可行，则该基本可行解也就是最优解，这就是对偶单纯形法的基本思想。单纯形法：可行性→最优性对偶单纯形法：最优性→可行性

29第29页，课件共60页，创作于2023年2月例6求解下列线性规划

minz=5x1+2x2+6x32x1+4x2

+8x3≥244x1+x2+4x3≥8x1、x2，x3≥0解

minz=5x1+2x2+6x32x1+4x2+8x3-x4=244x1+x2+4x3-x5=8x1、x2，x3，x4，x5≥0

minz=5x1+2x2+6x3－2x1－4x2

－8x3+x4=－24－4x1－x2－4x3+x5=－8x1、x2，x3，x4，x5≥030第30页，课件共60页，创作于2023年2月Cj52600bCBXBx1x2x3x4x50x4-2[-4]-810-240x5-4-1-401-8526000θ5/-22/-46/-80031第31页，课件共60页，创作于2023年2月

对偶单纯形法基变换的次序和一般单纯形法不同：一般单纯形法首先由最大减少原则确定换入变量，然而用最小比值原则确定换出变量。

对偶单纯形法则是先将具有负分量的基变量取出，作为换出变量，然后确定某个非基变量作为换入变量。其变换目的是在保持对偶问题可行性的前提下，使原问题的基本解向可行解靠拢。32第32页，课件共60页，创作于2023年2月对偶单纯形法的计算步骤如下：（4）以为主元进行旋转变换，得新的单纯形表，返回（2）。

（2）确定换出变量根据，确定基变量作为换出变量。检验所在行各元素若所有,则无可行解，停止计算。否则转入(３).（3）确定换入变量按最大比值原则，若确定非基变量为换入变量。（1）根据原始线性规划，列出初始单纯形表，检查b列数字，若b列数字全部非负，则已经求得最优解，停止计算。若b列中至少有一个负分量，则转入（2）.33第33页，课件共60页，创作于2023年2月例6用对偶单纯形法求解下列线性规划

minz=5x1+2x2+6x32x1+4x2

+8x3≥244x1+x2+4x3≥8x1、x2，x3≥0解将问题改写成如下形式

minz=5x1+2x2+6x3－2x1－4x2

－8x3+x4=－24－4x1－x2－4x3+x5=－8x1、x2，x3，x4，x5≥0显然，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正则基。34第34页，课件共60页，创作于2023年2月Cj52600bCBXBx1x2x3x4x50x4-2[-4]-810-240x5-4-1-401-8526000θ5/-22/-46/-800-2x21/212-1/4060x5-7/20[-2]-1/41-24021/20-120θ4/(-7/2)02/-2(1/2)/(-1/4)0-2x2-310-1/214-6x37/4011/8-1/211/2001/40-3235第35页，课件共60页，创作于2023年2月最后一个单纯形表中，已得到一个可行的正则解，因而得到问题的最优解为X*=（0，4，1）T最优值为z*=14（1）对于形如minz=CX，AX≥b，X≥0，且C≥0的线性规划问题。因为将其改写为max(－z)=－CX，－AX+XS=－b，X≥0，则立即可以得到初始正则解；

（2）在灵敏度分析中，有时需要用对偶单纯形法，可使问题的处理简化。对偶单纯形法在以下情况下较为方便。36第36页，课件共60页，创作于2023年2月例7用对偶单纯形法求解解：先化为标准型

对偶单纯形允许约束方程右端为负，因此可将方程2，3两端同乘-1，可得含单位矩阵的标准型：37第37页，课件共60页，创作于2023年2月据此列出初始单纯形表，并施行对偶单纯形法迭代步骤如下：5/47/4000-1/41/40102x2

2-1/4-3/40014x1

35/43/41004x3

02/30007/3-1/30011/310/3x2

21/3100-4/3-16/3x4

0101018x3

000023100-3-1-10x5

00101-1-2x4

00013218x3

0x5

x4

x3

x2

x1

bXB

CB

00023C可得最优解38第38页，课件共60页，创作于2023年2月例8用对偶单纯形法求解下列线性规划

minz=x1+2x2x1+x2

≤42x1+3x2≥18x1、x2≥0解将问题改写成如下形式

minz=x1+2x2x1+x2+x3=4－2x1－3x2+x4=－18x1、x2，x3，x4≥0显然，p3、p4可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p3、p4构成的就是初始z正则基。39第39页，课件共60页，创作于2023年2月§4灵敏度分析线性规划问题所对应的数据集合Ａ，b，Ｃ常常是通过预测或估计所得到的统计数据，在实际使用中，不免会有一定的误差。而且随着市场环境，工艺条件和资源数量的改变，这些数据完全可能发生变化。

因此有必要来分析一下当这些数据发生波动时，对目前的最优解，最优值或者最优基会产生什么影响，这就是所谓的灵敏度分析。

40第40页，课件共60页，创作于2023年2月灵敏度分析主要讨论如下二类问题：数据集合在什么范围内波动将不影响最优解或最优基？

若最优解发生变化，应如何找到新的最优解。CC1

C2

…Cn

CB

XB

bx1

x2

…xn

CB1

XB1

B-1bB-1A=B-1(P1，P2，…，Pn)CB2

XB2

::CBm

XBm

C-CBTB-1A列出标准型线性规划问题最优单纯形表：41第41页，课件共60页，创作于2023年2月价值向量C的改变

当价值向量由时，检验行应修改为：目标函数值应为。只要非基变量检验数那么原最优解仍然为最优。至于目标函数值是否改变，取决于分别就价值系数对应非基变量或基变量加以讨论：42第42页，课件共60页，创作于2023年2月若是非基变量的价值系数，为其改变量，在最优表中检验数发生变化。

若超出范围，那么，当前解已不是最优解。此时以修改后的最优单纯形表出发，进行单纯形迭代，直至求出新的最优解。

由只要即就可以保持现行最优解仍为最优。

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

若是某基变量的价值系数，为改变量，在最优表中所有的非基变量检验数均发生了变化.

由上式可得到一个不等式组，求解该不等式组就可得到价值系数的可变动范围。由，只要检验数：

或则最优解仍然保持为最优.

44第44页，课件共60页，创作于2023年2月例7、某工厂用甲乙两种原料生产A，B，C，D四种产品，每种产品的利润，现有原料数及每种产品消耗原料定额如表所示：

原料（公斤）产品（万件）供应量ABCD甲乙321040021/2183利润（万元/万件）985019问应该怎样组织生产，才能使总利润最大，若产品Ａ或Ｃ的利润产生波动，波动范围多大时，原最优解保持不变？解：设生产Ａ，Ｂ，Ｃ，Ｄ四种产品各万件，则此问题的线性规划模型为：45第45页，课件共60页，创作于2023年2月标准化，引入松弛变量x5,x6，，

利用单纯形表求解：42/30013/310/324/3012/3-10/3-1/2-1/310-1/64/321x4x3-19-500-20-23102612/301/21/3-5/30011/401/213/2x1x3-9-50-9-80-13/20251-3203/21-50011/401/233/2x5x30-50-9-8-50-19009/53/232104100021/201183x5x600x1x2x3x4x5x6bXBCBθ-9-8-50-1900C即最优生产方案是生产Ｃ产品1万件，Ｄ产品2万件，不生产Ａ,Ｂ两种产品。可得最大利润为88万元。46第46页，课件共60页，创作于2023年2月C

-9-8-50-1900θCBXBbx1x2x3x4x5x6-19-50x4x32124/3012/3-10/3-1/2-1/310-1/64/3Z8842/30013/310/3最优表：原最优解不变，最优利润值（万元）也不变。(1)若有改变量。因为为非基变量，由推得即或时47第47页，课件共60页，创作于2023年2月C

-9-8-50-1900θCBXBbx1x2x3x4x5x6-19-50x4x32124/3012/3-10/3-1/2-1/310-1/64/3Z8842/30013/310/3最优表：(２)若有改变量。因为为基变量，由推得即当或时原最优解不变，最优利润值万元48第48页，课件共60页，创作于2023年2月右端项向量b的改变

当右端项向量时，改变的是表中右端常数列。此时基变量，目标函数值。而检验行的检验向量保持不变。

若，可用对偶单纯形法再次进行迭代，直到求得新最优解。

为了使B可行，只要或49第49页，课件共60页，创作于2023年2月例8、在例7中，若想增加甲种原料，问增加多少时原最优基不变？

解：设甲种原料的改变量为,则由即

最优目标函数值(万元)由此可以推得，即当时，原最优基不变。此时最优解或50第50页，课件共60页，创作于2023年2月约束矩阵A的改变

假设原线性规划问题有一个最优解其中Ｂ为最优基，

约束矩阵A的改变可能导致不同的最优解和最优基.以下只涉及两种较简单的情形：

增加一个变量，

增加一个约束条件。51第51页，课件共60页，创作于2023年2月

增加一个变量增加一个新变量，对应的价值系数为，对应的系数列向量为，可得新的线性规划问题：设，则

为新问题的一个可行解。因此可在此基础上开始单纯形法，求新的最优解。如果，则，是新问题的最优解。否则以为换入变量进行基变换，继续使用单纯形算法为新的线性规划寻求一个最优解。52第52页，课件共60页，创作于2023年2月增加一个约束

如果加入一个新的约束条件，不妨假设此约束条件为不等式形式，即

在附加不等式约束左端加上一个松弛变量

,

新的线性规划变成

53第53页，课件共60页，创作于2023年2月由此可以在原来最优基Ｂ的基础上定义一个新的基,

是非奇异矩阵，得到新问题的一个基本解在原最优解基础上对新问题作初等行变换，使基变量对应的系数列向量为单位矩阵，该基本解不一定是可行解，但是由于Ｂ是原线性规划问题的最优基，所以能保证该线性规划的对偶规划是可行的。54第54页，课件共60页，创作于2023年2月结论：如果由新基定义的基本解

是非负的。那么该基本解就是有附加约束条件的新线性规划问题的最优解。不满足非负条件。那么至少有一个基变量小于零，此时可用对偶单纯形法求出新问题的最优解。55第55页，课件共60页，创作于2023年2月解：（1）设生产Ｅ产品x7万件，1万件E产品的利润为c7万元，则数学模型变为：例9、在例7中，若考虑生产另一种产品Ｅ，已知每生产1万件Ｅ产品要消耗甲原料3公斤，乙原料1公斤，那么，Ｅ产品的每万件利润为多少时才有利于该种产品投产？若假设该工厂又增加了用电量不超过9千瓦的限制，已知生产Ａ，Ｂ，Ｃ，Ｄ四种产品各1万件分别耗电4，3，5，2千瓦，问此约束是否改变了原最优决策方案？56第56页，课件共60页，创作于2023年2月

已知