2019年运筹学对偶理论课件.ppt

《2019年运筹学对偶理论课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、对偶理论DualTheory2.1线性规划的对偶模型DualModelofLP2.2对偶性质Dualproperty2.3对偶单纯形法DualSimplexMethod2.4灵敏度与参数分析SensitivityandParametricAnalysis运筹学OperationsResearch2.1线性规划的对偶模型DualModelofLP在线性规划问题中，存在一个有趣的问题，即每一个线性规划问题都伴随有另一个线性规划问题，称它为对偶线性规划问题。【例2.1】某企业用四种资源生产三种产品，工艺系数、资源限量及价值系数如下表：建立总收益最大

2、的数学模型。产品资源ABC资源限量Ⅰ986500Ⅱ547450Ⅲ832300Ⅳ764550单件产品利润10080702.1线性规划的对偶模型DualmodelofLP【解】设x1，x2，x3分别为产品A，B，C的产量，则线性规划数学模型为：现在从另一个角度来考虑企业的决策问题。假如企业自己不生产产品，而将现有的资源转让或出租给其它企业，那么资源的转让价格是多少才合理？合理的价格应是对方用最少的资金购买本企业的全部资源，而本企业所获得的利润不应低于自己用于生产时所获得的利润。这一决策问题可用下列线性规划数学模型来表示。2.1线性规划的对偶模型D

3、ualmodelofLP设y1，y2，y3及y4分别表示四种资源的单位增值价格（售价＝成本＋增值），总增值最低可用minw=500y1+450y2+300y3+550y4表示。企业生产一件产品A用了四种资源的数量分别是9，5，8和7个单位，利润是100,企业出售这些数量的资源所得的利润不能少于100，即同理，对产品B和C有价格不可能小于零，即有yi≥0,i=1,…,4.从而企业的资源价格模型为2.1线性规划的对偶模型DualmodelofLP这是一个线性规划数学模型，称这一线性规划模型是前面生产计划模型的对偶线性规划模型,这一问题称为对偶问题

4、。生产计划的线性规划问题称为原始线性规划问题或原问题。2.1线性规划的对偶模型DualmodelofLP上面两种形式的线性规划称为规范形式。原问题和对偶问题是互为对偶的两个线性规划问题，已知一个问题就可写出另一个问题。规范形式（CanonicalForm）的定义：目标函数求极大值时，所有约束条件为≤号，变量非负；目标函数求极小值时，所有约束条件为≥号，变量非负。规范形式的线性规划的对偶问题亦是规范形式。以上是依据经济问题推导出对偶问题，还可以用代数方法推导出对偶问题。2.1线性规划的对偶模型DualmodelofLP原始问题Maxz=CTXs

5、.t.AX≤bX≥0对偶问题Minw=bTys.t.ATy≥Cy≥0≤maxbACTCATbT≥minmnmn对偶的定义规范对偶问题minz=CTXs.t.AX≥bX≥0maxw=bTys.t.ATy≤Cy≥0maxz=CTXs.t.AX≤bX≥0minw=bTys.t.ATy≥Cy≥0XBXNXSbXBBNEbCCBCN00XBXNXSbXBEB－1NB－1B－1bλ0CN－CBB－1N－CBB－1－CBB－1b表2-2表2－32.1线性规划的对偶模型DualmodelofLP设线性规划模型是式（2.1）的规范形式．由表2-3知，当检验数时

6、得到最优解，是的检验数,和,令,由得在两边有乘b,则有,又因Y≥0无上界,从而只存在最小值，得到另一个线性规划问题2.1线性规划的对偶模型DualmodelofLP即是原线性规划问题式（2.1）的对偶线性规划问题，反之，式（2.3）的对偶问题是式（2.1）．原问题和对偶问题是互为对偶的两个线性规划问题，规范形式的线性规划的对偶仍然是规范形式，参数矩阵的对应关系参看表2-4．因此已知一个规范形式问题就可写出另一个对偶问题．2.1线性规划的对偶模型DualmodelofLP【例2.2】写出下列线性规划的对偶问题【解】这是一个规范形式的线性规划，设

7、Y=（y1，y2），则有2.1线性规划的对偶模型DualmodelofLP从而对偶问题为对偶变量yi也可写成xi的形式。2.1线性规划的对偶模型DualmodelofLP【例2.3】写出下列线性规划的对偶问题【解】这是一个规范形式的线性规划，它的对偶问题求最小值，有三个变量且非负，有两个“≥”约束，即2.1线性规划的对偶模型DualmodelofLP若给出的线性规划不是规范形式，可以先化成规范形式再写对偶问题。也可直接按表2-1中的对应关系写出非规范形式的对偶问题。将上述原问题与对偶问题的对应关系列于表2-1例如，原问题是求最小值，按表2-1

8、有下列关系：1.第i个约束是“≤”约束时，第i个对偶变量yj≤02．第i个约束是“=”约束时，第i个对偶变量yi无约束；3．当xj≤0时，第j个对偶约束为“≥”约束