资源描述
第,*,页,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。,运 筹 帷 幄 之 中,决 胜 千 里 之 外,对 偶 理 论,运 筹 学 课 件,1/79,对 偶 理 论,对偶问,题,对偶理论,对偶单纯形算法,2/79,对偶问题提出,例：设某企业有,m,种资源，用于生产,n,种不一样产品，各种资源拥有量为,b,i,（,i=1,2,m,）,又知生产单位第,j,种产品（,j=1,2,n,）消费第,i,种资源,a,ij,单位，产值为,c,j,元。若用,x,j,表示第,j,种产品生产量，求产值最大，,LP,模型为：,任意线性规划问题都存在一个与之伴随对偶问题,3/79,现从,另一角度,提出问题：假设此企业拥有资源但未生产，而另一企业预将上述企业拥有资源买过来，最少应付出多少代价，才能使前一企业愿意放弃生产活动，出让资源。,若设,y,i,表示收买该企业一单位,i,种资源时付出代价。则另一线性规划问题为：,收买企业付出代价是该商品价格吗？若不是，它和原本价格是什么关系？,收购资源企业能盈利吗,?,怎么赚？,4/79,原问题与对偶问题对应关系,原问题（,L,）,一,一,对,应,对偶问题（,D,）,max,问题,min,问题,有,m,个约束条件,有,m,个变量,第,j,个约束条件为关系,第,j,个变量,0,第,j,个约束条件为关系,第,j,个变量,0,第,j,个约束条件为等式关系,第,j,个变量无非负约束，自由变量,第,j,个变量,0,第,j,个约束条件为关系,第,j,个变量,0,第,j,个约束条件为关系,第,j,个变量无非负约束，自由变量,第,j,个约束条件为关系,资源向量,价值向量,价值向量,资源向量,5/79,实 例,6/79,对偶问题基本性质,以下各性质基于以下假设,原问题,对偶问题,7/79,若,是原问题可行解，,是其对偶问题可行解，则恒有,证实,性质,1,（弱对偶性）,8/79,若,是原问题可行解，,是其对偶问题可行解，且有,则,是原问题最优解，,是其对偶问题最优解。,性质,2,（最优性）,9/79,性 质,2,证 明,又因为,则,10/79,性质,3,（无界性）：,若原问题（对偶问题）有没有界解，则其对偶问题（原问题）无可行解。,性质,4,（强对偶性，对偶定理）：,若原问题有最优解，则其对偶问题也一定有最优解，且,max z=min w,。,11/79,在线性规划问题最优解中，若对应某一约束条件对偶变量值为非零，则该约束条件取严格等式；反之若约束条件取严格不等式，则其对应对偶变量一定为零。即,（,另外说法）,：,分别是原问题和对偶问题,可行解，则,为最优解充分必要条件是,性质,5,（互补松弛性）,12/79,性 质,5,证 明,化原问题和对偶问题为标准形式,原问题,对偶问题,13/79,若,则,则,为最优解,.,为最优解,.,则,所以,14/79,Min,=2,x,1,3,x,2,5,x,3,2,x,4,3,x,5,原问题（,L,）,x,1,x,2,2,x,3,x,4,3,x,5,4,2,x,1,x,2,3,x,3,x,4,x,5,3,x,j,0,j,=1,2,5,Max z=4,y,1,3,y,2,对偶问题（,D,）,y,1,2,y,2,2,y,1,y,2,3,2,y,1,3,y,2,5,y,1,y,2,2,3,y,1,y,2,3,y,1,y,2,0,15/79,对偶问题（,D,）,原问题（,L,）,第,1,个约束,y,1,*,2,y,2,*,=2,第,1,个变量,x,1*0,第,2,个约束,y,1,*,y,2,*,3,第,2,个变量,x,2*=0,第,3,个约束,2,y,1,*,3,y,2,*,5,第,3,个变量,x,3*=0,第,4,个约束,y,1,*,y,2,*,2,第,4,个变量,x,4*=0,第,5,个约束,3,y,1,*,y,2,*,=3,第,5,个变量,x,5*0,第,1,个变量,y,1,*,0,第,1,个约束,x,1,*,x,2,*,2,x,3,*,x,4,*,3,x,5,*,=4,第,2,个变量,y,2,*,0,第,2,个约束,2,x,1,*,x,2,*,3,x,3,*,x,4,*,x,5,*,=3,16/79,设原问题和对偶问题为,原问题,对偶问题,性质,6,（变量对应关系）,则，原问题单纯形表检验数行对应其对偶问题一个基解。（对应关系见表）,17/79,补充：单纯形法矩阵描述,考虑问题,引入松弛变量,得,18/79,设,B,是一个,可行基,，若,则对应于,B,变量向量,则,同时将,C,也分成两块,所以,有,19/79,所以，,LP,问题写成,将（,2,）移项后得,将（,3,）左乘,将（,4,）代入目标（,1,）得,20/79,21/79,性 质,6,证 明,设,B,是原问题一个可行基，所以,对应对偶问题为,22/79,若求得原问题以解,检验数为,和,令,将它代入（*）,(*),得,23/79,最优单纯形表,原问题,L,对偶问题,D,原问题L普通形式,Max Z=2x13x2,x12x28,4x1 16,4x212,x1,x2 0,原问题,L,标准形,Max Z=2,x,1,3,x,2,x,1,2,x,2,x,3,=8,4,x,1,x,4,=16,4,x,2,x,5,=12,x,1,x,2,x,3,x,4,x,5,0,x,3,x,4,x,5,是松弛变量,Min,=8,y,1,16,y,2,12,y,3,y,1,4,y,2,2,2,y,1,4,y,3,4,y,1,y,2,y,3,0,对偶问题D最优解：,y1*=3/2,y2*=1/8,y3*=0,24/79,25/79,影子价格随详细情况而异：在完全市场经济条件下，当某种资源市场价格低于影子价格时，企业应该买进该资源用于扩大生产；当,某种资源市场价格高于影子价格时，企业应该把该资源卖掉。所以，影子价格含有市场调整作用。,26/79,27/79,28/79,29/79,对偶单纯形算法,基本思想,算法过程,算例,30/79,原问题,对偶问题,31/79,基 本 思 想,32/79,单 纯 形 算 法,33/79,对 偶 单 纯 形,34/79,35/79,算 例,36/79,c,j,-15,-24,-5,0,0,c,B,x,B,b,y,1,y,2,y,3,y,4,y,5,0,y,4,-2,0,-6,-1,1,0,0,y,5,-1,-5,-2,-1,0,1,C,j,-z,j,-15,-24,-5,0,0,-24,y,2,1/3,0,1,1/6,-1/6,0,0,y,5,-1/3,-5,0,-2/3,-1/3,1,C,j,-z,j,-15,0,-1,-4,0,-24,y,2,1/4,-5/4,1,0,-1/4,1/4,-5,y,3,1/2,15/2,0,1,1/2,-3/2,C,j,-z,j,-15/2,0,0,-7/2,-3/2,37/79,例：用对偶单纯形法求解,解：将问题化为下式，以得到对偶问题初始可行基,38/79,c,j,-2,-3,-4,0,0,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,0,x,4,-3,-1,-2,-1,1,0,0,x,5,-4,-2,1,-3,0,1,C,j,-z,j,-2,-3,-4,0,0,0,x,4,-1,0,-5/2,1/2,1,-1/2,-2,x,1,2,1,-1/2,3/2,0,-1/2,C,j,-z,j,0,-4,-1,0,-1,-3,x,2,2/5,0,1,-1/5,-2/5,1/5,-2,x,1,11/5,1,0,7/5,-1/5,-2/5,C,j,-z,j,0,0,-3/5,-8/5,-1/5,39/79,否,算 法 框 图,初始正则解,检验可行,是则停顿,得最优解,选出基变量,检验,是否无可,行解,是则停顿,否,无最优解,选入基变量,计算检验数,40/79,灵敏度分析,41/79,灵敏度分析研究问题,42/79,单纯行表中基位置,：,为清楚起见，把新单纯行表中基对应初始单纯行表中那些向量抽出来单独列一块，记为,B,，初始单纯行表为：,初始解,非基变量,基变量,b,B N,00,43/79,单纯行法迭代过程实际上是对约束方程系数矩阵实施行初等变换，由线代知道，对矩阵,基可行解,基变量,非基变量,00,实施行初等变换时，当,B,变为,I,时，,I,将变为,则，上述矩阵将变为,新单纯行表写为：,44/79,灵敏度分析步骤：,1,。将参数改变计算反应到最终单纯形表上：,详细方法是，按以下公式计算由参数,改变而引发最终单纯形表上相关数字改变：,45/79,2,。检验原问题是否仍为可行解；,3,。检验对偶问题是否仍为可行解；,4,。按下表所列情况得出结论和决定继续计算步骤：,原问题,对偶问题,结论（继续计算步骤）,可行解,可行解,非可行解,非可行解,可行解,非可行解,可行解,非可行解,仍为问题最优解,单纯形法继续求最优解,对偶单纯形法继续求最优解,引入人工变量，用新表计算,46/79,将,c,j,改变反应到最终单纯形表上,只能出现上页表中所表示前两种情形。,47/79,例：已知,LP,问题,用单纯形法求解得最终单纯形表以下：,48/79,c,j,2,1,0,0,0,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,15/2,0,0,1,5/4,-15/2,2,x,1,7/2,1,0,0,1/4,-1/2,1,x,2,3/2,0,1,0,-1/4,3/2,C,j,-z,j,0,0,0,-1/4,-1/2,（表,1,）,试确定：,a,）当目标函数变为,最优解会怎样改变；,b,）当目标函数变为,求,改变范围，使最优,解不变。,49/79,a),将,c,j,改变反应到最终单纯形表（,1,）上,得表（,2,）,c,j,5,1.5,0,0,0,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,15/2,0,0,1,5/4,-15/2,5,x,1,7/2,1,0,0,1/4,-1/2,1.5,x,2,3/2,0,1,0,-1/4,3/2,C,j,-z,j,0,0,0,-7/8,1/4,（表,2,）,表（,2,）中变量,x,5,检验数为正，继续迭代得表（,3,）,50/79,c,j,5,1.5,0,0,0,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,15,0,5,1,0,0,5,x,1,4,1,1/3,0,1/6,0,0,x,5,1,0,2/3,0,-1/6,1,C,j,-z,j,0,-1/6,0,-5/6,0,（表,3,）,即新解为,b),将,c,j,改变反应到最终单纯形表（,1,）上,得表（,4,）,51/79,c,j,2,1,0,0,0,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,15/2,0,0,1,5/4,-15/2,2,x,1,7/2,1,0,0,1/4,-1/2,1,x,2,3/2,0,1,0,-1/4,3/2,C,j,-z,j,0,0,0,-1/4-,1/4,-1/2+,1/2,（表,4,）,52/79,二、分析,b,i,改变影响,b,i,改变在实际问题中表明可用资源数量发生改变，将,b,i,改变反应到最终单纯形表上,只引发基变量列数字改变。所以灵敏度分析步骤为：,1,）按公式,算出,将其加到基变量列数字上；,2,）因为其对偶问题仍为可行解，故只需检验原问题是否为可行解。,例：上例中：,a,）当第二个约束条件右端项增大到,32,最优解会怎样改变；,b,）当第二个约束条件变为,求,改变范围，使表中基为最优基,53/79,解：,a,）,将其加到表（,1,）最终单纯形表基变量,b,这一列数字上得表（,5,）,54/79,c,j,2,1,0,0,0,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,35/2,0,0,1,5/4,-15/2,2,x,1,11/2,1,0,0,1/4,-1/2,1,x,2,-1/2,0,1,0,-1/4,3/2,C,j,-z,j,0,0,0,-1/4,-1/2,（表,5,）,表（,5,）中原问题为非可行解，故用对偶单纯形法继续计算得表（,6,）,55/79,c,j,2,1,0,0,0,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,15,0,5,1,0,0,2,x,1,5,1,1,0,0,1,0,x,4,2,0,4,0,1,6,C,j,-z,j,0,1,0,0,-2,（表,6,）,即新解为,56/79,解：,b,）,将其加到表（,1,）最终单纯形表基变量,b,这一列数字上得表（,7,）,57/79,c,j,2,1,0,0,0,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,(15/2)+,5/4,0,0,1,5/4,-15/2,2,x,1,(7/2)+,1/4,1,0,0,1/4,-1/2,1,x,2,(3/2)-,1/4,0,1,0,-1/4,3/2,C,j,-z,j,0,0,0,-1/4,-1/2,（表,7,）,58/79,表中基为最优基条件为：,所以有：,59/79,三、增加一个变量分析,增加一个变量在实际问题中表明增加一个新产品。灵敏度分析步骤为：,1,）计算,2,）计算,3,）若,只需将,和,值直接反应到最终,单纯形表中，原最优解不变，若,则按单纯形表继续迭代计算。,60/79,例：在前例中，若增加一个变量,x,6,，有,试分析最优解改变。,解：,将其反应到表（,1,）最终单纯形表中，得表（,8,）,61/79,c,j,2,1,0,0,0,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,15/2,0,0,1,5/4,-15/2,2,x,1,7/2,1,0,0,1/4,-1/2,1,x,2,3/2,0,1,0,-1/4,3/2,C,j,-z,j,0,0,0,-1/4,-1/2,（表,8,）,3,x,6,-7,0,2,1,所以，用单纯形法继续计算，得表（,9,）,62/79,c,j,2,1,0,0,0,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,5/4,0,7/2,1,3/8,-9/4,2,x,1,7/2,1,0,0,1/4,-1/2,3,x,6,3/4,0,1/2,0,-1/8,3/4,C,j,-z,j,0,-1/2,0,-1/8,-5/4,3,x,6,0,0,1,0,（表,9,）,即新解为,63/79,四、分析,a,ij,改变影响,假如,x,j,在最终表中为基变量，则,a,ij,改变将使最终表中,B,-1,改变，所以，有可能出现原问题与对偶问题均为非可行解情况。,例：在前例中，若,x,2,系数向量,p,2,变为,试分析最优解改变,。,64/79,解：,先将其作为一个新变量,x,2,/,列入最终单纯形表中，得表（,10,）,65/79,c,j,2,1,3,0,0,c,B,x,B,b,x,1,x,2,X,/,2,x,3,x,4,0,x,3,15/2,0,0,11/2,1,5/4,2,x,1,7/2,1,0,1/2,0,1/4,1,x,2,3/2,0,1,-1/2,0,-1/4,C,j,-z,j,0,0,3/2,0,-1/4,0,x,5,-15/2,-1/2,3/2,-1/2,（表,10,）,因,x,2,已改变为,x,/,2,，故用单纯形法算法将,x,/,2,替换出基变量中,x,2,，并在下一个表中不再保留,x,2,，得表（,11,）,66/79,c,j,2,3,0,0,0,c,B,x,B,b,x,1,x,/,2,X,3,x,4,x,5,0,x,3,-9,0,0,1,4,-24,2,x,1,2,1,0,0,1/2,-2,3,x,/,2,3,0,1,0,-1/2,3,C,j,-z,j,0,0,0,1/2,-5,（表,11,）,因表（,11,）中原问题与其对偶问题均为非可行解，所以经过引入人工变量，将原问题转化为可行解，再用单纯形法继续计算。,67/79,表（,11,）第一行可写成,因为，右端项为负值，故先将等式两端乘“,1”,，再加上人工变量,x,6,，得,将上式替换表（,11,）第一行，得表（,12,）,c,j,2,3,0,0,0,c,B,x,B,b,x,1,x,/,2,X,3,x,4,x,5,-M,x,6,9,0,0,-1,-4,-24,2,x,1,2,1,0,0,1/2,-2,3,x,/,2,3,0,1,0,-1/2,3,C,j,-z,j,0,0,-M,-4M+1/2,-5+24M,（表,12,）,-M,x,6,1,0,0,0,用单纯形法迭代，得表（,13,）,68/79,c,j,2,3,0,0,0,c,B,x,B,b,x,1,x,/,2,X,3,x,4,x,5,0,x,5,3/8,0,0,-1/24,-1/6,1,2,x,1,11/4,1,0,-1/12,1/3,0,3,x,/,2,15/8,0,1,1/8,0,0,C,j,-z,j,0,0,-5/24,-2/3,0,（表,13,）,-M,x,6,1/24,1/12,-1/8,-M+5/24,即新解为,69/79,五、增加一个约束条件分析,增加一个约束条件，在实际问题中相当于增添一道工序。分析方法是先将原问题最优解变量取值代入这个新增约束条件中，如满足，说明新增约束未起到限制作用，原最优解不变。不然，将新增约束直接反应到最终单纯形表中，再进行分析。,70/79,例：前例中增添一个约束条件,试分析最优解改变。,解：先将原问题最优解变量值代入，因为有,故，将约束条件写成,，并取,x,6,71/79,为基变量，直接反应到最终单纯形表中，得表（,14,）,c,j,2,1,0,0,0,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,15/2,0,0,1,5/4,-15/2,2,x,1,7/2,1,0,0,1/4,-1/2,1,x,2,3/2,0,1,0,-1/4,3/2,C,j,-z,j,0,0,0,-1/4,-1/2,（表,14,）,0,x,6,0,0,0,1,0,x,6,12,3,2,0,0,0,0,迭代，得表（,15,）,72/79,c,j,2,1,0,0,0,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,15/2,0,0,1,5/4,-15/2,2,x,1,7/2,1,0,0,1/4,-1/2,1,x,2,3/2,0,1,0,-1/4,3/2,C,j,-z,j,0,0,0,-1/4,-1/2,（表,15,）,0,x,6,0,0,0,1,0,x,6,-3/2,0,0,0,-1/4,-3/2,0,为使,x,1,x,2,列系数变换为单位向量，对表（,14,）进行行变换，表（,15,）中,1,，,2,，,3,行同表（,14,）中,1,，,2,，,3,行不变，表（,15,）中第,4,行由初等行变换“,4,行,32,行,23,行”得到，用对偶单纯形法计算，得表（,16,）,73/79,c,j,2,1,0,0,0,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,0,x,3,15,0,0,1,5/2,0,2,x,1,4,1,0,0,1/3,0,1,x,2,0,0,1,0,-1/2,0,C,j,-z,j,0,0,0,-1/6,0,（表,16,）,0,x,6,-5,-1/3,1,-2/3,0,x,5,1,0,0,0,1/6,1,-1/3,即新解为,74/79,作业,75/79,1.,已知线性规划问题：,要求,：,a),写出对偶问题，,b),已知原问题最有解,X,*=(2,2,4,0),用互补松弛性求出对偶问题最优解。,76/79,2,。已知线性规划问题,及最终单纯形表,77/79,c,j,3,2,0,0,0,0,c,B,x,B,b,x,1,x,2,x,3,x,4,x,5,x,6,2,x,2,4/3,0,1,2/3,-1/3,0,0,3,x,1,10/3,1,0,-1/3,2/3,0,0,0,x,5,3,0,0,-1,1,1,0,0,x,6,2/3,0,0,-2/3,1/3,0,1,c,j,z,j,0,0,-1/3,-4/3,0,0,表,1,78/79,分析以下各种条件单独改变时，最优解将怎样改变。,（,a,）第,1,，,2,个约束条件后端项分别由,6,变,7,，,8,变,4,；,（,b,）目标函数变为,;,（,c,）增加一个变量 ，系数为,（,d,）问题中变量 系数变为,（,e,）增加一个新约束,79/79,
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
