单纯形法的灵敏度分析与对偶课件

第六章*单纯形法的灵敏度分析与对偶单纯形表的灵敏度分析线性规划的对偶问题对偶单纯形法整理课件第六章*单纯形法的灵敏度分析与对偶单纯形表的灵敏度分析整1第六章*单纯形法的灵敏度分析与对偶如何利用最优单纯形表进行灵敏度分析。。整理课件第六章*单纯形法的灵敏度分析与对偶如何利用最优单纯形表进2单纯形表--求解结果：迭代次数基变量CBx1X2s1s2S3b比值501000000x1501010-150S2000-21150x210001001250Zj5010050050Z=2750000-500-50整理课件单纯形表--求解结果：迭代次数基变量CBx1X2s1s2S33第1节单纯形表的灵敏度分析一.目标函数中变量系数Ck灵敏度分析现要利用单纯形表法来进行Ck的灵敏度分析。由于目标函数变量分为基与非基变量，故讨论时,分两类来讨论。1.在最终的单纯形表里,xK非基变量.2.在最终的单纯形表里,xK基变量.整理课件第1节单纯形表的灵敏度分析一.目标函数中变量系数C4第1节单纯形表的灵敏度分析1.在最终的单纯形表里,xK非基变量。

由于约束条件（方程）系数增广矩阵在迭代中只是其本身的行的初等变换与CK没有任何关系，所以当CK变为CK

+△CK时，在最终单纯形表中其系数的增广矩阵不变，又因为xK

是非基变量，所以基变量的目标函数的系数不变，即CB

不变，可知ZK

也不变，只是CK变为CK

+△CK

。这时σK=CK－ZK

变成了CK

+△CK－ZK=σK+△CK

.要使得原来的最优解仍为最优解，只要σK+△CK≤0即可，也就是

△CK≤－σK

即可。整理课件第1节单纯形表的灵敏度分析1.在最终的单纯形表里,xK5第1节单纯形表的灵敏度分析２.在最终的单纯形表里,xK为基变量。

由于约束条件（方程）系数增广矩阵在迭代中只是其本身的行的初等变换与CK没有任何关系，所以当CK变为CK

+△CK时，在最终单纯形表中其系数的增广矩阵不变，但基变量在目标函数的系数CB变了，则Zj

也变了，相应地，σＪ也变了。变化规律为：整理课件第1节单纯形表的灵敏度分析２.在最终的单纯形表里,xK6目标函数：max z=50x1+100x2x1+x2≤3002x1+x2≤400x1≥0,x2≥0s.t.x2≤250max z=50x1+100x2x1+x2+s1=3002x1+x2+s2=400x1≥0,x2≥0,si≥0s.t.x2+s3=250整理课件目标函数：x1+x2≤3002x1+x2≤400x1≥07一、线性规划问题解的基本概念基及基本解:max z=50x1+100x2+0s1+0s2+0s31x1+1x2+1s1+0s2+0s3=3002x1+1x2+0s1+1s2+0s3=400x1≥0,x2≥0,s1≥0，s2≥0，s3≥0s.t.0x1+1x2+0s1+0s2+1s3=250整理课件一、线性规划问题解的基本概念基及基本解:max z=50x18表解形式的单纯形法例子:整理课件表解形式的单纯形法例子:整理课件9初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000002x1501010-150S2000-21150x210001001250Zj5010050050Z=2750000-500-50整理课件初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值5010（１）先分析非基变量s1:c3σ3

由于是非基变量，故套用公式（1）

当△C3≤-σ3,时最优解不变;已知σ3=-50,△C3≤－（－50）=50；c’=c+△C<=0+50=50最优解不变。整理课件（１）先分析非基变量s1:c3σ3当△C3≤-σ11（2）再分析基变量的系数分析：从表中获得了:a11=1,a12=0,a13=1,a14=0,a15=-1例如对基变量X1的系数C1进行灵敏度分析：整理课件（2）再分析基变量的系数分析：从表中获得了:例如对基变量X112单纯形表灵敏度分析迭代次数基变量CBx1X2s1s2S3b比值501000002x1501010-150S2000-21150x210001001250Zj5010050050Z=2750000-500-500---50L--50R缩小区间整理课件单纯形表灵敏度分析迭代次数基变量CBx1X2s1s2S3b513故，max{-50}≤△C1≤min{50}，左半径和右半径[保证区间半径最小]则当-50≤△C1≤50时最优解不变，即x1的目标函数系数C’有：50-50=c1+L≤C‘=C1+△C1≤c1+R=50+50，0≤C‘≤100时，最优解不变。整理课件故，max{-50}≤△C1≤min{50}，左半径和右半14

**********************最优解如下*************************目标函数最优值为:27500

变量最优解相差值

-----------------------x1500x22500

约束松弛/剩余变量对偶价格

----------------------------10

5025003050

目标函数系数范围:

变量下限当前值上限

-------------------------------x1050100x250100无上限常数项数范围:

约束下限当前值上限

-------------------------------12503003252350400无上限

3200250300整理课件**********************最优解如下**15LPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1)27500.00VARIABLEVALUEREDUCEDCOSTX150.0000000.000000X2250.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000050.0000003)50.0000000.0000004)0.00000050.000000NO.ITERATIONS=2RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLE

COEFINCREASEDECREASE

X150.00000050.00000050.000000X2100.000000INFINITY50.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE2300.00000025.00000050.0000003400.000000INFINITY50.0000004250.00000050.00000050.000000整理课件LPOPTIMUMFOUNDATSTEP16二、基于单纯形法的约束方程右边常数灵敏度分析迭代次数基变量CBx1X2s1s2S3b比值501000002x1501010-150台时S2000-21150x210001001250Zj5010050050Z=2750000-500-50整理课件二、基于单纯形法的约束方程右边常数灵敏度分析迭代次数基变量C17二、约束方程右边常数灵敏度分析从上页表中我们,知道了右边系数bj的灵敏度,对偶价格不变与bj变化范围.现要从单纯形表的数据进行分析：

Zj的值刚好是对偶价格.那么，当bj变为bj+△b时,非基变量的检验数不变,但基变量的检验数会变。bk允许范围为:整理课件二、约束方程右边常数灵敏度分析从上页表中我们,知道了右边系数18二、约束方程右边常数灵敏度分析那么，当br变为br+△br时,非基变量的检验数不变,但基变量的检验数会变.△br允许范围为:整理课件二、约束方程右边常数灵敏度分析那么，当br变为br+△br时19初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000000x1501010-150S2000-21150x210001001250Zj5010050050Z=2750000-500-50整理课件初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值5020现对b1进行灵敏度分析,先要找出b1的列元素:它就是S1.因为可逆矩阵B的第一列为S1=(1,-2,0)TMax{-50/1}=-50≤△b1≤min{-50/-2}=25-50≤△b1≤+25那么,300-50≤b’=b+△b1≤300+25250≤b’=b+△b1≤325练习：分析B3整理课件现对b1进行灵敏度分析,先要找出b1的列元素:它就是S1.因21三、约束方程系数矩阵A灵敏度分析技术系数aij发生变化时对线性规划最优解结构的影响比较复杂。从下式中可知，非基变量的检验数和基变量XB的值都与技术系数有关。通常把技术系数aij的灵敏度分析分为如下三类：（1）对应基变量的AIJ，且资源BI已全部用完；（2）对应基变量的AIJ，但资源BI未用完；（3）对应非基变量的AIJ，且资源BI全部用完或未用完；整理课件三、约束方程系数矩阵A灵敏度分析技术系数ai22三、约束方程系数矩阵A灵敏度分析线性规划最优解结构不变的条件是（1）对应基变量的aij，且资源Bi已全部用完，则技术系数变化范围为：△aij=0;（2）对应基变量的aij，但资源bi未用完,则技术系数变化范围为：－∞≤△aij≤Xn+i/xj（3）对应非基变量的aij，且资源bi全部用完或未用完,我们要分以下两种情况讨论：（A）△aij>0,不会破坏最优解。（B）△aij<0，要使原线性规划最优解不变条件：必须保证该非基变量的检验数仍小于0，即cj-Zj≤0整理课件三、约束方程系数矩阵A灵敏度分析线性规划最优解结构不变的条件23第2节线性规划的对偶问题某工厂在计划安排I,II两种产品,III资源限制设备A11300台时设备B21400设备C01250生产I可获得50元,II可获得100元,如何安排生产,获得MAX?整理课件第2节线性规划的对偶问题某工厂在计划安排I,II两种产品,24模型目标:maxz=50x1+100x2S.t.x1+x2<=3002x1+x2<=400x2<=250x1,x2>=0整理课件模型目标:maxz=50x1+100x2整理课件25假设现在有一个公司要租用工厂设备，那么工厂获取利润有两种方法，一是自己生产，二是出租设备资源。自己生产已有模型。那么，如果出租，那么如何构建模型？设备价格为Ay1,By2,Cy3;

则目标:minf=300y1+400y2+250y3s.t.y1+2y2>=50y1+y2+y3>100y1,y2,y3>=0整理课件假设现在有一个公司要租用工厂设备，那么工厂获取利润有两种方法26目标:minf=300y1+400y2+250y3s.t.Y1+2y2>=50y1+y2+y3>100y1,y2,y3>=0目标:maxz=50x1+100x2S.t.x1+x2<=3002x1+x2<=400x2<=250

x1,x2>=0原问题对偶问题整理课件目标:minf=300y1+400y2+250y3目标:271.求目标函数最大问题中有n个变量,m个约束条件,它的约束条件都是小于等于不等式;其对偶则是m个变量,n个约束条件,并且是大于等于不等式;2.原问题的目标函数系数C是对偶问题中的约束条件B

ci=bi3.原问题右边系数B成为对偶问题的目标系数C,bi=ci4.对偶问题的约束条件系数矩阵A是原问题的AT整理课件1.求目标函数最大问题中有n个变量,m个约束条件,它的约束条28整理课件整理课件29整理课件整理课件30原问题（max,≤)对偶问题(min,≥)技术系数矩阵A技术系数矩阵AT价值系数C右端项b右端项b价值系数C第i行约束条件为≤型对偶变量yi≥0第i行约束条件为≥型对偶变量yi≤0第i行约束条件为=型对偶变量yi正负不限决策量xj≥0第j行约束条件为≥型决策量xj≤0第j行约束条件为≤型决策量xj正负不限第j行约束条件为=型整理课件原问题（max,≤)对偶问题(min,≥)技术系数矩阵A技术31转化例子：Maxf=3x1+4x2+6x3+4x4x1+4x2+2x3-3x4≤353x1+x2+5x3+6x4≤45x1,x2,x3,x4≥0Ming(y)=35y1+45y2Y1+3y2≥34y1+y2≥42y1+5y2≥6-3y1+6y2≥4Y1,y2≥0整理课件转化例子：Ming(y)=35y1+45y2整理课件32目标:minf=300y1+400y2+250y3s.t.Y1+2y2≥50y1+y2+y3≥100y1,y2,y3≥0目标:maxz=50x1+100x2S.t.x1+x2≤3002x1+x2≤400x2≤250

x1,x2≥0原问题对偶问题整理课件目标:目标:原问题对偶问题整理课件33Max-f=-300y1-400y2-250y3-Ma1y1+2y2-s1+a1=50y1+y2+y3-s2=100y1,y2,y3,s1,s2,a1>0对偶单纯形法求解：整理课件Max-f=-300y1-400y2-250y3-Ma1对34初始单纯形表迭代次数基变量CBy1y2y3s1s2a1b比值-300-400-25000-M0a1-M120-10150y3-2501110-10100Zj-M-250-2M-250-250M250-M-50M-2500Cj-ZjM-502M-1500-M-2500②整理课件初始单纯形表迭代次数基变量CBy1y2y3s1s2a1b-335初始单纯形表迭代次数基变量CBy1y2y3s1s2a1b比值-300-400-25000-M0y2-4001/210-1/201/225y3-2501/2011/2-1-1/275Zj-325-400-25075250-75-28750Cj-Zj2500-75-250-M+75(1/2)整理课件初始单纯形表迭代次数基变量CBy1y2y3s1s2a1b-336初始单纯形表迭代次数基变量CBy1y2y3s1s2a1b比值-300-400-25000-M0y1-300120-10150y3-2500-111-1-150Zj-300-350-25050250-50-27500Cj-Zj0-500-50-250-M+50(1/2)最优解:y1=50,y2=0,y3=50,s1=0,s2=0,a1=0,-f的最大值为-27500,即目标f的最小值为:27500A设备租金为50元,B设备租金为0元,C设备租金为50元;整理课件初始单纯形表迭代次数基变量CBy1y2y3s1s2a1b-337二.任意形式的对偶问题

maxZ=3x1+4x2+6x3s.t.2x1+3x2+6x3≤4406x1-4x2-x3≥1005x1-3x2+x3=200x1,x2,x3≥0整理课件二.任意形式的对偶问题整理课件38二.任意形式的对偶问题

maxZ=3x1+4x2+6x3s.t.2x1+3x2+6x3≤440-6x1+4x2+x3≤-1005x1-3x2+x3≥200

5x1-3x2+x3≤200x1,x2,x3≥05x1-3x2+x3=200整理课件二.任意形式的对偶问题5x1-3x2+x3=20039maxZ=3x1+4x2+6x3s.t.2x1+3x2+6x3≤440-6x1+4x2+x3≤-1005x1-3x2+x3≤200-5x1+3x2-x3≤-200

x1,x2,x3≥0s.t.2y1-6y2+5y3-5y4≥33y1+4y2+3y3-3y4≥4

6y1+y2+y3-y4≥6y1,y2,y3,y4≥0minf=440y1-100y2+200y3-200y4二.任意形式的对偶问题对偶问题整理课件maxZ=3x1+4x2+6x3s.t.minf=440原问题的对偶问题为

minf=440y1-100y2+200y3-200y4s.t.2y1-6y2+5y3-5y4≥33y1+4y2+3y3-3y4≥4

6y1+y2+y3-y4≥6y1,y2,y3,y4≥0整理课件原问题的对偶问题为整理课件41原问题的对偶问题为

minf=440y1-100y2+200(y3-y4)s.t.2y1-6y2+5(y3-y4)≥33y1+4y2+3(y3-y4)≥4

6y1+y2+(y3-y4)≥6y1,y2,y3,y4≥0整理课件原问题的对偶问题为整理课件42原问题的对偶问题为

minf=440y1-100y2+200s3s.t.2y1-6y2+5s3≥33y1+4y2+3s3≥4

6y1+y2+s3≥6y1,y2≥0,S3无非负限制整理课件原问题的对偶问题为整理课件43练习：Maxf(x)=4x1+5x2s.t.3x1+2x2≤204x1-3x2≥10

x1+x2=5x2≥0,x1正负不限整理课件练习：整理课件44练习转换：Maxf(x)=4x11-4x12+5x2s.t.3x11-3x12+2x2≤204x11-4x12-3x2≥10

x11-x12+x2=5x11,x12,x2≥0整理课件练习转换：整理课件45练习转换：Maxf(x)=4x11-4x12+5x2s.t.3x11-3x12+2x2≤204x11-4x12-3x2≥10

x11-x12+x2≥5

x11-x12+x2≤5x11,x12,x2≥0整理课件练习转换：整理课件46练习转换：Maxf(x)=4x11-4x12+5x2s.t.3x11-3x12+2x2≤20-(4x11-4x12-3x2)≤-10

-(x11-x12+x2)≤-5

x11-x12+x2≤5x11,x12,x2≥0整理课件练习转换：整理课件47练习转换：Maxf(x)=4x11-4x12+5x2s.t.3x11-3x12+2x2≤20-4x11+4x12+3x2≤-10

-x11+x12-x2≤-5

x11-x12+x2≤5x11,x12,x2≥0整理课件练习转换：整理课件48练习转换：Minf(y)=20y1-10y2-5y3+5y4s.t.

3y1-4y2-y3+y4>=4-3y1+4y2+y3-y4>=-42y1+3y2-y3+y4>=5y1,y2,y3,y4>=0整理课件练习转换：整理课件49练习转换：Minf(y)=20y1-10y2-5(y3-y4)s.t.

3y1-4y2-(y3-y4)>=4-3y1+4y2+(y3-y4)>=-42y1+3y2-(y3-y4)>=5y1,y2,y3,y4>=0整理课件练习转换：整理课件50练习转换：Minf(y)=20y1-10y2-5y3s.t.

3y1-4y2-y3>=4-3y1+4y2+y3>=-42y1+3y2-y3>=5y1,y2>=0，y3无限制整理课件练习转换：整理课件51练习转换：Minf(y)=20y1-10y2-5y3s.t.

3y1-4y2-y3=42y1+3y2-y3>=5y1,y2>=0，y3无限制整理课件练习转换：整理课件52练习转换：Minf(y)=20y1-10y2-5y3+5y4s.t.

3y1-4y2-y3+y4>=4-3y1+4y2+y3-y4>=-42y1+3y2-y3+y4>=5y1,y2,y3,y4>=0整理课件练习转换：整理课件53练习答案：Minh(y)=20y1+10y2+5y3s.t.3y1+4y2+y3=42y1-3y2+y3≥5y1≥0,y2≤0,y3不限整理课件练习答案：整理课件54原问题（max,≤)对偶问题(min,≥)技术系数矩阵A技术系数矩阵AT价值系数C右端项b右端项b价值系数C第i行约束条件为≤型对偶变量yi≥0第i行约束条件为≥型对偶变量yi≤0第i行约束条件为=型对偶变量yi正负不限决策量xj≥0第j行约束条件为≥型决策量xj≤0第j行约束条件为≤型决策量xj正负不限第j行约束条件为=型整理课件原问题（max,≤)对偶问题(min,≥)技术系数矩阵A技术55第3节对偶单纯形法对偶单纯法和单纯形法一样都是求解原线性规划问题的一种方法.单纯形法是在保持原问题的所有约束条件的bj都大于0的情况下,通过迭代,使得所有检验数都小于等于0,最后求得最优解;而对偶单纯形法则是在保持原问题的所有检验数都小于等于0的情况下,通过迭代,使得所有约束条件的常数都大于等于0,最后求得最优解。整理课件第3节对偶单纯形法对偶单纯法和单纯形法一样都是求解原线性规56第3节对偶单纯形法例，用对偶单纯形法求解如下线性规划问题：Minf=x1+5x2+3x4s.t.X1+2x2-x3+x4≥6-2x1-x2+4x3+x4≥4x1,x2,x3,x4>=0整理课件第3节对偶单纯形法例，用对偶单纯形法求解如下线性规划问题：57第3节对偶单纯形法例，用对偶单纯形法求解如下线性规划问题：将上述线性规划问题变换为如下适合对偶单纯形法的形式：Maxz=-f=-x1-5x2-3x4s.t.-X1-2x2+x3-x4+x5=-62x1+x2-4x3-x4+x6=-4x1,x2,x3,x4,x5,x6>=0x5,x6为剩余变量整理课件第3节对偶单纯形法例，用对偶单纯形法求解如下线性规划问题：58初始单纯形表迭代次数基变量CBx1x2x3x4x5x6b比值-1-50-3000x50-1-21-110-6x6021-4-101-4Zj0000000Cj-Zj-1-50-300②X=(0,0,0,0,-6,-4)是基本解，但不是基本可行解，不可行。整理课件初始单纯形表迭代次数基变量CBx1x2x3x4x5x6b-159（1）确定出基变量：min{bi|bi<0}=min{-6,-4}=-6

=b1,所以第L=1行为主行，x5出基变量。

（2）入基变量:所以第K=1列为主列，第1列的变量X1为入基变量。整理课件（1）确定出基变量：min{bi|bi<0}=min{-6,60迭代次数基变量CBx1x2x3x4x5x6b比值-1-50-3000x50-1-21-110-6x6021-4-101-4Zj0000000Cj-Zj-1-50-300(-1)整理课件迭代次数基变量CBx1x2x3x4x5x6b-1-50-3061迭代次数基变量CBx1x2x3x4x5x6b比值-1-50-3000x1-112-11-106x600-3-2-321-16Zj-1-21-110-6Cj-Zj0-3-1-2-10(-2)整理课件迭代次数基变量CBx1x2x3x4x5x6b-1-50-3062迭代次数基变量CBx1x2x3x4x5x6b比值-1-50-3000x1-117/205/2-2-1/214x3003/213/2-1-1/28Zj-1-7/20-5/221/2Z=-14Cj-Zj0-3/20-1/2-2-1/2(-2)X=(x1,x2,x3,x4,x5,x6)=(14,0,8,0,0,0)满足可行性检验，所以上述X是原线性规划的最优解。最优值：f=-g(X0=-(-14)=14整理课件迭代次数基变量CBx1x2x3x4x5x6b-1-50-3063对偶单纯形法的步骤：1。求一个满足最优检验条件的初始基本解，列出初始单纯形表；2。可行性检验，若所有的右系数均大于0，则已得最优解，停止运算，否则，转33。求另一个满足最优检验条件且更接近可行解的基本解；（1）确定出变量：找出bi中的最小者，确定行号及变量；（2）确定入变量：最小比原则min(σj/aij}定出列号；若找不到，则原规划问题的解无界解，停止运算，否则转步骤（3）（3）以主元alk为中心，迭代，单位化，得到新的基本解，让其接近基本可行解。再转2；整理课件对偶单纯形法的步骤：整理课件64第六章*单纯形法的灵敏度分析与对偶单纯形表的灵敏度分析线性规划的对偶问题对偶单纯形法整理课件第六章*单纯形法的灵敏度分析与对偶单纯形表的灵敏度分析整65第六章*单纯形法的灵敏度分析与对偶如何利用最优单纯形表进行灵敏度分析。。整理课件第六章*单纯形法的灵敏度分析与对偶如何利用最优单纯形表进66单纯形表--求解结果：迭代次数基变量CBx1X2s1s2S3b比值501000000x1501010-150S2000-21150x210001001250Zj5010050050Z=2750000-500-50整理课件单纯形表--求解结果：迭代次数基变量CBx1X2s1s2S367第1节单纯形表的灵敏度分析一.目标函数中变量系数Ck灵敏度分析现要利用单纯形表法来进行Ck的灵敏度分析。由于目标函数变量分为基与非基变量，故讨论时,分两类来讨论。1.在最终的单纯形表里,xK非基变量.2.在最终的单纯形表里,xK基变量.整理课件第1节单纯形表的灵敏度分析一.目标函数中变量系数C68第1节单纯形表的灵敏度分析1.在最终的单纯形表里,xK非基变量。

由于约束条件（方程）系数增广矩阵在迭代中只是其本身的行的初等变换与CK没有任何关系，所以当CK变为CK

+△CK时，在最终单纯形表中其系数的增广矩阵不变，又因为xK

是非基变量，所以基变量的目标函数的系数不变，即CB

不变，可知ZK

也不变，只是CK变为CK

+△CK

。这时σK=CK－ZK

变成了CK

+△CK－ZK=σK+△CK

.要使得原来的最优解仍为最优解，只要σK+△CK≤0即可，也就是

△CK≤－σK

即可。整理课件第1节单纯形表的灵敏度分析1.在最终的单纯形表里,xK69第1节单纯形表的灵敏度分析２.在最终的单纯形表里,xK为基变量。

由于约束条件（方程）系数增广矩阵在迭代中只是其本身的行的初等变换与CK没有任何关系，所以当CK变为CK

+△CK时，在最终单纯形表中其系数的增广矩阵不变，但基变量在目标函数的系数CB变了，则Zj

也变了，相应地，σＪ也变了。变化规律为：整理课件第1节单纯形表的灵敏度分析２.在最终的单纯形表里,xK70目标函数：max z=50x1+100x2x1+x2≤3002x1+x2≤400x1≥0,x2≥0s.t.x2≤250max z=50x1+100x2x1+x2+s1=3002x1+x2+s2=400x1≥0,x2≥0,si≥0s.t.x2+s3=250整理课件目标函数：x1+x2≤3002x1+x2≤400x1≥071一、线性规划问题解的基本概念基及基本解:max z=50x1+100x2+0s1+0s2+0s31x1+1x2+1s1+0s2+0s3=3002x1+1x2+0s1+1s2+0s3=400x1≥0,x2≥0,s1≥0，s2≥0，s3≥0s.t.0x1+1x2+0s1+0s2+1s3=250整理课件一、线性规划问题解的基本概念基及基本解:max z=50x172表解形式的单纯形法例子:整理课件表解形式的单纯形法例子:整理课件73初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000002x1501010-150S2000-21150x210001001250Zj5010050050Z=2750000-500-50整理课件初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值5074（１）先分析非基变量s1:c3σ3

由于是非基变量，故套用公式（1）

当△C3≤-σ3,时最优解不变;已知σ3=-50,△C3≤－（－50）=50；c’=c+△C<=0+50=50最优解不变。整理课件（１）先分析非基变量s1:c3σ3当△C3≤-σ75（2）再分析基变量的系数分析：从表中获得了:a11=1,a12=0,a13=1,a14=0,a15=-1例如对基变量X1的系数C1进行灵敏度分析：整理课件（2）再分析基变量的系数分析：从表中获得了:例如对基变量X176单纯形表灵敏度分析迭代次数基变量CBx1X2s1s2S3b比值501000002x1501010-150S2000-21150x210001001250Zj5010050050Z=2750000-500-500---50L--50R缩小区间整理课件单纯形表灵敏度分析迭代次数基变量CBx1X2s1s2S3b577故，max{-50}≤△C1≤min{50}，左半径和右半径[保证区间半径最小]则当-50≤△C1≤50时最优解不变，即x1的目标函数系数C’有：50-50=c1+L≤C‘=C1+△C1≤c1+R=50+50，0≤C‘≤100时，最优解不变。整理课件故，max{-50}≤△C1≤min{50}，左半径和右半78

**********************最优解如下*************************目标函数最优值为:27500

变量最优解相差值

-----------------------x1500x22500

约束松弛/剩余变量对偶价格

----------------------------10

5025003050

目标函数系数范围:

变量下限当前值上限

-------------------------------x1050100x250100无上限常数项数范围:

约束下限当前值上限

-------------------------------12503003252350400无上限

3200250300整理课件**********************最优解如下**79LPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1)27500.00VARIABLEVALUEREDUCEDCOSTX150.0000000.000000X2250.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000050.0000003)50.0000000.0000004)0.00000050.000000NO.ITERATIONS=2RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLE

COEFINCREASEDECREASE

X150.00000050.00000050.000000X2100.000000INFINITY50.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE2300.00000025.00000050.0000003400.000000INFINITY50.0000004250.00000050.00000050.000000整理课件LPOPTIMUMFOUNDATSTEP80二、基于单纯形法的约束方程右边常数灵敏度分析迭代次数基变量CBx1X2s1s2S3b比值501000002x1501010-150台时S2000-21150x210001001250Zj5010050050Z=2750000-500-50整理课件二、基于单纯形法的约束方程右边常数灵敏度分析迭代次数基变量C81二、约束方程右边常数灵敏度分析从上页表中我们,知道了右边系数bj的灵敏度,对偶价格不变与bj变化范围.现要从单纯形表的数据进行分析：

Zj的值刚好是对偶价格.那么，当bj变为bj+△b时,非基变量的检验数不变,但基变量的检验数会变。bk允许范围为:整理课件二、约束方程右边常数灵敏度分析从上页表中我们,知道了右边系数82二、约束方程右边常数灵敏度分析那么，当br变为br+△br时,非基变量的检验数不变,但基变量的检验数会变.△br允许范围为:整理课件二、约束方程右边常数灵敏度分析那么，当br变为br+△br时83初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000000x1501010-150S2000-21150x210001001250Zj5010050050Z=2750000-500-50整理课件初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值5084现对b1进行灵敏度分析,先要找出b1的列元素:它就是S1.因为可逆矩阵B的第一列为S1=(1,-2,0)TMax{-50/1}=-50≤△b1≤min{-50/-2}=25-50≤△b1≤+25那么,300-50≤b’=b+△b1≤300+25250≤b’=b+△b1≤325练习：分析B3整理课件现对b1进行灵敏度分析,先要找出b1的列元素:它就是S1.因85三、约束方程系数矩阵A灵敏度分析技术系数aij发生变化时对线性规划最优解结构的影响比较复杂。从下式中可知，非基变量的检验数和基变量XB的值都与技术系数有关。通常把技术系数aij的灵敏度分析分为如下三类：（1）对应基变量的AIJ，且资源BI已全部用完；（2）对应基变量的AIJ，但资源BI未用完；（3）对应非基变量的AIJ，且资源BI全部用完或未用完；整理课件三、约束方程系数矩阵A灵敏度分析技术系数ai86三、约束方程系数矩阵A灵敏度分析线性规划最优解结构不变的条件是（1）对应基变量的aij，且资源Bi已全部用完，则技术系数变化范围为：△aij=0;（2）对应基变量的aij，但资源bi未用完,则技术系数变化范围为：－∞≤△aij≤Xn+i/xj（3）对应非基变量的aij，且资源bi全部用完或未用完,我们要分以下两种情况讨论：（A）△aij>0,不会破坏最优解。（B）△aij<0，要使原线性规划最优解不变条件：必须保证该非基变量的检验数仍小于0，即cj-Zj≤0整理课件三、约束方程系数矩阵A灵敏度分析线性规划最优解结构不变的条件87第2节线性规划的对偶问题某工厂在计划安排I,II两种产品,III资源限制设备A11300台时设备B21400设备C01250生产I可获得50元,II可获得100元,如何安排生产,获得MAX?整理课件第2节线性规划的对偶问题某工厂在计划安排I,II两种产品,88模型目标:maxz=50x1+100x2S.t.x1+x2<=3002x1+x2<=400x2<=250x1,x2>=0整理课件模型目标:maxz=50x1+100x2整理课件89假设现在有一个公司要租用工厂设备，那么工厂获取利润有两种方法，一是自己生产，二是出租设备资源。自己生产已有模型。那么，如果出租，那么如何构建模型？设备价格为Ay1,By2,Cy3;

则目标:minf=300y1+400y2+250y3s.t.y1+2y2>=50y1+y2+y3>100y1,y2,y3>=0整理课件假设现在有一个公司要租用工厂设备，那么工厂获取利润有两种方法90目标:minf=300y1+400y2+250y3s.t.Y1+2y2>=50y1+y2+y3>100y1,y2,y3>=0目标:maxz=50x1+100x2S.t.x1+x2<=3002x1+x2<=400x2<=250

x1,x2>=0原问题对偶问题整理课件目标:minf=300y1+400y2+250y3目标:911.求目标函数最大问题中有n个变量,m个约束条件,它的约束条件都是小于等于不等式;其对偶则是m个变量,n个约束条件,并且是大于等于不等式;2.原问题的目标函数系数C是对偶问题中的约束条件B

ci=bi3.原问题右边系数B成为对偶问题的目标系数C,bi=ci4.对偶问题的约束条件系数矩阵A是原问题的AT整理课件1.求目标函数最大问题中有n个变量,m个约束条件,它的约束条92整理课件整理课件93整理课件整理课件94原问题（max,≤)对偶问题(min,≥)技术系数矩阵A技术系数矩阵AT价值系数C右端项b右端项b价值系数C第i行约束条件为≤型对偶变量yi≥0第i行约束条件为≥型对偶变量yi≤0第i行约束条件为=型对偶变量yi正负不限决策量xj≥0第j行约束条件为≥型决策量xj≤0第j行约束条件为≤型决策量xj正负不限第j行约束条件为=型整理课件原问题（max,≤)对偶问题(min,≥)技术系数矩阵A技术95转化例子：Maxf=3x1+4x2+6x3+4x4x1+4x2+2x3-3x4≤353x1+x2+5x3+6x4≤45x1,x2,x3,x4≥0Ming(y)=35y1+45y2Y1+3y2≥34y1+y2≥42y1+5y2≥6-3y1+6y2≥4Y1,y2≥0整理课件转化例子：Ming(y)=35y1+45y2整理课件96目标:minf=300y1+400y2+250y3s.t.Y1+2y2≥50y1+y2+y3≥100y1,y2,y3≥0目标:maxz=50x1+100x2S.t.x1+x2≤3002x1+x2≤400x2≤250

x1,x2≥0原问题对偶问题整理课件目标:目标:原问题对偶问题整理课件97Max-f=-300y1-400y2-250y3-Ma1y1+2y2-s1+a1=50y1+y2+y3-s2=100y1,y2,y3,s1,s2,a1>0对偶单纯形法求解：整理课件Max-f=-300y1-400y2-250y3-Ma1对98初始单纯形表迭代次数基变量CBy1y2y3s1s2a1b比值-300-400-25000-M0a1-M120-10150y3-2501110-10100Zj-M-250-2M-250-250M250-M-50M-2500Cj-ZjM-502M-1500-M-2500②整理课件初始单纯形表迭代次数基变量CBy1y2y3s1s2a1b-399初始单纯形表迭代次数基变量CBy1y2y3s1s2a1b比值-300-400-25000-M0y2-4001/210-1/201/225y3-2501/2011/2-1-1/275Zj-325-400-25075250-75-28750Cj-Zj2500-75-250-M+75(1/2)整理课件初始单纯形表迭代次数基变量CBy1y2y3s1s2a1b-3100初始单纯形表迭代次数基变量CBy1y2y3s1s2a1b比值-300-400-25000-M0y1-300120-10150y3-2500-111-1-150Zj-300-350-25050250-50-27500Cj-Zj0-500-50-250-M+50(1/2)最优解:y1=50,y2=0,y3=50,s1=0,s2=0,a1=0,-f的最大值为-27500,即目标f的最小值为:27500A设备租金为50元,B设备租金为0元,C设备租金为50元;整理课件初始单纯形表迭代次数基变量CBy1y2y3s1s2a1b-3101二.任意形式的对偶问题

maxZ=3x1+4x2+6x3s.t.2x1+3x2+6x3≤4406x1-4x2-x3≥1005x1-3x2+x3=200x1,x2,x3≥0整理课件二.任意形式的对偶问题整理课件102二.任意形式的对偶问题

maxZ=3x1+4x2+6x3s.t.2x1+3x2+6x3≤440-6x1+4x2+x3≤-1005x1-3x2+x3≥200

5x1-3x2+x3≤200x1,x2,x3≥05x1-3x2+x3=200整理课件二.任意形式的对偶问题5x1-3x2+x3=200103maxZ=3x1+4x2+6x3s.t.2x1+3x2+6x3≤440-6x1+4x2+x3≤-1005x1-3x2+x3≤200-5x1+3x2-x3≤-200

x1,x2,x3≥0s.t.2y1-6y2+5y3-5y4≥33y1+4y2+3y3-3y4≥4

6y1+y2+y3-y4≥6y1,y2,y3,y4≥0minf=440y1-100y2+200y3-200y4二.任意形式的对偶问题对偶问题整理课件maxZ=3x1+4x2+6x3s.t.minf=4104原问题的对偶问题为

minf=440y1-100y2+200y3-200y4s.t.2y1-6y2+5y3-5y4≥33y1+4y2+3y3-3y4≥4

6y1+y2+y3-y4≥6y1,y2,y3,y4≥0整理课件原问题的对偶问题为整理课件105原问题的对偶问题为

minf=440y1-100y2+200(y3-y4)s.t.2y1-6y2+5(y3-y4)≥33y1+4y2+3(y3-y4)≥4

6y1+y2+(y3-y4)≥6y1,y2,y3,y4≥0整理课件原问题的对偶问题为整理课件106原问题的对偶问题为

minf=440y1-100y2+200s3s.t.2y1-6y2+5s3≥33y1+4y2+3s3≥4

6y1+y2+s3≥6y1,y2≥0,S3无非负限制整理课件原问题的对偶问题为整理课件107练习：Maxf(x)=4x1+5x2s.t.3x1+2x2≤204x1-3x2≥10

x1+x2=5x2≥0,x1正负不限整理课件练习：整理课件108练习转换：Maxf(x)=4x11-4x12+5x2s.t.3x11-3x12+2x2≤204x11-4x12-3x2≥10

x11-x12+x2=5x11,x12,x2≥0整理课件练习转换：整理课件109练习转换：Maxf(x)=4x11-4x12+5x2s.t.3x11-3x12+2x2≤204x11-4x12-3x2≥10

x11-x12+x2≥5

x11-x12+x2≤5x11,x12,x2≥0整理课件练习转换：整理课件110练习转换：Maxf(x)=4x11-4x12+5x2s.t.3x11-3x12+2x2≤20-(4x11-4x12-3x2)≤-10

-(x11-x12+x2)≤-5

x11-x12+x2≤5x11,x12,x2≥0整理课件练习转换：整理课件111练习转换：Maxf(x)=4x11-4x12+5x2s.t.3x11-3x12+2x2≤20-4x11+4x12+3x2≤-10

-x11+x12-x2≤-5

x11-x12+x2≤5x11,x12,x2≥0整理课件练习转换：整理课件112练习转换：Minf(y)=20y1-10y2-5y3+5y4s.t.

3y1-4y2-y3+y4>=4-3y1+4y2+y3-y4>=-42y1+3y2-y3+y4>=5y1,y2,y3,y4>=0整理课件练习转换：整理课件113练习转换：Minf(y)=20y1-10y2-5(y3-y4)s.t.

3y1