北京交通大学 运筹学 教案6_对偶理论.ppt

《北京交通大学 运筹学 教案6_对偶理论.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、设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)XB=B-1b－B-1NXN－B-1XS代入（2.1）式，有Z=CB（B-1b－B-1NXN－B-1XS）+CNXN+0XS=CBB-1b+（CN－CBB-1N）XN－CBB-1XSZ=CB（B-1b－B-1NXN－B-1XS）+CNXN+0XS=CBB-1b+（CN－CBB

2、-1N）XN－CBB-1XS即方程组为：-Z+(C－CBB-1A)X－CBB-1XS=CBB-1bB-1AX+B-1XS=B-1b-ZXBXNXS右端此方程组的系数增广矩阵为：基变量非基变量XBXNXSI0B-1NCN-CBB-1NB-1-CBB-1B-1b-CBB-1b单纯形表的矩阵形式如例1的初始表和第三张表2改进单纯形法单纯形法中，除换入变量外，非基变量系数列的迭代运算是多余的。为了减少计算量和存储量，产生了改进单纯形法。当m<

3、、C三种配料组成，下表给出了1单位各种配料所含的营养成分、单位成本以及1份饲料必须含有的各种成份。问如何配制混合饲料使成本最小？营养成分DEF单位成本ABC111½½¼2116321份饲料应含量20610设:Xj=混合饲料中第j种配料的含量，j=A、B、CMinZ=6XA+3XB+2XCXA+XB+XC³201/2XA+1/2XB+1/4XC³62XA+XB+XC³10Xj³0有一个饲料厂，制造含有这3种营养成份各1单位的营养丸，知道养鸡场对混合饲料的要求，因此，在制定营养丸的价格时，使每丸D、E、

4、F营养丸的价格分别为q1、q2、q3。养鸡场采购1单位配料A,相当于对3种营养丸分别采购1、1/2、2丸等，采购1单位的B,…,1单位的C,因此饲料厂定营养丸售价时，必须有：q1+1/2q2+2q3£6q1+1/2q2+q3£3q1+1/4q2+q3£2MaxZ=20q1+6q2+10q3设出租单位设备台时的租金y1，转让原材料A、B的收费为y2，y3。第一章例1生产组织问题MaxZ=2x1+3x2x1+2x2≤84x1≤164x2≤12x1，x2≥0若工厂决策者准备将所有资源出租或转让，问应如何定

5、价？设备原材Ay1y2原材By3甲乙可用量机械设备128原材料A4016原材料B0412对偶问题的定义标准型为：互为转置列向量行向量n个变量n个约束≤2≥证：AX=bAX≤bAX≥bAX≤b-AX≤-by′y〃解：设对偶变量为y1,y2,y3,对偶问题模型为：Maxw=5y1+4y2+6y3y1+2y2y1+y3-3y1+2y2+y3y1-y2+y3≥2≤3≤-5=1y1≥0,y2≤0,y3无约束4.2对偶问题的基本性质注意：(D)无可行解，(P)不一定为无界解。此性质还说明：(P)有可行解，(D

6、)不一定有可行解。4、可行解是最优解时的性质设是(P)的可行解，是(D)的可行解，当时，是最优解。3、无界性若（P）问题可行，但目标函数无界，则（D）问题不可行。（D）不可行（P）无界（P）不可行利用弱对偶定理5、对偶定理若（P）有最优解，则（D）也有最优解，且目标函数最优值相等。例1已知线性规划问题试用对偶理论证明上述问题无最优解。无界性定理。（P）可行，但无界则（D）不可行。（D）不可行（P）无界（P）不可行对偶问题X（0）=（0，0，0）T是原问题的一个可行解对偶问题不可行6、互补松弛定理设X

7、*和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最优解点检验数行§5对偶问题的经济解释—影子价格(P)的最终单纯形表中松弛变量的检验数对应(D)的最优解。当某约束条件的右端常数增加一个单位时（假设原问题的最优基不变），原问题的目标函数最优值增加的数量。Z*=CX*

8、=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=14cj23000CBXBbx1x2x3x4x5203x1x5x2442100001-2½-3/2½-1/