对偶理论与灵敏度分析1

《对偶理论与灵敏度分析1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章主要内容：对偶规划对偶理论对偶单纯形算法14.1对偶问题的提出现从另一个角度来讨论，假定工厂考虑不安排生产，而是出售原材料，出租工时或转产新产品等。问如何定价，可使工厂获利不低于安排生产所获得的收益，且又能使这些定价具有竞争力？设出售原料的定价为毎公斤y1元，出租工时的定价为毎工时y2元.从工厂考虑，这些定价下的获利不应低于安排生产所获得的收益。否则工厂宁可生产，而不出售或出租或转产等,由此考虑出售或出租或转产的数学模型.2对偶问题?任何线性规划问题都有其对偶问题对偶问题有其明显的经济含义假设有商人要向厂方购买资源A和B，问他们谈判原料价格的模型是怎样的？3原问题—简

2、单的生产计划问题如何安排一天的生产计划，使企业利润最大？某工厂生产甲、乙两种产品，单位产品利润、耗工耗料及工料限额为下表4解：限制条件：“s.t.”:Subjectto目标函数决策变量约束条件5新问题—简单的生产计划问题设出售原料的定价为毎公斤y1元，出租工时的定价为毎工时元.6例生产计划问题某工厂用三种原料生产三种产品，已知的条件如表2.1.1所示，试制订总利润最大的生产计划。单位产品所需原料数量（公斤）产品Q1产品Q2产品Q3原料可用量（公斤/日）原料P12301500原料P2024800原料P33252000单位产品的利润（千元）3547（原问题）8*对偶问题9原问题

3、与对偶问题的关系（一）对称形式的对偶问题比较上述的两个互为对偶问题：101、一个问题中的约束条件个数等于它的对偶问题中的变量数。2、一个问题中目标函数的系数是其对偶问题中约束条件的右端项。3、约束条件在一个问题中为“≤”，则在其对偶问题中为“≥”.4、目标函数在一个问题中求最大值，在其对偶问题中则为求最小值。显然：对称形式的对偶问题，若已知其中一个问题，立即就可以写出相应的对偶问题。11表2.13对偶变换的规则约束条件的类型与非负条件对偶非标准的约束条件类型对应非正常的非负条件对偶变换是一一对应的12原问题（或对偶问题）对偶问题（或原问题）目标函数MaxZ目标函数MinW约

4、束条件数：m个第i个约束条件类型为“≤”第i个约束条件类型为“≥”第i个约束条件类型为“=”对偶变量数：m个第i个变量≥0第i个变量≤0第i个变量是自由变量决策变量数：n个第j个变量≥0第j个变量≤0第j个变量是自由变量约束条件数：n第i个约束条件类型为“≥”第i个约束条件类型为“≤”第i个约束条件类型为“=”13课堂练习：写出下面线性规划的对偶规划：14下面的答案哪一个是正确的？为什麽？（原问题是极小化问题，因此应从原始对偶表的右边往左边查！）√×15（二）非对称形式的对偶问题（1）如果原问题约束中包含等式约束，如AX=b等价于162.4.3对偶问题的基本性质定理1、对称

5、性定理：对偶问题的对偶是原问题。2、弱对偶定理：若X(0)是原问题的可行解,Y(0)是对偶问题的可行解,则有CX(0)≤Y(0)b.3、最优性定理：若X(0)是原问题的可行解,Y(0)是对偶问题的可行解,且有CX(0)=Y(0)b则X(0)、Y(0)分别是原问题和对偶问题的最优解。4、对偶定理：若两个互为对偶问题之一有最优解，则另一个必有最优解，且目标函数值相等。5、互补松弛性定理：X*、Y*分别是原问题和对偶问题的可行解，则X*、Y*是最优解的充分必要条件是X*YS=0和Y*XL=06、解的对应定理：原问题的单纯形表的检验数行对应其对偶问题的一个基解.由解的对应定理可知，

6、当在检验数行得到对偶问题的解可行时，原问题已达到最优解。17对偶定理是揭示原始问题的解与对偶问题的解之间重要关系的一系列定理。182.4.4对偶单纯形法什麽是对偶单纯形法？对偶单纯形法是应用对偶原理求解原始线性规划的一种方法——在原始问题的单纯形表格上进行对偶处理。注意：不是解对偶问题的单纯形法！192.4.4对偶单纯形法1、两种方法的特点单纯形法特点：在保持基可行解的情况下，每迭代一次，就使目标函数值增大一次，当问题取得最优解时，目标函数达到最大值。对偶单纯形法特点：将单纯形法应用于对偶问题的计算，在保持对偶问题有可行解的基础上，每迭代一次，就使目标函数值减少一次，当问题

7、得到最优解时，目标函数取到最小值。202、对偶单纯形法的计算步骤（1）把对偶问题化为标准形，但允许主约束条件右边常数为任意数。(注意到这里并不需引进人工变量)（2）通过对约束等式两边同乘“－1”产生初始基（单位矩阵），列出初始表。（3）确定“出基”变量：21出基原则：小于0的中最小者（绝对值最大者）所对应的行变量。即在所有<0中，对应的变量yr出基，yr所在行为主元行。原问题的进基原则：中最小对应的列变量。（4）确定“进基”变量若主元行中没有负元素，可以证明问题没有可行解，计算结束。（原问题中：若主元列都是负元素，