对偶理论与影子价格.ppt

《对偶理论与影子价格.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1第六节对偶理论与影子价格对偶问题的提出对偶问题的形式对偶问题的基本性质影子价格2对偶问题的提出例1：某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：问题：工厂应如何安排生产可获得最大的总利润？产品甲产品乙设备能力设备A3265设备B2140设备C0375利润15002500现在从另一个角度来讨论该问题：如果工厂考虑不安排生产，而准备把所有设备出租（或用于外协加工），工厂收取租金（或加工费）。试问：设备A、B、C每工时各如何收费（租金或加工费）才最有竞争

2、力？工厂为了获得最大利润，在为设备定价时，应保证生产某产品的设备工时所收取的费用不低于生产该产品的利润；同时，为了提高竞争力，应该使定价尽可能低。目标函数设x1，x2分别为生产甲乙两种产品的件数约束条件设y1，y2，y3分别为每工时设备A、B、C的收费。目标函数约束条件4解：可以建立如下的线性规划模型：目标函数约束条件化为标准型，利用单纯形法进行求解。最优解X=(5,25,0,5,0)，最优值（利润）为70000。5解：设y1，y2，y3分别为每工时设备A、B、C的收费。可以建立以下线性规划模型：化为标准型，利用单纯形法进行求解。最优解Y=(500,0,5

3、00,0,0)最优值（收费）为70000。6原问题对偶问题7原问题对偶问题目标函数MaxMin约束条件≤≥系数矩阵AAT资源常数bc目标系数cb2个变量2个约束3个约束3个变量解检验数检验数解可以看到，这两个问题关系密切，用同样的原始数据：线性规划有一个有趣的特性，就是对于任何一个求极大的线性规划问题都存在一个与其匹配的求极小的线性规划问题，并且这一对线性规划问题的解之间还存在着密切的关系。线性规划的这个特性称为对偶性。对这两个线性规划问题，一般称前者为原问题，后者是前者的对偶问题8对偶问题的形式9如果线性规划问题的变量均具有非负约束，其约束条件当目标函

4、数求极大值时均取“≤”，当目标函数求极小值时均取“≥”，则称具有对称形式。对称形式下原问题和对偶问题的形式：（LP）“Max——≤”s.t.（DP）“Min——≥”s.t.一对对称形式的对偶规划之间具有下面的对应关系：1.若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，≤”和“min，≥”相对应。2.从约束系数矩阵看：一个模型中为Ａ，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量3.从数据b、C的位置看：在两个规划模型中，b和C的位置对换

5、4.两个规划模型中的变量皆非负1011MaxzMinfx1x2…xnxi≥0y1a11a12…a1n≤b1y2a21a22…a2n≤b2……………≤…ymam1am2…amn≤bmyi≥0c1c2…cn≥≥≥≥一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。对于非对称形式的规划，可以按照下面的对应关系进行处理并给出其对偶规划：1.将模型统一为“max，≤”或“min，≥”的形式，对于其中的等式约束按下面的方法处理；2.若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；3.若原规划的某个变量的值没有非负限制，则

6、在对偶问题中与此变量对应的那个约束为等式。也可以直接给出其对偶规划。12例2：写出下面线性规划的对偶规划模13解：先化为对称形式（Max—≤）“≥”的约束两端同乘以“–1”“=”的约束等价转换为“≤”和“≥”的两个约束，再变换变量≤0，用变量替换，如变量无非负限制，用变量替换，如14写出对偶问题：15变量替换，令16把对偶问题和原问题进行比较17Maxz=x1+4x2+3x3s.t.2x1+3x2–5x3≤2原问题3x1–x2+6x3≥1x1+x2+x3=4x1≥0，x2≤0，x3没有非负限制Minf=2y1+y2+4y3s.t.2y1+3y2+y

7、3≥1对偶问题3y1–y2+y3≤4–5y1+6y2+y3=3y1≥0，y2≤0，y3无非负限制由此得到非对称形式的线性规划原问题和对偶问题的对应关系（对称形式也适用）18原问题对偶问题A约束系数矩阵约束系数矩阵的转置b约束条件右端项目标函数中的系数C目标函数中的系数约束条件右端项目标函数Maxz=ΣcjxjMinz=Σbiyi变量n个xj≥0(≤0，无限制)约束条件n个Σaijyj≥(≤，=)cj约束条件m个Σaijxj≤(≥，=)bi变量m个yi≥0(≤0，无限制)对偶问题的基本性质对偶问题的基本性质对对称形式和非对称形式都是同样适用的，但为了方便，在

8、说明或证明时以对称形式为例（非对称形式可以化为对称形式）对称形式下