对偶问题总结课件

2022/10/31--第2章对偶问题----1--第二章线性规划的对偶理论Duality

对偶DualProblem

对偶问题DualLinearProgramming

对偶线性规划DualTheory

对偶理论2022/10/23--第2章对偶问题----1--第2022/10/312例

甲方生产计划问题：

Ⅰ

Ⅱ能力设备A2212设备B4

016设备C0515利润23Ⅰ，Ⅱ各生产多少,可获最大利润?乙方租借设备：甲方以何种价格将设备A、B、C租借给乙方比较合理？请为其定价。2.1问题的提出--第2章对偶问题--2022/10/232例甲方生产计划问题：Ⅰ，Ⅱ各生产多2022/10/313而就乙方而言，希望甲方的租金收入在满足约束的条件下越小越好，这样双方才可能达成协议。于是得到下述的线性规划模型：解：假设A、B、C的单位租金分别为，所以生产产品Ⅰ的资源用于出租时，租金收入应满足：类似的，生产产品Ⅱ的资源用于出租时，租金收入应满足：总的租金收入：--第2章对偶问题--思路：就甲方而言，租金收入应不低于将设备用于自己生产时的利润。原问题的对偶问题2022/10/233而就乙方而言，希望甲方的租金收入在满足2022/10/31--第2章对偶问题----4--例：某企业计划生产甲、乙两种产品，该两种产品均需经A、B、C、D四种不同设备加工，按工艺资料规定，在各种不同设备上的加工时间及设备加工能力、单位产品利润如表中所示。问：如何安排产品的生产计划，才能使企业获利最大?

2022/10/23--第2章对偶问题----4--例：2022/10/31--第2章对偶问题----5--1.最大生产利润模型设企业生产甲产品为X1件，乙产品为X2件，则

maxz=2

X1+3

X2s.t2

X1+2X2

12

X1+2X28

4

X1

164

X212

X10,X202.资源最低售价模型(原问题)<========>(对偶问题)设第i种资源价格为yi,（i=1,2,3,4,）则有minw=12y1+8y2+16y3+12y4s.t2y1+y2+4y3+0y42

2y1+2y2+0y3+4y43yi0,(i=1,2,3,4)y1y2y3y42022/10/23--第2章对偶问题----5--1.2022/10/31--第2章对偶问题----6--2.2原问题与对偶问题的关系一般表示式：原问题：maxz=c1X1+c2X2+┈+

cnXns.t

a11X1+a12X2+┈+

a1nXn

b1

a21X1+a22X2+┈+

a2nXn

b2

·······················

am1X1+am2X2+┈+

amnXn

bm

xj0，j=1,2,┈,n

对偶问题：minw=b1y1+b2y2+┈+bmym

s.t

a11y1+a21y2+┈+am1ym

c1

a12y1+a22y2+┈+am2ym

c2

·························

a1ny1+a2ny2+┈+amnym

cn

yi0，(i=1,2,···,m)2022/10/23--第2章对偶问题----6--2.2022/10/31--第2章对偶问题----7--典式模型对应对偶结构矩阵表示（1） maxz=CX

s.tAXb

X0

minw=Ybs.tYAC

Y0对偶问题原问题这是规范形式的原问题，由此写出其对偶问题如右方所示，那么，当原问题不是规范形式时，应如何写出其对偶问题？可以先将原问题化成规范的原问题，再写出对偶问题。2022/10/23--第2章对偶问题----7--典式2022/10/31--第2章对偶问题----8--对偶模型其他结构关系（2）若模型为 maxz=CX s.tAX

b

X0 maxz=CXs.t-AX-b

X0变形minw=Ybs.tYAC

Y

0Minw=Y´(-b)st.Y´(-A)C Y´0令Y=-Y´对偶问题对偶变量Y2022/10/23--第2章对偶问题----8--对偶2022/10/31--第2章对偶问题----9--（3）maxz=CXs.tAX

b

X

0变形设X=-X´max=-CX´st.-AX´b X´0minw=Yb

s.tYA

C

Y

0则有minw=Yb

s.t-YA-C Y

02022/10/23--第2章对偶问题----9--（32022/10/31--第2章对偶问题----10--对偶问题典式：用矩阵形式表示：

（1）maxz=CXminw=Ybs.tAXb<========>s.tYACX0Y0

（2）maxz=CXminw=Ybs.tAX

b<========>s.tYACX0Y0

（3）maxz=CXminw=Ybs.tAXb<========>s.tYACX

0Y02022/10/23--第2章对偶问题----10--对11等式、无约束情况的对偶：原问题对偶问题11等式、无约束情况的对偶：原问题对偶问题12推导:原问题化为：即：12推导:原问题化为：即：13

根据对称形式的对偶模型,可直接写出上述问题的对偶问题:13根据对称形式的对偶模型,可直接写出上述问14令，得对偶问题为：14令，得对偶问题为：2022/10/31--第2章对偶问题----15--原问题与对偶问题关系表

原问题(对偶问题)对偶问题(原问题)

目标函数系数 约束右端项约束右端项 目标函数系数约束条件系数列向量A 约束条件系数行向量AT

变量个数 约束条件个数

max min

变量xj: 约束方程i: xj

0

xj

无约束 = xj0

约束方程: 变量yi: yi

0 = yi

无约束

yi0 2022/10/23--第2章对偶问题----15--原2022/10/31--第2章对偶问题----16--2.3对偶问题的基本性质Maxz=CX Minw=Ybst.AXb st.YACX0 Y0(1)弱对偶性：

若X0——原问题可行解，Y0——对偶问题可行解 则CX0

Y0b证明：∵Y00，AX0b，

∴Y0AX0

Y0b， 而Y0AC，∴CX0

Y0AX0，∴

CX0

Y0AX0

Y0b推论1:原问题任一可行解的目标函数值是其对偶问题目标函数值的下届；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。推论2:

在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；反之不成立。这也是对偶问题的无界性。2022/10/23--第2章对偶问题----16--22022/10/31--第2章对偶问题----17--（2）最优性：

若X0——原问题可行解，Y0——对偶问题可行解，且 CX0

=

Y0b

则X0——原问题最优解，Y0——对偶问题最优解证明：设X*

——原问题最优解，Y*

——对偶问题最优解则CX0

CX*Y*

bY0b

但CX0=

Y0b，∴CX0

=CX*=Y*

b=Y0b∴X0

=X*

，Y0=Y*

即X0——原问题最优解，Y0——对偶问题最优解证毕。

若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。2022/10/23--第2章对偶问题----17--（2022/10/31--第2章对偶问题----18--（3）无界性若原问题最优解无界，则对偶问题无可行解证：有性质1，CX0Y0b，当CX0∞时，则不可能存在Y0，使得CX0Y0b

。

注：逆定理不成立，即 如果原问题（对偶问题）无可行解，那么对偶问题（或原问题）“解无界”不成立。2022/10/23--第2章对偶问题----18--（2022/10/31--第2章对偶问题----19--（4）强对偶性（对偶定理）

若原问题有最优解，则对偶问题一定有最优解， 且有zmax

=wmin证：由

=

C-CB

B-1A0令CBB-1=

Y*

，

得 Y*

AC

-Y*

=-CBB-10， Y*

0

因此，Y*是对偶问题的可行解， 又CX*=CB

(B-1b)=CB

B-1b=Y*

b∴Y*是对偶问题的最优解。

还可推出另一结论：若（LP）与（DP）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。2022/10/23--第2章对偶问题----19--（2022/10/31--第2章对偶问题----20--Maxz=CXst.AXb X0Maxz=CXst.AX+Xs=b X

0标准形Maxz=CBXB+CNXN+0XSst. BXB+NXN+IXS=b， XB,XN,XS

0改写∴B-1存在Maxz=CBXB+CNXN+0XSst. B-1BXB+B-1NXN+B-1IXS=B-1b XB,XN,XS

0左乘B-1LP模型矩阵变换：|B|≠0，（XB+B-1NXN+B-1XS=B-1b）2022/10/23--第2章对偶问题----20--M2022/10/31--第2章对偶问题----21--单纯形法的矩阵描述：XBXNXSBNIIN´B-1bb´XSXBσCBCN0CBCN0σ=C-CBB-1A´00σNσSxjcjpj0pj´σjcjXB=b´=B-1bN=B-1N

σN=CN-CBB-1

N0CBσS=-CBB-1

0σ初始表最终表A´=[BNI]2022/10/23--第2章对偶问题----21--单2022/10/31--第2章对偶问题----22--（5）互补松弛性

n

若yi*>0,则 aijxj*=bi

j=1

n

若aijxj*<bi,则yi*=0

j=1 n

n

mm

证：∵

cj

x

j*=(aij

yi*)xj*=

biyi*

j=1

j=1i=1i=1

n

mm∴(aij

yi*)xj*

-

biyi*=0

j=1i=1i=1

m

n

(aij

xj*

-

bi

）yi*=0

i=1j=1∴当yi*>0,aij

xj*

-

bi=0,即aij

xj*

=

bi

当aij

xj*

-

bi<0,yi*=0j=1j=1j=1

n

n

n2022/10/23--第2章对偶问题----22--（2022/10/31--第2章对偶问题----23--设X0和Y0分别是P问题和D问题的可行解，则它们分别是最优解的充要条件是：其中：Xs、Ys为松弛变量证明：（LP）和（LD）标准化为：则有:2022/10/23--第2章对偶问题----23--2022/10/31--第2章对偶问题----24--必要性：则于是所以充分性：若

若为最优解所以

为最优解则2022/10/23--第2章对偶问题----24--必2022/10/31--第2章对偶问题--25该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知Y*求X*或已知X*求Y*互补松弛条件由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：若Y*

≠0，则Xs必为0；若X*≠0，则Ys必为0利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。例

已知线性规划其对偶问题的最优解为Y*=(0,-2)，求原问题的最优解。2022/10/23--第2章对偶问题--25该解:对偶问题是标准化设原问题最优解为X*＝(x1，x2，x3)T,由互补松弛性定理可知，X*和Y*满足：将Y*带入由方程可知，y3＝y5＝0，y4＝1。∵y2=-2≠0∴x5＝0又∵y4=1≠0∴x2＝0解:对偶问题是标准化设原问题最优解为X*＝(x将x2，x5分别带入原问题约束方程中，得：解方程组得：x1=-5,x3=-1,所以原问题的最优解为X*=(-5,0,-1)，最优值z=-12若其对偶问题的最优解为：y1﹡=4/5,y2﹡=3/5,Z﹡=5

用互补松弛定理求最优解。例2:将x2，x5分别带入原问题约束方程中，得：解方程组得：x1=2022/10/31--第2章对偶问题----28--解：对偶问题为将y1﹡，y2﹡代入，知(2),(3),(4)为严格不等式∴x2

=x3=x4=0由y1﹡，y2﹡﹥0知原约束为等式:∴x

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

,minW=52022/10/23--第2章对偶问题----28--解2022/10/31--第2章对偶问题----29--（6）单纯形表中的对应关系原问题与其对偶问题的变量与解的对应关系： 在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量。

maxz=2x1+3x2

minw=12y1+8y2+16y3+12y4s.t2x1+2x2

12s.t2y1+y2+4y3+0y4

2

x1+2x2

82y1+2y2+0y3+4y4

3

4x1

16yi

0,i=1,2,3,44x2

12x1

0,x2

0-y5-y6-y1-y2-y3-y42022/10/23--第2章对偶问题----29--（2022/10/31--第2章对偶问题----30--XBb原问题的变量原问题的松弛变量x1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2000－1/4－1/2XBb对偶问题的变量对偶问题的剩余变量y1y2y3y4y5y21/4-4/510-1/41/4y31/215/2011/2-3/215/2007/23/2原问题最优表对偶问题最优表2022/10/23--第2章对偶问题----30--X原问题与对偶问题解的对应关系小结对应关系原问题最优解无界解无可行解对偶问题最优解(Y,Y)(N,N)————无界解————(Y,Y)无可行解——(Y,Y)无法判断原问题与对偶问题解的对应关系小结对应关系原问题最优解无界解无32原问题的检验数行对应对偶问题的一个基解。证明：（LP）和（LD）标准化为：

设B是原问题的一个可行基，于是A＝(B,N)，所以原问题可以改写为：032原问题的检验数行对应对偶问题的一个基解。证明：（LP）33

当求得原问题的一个解其相应检验数为：相应地对偶问题可表示为：令，并将它代入上式得：33当求得原问题的一个解其相应检验数为：相应地对偶问题可思考题判断下列结论是否正确，如果不正确，应该怎样改正？1）任何线性规划都存在一个对应的对偶线性规划.2）原问题第i个约束是“≤”约束，则对偶变量yi≥0.3）互为对偶问题，或者同时都有最优解，或者同时都无最优解.4）对偶问题有可行解，则原问题也有可行解.5）原问题有多重解，对偶问题也有多重解.6）对偶问题有可行解，原问题无可行解，则对偶问题具有无界解.7）原问题无最优解，则对偶问题无可行解.8）对偶问题不可行，原问题可能无界解.9）原问题与对偶问题都可行，则都有最优解.10）原问题具有无界解，则对偶问题不可行.11）对偶问题具有无界解，则原问题无最优解.12）若X*、Y*是原问题与对偶问题的最优解，则X*=Y*.思考题判断下列结论是否正确，如果不正确，应该怎样改正？1）任2022/10/31--第2章对偶问题----35--2.4影子价格(Shadowprice)1、对偶变量yi可理解为对一个单位第i种资源的估价，称为影子价格，但并非市场价格。假设有原问题和对偶问题如下：2、对偶变量yi

的值（即影子价格）表示第i种资源数量变化一个单位时，目标函数的增量，是一种边际价格。对bi求偏导

说明yi的值相当于在资源得到最优利用的生产条件下，bi每增加一个单位时目标函数Z的增量。2022/10/23--第2章对偶问题----35--22022/10/3136资源增加一个单位时，最优解及目标函数值的变化目标函数等值线2022/10/2336资源增加一个单位时，最优解及目标函数2022/10/31--第2章对偶问题----37--

生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为零；经济解释：资源未用完，再增加对目标函数也无贡献。当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。经济解释：该种资源用尽，再购进用于扩大生产可增加总利润。

在对偶问题的互补松弛性质中有2022/10/23--第2章对偶问题----37--影子价格是一种机会成本

影子价格是在资源最优利用条件下对单位资源的估价，这种估价不是资源实际的市场价格。因此，从另一个角度说，它是一种机会成本，可用于指导资源的购入与卖出。若第i种资源的单位市场价格为mi

，则有当yi*>mi

时，企业愿意购进这种资源，单位纯利为yi*－mi

，则有利可图；如果yi*<mi

，则企业有偿转让这种资源，可获单位纯利mi－yi*

，否则，企业无利可图，甚至亏损。结论：若yi*>mi则购进资源i，可获单位纯利yi*－mi

若yi*<mi则转让资源i，可获单位纯利mi－yi影子价格是一种机会成本若第i种资源的单位市场价格为mi，单纯形表检验数单纯形表中的检验数与影子价格其中cj表示第j种产品的价格;

表示生产该种产品所消耗的各项资源的影子价格的总和,即产品的隐含成本。当产值大于隐含成本时，即，表明生产该项产品有利，可在计划中安排；否则，用这些资源生产别的产品更有利，不在生产中安排该产品。单纯形表检验数单纯形表中的检验数与影子价格其中cj表示第j种2022/10/31402.5对偶单纯形法在单纯形表中，

列对应原问题的基可行解，行对应对偶问题的一个基解（不一定可行），当时，在检验数行就得到对偶问题的基可行解，此时两个问题的目标函数值相等，由最优性条件知，两个问题都达到了最优解。单纯形法：找一个初始基可行解，保持b列为正，通过迭代找到下一个基可行解，使目标函数值不断增大，当检验数行全部小于等于零时，达到最优解。2022/10/23402.5对偶单纯形法在单纯形表中，41原问题基可行解最优解判断对偶问题的可行解对偶问题最优解判断对偶单纯形法基本思路单纯形法的基本思路：

对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。41对偶问题的可行解对偶问题对偶单纯形法单纯形法的基本思路：找出一个DP的可行基LP是否可行（XB≥0）保持DP为可行解情况下转移到LP的另一个基本解最优解是否循环结束根据对偶问题的对称性，保持对偶问题的解是可行解，即检验数行非负，而原问题从非可行解开始，逐步迭代到基本可行解，也使原问题和对偶问题达到最优解。找出一个DP的可行基LP是否可行保持DP为可行解情况下转移到2022/10/31--第2章对偶问题----43--2.5对偶单纯形法由于单纯表中同时反映原问题与对偶问题的最优解，故可以从求对偶问题最优解角度求解LP模型。例：minz=2x1+3x2maxz'=-2x1-3x2+0x3+0x4 s.tx1+x23标准化s.tx1+x2-x3=3 x1+2x24 x1+2x2-x4=4 x10,x20 xj0,(j=1,2,3,4)maxz'=-2x1-3x2+0x3+0x4

s.t-x1-x2+x3=-3 -x1-2x2+x4=-4 xj0,(j=1,2,3,4)2022/10/23--第2章对偶问题----43--22022/10/31--第2章对偶问题----44--Cj→x1x2x3x4XBbCB-1 -1 1 0-1 -2 01-2 -3 0 0-3-4x3x400cj-zj-2-300-1/2 0 1 -1/21/2 1 0-1/2x3x2-12cj-zj-1/2 00-3/20-31 0 -2 10 1 1-1x1x221cj-zj0 0 -1 -1-2-3列单纯表计算：2022/10/23--第2章对偶问题----44--C2022/10/31--第2章对偶问题----45--对偶单纯形法步骤：1.列初始单纯形表，使得所有检验数j0

；2.出基变量：取min{bi<0

}=bl

→x(l) 3.入基变量：min{——|alk<0}=→xk 4.主元素：[alk]5.迭代：同单纯形法，新单纯表中pk化为单位向量cj-zjalj说明：10使用对偶单纯形法时，初始表中检验数必须全部为j0，即使得其对偶问题为可行解，20为便于说明，这里采取从原问题角度叙述迭代步骤。2022/10/23--第2章对偶问题----45--对2022/10/31461、

为何只考虑行中的元素对应的变量进基？为使迭代后的基变量取正值。2、为何采用最小比值规则选择进基变量？为了使得迭代后的多偶问题解仍为可行解（检验数行仍为非正）3、原问题无可行解的判别准则：当对偶问题存在可行解时，若有某个，而所有，则原问题无可行解，对偶问题目标值无界。因为第r行的约束方程即为：其中，，因此不可能存在使上式成立。也即原问题无可行解。2022/10/23461、为何只考虑行中2022/10/31--第2章对偶问题----47--对偶单纯形法的优点：不需要人工变量；对变量较少，而约束条件很多的LP,可以先将其变成LD，再运用对偶单纯形法计算；在灵敏度分析中，有时需要用对偶单纯形法处理简化。2022/10/23--第2章对偶问题----47--对用对偶单纯形法求解LDLPLD用对偶单纯形法求解LDLPLDyy1y2y3y4y5c-12-16-1500y40-2-4010-2y50-20-501-3zjzj-cjyyzjzj-cjyy1y2y3y4y5c-12-16-1500y40-2-4yyzjzj-cj最优解=？最优值=？yyzjzj-cj最优解=？练习（对偶单纯形法求解）练习（对偶单纯形法求解）2022/10/31--第2章对偶问题----52--2.6灵敏度分析1．灵敏度分析的概念：当某一个参数发生变化后，引起最优解如何改变的分析。可以改变的参数有：

bi——约束右端项的变化，通常称资源的改变；

cj——目标函数系数的变化，通常称市场条件的变化；

pj

——约束条件系数的变化，通常称工艺系数的变化；其他的变化有：增加一种新产品、增加一道新的工序等。2022/10/23--第2章对偶问题----52--22022/10/31--第2章对偶问题----53--2.灵敏度分析的一般步骤：(1)将参数的改变经计算后反映到最终单纯形表中；(2)检查原问题和对偶问题是否仍为可行解；(3)按照下表对应情况，决定下一步骤。原问题对偶问题结论或计算步骤可行解可行解仍是最优解可行解非可行解用单纯形法继续迭代得到新的最优解非可行解可行解用对偶单纯形法继续迭代得到新的最优解非可行解非可行解引入人工变量，重新编单纯形表，重新计算2022/10/23--第2章对偶问题----53--22022/10/31--第2章对偶问题----54--3．分析原理：借助最终单纯形表，将变化后的结果按下述基本原则反映到最终表中去。（1）bi变化：（b+△b）´=B-1

（b+△b） =B-1b+B-1

△b=b´+B-1

△b（2）pj变化：（pj+△pj

）´=B-1

（pj+△pj

） =B-1pj+B-1

△pj

=pj

´+B-1

△pj

（3）cj变化：直接反映到最终表中，计算检验数。（4）增加一个约束方程：直接反映到最终表中。（5）增加新产品：仿照pj变化。2022/10/23--第2章对偶问题----54--32022/10/3155一、C的变化分析

C的变化只影响检验数。例、设有如下的线性规划模型试分析分别在什么范围变化时，最优解不变？2022/10/2355一、C的变化分析例、设有如下的线性2022/10/31562300023101/20-1/50400-214/53301001/500-10-1/5解：问题的最终单纯形表如下：30003101/20-1/50400-214/53301001/50002022/10/23562300023101/20-1/502022/10/31571、当变化时，假设，则要使得问题的最优解保持不变，则检验数行即可，即要求2、当变化时，假设，则要使得问题的最优解保持不变，则检验数行即可，即要求2022/10/23571、当变化时，假设2022/10/3158二、b的变化分析

b的变化将只影响原问题的基可行解，即最终表中的b列数值。例、设有如下的线性规划模型试分析分别在什么范围变化时，最优基不变？2022/10/2358二、b的变化分析例、设有如下的线性2022/10/3159解：将重新计算后填入问题的最终单纯形表：1、当变化时，假设，则问题的解变为填入下表，得230002101/20-1/5000-214/5301001/500-10-1/52022/10/2359解：将重新计算后填入问题2022/10/3160要使得最优基保持不变，则b列数值

即可，即要求同理可得的变化范围是：

的变化范围是：2022/10/2360要使得最优基保持不变，则b列数值2022/10/3161三、增加一个变量的变化分析

增加一个变量，在方程组（矩阵A）中就要增加一个系数列，在原来的最终表中也要添加一列，检验数也要计算，其余部分不受影响。如果检验数行仍，则最优解不变，否则继续迭代寻找最优。一般分析步骤：1、计算增加的新变量系数列在原最终表中的结果；2、计算新变量对应的检验数；3、根据的符号判断是否仍是最优解，若是，最优解不变；若不是，继续求解。

2022/10/2361三、增加一个变量的变化分析2022/10/3162例、设有如下的线性规划模型现增加变量，其对应系数列为，价值系数，请问最优解是否改变？

解：最终表2300023101/20-1/50400-214/53301001/500-10-1/52022/10/2362例、设有如下的线性规划模型解：最终表2022/10/3163新变量的检验数及系数列分别为：填入表中，易知未达最优，继续迭代求解。2022/10/2363新变量的检验数及系数列分别为：填入表2022/10/31642300023101/20-1/50400-214/53301001/500-10-1/523101/20-1/50100-1/21/41/532011/2-1/4000-1/2-1/4-2/5010000411已达最优。最优解为

最优目标值2022/10/23642300023101/20-1/502022/10/3165四、增加一个约束条件的变化分析

增加一个约束条件，相当于增加一道工序。分析方法:1）先将原最优解带入此新约束，若满足条件，说明此约束未起作用，原最优解不变；2）否则，将新约束加入到最终表中，继续分析。例、在上例中添加新约束，分析最优解的变化情况。解：因为将原最优解带入此约束，不满足约束，原解已不是最优，继续分析。2022/10/2365四、增加一个约束条件的变化分析例、在2022/10/31662300023101/20-1/50400-214/53301001/50143200000-10-1/500001023101/20-1/50400-214/53301001/50-100-3/201/500-10-1/5000106x2022/10/23662300023101/20-1/502022/10/316728/31000-1/10016/300018/153301001/502/30010-2/150000-2/51/3-4/30-2/3-2/3已达最优。最优解为

最优目标值2022/10/236728/31000-1/10016/32022/10/31--第2章对偶问题----68--3．计算示例：maxz=2x1+3x2s.t2x1+2x2

12

x1+2x28

4x1

164x212x10,x20例：已知某线性规划模型及最终的单纯表如下：问：（1）若b2增加8个单位，最优解如何变化？（2）若c2还可增加2个单位，最优解如何改变？（3）若引进一个新变量（产品）y，其目标函数系数为cy=5，系数列向量为py=[3263]T，问最优解是否会改变？

cj—230000

CBXBbx1x2x3x4x5x60x302x140x643x22001-1-0.25010000.250000-20.510100.5-0.1250cj－zj000-1.5-0.12502022/10/23--第2章对偶问题----68--32022/10/31--第2章对偶问题----69--解：（1）（b+△b）´=B-1b+B-1

△b=b´+B-1

△b =0442T

+-80-164T=-84-126TB-1△b=1-1-0.250000.2500-20.5100.5-0.12500800=-80-164利用对偶单纯形法继续求最优解。（2）当cj变化时，´=C´－CB´B-1

A，列出单纯形表，重新求出检验数，如表中所示：（3）增加y时，y=cy-CB

B-1

py=5-(01.50.1250)[3263]T =1.25>0选择y作入基变量，py´=B-1

py==-0.51.520.25T继续迭代：2022/10/23--第2章对偶问题----69--解2022/10/31--第2章对偶问题----70--

cj—230000

CBXBbx1x2x3x4x5x60x3-82x140x6-123x26001-1-0.25010000.250000-20.510100.5-0.1250cj－zj000-1.5-0.12500x3-22x140x463x230010-0.5-0.510000.2500001-0.25-0.5010000.25cj－zj0000-0.5-0.750x542x130x673x2300-2011100.500-0.2500-0.510-0.25010000.25cj－zj00-100-0.25返回右端项变化分析单纯形表：2022/10/23--第2章对偶问题----70--2022/10/31--第2章对偶问题----71--

cj—250000

CBXBbx1x2x3x4x5x60x302x140x645x22001-1-0.25010000.250000-20.510100.5-0.1250cj－zj000-2.50.12500x322x120x585x23001-200.510010-0.5000-412010000.25cj－zj000-20-0.25返回Cj变化分析单纯形表：2022/10/23--第2章对偶问题----71--2022/10/31--第2章对偶问题----72--

cj—230000

5

CBXBbx1x2x3x4x5x6y0x302x140x643x22001-1-0.250-0.510000.2501.5000-20.5120100.5-0.12500.25cj－zj000-1.5-0.12501.250x312x115y23x21.5001-1.5-0.1250.2501001.5-0.125-0.750000-10.250.510100.75-0.1875-0.1250cj－zj000-0.25-0.4375-0.6250增加新产品（变量y）变化分析单纯形表：2022/10/23--第2章对偶问题----72--2022/10/31--第2章对偶问题----73--2.7参数线性规划1.概念：研究目标函数值随某一参数变化的规律及最优解相应的变化。算法：先令变化量=0，当多