第2章对偶理论和灵敏度分析-第3节

《第2章对偶理论和灵敏度分析-第3节》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、运筹学（第三版）《运筹学》教材编写组编写清华大学出版社第2章对偶理论和灵敏度分析第3节对偶问题的提出钱颂迪制作第2章对偶理论和灵敏度分析第3节对偶问题的提出第3节对偶问题的提出对偶是什么：是指对同一事物（或问题），从不同的角度（或立场）进行观察,提出对立的两种不同的表述。例如在平面内，矩形的面积与其周长之间的关系，有两种不同的表述方法。（1）周长一定，面积最大的矩形是正方形。（2）面积一定，周长最短的矩形是正方形。这是互为对偶关系的表述。这种表述有利于加深对事物的认识和理解。线性规划问题也有对偶关系。第1章例1的不同表述现对第1章例1,我们从另一角度来讨论这个问

2、题。假设该工厂的决策者决定不生产产品Ⅰ、Ⅱ，而将其所有资源出租或外售。这时工厂的决策者就要考虑给每种资源如何定价的问题。设用y1，y2，y3分别表示出租单位设备台时的租金和出让单位原材料A，B的附加额。他在做定价决策时，做如下比较：若用1个单位设备台时和4个单位原材料A可以生产一件产品Ⅰ，可获利2元，那么生产每件产品Ⅰ的设备台时和原材料出租或出让的所有收入应不低于生产一件产品Ⅰ的利润，这就有y1+4y2≥2同理将生产每件产品Ⅱ的设备台时和原材料出租或出让的所有收入应不低于生产一件产品Ⅱ的利润，这就有2y1+4y3≥3把工厂所有设备台时和资源都出租或出让，其收入为

3、ω=8y1+16y2+12y3从工厂的决策者来看当然ω愈大愈好；但受到接受方的制约，从接受者来看他的支付愈少愈好，所以工厂的决策者只能在满足大于等于所有产品的利润条件下，提出一个尽可能低的出租或出让价格，才能实现其原意，为此需解如下的线性规划问题minω=8y1+16y2+12y3y1+4y2≥22y1+4y3≥3yi≥0，i=1,2,3(2-8)称这个线性规划问题为例1线性规划问题(这里称原问题)的对偶问题。这就是从另一角度提出的线性规划问题。进一步讨论它们之间的关系从第2章第1节得到检验数的表达式是CN-CBB-1N与-CBB-1在第1章已提到，当检验数CN

4、-CBB-1N≤0(2-9)-CBB-1≤0(2-10)这表示线性规划问题已得到最优解。这也是作为得到最优解的判断条件。现在讨论这两个条件(1)(2-9)式，(2-10)式中都有乘子CBB-1，称它为单纯形乘子，用符号Y=CBB-1表示。由(2-10)式，可得到Y≥0(这表明Y取值上界无限大)(2)对应基变量XB的检验数是0。它是CB-CBB-1B=0。包括基变量在内的所有检验数可用C-CBB-1A≤0表示。从此可得C-CBB-1A=C-YA≤0移项后，得到YA≥C(3)Y由(2-10)式，得到-Y=-CBB-1(2-11)将(2-11)式两边右乘b，得到-Yb

5、=-CBB-1b(2-12)Yb=CBB-1b=z因Y的上界为无限大，所以只存在最小值.(4)从这里可以得到另一个线性规划问题minω=YbYA≥CY≥0称它为原线性规划问题｛maxz=CX｜AX≤b，X≥0｝的对偶规划问题对偶规划问题课堂练习:用单纯形法求解例1对偶线形规划问题的最优解.