《管理运筹学》第3章--线性规划的对偶问题说课材料.ppt

《《管理运筹学》第3章--线性规划的对偶问题说课材料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《管理运筹学》第3章--线性规划的对偶问题每一个线性规划问题都有一个与之相伴随的另一个问题。这两个问题：一是，在数学模型上有着对应关系；二是，从一个问题的最优解完全可以得出另一个问题最优解的全部信息。3.1.1问题的提出例1引入一个资源价格问题。§3-1线性规划的对偶理论2类似于第2章例1的生产计划问题。某企业生产甲、乙两种产品，需消耗A、B、C三种材料。据市场分析，单位甲、乙产品的销售收益分别为4万元和5万元。单位甲、乙产品对材料的消耗量及材料的供应量如表3.1所示。原问题：应如何制定生产计划，使总收益为最大。表3

2、.1产品材料甲乙供应量A1145B2180C1390收益4万元/单甲5万元/单乙3运用单纯形法，可求得其最优解为：设计划安排：x1为甲产品的产量，x2为乙产品的产量。（决策变量）则，该问题的数学模型为：4新问题：现在从另一角度来讨论这个问题。假设该企业经过市场预测，准备进行转产，且把现有三种材料进行转让，也恰好有一个制造商急需这批材料。于是买卖双方开始对资源的出让价格问题进行磋商，希望寻找一个双方都认为比较满意的合理价格。分析：设A、B、C三种材料的单价分别为y1、y2、y3.对于卖方来说，生产单位甲产品所获收益为4

3、万元，为保证其总收入不少于405/2万元，则将生产单位甲产品所需资源转让出去，该企业的收入不能少于4万元。故y1、y2、y3必须满足约束条件：y1+2y2+y3≥4同样，将生产单位乙产品所需的资源转让出去，其收入不能少于生产单位乙产品的收益5万元，所以y1、y2、y3还必须满足约束条件：y1+y2+3y3≥55对于买方来说，他希望在满足上述约束条件下使总的支出W（y）=45y1+80y2+90y3达到最小。综上所述，资源价格问题的数学模型可描述为：上述两个模型（3-1）和（3-2）是对同一问题的两种不同考虑的数学描述

4、，其间有着一定的内在联系，将逐一剖析。6首先，分析这两个模型之间的对应关系：（1）一个问题的目标函数为极大化，约束条件为“≤”类型，另一个问题的目标为极小化，约束条件为“≥”类型；（2）一个问题的变量个数等于另一个问题的约束条件个数；（3）一个问题的右端常数（约束系数）是另一个问题的目标函数的系数（成本系数）；（4）两个问题的系数矩阵互为转置。我们把这种对应关系称为对偶关系。如果把（3-1）称为原始问题，则（3-2）称为对偶问题。73.1.2对称型线性规划问题——对称型对偶问题每一个线性规划问题都必然有与之相伴随的对

5、偶问题存在。先讨论对称型对偶问题；对于非对称型对偶问题，可以先转化为对称型，然后再进行分析，也可以直接从非对称型进行分析。对称型线性规划问题数学模型的一般形式为Y1Y2…ym8这种模型的特点是：（1）目标函数是最大化类型(或是最小化类型)；（2）所有约束条件都是“≤”型（或都是“≥”型）；（3）所有决策变量都是非负的。如果把（3-3）作为原始问题，根据原始与对偶问题的对应关系可得（3-3）的对偶问题为9用矩阵表示的原始问题（3-3）和对偶问题（3-4）为其中Y=（y1,y2,…,ym）,其它同前。3.1.3一般问题的

6、对偶问题——非对称型对偶问题线性规划有时以非对称型出现，那么如何从原始问题写出它的对偶问题呢？10解：（1）首先把上述非对称型问题化为对称型问题。①在第一个约束条件的两边同×（-1）②把第三个约束方程分解成两个x1-x2+3x3≤0和x1-x2+3x3≥0再将后一个两边同×（-1）改写成-x1+x2-3x3≤0例1写出下列线性规划的对偶问题11③转换成对称型（2）写出相应的对偶问题（4个约束，分别对应4个对偶变量y1、y2、y/3、y//3）Y1Y2Y/3y//312再设y/3-y//3=y3，代入上述模型

7、得：13解：（1）首先把上述非对称型问题化为对称型问题。①在第一个约束条件的两边同×（-1）②把第三个约束方程分解成两个x1-x2+3x3≤0和x1-x2+3x3≥0再将后一个两边同×（-1）改写成-x1+x2-3x3≤0例2将例1模型中的x2改为无非负约束变量，即模型为写出其对偶问题14③令x2=x/2-x//2.其中x/2,x//2≥0④转换成对称型（2）写出相应的对偶问题（4个约束，分别对应4个对偶变量y1、y2、y/3、y//3）Y1Y2Y/3y//315令y/3-y//3=y3,并将第二和第三个条

8、件合并为方程，得16综合上述两个例子，可以看出，线性规划与其对偶模型的关系有了新的拓展：（1）一个问题的目标函数为极大化，约束条件为“≤”或“=”类型，另一个问题的目标为极小化，约束条件为“≥”或“=”类型；（2）一个问题的变量个数等于另一个问题的约束条件个数；（3）一个问题的右端常数（约束系数）是另一个问题的目标函数的系数（成本系数）；（4）