第二章 线性规划进一步研究

第二章线性规划进一步研究第一节对偶问题(DualProblem)线性规划早期发展过程中的最为重要的理论成果之一就是线性规划的对偶问题及相关理论的提出。线性规划的对偶理论解释资源的影子价格、线性规划问题的灵敏度分析等的理论基础。一、对偶问题的提出–例1（生产计划问题）某企业利用A、B、C三种资源，在计划期内生产甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？产品资源甲乙资源限制ABC120111300kg400kg250kg单位产品利润(元/件)50100•决策变量：x1、x2——分别代表甲、乙两种产品的生产数量。–即有数学模型（问题A）：问题Amaxz=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1、x2≥0–称之为上述问题的数学模型。•同样是上述问题，提问：企业不安排生产，而转让三种资源，应如何给三种资源定价？–决策变量：y1、y2、y3——分别代表A、B、C三种资源的价格（最低转让净收入）。–约束条件1：生产一件产品甲所耗资源数量转让所得净收入不能低于一件产品甲所获利润，即：1y1+2y2≥50–约束条件2：生产一件产品乙所耗资源数量转让所得净收入不能低于一件产品乙所获利润，即：1y1+1y2+1y3≥100–目标函数为：w=300y1+400y2+250y3–即有w=300y1+400y2+250y3y1+2y2≥50y1+y2+y3≥100y1、y2、y3≥0–从数学和经济的角度分析，该问题的目标函数只能极小，即该问题的数学模型为：–问题Bminw=300y1+400y2+250y3y1+2y2≥50y1+y2+y3≥100y1、y2、y3≥0–称问题B为问题A的对偶问题，问题A为原问题。–问题Amaxz=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1、x2≥0定义2.1设有线性规划问题maxz=CXAX≤bX≥0•其对偶问题定义为minw=YbYA≥CY≥0•且前者称为原问题，后者称为对偶问题。二、对偶问题的定义具体的数量对应关系为•原问题maxz=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2…………………………am1x1+am2x2+…+amnxn≤bmx1，x2，…，xn≥0•对偶问题minw=b1y1+b2y2+…+bmyma11y1+a21y2+…+am1ym≥c1a12y1+a22y2+…+am2ym≥c2…………………………a1ny1+a2ny2+…+amnym≥cny1，y2，…，ym≥0•根据对偶问题的定义不难推出，对于线性规划问题：minw=Yb；YA≥C；Y≥0•其对偶问题为：maxz=CX；AX≤b；X≥0•即两线性规划问题互为对偶。•事实上，任一线性规划问题都有一个固定的线性规划问题与之对偶，且二者互为对偶关系，线性规划的这种性质称为对称性。•更进一步有，对于线性规划问题：maxz=CX；AX=b，X≥0•其对偶问题为：minw=Yb；YA≥C，Y无限制–根据以上分析，线性规划原问题与对偶问题的数量关系可用下表描述。原问题（或对偶问题）对偶问题（或原问题）目标函数maxzminw目标函数变量n个≥0≤0无约束n个≥≤=约束条件约束条件m个≤≥=m个≥0≤0无约束变量约束条件右端常数项目标函数变量系数目标函数变量系数约束条件右端常数项•例2.1写出下列线性规划问题的对偶问题maxz=2x1+2x2－4x3x1+3x2+3x3≤304x1+2x2+4x3≤80x1、x2，x3≥0解：其对偶问题为minw=30y1+80y2y1+4y2≥23y1+2y2≥23y1+4y2≥－4y1、y2≥0•例2.2写出下列线性规划问题的对偶问题minz=2x1+8x2－4x3x1+3x2－3x3≥30－x1+5x2+4x3=804x1+2x2－4x3≤50x1≤0、x2≥0，x3无限制•解：其对偶问题为maxw=30y1+80y2+50y3y1－y2+4y3≥23y1+5y2+2y3≤8－3y1+4y2－4y3=－4y1≥0，y2无限制，y3≤0一、单纯形法的矩阵描述设有线性规划问题maxz=CXAX≤bX≥0加上松弛变量XS=（xn+1，xn+2，…，xn+m）T，将其化为标准形式得到maxz=CX+0XSAX+IXS=bX≥0，XS≥0其中I为m×m阶单位阵。第二节对偶理论(DualityTheory)–设A中存在一可行基B，相应的变量X分成基变量XB和非基变量XN，价格系数C也相应地分成CB和CN两部分，A阵也分成B、N两部分，即A=（B，N），X=（XB，XN）T，C=（CB，CN）–这样–因而有BXB+NXN+IXS=b–即XB=B-1b－B-1NXN－B-1XS–用非基变量XN表示目标函数有=CBXB+CNXN+0XSBNBNSSSXX(A,I)=(B,N,I)X=BX+NX+IXXXBSBNSNXz=CX+0X=(C,C)+0XX–将XB=B-1b－B-1NXN－B-1XS代入得z=CB（B-1b－B-1NXN－B-1XS）+CNXN+0XS=CBB-1b+（CN－CBB-1N）XN－CBB-1XS–令XN=0，XS=0–得到对应于基B的基可行解X=（XB，XX，XS）T=（B-1b，0，0）T–目标值为z=CBB-1b–相应的非基变量的检验数为σN=（CN－CBB-1N，CBB-1）–若将基变量一起考虑有σ=（0，CN－CBB-1N，CBB-1）=（C－CBB-1A，CBB-1）–此外，从上式中可推出计算某一具体变量xj的检验数计算公式，即σj=cj－CBB-1pj–由最优性判别定理可知，当σ=（C－CBB-1A，CBB-1）≤0时，X=（XB，XX，XS）T=（B-1b，0，0）T为线性规划的最优解；若存在σj=cj－CBB-1pj0，（j∈J），有B-1pj≤0，则线性规划问题有无界解。CCBCN0bCBXBXBXNXSCBXBIB-1NB-1B-1b－z0CN－CBB-1N-CBB-1-CBB-1b上述过程可用如下单纯形表描述。定理2.1(弱对偶定理)设X(0)是原问题maxz=CX，AX≤b，X≥0的可行解Y(0)是其对偶问题minw=Yb，YA≥C，Y≥0的可行解则CX（0）≤Y（0）b。–原问题任一可行解对应的目标函数值不大于其对偶问题的任一可行解对应目标函数值???二、对偶问题基本定理定理2.2(最优性定理)设X(0)是原问题maxz=CX，AX≤b，X≥0的可行解，Y（0）是其对偶问题minw=Yb，YA≥C，Y≥0的可行,若CX（0）=Y（0）b，则X（0）、Y（0）分别是它们的最优解。定理2.3(对偶定理)若原问题maxz=CX，AX≤b，X≥0有最优解，则其对偶问题minw=Yb，YA≥C，Y≥0一定有最优解，且二者的目标函数值相等。定理2.4(互补松弛定理)原问题maxz=CX，AX≤b，X≥0及其对偶问题minw=Yb，YA≥C，Y≥0的可行解X（0）、Y（0）是最优解的充要条件是Y（0）XS=0；YSX（0）=0其中，XS、YS分别是原问题松弛变量向量和对偶问题剩余变量向量。–例2.3已知线性规划问题maxz=x1+2x2+3x3+4x4x1+2x2+2x3+3x4≤202x1+x2+3x3+2x4≤20x1、x2，x3，x4≥0–解：其对偶问题为minw=20y1+20y2y1+2y2≥1（1）2y1+y2≥2（2）2y1+3y2≥3（3）3y1+2y2≥4（4）y1、y2≥02x3*+3x4*=203x3*+2x4*=20解得x3*=x4*=4。故原问题的最优解为X*=（0，0，4，4）T其对偶问题的最优解为y1*=6/5，y2*=1/5。试用互补松弛定理求该线性规划问题的最优解。将y1*=6/5，y2*=1/5代入上述约束条件，得（1）、（2）为严格不等式；由互补松弛定理可以推得x1*=0，x2*=0。又因y1*0，y2*0，故原问题的两个约束条件应取等式，所以–定理2.5原问题单纯形表的检验数行对应对偶问题的一个基本解。–该定理的进一步解释有：若原问题最优解存在，则原问题最优单纯形表的检验数行中，松弛变量或剩余变量的检验数对应对偶问题的最优解。–例2.4（原问题为极大化问题）–对于原问题：maxz=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1、x2≥0–其对偶问题为：minw=300y1+400y2+250y3y1+2y2≥50y1+y2+y3≥100y1、y2、y3≥0表中x3、x4、x5为松弛变量；–原问题最优解为：X*=（500，250）T，z*=27500–对偶问题的最优解为：Y*=（y1*，y2*，y3*）=（50，0，50），w*=27500Cj50100000bCBXBx1x2x3x4x550x11010-15000x400-21150100x2010-01250－z0050050-27500对偶问题最优解－y1*－y2*－y3*–解原问题最优单纯形表如表所示，对应的对偶问题最优解列于表中最后一行。–例2.5（原问题为极小化问题）–对于原问题：minz=2x1+3x2x1+x2≥350x1≥1252x1+x2≤600x1、x2≥0–其对偶问题为：maxw=350y1+125y2+600y3y1+y2+2y3≤2y1+y3≤3y1、y2≥0、y3≤0•解用以极小化为标准形式的单纯形法求得原问题最优单纯形表如下表所示，对应的对偶问题最优解列于表中最后一行。–表中x3、x4为剩余变量，x5为松弛变量；–原问题最优解为：X*=（250，100）T，Z*=800–对偶问题的最优解为：Y*=（y1*，y2*，y3*）=（4，0，－1），–w*=800Cj23000MMbCBXBx1x2x3x4x5x6x73X201-20-1201002X110101-102500X400111-1-1125-z00401-4+MM-800对偶问题最优解y1*y2*-y3*－y1*+m－y2*+m–从上述两个例子可以总结出：对偶问题的最优解对应原问题最优单纯形表中松弛变量检验数的相反数或剩余变量的检验数。一、资源的影子价格(ShadowPrice)如前所述，若X*为线性规划maxz=CX，AX≤b，X≥0的最优解，则z*=CX*；若Y*为其对偶问题的最优解，则有w*=Y*b。根据对偶定理有z*=w*即z*=Y*b因此即由此可以看出，对偶问题的最优解实际上是右端常数项的单位变化所引起的目标值的变化；/*z*b=Y/**iiyzbi=1,...,m第三节对偶问题的经济意义•若原问题描述的是资源有限条件下最优生产决策问题，则其对偶问题的最优解yi*(i=1,…，m)表示第i种资源在最优生产决策下的边际值，即若其他条件不变，增加单位第i种资源将会使目标函数值增加yi*。•其经济意义是：yi*描述了第i种资源在具体生产中的一种估价，这种估价不同于该种资源的市场价格，而是该种资源在给定条件某生产的最优生产方案下的一种实际存在而又看不见的真实价值，因此称之为影子价格（shadowprice）。1)同一种资源在不同的生产条件或不同的范围可能有不同的影子价格；2)产品的市场价格变化，资源的影子价格也会发生变化；3)资源的数量结构不同，资源的影子价格也不同。资源的影子价格是针对具体生产或具体企业而言的1)与资源的市场价格比较以决定是否安排生产或转让资源或提高产品的价格；2)革新可以提高资源的影子价格；3)可以指导管理部门对紧缺资源进行“择优分配”；4)帮助预测产品的价格。因此，产品的价格应在“成本”和影子价格之间；5)影子价格的高低可以作为同类企业经济效益的评估标准之一。影子价格对于拥有资源的决策者有非常重要的作用–对于目标函数极小化约束条件为大等号的问题minz=CX，AX≥b，X≥0，其右端常数项可理解