资源描述：
《北交大管理学课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、上一讲复习和总结1单纯形法的矩阵描述线性规划Maxz=CXMaxz=CX+0XsAX≤bAX+IXs=b设B为A中的一个m×m可行基，A=（B，N），X=（XB，XN）T，C=（CB，CN），原模型MaxZ=CBXB+CNXN+0XS(2.1)BXB+NXN+IXS=b(2.2)XB,XN,XS≥0(2.3)即方程组为：-Z+(C－CBB-1A)X－CBB-1XS=CBB-1bB-1AX+B-1XS=B-1bZXBXNXS右端此方程组的系数增广矩阵为：Z=CB（B-1b－B-1NXN－B-1XS）+C
2、NXN+0XS=CBB-1b+（CN－CBB-1N）XN－CBB-1XSúûùêëé--=----NI0--N011111bBBBbBCBCBCC-1-1BBBN基变量非基变量XBXNXSI0B-1NCN-CBB-1NB-1-CBB-1B-1b-CBB-1b单纯形表的矩阵表示的几个特征1.检验数:非基底的检验数：(cj–zj)=(CN–CBB-1N)基底的检验系数为零：(cj–zj)=CB–CBB-1B=0进一步非基底变量可分解XN→XN1,Xs；Xs的目标系数为零,则该非基底的检验数(cj–zj)=
3、(0–CBB-1)=–CBB-1所有的检验数可用C–CBB-1A与–CBB-1表示(提示(A,I)→(B,N))6、互补松弛定理设X*和Y*分别(P）问题(D）问题的可行解，则它们分别是最优解的充要条件是Y*（b-AX*)=0(Y*A-C)X*=0如何应用该定理？AX*≤bAX*+XS*=bb-AX*=XS*Y*（b-AX*)=0Y*XS*=0对偶变量不为0，原问题相应约束式是等式原问题约束为不等式，相应对偶变量为0最优解点检验数行maxz=CTXs.t.AX+XS=bX,XS≥0maxW=bTys.
4、t.ATY-YS=CY,YS≥0XTYS=0YTXS=0mn=YYSAT-ICn=AXSIbnmmX原始问题和对偶问题变量、松弛变量的维数补充图示y1yiymym+1ym+jyn+mx1xjxnxn+1xn+ixn+m对偶问题的变量对偶问题的松弛变量原始问题的变量原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,…,m;j=1,2,…,n)在一对变量中，其中一个大于0，另一个一定等于0检验数§4对偶问题的经济解释—影子价格(P)的最终单纯形表中松弛变量的检验数对应(D)的最优解。当某约束
5、条件的右端常数增加一个单位时（假设原问题的最优基不变），原问题的目标函数最优值增加的数量。Z*=CX*=Y*b=(y1*,y2*,…,ym*)b1b2﹕﹒bm=y1*b1+y2*b2+…+ym*bm当某个右端常数bibi+1时bi+1yi*+yi*(bi+1)=Y*b+yi*=Z*+yi*第I种资源的影子价格是第i个约束条件的右端常数增加一个单位时，目标函数增加的数量甲乙可用量机械设备128原材料A4016原材料B0412X(3)=(4，2，0，0,4)T，z3=14cj23000CBXBbx1x2x
6、3x4x5203x1x5x2442100001-2½-3/2½-1/81/8010-1400-3/2-1/80经济意义：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。影子价格产品资源ⅠⅡ现有资源数钢材12100（吨）煤22180（吨）机时16240（小时）利润（万元）13x1x2x3x4x5-zXB-13500-3/40-1/4x130103/20-1/2x45000-5/211/2x23501-1/401/4X*=(30,35,0,50,0)T,Z*=135y1*=3/4y2*
7、=0,y3*=1/4影子价格经济意义：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。例用线性规划的对偶问题进行求解解线性规划的对偶问题为求解得即工时的影子价格为5/3，材料的影子价格为1/3如果目前市场上材料的价格低于1/3，则企业可以购进一部分材料来扩大生产，反之若市场价高于1/3，则企业可以卖掉部分材料。如果有客户以高于5/3的价格购买该企业的工时，则可以出售一些工时，反之若客户出价低于5/3则不应出售工时，若企业能够通过加班或租用别人的设备来扩大工时，则当所获得的额外工时的
8、成本低5/3时，企业可以增加工时，否则不应增加工时。在这两个互为对偶的线性规划问题中，生产计划问题的对偶问题是资源定价问题，对偶问题的最优解所代表的是企业在当前面临的资源状况b，技术状况A和市场状况C已知的情况下单位资源对企业的价值。因此，y*代表着当第i个右端常数bi增加一个单位时，最优目标函数值的相应增量。在这两个互为对偶的线性规划问题中，生产计划问题的对偶问题是资源定价问题，对偶问题的最优解所代表是企业在当前面临的资源状况b，技术状况A和市场状况C
