管理运筹学第3章对偶规划课件

第3章对偶规划3/15/20231管理运筹学课件教学目标与要求【教学目标】通过对本章的学习，理解对偶定义和性质及影子价格的含义；了解对偶单纯形法；会根据最终单纯形表对于资源项、目标系数变动进行敏感性分析。【知识结构】3/15/20232管理运筹学课件本章主要内容3.1线性规划的对偶模型3.1.1对偶问题3.1.2线性规划对偶模型3.1.3对偶问题的基本性质3.2对偶单纯形法简介3.3影子价格3.4灵敏度分析3.4.1价值系数的变化分析3.4.2右端常数的变化分析3.4.3增加一个新变量的分析3.4.4增加新的约束条件的分析3.5如何看计算机求解报告本章小结3/15/20233管理运筹学课件3.1.1对偶问题原始规划设：两种设备单位台时租金分别为y1,y2由于承租方是理智的，会把租金压至最低。故出租方在满足上述二约束情况下，至少出租总收入（目标函数）为约束一：生产甲产品的利润不大于放弃生产而出租的租金收入约束二：生产乙产品的利润不大于放弃生产而出租的租金收入对偶规划称（2）为（1）的对偶，也称（1）为（2）的对偶。3/15/20235管理运筹学课件3.1.2对偶问题的数学模型（1）对称形式对偶问题原问题对偶问题3/15/20236管理运筹学课件3.1.2对偶问题的数学模型（2）非对称形式对偶问题【例3.1】写出下列线性规划的对偶规划。对偶模型：3/15/20237管理运筹学课件3.2对偶单纯形法简介3/15/20239管理运筹学课件3.2对偶单纯形法简介标准化（若≥乘-1）计算检验数所有σ≤0?Yes所有b≥0?不符合对偶单纯形法条件，改用大M法No结束Yes找到最优解No找出最小bk

xk为离去变量所有akj≥0?θs=min{akj/σj|σj<0}，xs入基，迭代得新单纯形表No无可

行解Yes3/15/202310管理运筹学课件3.2对偶单纯形法简介【例3.2】用对偶单纯形法解解标准化初始单纯形表第1次迭代第2次迭代最优解最优值203/15/202311管理运筹学课件3.3影子价格导入案例原问题的解如图.对偶问题的解3/15/202313管理运筹学课件3.3影子价格原问题bi代表第i种资源拥有量yi代表第i种资源的估价，该估价并非市价格，而是在生产中的单位贡献所做的估价,称为影子价格。其含义：（1）资源的市场价格由供求关系决定，而它的影子价格则有赖于资源的利用情况。（2）影子价格是一种边际价格。（3）资源的影子价格实际上又是一种机会成本。（4）当影子价格为0时，表明该种资源未得到充分利用；当影子价格不为0时，表明该种资源已耗费完毕。（5）在一个大公司内部，可借助资源的影子价格确定一些内部结算价格，以便控制有限资源的使用和考核下属企业经营的好坏。对偶问题3/15/202314管理运筹学课件3.4灵敏度分析线性规划的各个参数A，C，b往往是根据统计数据测算的，不可能完全准确，而且随着实际情况变化。灵敏度分析是指各参数变化对最优解的影响。3/15/202315管理运筹学课件3.4.2右端项bi的变化分析设由式3-8，若则最优基保持不变.【例3.5】由[例3.4]最终单纯形表求最优基不变的b3允许变化范围。初始基最优基即b3的允许变化范围：[40,50]3/15/202317管理运筹学课件3.4.3增加一个新变量的分析3/15/202318管理运筹学课件3.4.3增加一个新变量的分析在操作上：由若大于0应安排生产。【例3.6】在例3.4中增加一个新产品是否可行。其消耗系数列向量p6=（3/2，1，1/2）及价值系数c6=3.3/15/202319管理运筹学课件3.5如何看计算机求解报告【例3.8】Globaloptimalsolutionfound.Objectivevalue: 35.00000Totalsolveriterations: 2Variable Value ReducedCostX(1) 5.000000 0.000000X(2) 0.000000 2.000000X(3) 5.000000 0.000000Row SlackorSurplus DualPrice1 35.00000 1.0000002 0.000000 0.20000003 0.000000 0.6000000Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRanges

Current Allowable AllowableVariable Coefficient Increase DecreaseX(1) 3.000000 1.800000 0.6000000X(2) 1.000000 2.000000 INFINITYX(3) 4.000000 1.000000 1.500000

RighthandSideRangesRowCurrent Allowable AllowableRHS Increase Decrease2

55.00000 25.00000 15.000003

40.00000 15.00000 12.50000最优值迭代次数最优解缩减成本（ReducedCost）指在资源总量不变的情况下，某一个变量在最优解的基础上增加1个单位时，目标成本增加量。由求解结果可见，X(2)=0，其缩减成本为2，表示如果X(2)入基后，每增加1个单位，成本将增加2个单位。松弛或剩余变量（SlackorSurplus）反映了资源的利用情况。若松弛变量为0，表示该资源已耗费完毕，若大于0，表示尚有剩余。本例2个约束的松弛变量（第2、3行）均为0，表示两种资源均已耗费完毕。而第1行是生产一个单位产品所消耗的各项资源的影子价格的总和，称为产品的隐含成本。影子价格（DualPrice）的含义见节3.3。当松弛变量为0时，影子价格大于0。目标系数当前值保持最优基不变时允许增量保持最优基不变时允许减量3/15/202321管理运筹学课件本章小结本章主要内容包括线性规划对偶问题；线性规划原模型与对偶模型之间的结构关系；基于线性规划对偶问题的资源影子价格的含义；各参数变化的敏感性分析；对偶单纯形法。原始规划的解与对偶规划的解之间有一些重要的关系，这些基本性质统称为对偶定理，包括对称性定理，弱对偶定理，最优性准则定理，主对偶定理。对偶变量表示一个单位第i种资源的估价，这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格（Shadowprice），线性规划的灵敏度分析就是研究参数