线性规划进一步研究

第二章线性规划进一步研究,第一节对偶问题(DualProblem),线性规划早期发展过程中的最为重要的理论成果之一就是线性规划的对偶问题及相关理论的提出。线性规划的对偶理论解释资源的影子价格、线性规划问题的灵敏度分析等的理论基础。,一、对偶问题的提出,例1（生产计划问题）某企业利用A、B、C三种资源，在计划期内生产甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？,决策变量：x1、x2分别代表甲、乙两种产品的生产数量。即有数学模型（问题A）：问题Amaxz=50 x1+100 x2x1+x23002x1+x2400 x2250 x1、x20称之为上述问题的数学模型。同样是上述问题，提问：企业不安排生产，而转让三种资源，应如何给三种资源定价？,决策变量：y1、y2、y3分别代表A、B、C三种资源的价格（最低转让净收入）。约束条件1：生产一件产品甲所耗资源数量转让所得净收入不能低于一件产品甲所获利润，即：1y1+2y250约束条件2：生产一件产品乙所耗资源数量转让所得净收入不能低于一件产品乙所获利润，即：1y1+1y2+1y3100目标函数为：w=300y1+400y2+250y3即有w=300y1+400y2+250y3y1+2y250y1+y2+y3100y1、y2、y30,从数学和经济的角度分析，该问题的目标函数只能极小，即该问题的数学模型为：问题Bminw=300y1+400y2+250y3y1+2y250y1+y2+y3100y1、y2、y30称问题B为问题A的对偶问题，问题A为原问题。问题Amaxz=50 x1+100 x2x1+x23002x1+x2400 x2250 x1、x20,定义2.1设有线性规划问题maxz=CXAXbX0其对偶问题定义为minw=YbYACY0且前者称为原问题，后者称为对偶问题。,二、对偶问题的定义,具体的数量对应关系为,原问题maxz=c1x1+c2x2+cnxna11x1+a12x2+a1nxnb1a21x1+a22x2+a2nxnb2am1x1+am2x2+amnxnbmx1，x2，xn0对偶问题minw=b1y1+b2y2+bmyma11y1+a21y2+am1ymc1a12y1+a22y2+am2ymc2a1ny1+a2ny2+amnymcny1，y2，ym0,根据对偶问题的定义不难推出，对于线性规划问题：minw=Yb；YAC；Y0其对偶问题为：maxz=CX；AXb；X0即两线性规划问题互为对偶。事实上，任一线性规划问题都有一个固定的线性规划问题与之对偶，且二者互为对偶关系，线性规划的这种性质称为对称性。更进一步有，对于线性规划问题：maxz=CX；AX=b，X0其对偶问题为：minw=Yb；YAC，Y无限制,根据以上分析，线性规划原问题与对偶问题的数量关系可用下表描述。,例2.1写出下列线性规划问题的对偶问题maxz=2x1+2x24x3x1+3x2+3x3304x1+2x2+4x380 x1、x2，x30,解：其对偶问题为minw=30y1+80y2y1+4y223y1+2y223y1+4y24y1、y20,例2.2写出下列线性规划问题的对偶问题minz=2x1+8x24x3x1+3x23x330x1+5x2+4x3=804x1+2x24x350 x10、x20，x3无限制解：其对偶问题为,maxw=30y1+80y2+50y3y1y2+4y323y1+5y2+2y383y1+4y24y3=4y10，y2无限制，y30,一、单纯形法的矩阵描述设有线性规划问题maxz=CXAXbX0加上松弛变量XS=（xn+1，xn+2，xn+m）T，将其化为标准形式得到maxz=CX+0XSAX+IXS=bX0，XS0其中I为mm阶单位阵。,第二节对偶理论(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-1bB-1NXNB-1XS用非基变量XN表示目标函数有=CBXB+CNXN+0XS,将XB=B-1bB-1NXNB-1XS代入得z=CB（B-1bB-1NXNB-1XS）+CNXN+0XS=CBB-1b+（CNCBB-1N）XNCBB-1XS令XN=0，XS=0得到对应于基B的基可行解X=（XB，XX，XS）T=（B-1b，0，0）T目标值为z=CBB-1b相应的非基变量的检验数为N=（CNCBB-1N，CBB-1）若将基变量一起考虑有=（0，CNCBB-1N，CBB-1）=（CCBB-1A，CBB-1）此外，从上式中可推出计算某一具体变量xj的检验数计算公式，即j=cjCBB-1pj,由最优性判别定理可知，当=（CCBB-1A，CBB-1）0时，X=（XB，XX，XS）T=（B-1b，0，0）T为线性规划的最优解；若存在j=cjCBB-1pj0，（jJ），有B-1pj0，则线性规划问题有无界解。,上述过程可用如下单纯形表描述。,定理2.1(弱对偶定理)设X(0)是原问题maxz=CX，AXb，X0的可行解Y(0)是其对偶问题minw=Yb，YAC，Y0的可行解则CX（0）Y（0）b。原问题任一可行解对应的目标函数值不大于其对偶问题的任一可行解对应目标函数值?,二、对偶问题基本定理,定理2.2(最优性定理)设X(0)是原问题maxz=CX，AXb，X0的可行解，Y（0）是其对偶问题minw=Yb，YAC，Y0的可行,若CX（0）=Y（0）b，则X（0）、Y（0）分别是它们的最优解。定理2.3(对偶定理)若原问题maxz=CX，AXb，X0有最优解，则其对偶问题minw=Yb，YAC，Y0一定有最优解，且二者的目标函数值相等。定理2.4(互补松弛定理)原问题maxz=CX，AXb，X0及其对偶问题minw=Yb，YAC，Y0的可行解X（0）、Y（0）是最优解的充要条件是Y（0）XS=0；YSX（0）=0其中，XS、YS分别是原问题松弛变量向量和对偶问题剩余变量向量。,例2.3已知线性规划问题maxz=x1+2x2+3x3+4x4x1+2x2+2x3+3x4202x1+x2+3x3+2x420 x1、x2，x3，x40解：其对偶问题为minw=20y1+20y2y1+2y21（1）2y1+y22（2）2y1+3y23（3）3y1+2y24（4）y1、y202x3*+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=50 x1+100 x2x1+x23002x1+x2400 x2250 x1、x20其对偶问题为：minw=300y1+400y2+250y3y1+2y250y1+y2+y3100y1、y2、y30,表中x3、x4、x5为松弛变量；原问题最优解为：X*=（500，250）T，z*=27500对偶问题的最优解为：Y*=（y1*，y2*，y3*）=（50，0，50），w*=27500,解原问题最优单纯形表如表所示，对应的对偶问题最优解列于表中最后一行。,例2.5（原问题为极小化问题）对于原问题：minz=2x1+3x2x1+x2350 x11252x1+x2600 x1、x20其对偶问题为：maxw=350y1+125y2+600y3y1+y2+2y32y1+y33y1、y20、y30,解用以极小化为标准形式的单纯形法求得原问题最优单纯形表如下表所示，对应的对偶问题最优解列于表中最后一行。,表中x3、x4为剩余变量，x5为松弛变量；原问题最优解为：X*=（250，100）T，Z*=800对偶问题的最优解为：Y*=（y1*，y2*，y3*）=（4，0，1），w*=800,从上述两个例子可以总结出：对偶问题的最优解对应原问题最优单纯形表中松弛变量检验数的相反数或剩余变量的检验数。,一、资源的影子价格(ShadowPrice)如前所述，若X*为线性规划maxz=CX，AXb，X0的最优解，则z*=CX*；若Y*为其对偶问题的最优解，则有w*=Y*b。根据对偶定理有z*=w*即z*=Y*b因此即由此可以看出，对偶问题的最优解实际上是右端常数项的单位变化所引起的目标值的变化；,第三节对偶问题的经济意义,若原问题描述的是资源有限条件下最优生产决策问题，则其对偶问题的最优解yi*(i=1,，m)表示第i种资源在最优生产决策下的边际值，即若其他条件不变，增加单位第i种资源将会使目标函数值增加yi*。其经济意义是：yi*描述了第i种资源在具体生产中的一种估价，这种估价不同于该种资源的市场价格，而是该种资源在给定条件某生产的最优生产方案下的一种实际存在而又看不见的真实价值，因此称之为影子价格（shadowprice）。,同一种资源在不同的生产条件或不同的范围可能有不同的影子价格；产品的市场价格变化，资源的影子价格也会发生变化；资源的数量结构不同，资源的影子价格也不同。,资源的影子价格是针对具体生产或具体企业而言的,与资源的市场价格比较以决定是否安排生产或转让资源或提高产品的价格；革新可以提高资源的影子价格；可以指导管理部门对紧缺资源进行“择优分配”；帮助预测产品的价格。因此，产品的价格应在“成本”和影子价格之间；影子价格的高低可以作为同类企业经济效益的评估标准之一。,影子价格对于拥有资源的决策者有非常重要的作用,对于目标函数极小化约束条件为大等号的问题minz=CX，AXb，X0，其右端常数项可理解为需要完成的任务。因此，该类线性规划一般为描述完成一定任务使耗费的资源最小的问题。此时，其对偶问题的最优解yi*(i=1,，m)表示第i种任务的边际成本，即单位任务的增加引起的资源耗费的增加量。,二、任务的边际成本(MarginalCost),M问题描述:一定时期内，经理必须决定生产水平，使公司能够满足生产需求，在受到产品生产量、劳动力水平以及存储空间上所有限制的同时，还要使生产成本最小。线性规划解决该类问题的优点：可重复利用已建立好的线性规划模型指定不同时期的生产计划。,案例,Bollinger电子公司接到未来三个月的两种产品的定单：生产部门分析，生产费用有以下方面：（1）生产成本；（2）库存储成本；（3）改变生产力水平所需费用。有关数据如下表,现要求制定一个未来3个月的生产计划，使总成本最小。,决策变量（能描述问题）：x1i=第i月生产322A的数量；i=1，2，3(四、五、六月)x2i=第i月生产802B的数量；i=1，2，3s1i=第i月末322A的存储量；i=1，2，3s2i=第i月末802B的存储量；i=1，2，3Ii=第i月生产量增加量；i=1，2，3Di=第i月生产量下降量；i=1，2，3目标函数minz=20 x11+20 x12+20 x13+10 x21+10 x22+10 x23+0.3s11+0.3s12+0.3s13+0.15s21+0.15s22+0.15s23+0.5I1+0.5I2+0.5I3+0.2D1+0.2D2+0.2D3,约束条件（1）需求约束上月期末库存+本月生产量本月期末库存=本月需求量第一个月：设期初库存为：322A：500；802B：200；这样有：500+x11-s11=1000x11-s11=500200+x21-s21=1000x11-s11=800第二个月s11+x12s12=3000s21+x22s22=500第三个月s12+x13s13=5000s22+x23s23=3000（2）期末库存量约束s13400;s23200,(3)机器生产能力约束0.1x11+0.08x21400第一个月0.1x12+0.08x22500第二个月0.1x13+0.08x23600第三个月(4)劳动力能力约束0.05x11+0.07x21300第一个月0.05x12+0.07x22300第二个月0.05x13+0.07x23300第三个月(5)库存能力约束2s11+3s2110000第一个月2s12+3s2210000第二个月2s13+3s2310000第三个月,(6)生产量变化约束本月产量-上月产量=本月产量变化量四月份x11+x212500=I1D1x11+x21I1+D1=2500五月份x12+x22(x11+x21)=I2D2x12+x22(x11+x21)I2+D2=0六月份x13+x23(x12+x22)=I3D3x13+x23(x12+x22)I3+D3=0注意：这里的Ii和Di均为非负变量，而且至少有一个为零。计算机求解结果：,（三）劳动力分配问题问题描述：一个企业有多个生产部门，一定时期各生产部门劳动力数量一定，但劳动力可以在各部门之间转移或再分配最佳的分配方案。案例（麦科米克公司劳动时间分配问题）,设P1,P2分别为产品1、2的产量，则问题的数学模型为：maxz=10P1+9P20.65P1+0.95P265000.45P1+0.85P260001.00P1+0.70P270000.15P1+0.30P21400P1、P20计算机求解结果目标函数最优值为：73589.744变量最优解检验数P15743.590P21794.870约束松弛/剩余变量对偶价格11061.583021889.7440308.4624010.256,问题：若部门之间可利用时间可以调配，是否可以增加总利润？假设各部门之间交叉培训能力和可转移时间信息如下,引入新的决策变量：tij=从i部门转移到j部门的劳动时间bi=分配给第i部门的劳动时间,这样，问题的约束条件如下：（1）生产能力约束0.65P1+0.95P2b100.45P1+0.85P2b201.00P1+0.70P2b300.15P1+0.30P2b30（2）劳动时间平衡约束分配到本部门的劳动时间=总可用时间+转入时间转出时间因此：b1=6500+t41-t12-t13b2=6000+t12+t42-t23-t24b3=7000+t13+t23-t34b4=1400+t24+t34-t41-t42（3）最大转移时间约束t12+t13400t34100t23+t24800t41+t42200,b1-t41+t12+t13=6500b2-t12-t42+t23+t24=6000b3-t13-t23+