运筹学第二章电子讲稿1

第二章对偶理论与灵敏度分析§1.单纯形表的矩阵描述maxΖ=CXs.t.AX=bX0A=[B,N],C=(CB,CN),X=则有maxΖ=CBXB+CNXNx.t.BXB+NXN=bXB,XN≥0XB=B-1b-B-1NXNΖ=CB(B-1b-B-1NXN)+CNXN=CBB-1b+(CN-CBB-1N)XNXBXN单纯形表XBXNXSB-1bIB-1NB-1-CBB-1b0CN-CBB-1N-CBB-1§3.对偶问题的提出原问题：有n种食物，每种食物含有m种营养成分，第j种食物每个单位含第i种营养成分为aij单位。现知每人每天需要第i种营养成分为bi单位，第种食物的单价为cj。试问一个消费者如何选购食物，才能使得既满足需要，又花费最小？问题归结为minCXs.t.AX≥bX≥0xj—选购第j种食物的数量（单位）对偶问题：设有一个制造商，要生产m种不同的药丸来代替上述n种不同的食物。试问每种药丸的价格如何确定，才能获利最大？设第i种药丸的价格为yi，为了达到畅销的目的，药丸的价格当然不能超过与之相当的食品价格，于是，问题变成：maxYbYA≤CY≥0§4.线性规划的对偶理论4.1.原问题与对偶问题的关系(P)maxΖ=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…a1nxn≤b1a21x1+a22x2+…a2nxn≤b2┆┆┆┆┆am1x1+am2x2+…amnxn≤bmxj≥0,j=1,2,…,nminω=b1y1+b2y2+…+bmyms.t.a11y1+a21y2+…+am1ym≥c1a12y1+a22y2+…+am2ym≥c2┆┆┆┆┆a1ny1+a2ny2+…+amnym≥cnyi≥0,i=1,2,…,m(D)对偶问题原问题用矩阵表示为：(P)maxΖ=CX(D)minω=YbAX≤bYA≥CX≥0Y≥0x1x2…xny1a11a12…a1nb1y2a21a22…a2nb2┆┆┆┆┆ymam1am2…amnbmc1c2…cn例写出下面问题的对偶问题maxΖ=8x1+9x2s.t.4x1+x2≤52x1+3x2≤6x1,x2≥0对偶问题是：minω=5y1+6y2s.t.4y1+2y2≥8y1+3y2≥9y1,y2≥0maxmin≤对于标准形式的线性规划问题maxΖ=CXs.t.AX=bX≥0其对偶问题是minω=Ybs.t.YA≤CY无非负约束[证]标准形式的线性规划问题可以写为maxΖ=CXs.t.AX≤b-AX≤-bX≥0其对偶问题为minω=Y’b-Y”bs.t.Y’A-Y”A≥CY’,Y”≥0令Y=Y’-Y”，则上述问题变为minω=Ybs.t.YA≥0Y没有限制例maxΖ=2x1+x2+3x3+x4s.t.x1+x2+x3+x4≤52x1-x2+3x3=-4x1-x3+x4≥1x1,x3≥0,x2,x4无约束其对偶问题为minω=5y1+4y2-y3s.t.y1-2y2-y3≥2y1+y2=14.2.对偶问题的基本性质1.对称性：对偶问题的对偶问题是原问题。2.弱对偶性：若X和Ŷ分别为(P)，(D)的可行解，则有Ζ=CX≤Ŷb=ω3.无界性：若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解。4.可行解是最优解的性质：若X,Ŷ分别是问题(P),(D)的可行解。并且CX=Ŷb，则X,Ŷ分别为(P),(D)的最优解。^^^^^5.对偶定理：若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等。6.互补松驰性(松紧定理)：若X，Ŷ分别是(P),(D)问题的可行解，那么X,Ŷ为最优解的充要条件是：ŶXS=0,YSX=0(即若AiXbi=Ŷi=0AiX=bi=Ŷi0ŶPj=Cj=Xj0ŶPjCj=Xj=0)^^^^^^^例1.求解下列线性规划问题maxΖ=x1+2x2+3x3+4x4s.t.x1+2x2+2x3+3x4≤202x1+x2+3x3+2x4≤20xj≥0,j=1,2,3,4[解]其对偶问题为minω=20y1+20y2s.t.y1+2y2≥12y1+y2≥22y1+3y2≥33y1+2y2≥4y1,y2≥0(1.2,0.2)1212..y1y2用图解法得最优解y1=1.2,y2=0.2根据松紧定理，原问题的最优解必满足ŶXS=0及YSX=0^及(y3,y4,y5,y6)=0x5(y1,y2)x6=0x1x2x3x4将y1=1.2,y2=0.2代入对偶问题的约束条件，得y3≠0,y4≠0,所以x1=x2=0又因y10,y20。所以x5=x6=0，即原问题为等式约束x1=x2=0x1+2x2+2x3+3x4=202x1+x2+3x3+2x4=20即x1=x2=0，x3=4,x4=4∴原问题的最优解为(0,0,4,4)T7.原问题单纯形表的检验数行对应其对偶问题的一个基解.其对应关系见表：XBXNXS0CN-CBB-1N-CBB-1YS1–YS2-YYS1为对应原问题中基变量XB的剩余变量，YS2是对应原问题中非基变量XN的剩余变量。设B是原问题的一个基本可行基，则A=(B,N)maxΖ=CBXB+CNXNBXB+NXN+XS=bXB,XN,XS≥0相应地对偶问题可表示为minω=YbYB-YS1=CBYN-YS2=CNY,YS1,YS2≥0令Y=CBB-1，则YS1=0-YS2=CN-CBB-1N例1.maxΖ=x1+4x2+3x3s.t.2x1+2x2+x3≤4x1+2x2+2x3≤6xj≥0对偶问题为minω=4y1+6y2s.t.2y1+y2≥12y1+2y2≥4y1+2y2≥3y1,y2≥0初始单纯形表为422110612201014300对偶问题的基本解为y1=0,y2=0，ys1=-1，ys2=-4，ys3=-3其最终表为13/2101-1/22–101–11-10–200–1-1由原问题的最终表可知，y1=1,y2=1(最优解)，ys1=2§5.对偶问题的经济解释——影子价格设B是最优基，则目标函数的最优值是Ζ*=CBB-1b=Y*b**Ybzyi*的经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数最优值的变化。影子价格：在其它数据不变的条件下，一个约束右边的项增加一个单位，目标函数最优值的变化，称为与这个约束相联系的影子价格。在完全市场经济的条件下，当某种资源的市价低于影子价格，企业应买进资源用于扩大生产；而当某种资源的市价高于企业影子价格时，则企业的决策者应把已有资源卖掉，因此影子价格有调节市场的作用。例某工厂以一种贵重金属为原料生产两种产品，两种产品都必须经过粗加工和精加工两道工序，生产每件A产品需粗加工1小时，精加工2小时，需贵金属3克，出厂价60元，生产B产品需粗加工7小时，精加工4小时，需贵金属2克，出厂价70元。在一个生产周期中，按该厂的设备和人员，粗加工能力为140，000小时，精加工能力为100，000小时，由计划渠道供应的贵金属只有120公斤。每个粗加工工时的成本计为1.5元，精加工工时为2.5元，每克贵金属成本为10元。因本厂的工人工资和设备折旧在同一个生产周期内是固定的，所以不论产品多少，都以其最大加工能力的工时计入成本，而贵金属按实际使用量计入成本。如设A、B产品分别生产x1和x2千件，则利润可按下式计算（单位：万元）S=6x1+7x2-[（3x1+2x2）+（141.5+102.5)]=3x1+5x2-46使得毛利最大的生产计划即为如下线性规划的最优解：maxS1=3x1+5x2（S1=S-46）s.t.x1+7x2140(粗加工能力约束）2x1+4x2100（精加工能力约束）3x1+2x2120（贵金属用量约束）x1，x20用单纯形法求解可得如下最优表：XBbx1x2x3x4x5x27.50100.375-0.25x135100-0.250.5x352.5001-2.3351.25142.5000-1.125-0.25由松驰变量的检验数可知：粗加工能力的影子价格为0；精加工能力的影子价格为1.125，单位是万元/千小时；贵金属的影子价格为0.25万元/公斤。§6.对偶单纯形法对偶单纯形法的思想是：使对偶问题保持可行，而使原问题从非可行的基本解，逐步达到基本可行解，这样就得到了两个问题的最优解。计算步骤：(1)列出初始单纯形表，检验b列数字，若其全部非负且检验数j≤0，则已得到最优解，停止；若列中至少有一个负分量，且j≤0,转(2)(2)按min(B-1b)i(B-1b)i0=(B-1b)l确定换出变量xl；(3)确定换入变量若xl所在行的各系数alj≥0(j=1,2,…,n),则无可行解，停止；若alj0，则计算θ=minj/aljalj0=k/alkxk为换入变量。(保持对偶问题的可行性)(4)以alk为主元素，按单纯形法在表中进行迭代运算，得新的表.转(1)例.minΖ=3x1+4x2+5x3s.t.x1+2x2+3x3≥52x1+2x2+x3≥6x1,x2,x3≥0[解]引进松驰变量，问题化为minΖ=3x1+4x2+5x3s.t.x1+2x2+3x3-x4=52x1+2x2+x3-x5=6x1,x2,x3,x4,x5≥0XBbx1x2x3x4x5x4–5–1–2–310x5–6–2–2–101–3–4–500x4–20–1–5/21–1/2x13111/20–1/20–1-7/20–3/2x22015/2-11/2x1110–21–100–1–1–1所以最优解为x1=1,x2=2,x3=0，Ζmin=11§7.灵敏度分析问题：①当aij,bi,cj中的一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化？②这些系数在什么范围变化时，线性规划问题的最优解或最优基不变？可按下表中的几种情况处理：原问题对偶问题结论或继续计算的步骤可行解可行解表中的解仍为最优解可行解可行解用单纯形法继续迭代求最优解非可行解可行解用对偶单纯形法继续迭代求最优解非可行解非可行解引入人工变量，编制新的单纯形表求最优解7.1资源数量变化的分析资源数量变化是指系数br发生变化，其它参数不变。原最优解为b*=B-1bbr的变化仅引起最优解的变化XB’=B-1b’=B-1(b+Δb)=B-1=B-1+B-1=B-1b+B-1若要所得的基还是最优基，必须XB’≥0，而其若大于零，则得到的解必为最优解。b1b100┆┆┆┆br+ΔbrbrΔbrΔbr┆┆┆┆bmbm000┆br┆00a1rΔbra1r┆┆┆B-1Δbr=airΔbr=Δbrair┆┆┆0amrΔbramrB-1的第r列元素要XB’≥0,即要b*+B-1≥0即bi+Δbrair≥0Δbr≥-bi/air若air0Δbr≤-bi/air若air0max{-bi/airair0}≤Δbr≤min{–bi/airair0}例.线性规划问题maxΖ=-x2+3x2-2x5s.t.x1+3x2-x3+2x5=7-2x2+4x3+x4=12-4x2+3x3+8x5+x6=10xj≥0XBbx1x2x3x4x5x6x1713–1020x4120–24100x6100–43081-1030–20最终表是XBbx1x2x3x4x5x6x245/2101/104/50x351/5013/102/50x611100–1/2101-1/500–4/5–12/50B=[P2,P3,P6]5/21/100B-1=1/53/1001-1/21求b2的变动范围1/10B-12列=3/10-1/2max{-4/(1/10),-5/(3/10)}≤Δb2≤min{-11/((-1/2)}-50/3≤Δb2≤22要保持最优基不变，则-14/3≤b2≤34若Δb2超出此范围，则b0可用对偶单纯形法继续求解例上题中，若令b2增加Δb2=30,则5/21/10003B-1Δb=1/53/10030=91–1/210-15将上式结果反映到最终表中，得下表XBbx1x2x3x4x5x6x24+35/2101/104/50x35+41/501