whut运筹学-7 矩阵表示 对偶问题 理论 影子价格.ppt

《whut运筹学-7 矩阵表示 对偶问题 理论 影子价格.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、对偶理论与灵敏度分析(DualTheoriesandSensitivityAnalysis)单纯形法的矩阵描述线性规划的对偶问题对偶问题的基本性质对偶问题的经济解释----影子价格对偶单纯形法灵敏度分析例单纯形法的矩阵描述(MatricesDescription)XBx1x2x3x4x5bx11001/404x500-20.514x2010.5-1/802-z00-3/2-1/80-14CB=[203]CN=[00]单纯形法的矩阵描述BCBXBCNXNNb单纯形法的矩阵描述单纯形法的矩阵描述B-1NB-1b单纯形法的矩阵描述考虑线性规划问题的标准型ACm

2、n,R(A)=m.可行基相应于非基变量的系数矩阵令A=(BN)X=(XBXN)TC=(CBCN)单纯形法的矩阵描述矩阵形式的单纯形表XBXBXNbXBIB-1NB-1b-z0CN-CBB-1N-CBB-1b单纯形表中变量xj的系数列向量：B-1aj单纯形表中约束方程的右端项：B-1b单纯形表中目标函数值：CBB-1b单纯形表中变量xj的检验数：Cj-CBB-1aj单纯形法的矩阵描述单纯形法的矩阵描述继续讨论上例XBx1x2x3x4x5bx11001/404x500-20.514x2010.5-1/802-z00-3/2-1/80-14CB=[203]CB

3、B-1=[1.51/80]单纯形法的矩阵描述例用单纯形法求解下述线性规划问题.解:把原问题化为标准型单纯形法的矩阵描述用单纯形法求解如下:迭代XBx1x2x3x4x5bRx31210084x44001016-x504001123-z230000XBx1x2x3x4x5bRx31010-0.522x440010164x201001/43--z2000-3/4-9单纯形法的矩阵描述迭代迭代X*=(4,2)Tz*=14XBx1x2x3x4x5bRx11010-0.52-x400-41284x201001/4312-z00-201/4-13XBx1x2x3x4x5

4、bRx11001/404x500-20.514x2010.5-1/802-z00-3/2-1/80-14单纯形法的矩阵描述线性规划问题的对偶问题(DualProblems)1.对偶问题的提出(DualProblem)例1某工厂用两台机器生产三种产品,有关数据如下表:如何组织生产，使总利润最大？甲(m)乙(m)丙(m)限制条件机器I111135机器II147405利润2311/3x1,x2,x3------分别生产甲、乙、丙产品的数量例2若另一工厂想要租赁这两台机器用于生产产品，那么该工厂应该如何确定合理的租金呢？线性规划问题的对偶问题y1,y2----机器

5、I与机器II的每台时的租金例1与例2是一个问题的两个方面两个线性规划模型是一对对偶问题线性规划问题的对偶问题2.原问题与对偶问题的关系对称性关系例3求下列问题的对偶问题对称性形式的对偶关系线性规划问题的对偶问题非对称性关系练习：线性规划问题的对偶问题原(对偶)问题目标函数maxz=CX≥0n个变量≤0自由变量≤m个约束AX≥b=对偶(原)问题目标函数minw=YTb≥n个约束ATY≤CT=≥0m个变量≤0自由变量原问题与对偶问题对偶关系对照表线性规划问题的对偶问题例4求下列问题的对偶问题线性规划问题的对偶问题例5求下列问题的对偶问题线性规划问题的对偶问题考

6、虑对称性关系的对偶：对称性对偶问题的基本性质(BasicProperties)对偶问题的对偶是原问题。弱对偶性若原(对偶)问题有无界解，则对偶(原)问题无可行解.无界性对偶问题的基本性质原对偶原对偶不可行不可行无界不可行可行解是最优解时的性质对偶定理若原问题有最优解，相应的最优基为B,则对偶问题也有最优解，且最优解为(CBB-1)T；并且目标函数值相等，均为CBB-1b.对偶问题的基本性质对偶问题的基本性质变量对应关系设原问题是它的对偶问题是则原问题单纯性表的检验数行对应其对偶问题的一个基解：原问题XBXNXS检验数0CN-CBB-1N-CBB-1对偶问题

7、YTS1-YTS2-YT例已知用单纯形法求解下述线性规划问题所得最终表如下，试确定该问题的对偶问题的最优解.对偶问题的基本性质解:由已知得CB=(203),因此，由对偶定理可得所求问题的对偶问题的最优解为：XBx1x2x3x4x5bRx11001/404x500-20.514x2010.5-1/802-z00-3/2-1/80-14其中x3,x4,x5为松弛变量。(Y*)Tb=?对偶问题的基本性质互补松弛性令原问题的可行解，是对偶问题的可行解，则它们分别是原问题与对偶问题的最优解的充要条件是:例6已知线性规划问题且其最优解为x*1=2,x*2=0,x*3=

8、8.试用对偶问题的性质求其对偶问题的最优解。对偶问题的基本性质解: