运筹学2对偶问题课件

运筹学2对偶问题6、法律的基础有两个，而且只有两个……公平和实用。——伯克7、有两种和平的暴力，那就是法律和礼节。——歌德8、法律就是秩序，有好的法律才有好的秩序。——亚里士多德9、上帝把法律和公平凑合在一起，可是人类却把它拆开。——查·科尔顿10、一切法律都是无用的，因为好人用不着它们，而坏人又不会因为它们而变得规矩起来。——德谟耶克斯运筹学2对偶问题运筹学2对偶问题6、法律的基础有两个，而且只有两个……公平和实用。——伯克7、有两种和平的暴力，那就是法律和礼节。——歌德8、法律就是秩序，有好的法律才有好的秩序。——亚里士多德9、上帝把法律和公平凑合在一起，可是人类却把它拆开。——查·科尔顿10、一切法律都是无用的，因为好人用不着它们，而坏人又不会因为它们而变得规矩起来。——德谟耶克斯Chapter2对偶问题DualProblem1.线性规划的对偶模型DualModelofLP2.对偶性质Dualproperty3.对偶单纯形法DualSimplexMethod4.灵敏度分析SensitivityAnalysis运筹学OperationsResearch在线性规划问题中，存在一个有趣的问题，即每一个线性规划问题都伴随有另一个线性规划问题，称它为对偶线性规划问题。【例2.1】某企业用四种资源生产三种产品，工艺系数、资源限量及价值系数如下表：建立总收益最大的数学模型。1.发掘生活素材、运用直观教具与实践活动，使学生直观地理解几何概念在课堂教学中，借助直观教具，联系生活实际，充分利用有价值的生活素材来补充教材，重组教材内容，以便更好地组织学生学习"空间与图形"的知识。1.1通过直观的工具，为学生理解几何概念提供帮助。小学生在思维方面，多是以形象思维和直观思维为主。因此，教师在几何图形的教学期间，借助一些直观的工具，对学生理解几何图形的概念可起到一定的帮助。以"长方体"的教学为例，在教学期间教师可对一些相关的道具加以利用，如书本、长方体纸盒等，通过演示道具，使学生直接观察到几何图像的特征。在实践操作的过程中，教师可借由长方体的模型让学生直接观察到长方体在面与面之间的特征，接着，由此引出正方体中的"棱"，进而通过"棱"将"顶点"引出。通过模型，学生可更快速地理解长方体的概念。在选择教具时，教师要注意选择具有典型性的实物或者模型，它们要能明显地体现学习对象的本质，减少非本质属性的干扰。同时还要注意教具的大小及演示的高度，要做到让全班学生都看得到，看得清楚。1.2通过直观操作，促进学生理解概念。《数学课程标准》指出：动手操作、自主探索与合作交流是学生学习的重要方式。几何形体概念需要理解它的本质，只借助看、听、说等方法是不够的，在教学时，应当遵循学生的认知规律，结合实例，联系学生已有知识经验，采用直观操作等实践活动的形式，帮助学生理解概念。给学生创设动手操作、自主探究的学习机会和空间，让学生在操作中从抽象到概括，获取数学知识和体验。在指导学生动手操作、自主探究的过程中，注意操作的可行性和有效性。我的具体做法是：制定明确的目标；选择合适的时机；留有适当的空间；加强方法的指导。例如：教学"长方形的认识"的教学，在学生掌握图形名称的基础上，让学生借助自己动手制作的长方形实物模型，通过折一折，量一量，进一步观察、分析、对比，自己说出长方形的特征（对边相等四个角都是直角），在此基础上，再扩展到生活中去，答出哪些物体的形状是长方形的。这样让学生在操作中思维，在思维中操作，在头脑中形成清晰的表象。2.紧紧围绕几何图像的特点，使学生更迅速地理解几何概念在解决几何图像问题的过程中，学生通常会联想到相应的几何图像，所以在几何图形的教学过程中，教师应注意将几何图形的概念与相关的几何图像联系到一起。2.1加强变式，帮助学生理解概念本质。变式是指概念的肯定例证在无关特征方面的变化。变式用以说明同一个概念的本质特征相同、非本质特征不同的一组实例。这些实例都是概念的正例，但是它们在概念的非本质特征方面有变化。由于概念所指的对象除了具有相同的本质属性以外，还会在非本质属性方面有不同的表现，在几何形体概念的教学中，我们可以充分运用变式来帮助学生获得更精确、更稳定的概念。例如，学生在学习"互相垂直"的概念时，常常习惯于竖着理解，过直线外一线作垂线也习惯于向水平方向画。当变化了直线的方向、位置，就会受标准方向的定势影响，发生错误，以至后来在位置或形状有了变化的三角形（平行四边形、梯形）中找错、画错高，影响面积的正确计算，其原因就在于"互相垂直"这个概念的形成阶段未能为学生提供充分的变式材料，学生没能在"两条直线相交成直角"这一本质意义上对"互相垂直"实行抽象概括。其实，在学生开始学习"互相垂直"时，教师不仅要提供互相垂直的标准式，而且要提供互相垂直的各种变式的练习。在认识和画出三角形（平行四边形、梯形）的高时，不仅在标准图形中进行，而且要在变式图形中进行。然后引导学生分析、比较，找出它们的相同点和不同点，从而帮助学生从不同方面理解"三角形的高"，明确"三角形的高"的本质特征。2.2通过表象作用，为学生理解几何概念提供帮助。首先，在教学期间为学生准备相应的几何图形直观感知材料，使学生通过材料直接取得几何图像的表象。其次，适当对形成表象采取加工处理，为学生建立起表象。在教学的过程中，教师可引导学生通过想象来描写直观材料所具有的特征。在建立起几何图形的表象后，将会为学生在今后的几何学习与解题中提供很大的帮助。3.建立几何图像概念网络体系，使学生更精确地掌握几何概念在教学前，教师可对学生的学习情况进行了解，进而对新旧知识、生活与知识等之间的相关点进行探索，从而设计出合理有效的教学方案，为学生建立起当中的关系网。3.1分清概念的不同之处。几何图像的概念学习中，存在不少相近概念，若学生未能正确区分，极易发生混淆现象。因此教师需教会学生如何分清与辨别各个概念，此时，教师可通过对比相近的事物，帮助学习正确分析相近几何图像的概念。3.2巧妙结合图示和意义。一般情况下，学生在学习几何图像的概念时，均是通过具体至表象至抽象这一个过程认识并建立起的。所以，在教学期间，教师应注意结合图示和意义，引导学生整理与归纳几何图形的概念，加深学生对几何图形概念的理解。总之，促进学生发展是几何形体概念教学永恒不变的追求！教师只有根据概念的本质属性，从学生的认知特点和现实起点出发，运用各种有效地尝试教学方法、策略，以发展的观点开展尝试教学，在概念的系统中教学概念，建立起概念之间的联系，紧扣概念本质，帮助学生在观察、探索、体验、实践中深入剖析理解概念本质，才能收到良好的尝试教学效果和享受。2011版义务教育课程标准的正式颁行，意味着课程改革又进入了一个新的阶段。新课标明确指出：“义务教育物理课程应体现物理学的本质，反映物理学对社会发展的影响；应注重学生的全面发展，关注学生应对未来社会挑战的需求；应发挥在培养学生科学素养方面的重要作用”，这为初中物理教学指明了方向。这次修订，为减轻学生课业负担，在“知识与技能”方面作了适当调整，但由于“过程”和“情感”目标对学生基本素质的形成具有关键意义，在“过程与方法”和“情感、态度与价值观”方面，不仅没有弱化，而且有一定程度的加强，它更突出能力为重、强化能力培养。下面通过分析新课标中课程内容的变化及特点，思考对初中物理教学和考试评价带来的影响，以更好地培养学生的科学素养。课标的第三部分原名为“内容标准”，现改为“课程内容”，其中包含科学探究和科学内容两部分；原主题栏目“内容标准”现改为“内容要求”。笔者认为名词更改后用词更准确，对教学的指导更确切，它规定的是义务教育物理课程的基本学习内容和应达到的基本要求，也就是我们常说教学中的最低要求，在教学中应根据学生的实际能力分层次要求，防止个别教师误解为“到此为止”。一、科学探究的变化1.“科学探究要素”名称变化科学探究第三个要素名称由原“制定计划与设计实验”改为“设计实验与制订计划”，更加突出了对学生设计实验能力的培养。因此，在平时教学中要注重培养学生依据实验原理设计实验，学会选择研究方法和测量器材，制订出较科学的实验计划和步骤。2.“科学探究能力基本要求”的修订新课标对科学探究七个要素的具体能力要求在水平层次和内容上适度微调和整合。（1）各要素的认知目标均由“认识”改为“了解”，即把“认识……的意义（重要性、作用）”的表述统一改为“了解……的意义”，适当降低了对学生认知目标的水平层次。（2）删去“尝试评估有关信息的科学性”、“能注意假设与探究结果间的差异”，增加了“能对收集的信息进行简单的归类”。个别要求在文字上作了调整和整合，如将“尝试对问题的成因提出猜想”中“成因”改为“可能答案”，将“会阅读简单仪器的说明书，能按书面说明进行操作”中“书面说明”改为“要求”，将“能写出简单的探究报告”改为“能表述探究的问题、过程和结果”，对学生能力要求的可操作性增强。3.“科学探究案例”的修订原课标有两个课外科学探究案例，修订后删去了其中一个案例，补充了两个课内探究实例。原课标的探究案例对教师认识科学探究要素起了很大帮助，修订后的三个案例有较合理的内容结构：既有课内探究，也有课外探究，且在每一个案例后增写了一段“评析”。目的在引导教师认识：课内的探究和课外的探究有什么区别？案例是怎样处理课堂时间少和探究过程多的矛盾？怎样处理学生“自主”和教师“指导”的矛盾？解决以上矛盾的办法是：侧重部分探究要素的教学。在教学中，教师应明确本课要培养的探究能力目标是什么？重点要训练的探究要素是什么？属于本课题能力目标的要素，应充分发挥学生的自主性，让他们独立完成；不属于本课题的过程目标，可以大胆发挥教师的主导作用，让学生把主要精力放在教师事先设计需要强化的要素上。实际上，由于不同的课题分别突出了不同的探究要素，学生探究能力得到的是深入和全面的发展。二、科学内容的调整课标中科学内容含“物质”、“运动与相互作用”及“能量”三大一级主题，在每个一级主题下有若干二级主题，每个二级主题下又有若干三级主题。此次修订保留了原课标中的一级、二级主题，主要针对三级主题内容进行了修改。原有“内容标准”68条，修订后有“内容要求”63条。具体有如下变化、特点：1.删减或整合内容，以减轻学生的课业负担（1）删去的条目*“能从生活或社会应用的角度，对物质进行分类”。在化学学科已有类似条目，课标对此不再单列，将对生活和社会的关注在其它条目中予以重视。*在“比较色光混合与颜料混合的不同现象”中，删去了“颜料混合”的内容，改为“了解色光混合的现象”。*“知道波长、频率和波速的关系”，改为“知道波长、频率和波速”。这些知识进入高中后将会进一步学习，删去后并不影响初中知识结构的系统和完整，因此关于计算问题就可以不考虑。*“探究光在同种均匀介质中的传播特点”。此知识小学科学课已学，初中又没有进一步提升，没有必要列入条目重复提出要求。但学生若对此知识不够清晰，教学中还是有必要提醒的。（2）降低要求的条目课标是通过行为动词的调整，适当降低内容要求。*原“理解机械效率”的要求，现下调为“知道”。机械效率问题本来就是教学难点，修订后机械效率的简单计算可以要求，较复杂的问题能力高的学生可以选择面对。*原“理解物体的惯性”要求，现为“能用物体的惯性解释生活和自然中的有关现象”，侧重于解释现象。*关于“不可再生能源和可再生能源”，修订后只要求“列举”，不再强调“说出特点”。值得注意的是“知道白光是由色光组成的”改为“了解白光的组成”；“解释机械功的含义”调为“说明”；“认识机械的使用对社会发展的作用”调为“了解”；“尝试用比热容解释简单的自然现象”中“解释”调为“说明”。这些基本上是在同一水平层次的规范表述，但从行为动词改变看，似乎也隐含着一点微调。（3）整合的条目课标将半导体、超导体、纳米材料等有关条目合并为“通过收集信息，了解一些新材料的应用和发展前景，了解新材料的发展对人类生活和社会发展带来的影响”，而原来相关的三个条目则作为例子列入，这样既降低了难度，又为教材编写和教学留下了更多空间。2.明确和细化内容要求，以利于教学和评价（1）认知领域只设了解、认识、理解三个水平层次。修订后规范了行为动词，不再使用“初步认识”、“大致了解”等介于两者之间的说法，使各认知水平更加统一和简洁。（2）细化条目，使教学和评价要求进一步明确。原课标中有些内容条目比较原则，不便于评价，修订后做了进一步细化，详见下表。（3）明确列出了学生实验具体项目课标对具体实验项目的要求有31条，哪些是演示实验，哪些应作为学生实验，过去不明确。本次修订明确列出了20个实验项目作为学生实验，也就是说学生至少要动手操作这20个实验，对于其他实验，如果可能，教师也可以创造条件让学生做分组实验。3.适当增加内容，优化三维目标（1）增加了优化知识结构的内容“观察摩擦起电现象，探究并了解同种电荷相互排斥，异种电荷相互吸引。”此条目在小学科学、高中物理课程中皆未明确要求，此内容与生产生活联系密切且对后续学习有一定影响。除此外还增加了“知道原子是由原子核和电子组成的”，“知道噪声的危害”，“知道地磁场”，“了解热机的工作原理”，“知道电压、电流和电阻”，“了解串、并联电路电流和电压的特点”，“理解电功”等知识点。（2）增加了探究过程的内容“通过实验测量物体运动的速度”，“通过实验，探究液体压强与哪些因素有关”，“通过实验，认识磁场”，“通过实验，了解电流周围存在磁场”。（3）增加了注重情感、态度与价值观目标落实的内容“运用物体的浮沉条件说明生产、生活中的一些现象”，“知道大气压强及其与人类生活的关系”，“了解提高机械效率的途径和意义”，“了解电磁感应在生产、生活中的应用”，“用焦耳定律说明生产、生活中的一些现象”，“能在个人力所能及的范围内对社会的可持续发展有所作为”，“有节约用电的意识”等，这些内容强化了物理知识与生产、生活的联系，更加关注知识的实践应用，是教学联系实际的好素材。值得注意的是：课标看似删去了“了解测量大气压强的方法”，其实在“知道大气压强及其与人类生活的关系”中已体现。看似删去了“了解物体运动状态变化的原因”，其实在“认识力的作用效果”中体现了物体受到力时运动状态如何改变，在“通过实验，认识牛顿第一定律”中体现了物体不受力时运动状态如何。课标删去这两条，是为了使行文的含义准确，避免重复陈述，并没有删去这两方面的内容要求。再如，看似删了“能用实验证实电磁相互作用”，实则在“通过实验，了解电流周围存在磁场”、“通过实验，了解通电导线在磁场中会受到力的作用”中已有体现，不需再重复。看似删了“有评估某些物质对人和环境的积极和消极影响的意识”，实则在其他条目中有“关注环境、保护环境”的要求。看似删了“能简单描述温度和内能的关系”，其实在“了解分子热运动的特点”中已包含。Chapter2对偶问题DualProblem1.线性规划的对偶模型

DualModelofLP2.对偶性质

Dualproperty3.对偶单纯形法

DualSimplexMethod4.灵敏度分析

SensitivityAnalysis运筹学OperationsResearch在线性规划问题中，存在一个有趣的问题，即每一个线性规划问题都伴随有另一个线性规划问题，称它为对偶线性规划问题。【例2.1】某企业用四种资源生产三种产品，工艺系数、资源限量及价值系数如下表：产品资源ABC资源限量Ⅰ986500Ⅱ547450Ⅲ832300Ⅳ764550每件产品利润1008070

建立总收益最大的数学模型。【解】设x1，x2，x3分别为产品A，B，C的产量，则线性规划数学模型为：现在从另一个角度来考虑企业的决策问题。假如企业自己不生产产品，而将现有的资源转让或出租给其它企业，那么资源的转让价格是多少才合理？价格太高对方不愿意接受，价格太低本单位收益又太少。合理的价格应是对方用最少的资金购买本企业的全部资源，而本企业所获得的利润不应低于自己用于生产时所获得的利润。这一决策问题可用下列线性规划数学模型来表示。设y1，y2，y3及y4分别表示四种资源的单位增殖价格（售价＝成本＋增殖），总增殖最低可用minw=500y1+450y2+300y3+550y4

表示。企业生产一件产品A用了四种资源的数量分别是9，5，8和7个单位，利润是100,企业出售这些数量的资源所得的利润不能少于100，即同理，对产品B和C有价格不可能小于零，即有yi≥0,i=1,…,4.从而企业的资源价格模型为这是一个线性规划数学模型，称这一线性规划问题是前面生产计划问题的对偶线性规划问题或对偶问题。生产计划的线性规划问题称为原始线性规划问题或原问题。【例2.2】某人根据医嘱，每天需补充A、B、C三种营养，A不少于80单位，B不少于150单位，C不少于180单位。此人准备每天从六种食物中摄取这三种营养成分。已知六种食物每百克的营养成分含量及食物价格如下表，试建立此人在满足健康需要的基础上花费最少的数学模型。

营养成分

一

二

三

四

五

六需要量80B24930251215≥150C1872134100≥180食物单价（元/100g）0.50.40.80.90.30.2

含量食物【解】设xj为每天第j种食物的用量，数学模型为现有一制药厂要生产一种包含A、B、C三种营养成分的合成药，如何制定价格，使得此药既要畅销又要产值最大。设yi（i=1，2，3）为第i种营养成分的单价，则影子价格(Shadowprice):

上面两个线性规划有着重要的经济含义。原始线性规划问题考虑的是充分利用现有资源，以产品的数量和单位产品的收益来决定企业的总收益，没有考虑到资源的价格，但实际在构成产品的收益中，不同的资源对收益的贡献也不同，它是企业生产过程中一种隐含的潜在价值，经济学中称为影子价格，即对偶问题中的决策变量yi的值。由后面的对偶性质可知：原问题和对偶问题的最优值相等，故有即yi是第i种资源的变化率，说明当其它资源供应量bk(k≠i)不变时，bi增加一个单位时目标值Z增加yi个单位。例如，第一种资源的影子价格为y1=2，第二种资源的影子价格为y2=2，即当第一种资源增加一个单位时，Z增加2个单位，当第二种资源增加一个单位时，Z增加2个单位。企业可利用影子价格调节生产规模。例如，目标函数Z表示利润（或产值），当第i种资源的影子价格大于零（或高于市场价格）时，表示有利可图，企业应购进该资源扩大生产规模，当影子价格等于零（或低于市场价格），企业不能增加收益，这时应将资源卖掉或出让，缩小生产规模。应当注意，是在最优基B不变的条件下有上述经济含义，当某种资源增加或减少后，最优基B可能发生了变化，这时yi的值也随之变化。在例2.1中，原问题的最优解X＝（24.24，0，46.96）对偶问题的最优解Y＝（10.6，0.91，0，0）最优值z=w=5712.12分析：1.y1=10.6说明在现有的资源限量的条件下，增加一个单位第一种资源可以给企业带来10.6元的利润；如果要出售该资源，其价格至少在成本价上加10.6元。2.y3=0说明增加第三种资源不会增加利润，因为第三种资源还有没有用完。问题：1.第三、四种资源的售价是多少，是否不值钱？2.如果要增加利润，企业应增加哪几种资源，各增加多少后再进行调整？上面两种形式的线性规划称为对称形式。原问题和对偶问题是互为对偶的两个线性规划问题，已知一个问题就可写出另一个问题。对称形式的定义是：目标函数求极大值时，所有约束条件为≤号，变量非负；

目标函数求极小值时，所有约束条件为≥号，变量非负。

对称形式的线性规划的对偶问题亦是对称形式。以上是依据经济问题推导出对偶问题，还可以用代数方法推导出对偶问题。【例2.3】写出下列线性规划的对偶问题【解】这是一个对称形式的线性规划，设Y=（y1，y2），则有从而对偶问题为对偶变量yi也可写成xi的形式。【例2.4】写出下列线性规划的对偶问题【解】这是一个对称形式的线性规划，它的对偶问题求最小值，有三个变量且非负，有两个“≥”约束，即若给出的线性规划不是对称形式，可以先化成对称形式再写对偶问题。也可直接按表2－1中的对应关系写出非对称形式的对偶问题。将上述原问题与对偶问题的对应关系列于表2－1例如，原问题是求最小值，按表2-1有下列关系：1.第i个约束是“≤”约束时，第i个对偶变量yj≤02．第i个约束是“=”约束时，第i个对偶变量yi无约束；3．当xj≤0时，第j个对偶约束为“≥”约束，当xj无约束时，第j个对偶约束为“=”约束。原问题（或对偶问题）对偶问题（或原问题）目标函数（max）目标函数系数（资源限量）约束条件系数矩阵A（AT）目标函数（min）资源限量（目标函数系数）约束条件系数矩阵ATA）变

量n个变量第j个变量≥0第j个变量≤0第j个变量无约束约

束n个约束第j个约束为≥第j个约束为≤第j个约束为=约

束m个约束第i个约束≤第i个约束≥第i个约束为=变

量m个变量第i个变量≥0第i个变量≤0第i个变量无约束表2－1【例2.5】写出下列线性规划的对偶问题【解】目标函数求最小值，应将表2－1的右边看作原问题，左边是对偶问题，原问题有3个约束4个变量，则对偶问题有3个变量4个约束，对照表2－1的对应关系，对偶问题为：本节以实例引出对偶问题;介绍了如何写对称与非对称问题的对偶问题;1.您应该会写任意线性规划的对偶问题；2.深刻领会影子价格的含义，学会用影子价格作经济活动分析。作业：教材P74T2.3（1）（2）TheEndofSection2.1对偶性质Exit返回首页设原问题是（记为LP）：对偶问题是（记为DP）：这里A是m×n矩阵X是n×1列向量，Y是1×m行向量。假设Xs与Ys分别是（LP）与（DP）的松驰变量。【性质1】对称性对偶问题的对偶是原问题。【证】设原问题是7/16/2023它与下列线性规划问题是等价的：再写出它的对偶问题。它与下列线性规划问题是等价的即是原问题。由表2－1知，它的对偶问题是7/16/2023【性质2】弱对偶性设X°、Y°分别为（LP）与（DP）的可行解，则【证】因为X°、Y°是可行解，故有AX°≤b,X°≥0及Y°A≥C，Y°≥0,将不等式AX°≤b两边左乘Y°得Y°AX°≤Y°b再将不等式Y°A≥C两边右乘X°，故CX°≤Y°AX≤Y°b这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都不会大于求最小值的线性规划的任一目标值，不能理解为原问题的目标值不超过对偶问题的目标值。得CX°≤Y°AX°7/16/2023由这个性质可得到下面几个结论：（1）（LP）的任一可行解的目标值是（DP）的最优值下界；（DP）的任一可行解的目标是（LP）的最优值的上界；（2）在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解；(3）若原问题可行且另一个问题不可行，则原问题具有无界解。注意上述结论（2）及（3）的条件不能少。一个问题有可行解时，另一个问题可能有可行解（此时具有无界解）也可能无可行解。7/16/2023例如：无可行解，而对偶问题有可行解，由结论（3）知必有无界解。7/16/2023【性质3】最优准则定理设X°与Y°分别是（LP）与（DP）的可行解，则当X°、Y°是（LP）与（DP）的最优解当且仅当CX°=Y°b.【证】若X°、Y°为最优解，B为（LP）的最优基，则有Y°=CBB－1，并且当CX°=Y°b时，由性质1，对任意可行解有即Y°b是（DP）中任一可行解的目标值的下界，CX°是（LP）中任一可行解的目标值的上界，从而X°、Y°是最优解。7/16/2023【性质4】还可推出另一结论：若（LP）与（DP）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。【证】设（LP）有最优解X°，那么对于最优基B必有C－CBB-1A≤0与－CBB-1≤0，即有Y°A≥C与Y°≥0，这里Y°=CBB-1，从而Y°是可行解，对目标函数有由性质3知Y°是最优解。由性质4还可推出另一结论：若（LP）与（DP）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。7/16/2023【性质5】互补松弛定理设X°、Y°分别为（LP）与（DP）的可行解，XS和YS是它的松弛变量的可行解，则X°和Y°是最优解当且仅当YSX°=0和Y°XS=0【证】设X°和Y°是最优解，由性质3，CX°=Y°b，由于XS和YS是松弛变量，则有AX°＋XS＝bY°A－YS=C将第一式左乘Y°，第二式右乘X°得Y°AX°＋Y°XS＝Y°bY°AX°－YSX°=CX°7/16/2023显然有Y°XS=－YSX°又因为Y°、Xs、Ys、X°≥0，所以有Y°XS=0和YSX°=0成立。反之，当Y°XS=0和YSX°=0时，有Y°AX°＝Y°bY°AX°=CX°显然有Y°b=CX°,由性质3知Y°与X°是（LP）与（DP）的最优解。证毕。7/16/2023性质5告诉我们已知一个问题的最优解时求另一个问题的最优解的方法，即已知Y°求X°或已知X°求Y°。Y°XS=0和YSX°=0两式称为互补松弛条件。将互补松弛条件写成下式由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：7/16/2023（1）当yi°>0时，，反之当时yi°=0；注意：对于非对称形式，性质5的结论仍然有效。【例2.6】已知线性规划的最优解是，求对偶问题的最优解。7/16/2023的最优解是，求对偶问题的最优解。【解】对偶问题是因为X1≠0，X2≠0，所以对偶问题的第一、二个约束的松弛变量等于零，即解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为Y=（1，1），最优值w=26。7/16/2023【例2.7】已知线性规划的对偶问题的最优解为Y=（0,-2），求原问题的最优解。【解】对偶问题是由y2≠0得=0，由得x2=0，原问题的约束条件变为:解此方程组得原问题最优解：X=(-5,0,-1)T，minZ=-12。7/16/2023【例2.8】证明下列线性规划无最优解：【证】容易看出X=（4，0，0）是一可行解，故问题可行。对偶问题将三个约束的两端分别相加得，而第二个约束有y2≥1，矛盾，故对偶问题无可行解，因而原问题为无界解，即无最优解。7/16/2023【性质6】（LP）的检验数的相反数对应于（DP）的一组基本解.其中第j个决策变量xj的检验数的相反数对应于（DP）中第j个松弛变量的解，第i个松弛变量的检验数的相反数对应于第i个对偶变量yi的解。反之，（DP）的检验数（注意：不乘负号）对应于（LP）的一组基本解。证明略。7/16/2023【例2.9】线性规划（1）用单纯形法求最优解；（2）写出每步迭代对应对偶问题的基本解；（3）从最优表中写出对偶问题的最优解；（4）用公式Y=CBB-1求对偶问题的最优解。【解】（1）加入松弛变量x4、x5后，单纯形迭代如表2－2所示。7/16/2023表2－2XBx1x2x3x4x5b(1)x4x52*1-102410012→4λj6↑-2100

(2)x1x510-1/21/2*131/2-1/20113→λj01↑-5-30

(3)x1x21001460-11246λj00-11-2-2

7/16/2023最优解X=（4，6，0），最优值Z=6×4－2×6=12；（2）设对偶变量为y1、y2,松弛变量为y3、y4、y5,Y=（y1、y2、y3、y4、y5），由性质6得到对偶问题的基本解（y1、y2、y3、y4、y5）=（－λ4，－λ5，－λ1，－λ2，－λ3），即表2－2（1）中λ=（6，－2，1，0，0），则Y（1）=（0，0，-6，2，－1）表2－2（2）中λ=（0，1，－5，－3，0），则Y（2）=（3，0，0，－1，5）表2－2（3）中λ=（0，0，－11，－2，－2），则Y（3）=（2，2，0，0，11）7/16/2023（1）因为表2－2（3）为最优解，故

Y（3）=（2，2，0，0，11）为对偶问题最优解；（1）表2－2（3）中的最优基

B-1为表2－2（3）中x4，x5两列的系数，即CB=（6，－2），因而7/16/2023本节您学了六个对偶性质；这些性质是研究原问题与对偶问题解的对应关系；表2－3也许对您了解这些性质有帮助。表2－3一个问题max另一个问题min有最优解有最优解性质4无最优解无最优解无最优解性质4无界解（有可行解）无可行解性质2无可行解无界解（有可行解）应用已知最优解通过解方程求最优解性质5已知检验数检验数乘以－1求得基本解性质67/16/2023试一试：判断下列结论是否正确，如果不正确，应该怎样改正？1．任何线性规划都存在一个对应的对偶线性规划.2．原问题第i个约束是“≤”约束，则对偶变量yi≥0.3．互为对偶问题，或者同时都有最优解，或者同时都无最优解.4．对偶问题有可行解，则原问题也有可行解.5．原问题有多重解，对偶问题也有多重解.6．对偶问题有可行解，原问题无可行解，则对偶问题具有无界解.7．原问题无最优解，则对偶问题无可行解.8．若某种资源影子价格为零，则该资源一定有剩余.9．对偶问题不可行，原问题可能无界解.10．原问题与对偶问题都可行，则都有最优解.11．原问题具有无界解，则对偶问题不可行.12．对偶问题具有无界解，则原问题无最优解.13．若X*、Y*是原问题与对偶问题的最优解，则X*=Y*.14．在资源优化的线性规划问题中，若某一资源有剩余，则该资源影子价格为零.

7/16/2023作业：教材P75T2.4、2.6、2.5TheEndofSection2.2对偶单纯形法Exit7/16/2023设原问题是（记为LP）：对偶问题是（记为DP）：根据对偶性质6，可以构造一个求线性规划的另一种方法，即对偶单纯形法。对偶单纯形法的计算步骤：对偶单纯形法的条件是：初始表中对偶问题可行，即极大化问题时λj≤0，极小化问题时λj≥0。7/16/2023（1）将线性规划的约束化为等式，求出一组基本解，因为对偶问题可行，即全部检验数λj≤0（max）或λj≥0（min）,当基本解可行时，则达到最优解；若基本解不可行，即有某个基变量的解bi<0，则进行换基计算；（2）先确定出基变量。行对应的变量xl出基；（3）再选进基变量。求最小比值（4）求新的基本解，用初等变换将主元素alk化为l,k列其它元素化为零，得到新的基本解，转到第一步重复运算。7/16/2023【例2.10】用对偶单纯形法求解【解】先将约束不等式化为等式，再两边同乘以（－1），得到用对偶单纯形法，迭代过程如下页或看演示(请启用宏)。7/16/2023表2－47/16/2023应当注意：（1）用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解；（2）初始表中一定要满足对偶问题可行，也就是说检验数满足最优判别准则；（3）最小比值中的绝对值是使得比值非负，在极小化问题时λj≥0，分母aij<0这时必须取绝对值。在极大化问题中，λ≤j0分母aij<0，总满足非负，这时绝对值符号不起作用，可以去掉。如在本例中将目标函数写成这里λj≤0在求θk时就可以不带绝对值符号。7/16/2023（4）对偶单纯形法与普通单纯形法的换基顺序不一样，普通单纯形法是先确定进基变量后确定出基变量，对偶单纯形法是先确定出基变量后确定进基变量；（5）普通单纯形法的最小比值是其目的是保证下一个原问题的基本解可行，对偶单纯形法的最小比值是其目的是保证下一个对偶问题的基本解可行；（6）对偶单纯形法在确定出基变量时，若不遵循规则，任选一个小于零的bi对应的基变量出基，不影响计算结果，只是迭代次数可能不一样。7/16/2023【例2.12】用对偶单纯形法求解求解过程见演示（链接到Excel文件，需启用宏）。7/16/2023例2.12可用性质6及性质2来说明，表（2）的第2行对应于对偶问题的第2列（相差一个负号），检验数行对应于对偶问题的常数项（相差一个负号），比值对应于对偶问题的比值失效也说明即对偶问题具有无界解，由性质2知原问题无可行解。7/16/2023本节利用对偶性质6：原问题的检验数与对偶问题的基本解的对应关系，介绍了一种特殊线性规划的求解方法—对偶单纯形法。1.对偶单纯形法的应用条件；2.出基与进基的顺序；3.如何求最小比值；4.最优解、无可行解的判断。作业：教材P76T2.7TheEndofSection3灵敏度分析Exit7/16/2023线性规划的灵敏度分析也称为敏感性分析，它是研究和分析参数（cj，bi，aij）的波动对最优解的影响程度，主要研究下面两个方面：（1）参数在什么范围内变化时，原最优解或最优基不变；（2）当参数已经变化时，最优解或最优基有何变化。当模型的参数发生变化后，可以不必对线性规划问题重新求解，而用灵敏度分析方法直接在原线性规划取得的最优结果的基础上进行分析或求解，既可减少计算量，又可事先知道参数的变化范围，及时对原决策作出调整和修正。2.4.1价值系数cj的变化分析为使最优解不变，求cj的变化范围。7/16/2023设线性规划其中Am×n，线性规划存在最优解，最优基的逆矩阵为检验数为要使最优解不变，即当cj变化为后，检验数仍然是小于等于零，即这时分cj是非基变量和基变量的系数两种情况讨论。7/16/2023一、cj是非基变量xj的系数即cj的增量不超过cj的检验数的相反数时，最优解不变，否则最优解就要改变。所以7/16/2023二、ci是基变量xi的系数因ci∈CB，所以每个检验数λj中含有ci,当ci变化为ci＋后λj同时变化，这时令令7/16/2023要使得所有，则有【例2.13】线性规划（1）求最优解；（2）分别求c1,c2,c3的变化范围，使得最优解不变。7/16/2023【解】（1）加入松弛变量x4,x5,x6，用单纯形法求解，最优表如表2－6所示。表2－6Cj113000bCBXBx1x2x3x4x5x60x40－201－1－151x111001－153x301100115λj0－300－1－2

最优解X=（5，0，15）;最优值Z=50。7/16/2023（2）x2为非基变量，x1、x3为基变量，则c2变化范围是：对于c1：表2－6是x1对应行的系数只有一个负数,有两个正数c1的变化范围是：7/16/2023对于c3：表2－6中x3对应行Δc3无上界，即有Δc3≥－2，c3的变化范围是。7/16/2023对c3的变化范围，也可直接从表2－6推出，将c3=3写成分别计算非基变量的检验数并令其小于等于零。7/16/2023得Δc3≥－2，同理，用此方法可求出c2和c1的变化区间。，要使、同时小于等于零，解不等式组2.4.2资源限量bi变化分析为了使最优基B不变，求bi的变化范围。设br的增量为Δbr，b的增量为原线性规划的最优解为X，基变量为XB=B－1b，要使最优基B不变，即要求，7/16/2023因为7/16/2023所以当令7/16/2023因而要使得所有必须满足这个公式与求的上、下限的公式类似，比值的分子都小于等于零，分母是B－1中第r列的元素，大于等于比值小于零的最大值，小于等于比值大于零的最小值。当某个时，可能上界或无下界。【例2.14】求例2.13的b1,b2,b3分别在什么范围内变化时，原最优基不变。7/16/2023【解】解：由表2－6知，最优基B、B－1及分别为对于b1：比值的分母取B－1的第一列，这里只有β11=1，而β21=β31=0，则7/16/2023Δb1无上界，即Δb1≥－5，因而b1在内变化时最优基不变。对于b2：比值的分母取B－1的第二列，，则即b2在[15，25]上变化时最优基不变。7/16/2023对于b3：比值的分母取B－1的第三列，有故有在[0，20]上变化时最优基不变。灵敏度分析方法还可以分析工艺系数aij的变化对最优解的影响，对增加约束、变量或减少约束、变量等情形的分析，下面以一个例子来说明这些分析方法。若线性规划模型是一个生产计划模型，当求出cj或bi的最大允许变化范围时，就可随时根据市场的变化来掌握生产计划的调整。7/16/2023【例2.15】考虑下列线性规划求出最优解后，分别对下列各种变化进行灵敏度分析，求出变化后的最优解。（1）将目标函数改为；（1）改变右端常数为:7/16/2023（3）改变目标函数x3的系数为c3=1;（4）改变目标函数中x2的系数为c2=2；（5）改变x2的系数为（6）改变约束（1）为（7）增加新约束（8）增加新约束7/16/2023【解】加入松弛变量x4、x5、x6，用单纯形法计算，最优表如2－7所示。表2－7Cj2-14000bCBXBx1x2x3x4x5x64x305/711/73/7022x112/70－1/74/7010x60－200－111λj0－31/70－2/7－20/70

7/16/2023最优解X=（1，0，2，0，0，1），最优值Z=10，最优基（1）等价于，即将cj改变为（－2，1，－4），其中c1=－2、c3=－4是基变量的系数，c2=1是非基变量的系数，求得检验数7/16/2023这里表2－7的解不是最优，将上述检验数代替表2－7的检验数，再单纯形法继续迭代，计算结果如表2－8所示。7/16/2023表2－8cj－21－4000bCBXBx1x2x3x4x5x6－4x305/711/73/702－2x112/70－1/74/7010x60－200－111λj031/702/720/70

1x2017/51/53/5014/5－2x110－2/5－1/52/501/50x60014/52/51/5033/5λj00－31/5－3/51/50

1x2－3/2121/2005/20x55/20－1－1/2101/20x6－1/2031/20113/2λj－1/20－6－1/200

7/16/2023最优解（2）基变量的解为基本解不可行，将求得的XB代替表2－7中的常数项，用对偶单纯形法求解，其结果见表2－9所示。7/16/2023表2－9Cj2－14000bCBXBx1x2x3x4x5x64x305/711/73/7022/72x112/70－1/74/706/70x60－200－11－2λj0－31/70－2/7－20/70

4x30011/71/145/1417/72x1100－1/73/71/74/7－1x201001/2－1/21λj000－2/7－9/14－31/14

7/16/2023最优解（3）由表2－7容易得到基变量x3的系数c3的增量变化范围是，而c3=1在允许的变化范围之外，故表2－7的解不是最优解。非基变量的检验数x4进基，用单纯形法计算，得到表2－10。7/16/2023表2－10XBx1x2x3x4x5x6

bx305/711/73/702x112/70－1/74/701x60－200－111λj0－16/