运筹学02对偶理论线性规划的对偶模型,对偶性质

《运筹学02对偶理论线性规划的对偶模型,对偶性质》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter3对偶理论DualTheory3.1线性规划的对偶模型DualModelofLP3.2对偶性质Dualproperty3.3对偶单纯形法DualSimplexMethod3.4灵敏度与参数分析SensitivityandParametricAnalysis运筹学OperationsResearch3.1线性规划的对偶模型DualModelofLP例3.1(原例1.1)某工厂生产甲、乙两种产品。这些产品分别要在A、B、C三种不同的设备上加工。企业决策者应如何安排生产计划，使企业总的利润最大？3

2、.1线性规划的对偶模型DualmodelofLP解：设x1、x2分别为甲、乙两种产品的产量，Z为总利润，则数学模型为：3.1线性规划的对偶模型DualmodelofLP现在从另一个角度来考虑企业的决策问题。假如企业不考虑自己生产产品，而将现有的资源标价出售，问题：决策者应怎样给定资源一个合理的价格？设y1，y2，y3分别表示三种资源的单位增值价格(售价＝成本＋增值)，总增值最低可用minw=36y1+40y2+76y3表示。企业生产一件产品甲用了四种资源的数量分别是3，5和9个单位，利润是32,企业出售这

3、些数量的资源所得的利润不能少于32，即同理，对产品乙有3.1线性规划的对偶模型DualmodelofLP这是一个线性规划数学模型，称这一线性规划模型是前面生产计划模型的对偶线性规划模型,这一问题称为对偶问题。生产计划的线性规划问题称为原始线性规划问题或原问题。3.1线性规划的对偶模型DualmodelofLP价格不可能小于零，即有yi≥0(i=1,…,4),从而企业的资源价格模型为注：以上两问题是同一组数据参数，只是位置有所不同，所描述的问题实际上是从两个不同的角度去描述。原始线性规划问题考虑的是充分利用

4、现有资源，以产品数量和单位产品的利润来决定企业的总利润，没有考虑资源的价格，实际上在构成产品的利润中，不同的资源对利润的贡献也不同，它是企业生产过程中一种隐含的潜在价值，经济学中称为影子价格。3.1线性规划的对偶模型DualmodelofLP线性规划问题(3.2)就是原线性规划问题(3.1)的对偶线性规划问题，反之，(3.2)的对偶问题就是(3.1)．3.1线性规划的对偶模型DualmodelofLP原问题与对偶问题有如下关系(假设原问题(3.1))：(1)原问题的约束个数(不含非负约束)等于对偶变量的个

5、数(2)原问题的目标函数系数对应于对偶问题的右端项(3)原问题的右端项对应于对偶问题的目标函数系数(4)原问题的约束矩阵转置就是对偶问题系数矩阵(5)原问题求最大，对偶问题是求最小(6)原问题不等式约束符号为“≤”,对偶问题不等式约束符号为“≥”【例3.2】写出下列线性规划的对偶问题【解】设Y=(y1，y2)，则有3.1线性规划的对偶模型DualmodelofLP从而对偶问题为【例3.3】写出下列线性规划的对偶问题【解】该线性规划的对偶问题是求最小值，有三个变量且非负,有两个“≥”约束,即3.1线性规划的

6、对偶模型DualmodelofLP线性规划问题的规范形式(CanonicalForm或叫对称形式)：定义：目标函数求极大值时，所有约束条件为≤号，变量非负；目标函数求极小值时，所有约束条件为≥号，变量非负。3.1线性规划的对偶模型DualmodelofLP注：(1)线性规划规范形式与标准型是两种不同形式，但可以相互转换。(2)规范形式的线性规划问题的对偶仍然是规范形式．原问题(或对偶问题)对偶问题(或原问题)目标函数max目标函数系数(资源限量)约束条件系数矩阵A(AT)目标函数min资源限量(目标函数系

7、数)约束条件系数矩阵AT(A)变量n个变量第j个变量≥0第j个变量≤0第j个变量无约束约束n个约束第j个约束为≥第j个约束为≤第j个约束为=约束m个约束第i个约束≤第i个约束≥第i个约束为=变量m个变量第i个变量≥0第i个变量≤0第i个变量无约束3.1线性规划的对偶模型DualmodelofLP问题：讨论一般形式的线性规划问题的对偶问题？方法：先将其转化为规范形式的线性规划问题，然后写出其对偶问题，适当将其进行化简。3.2对偶性质(了解)Dualproperty对偶问题是(记为DP)：这里A是m×n矩阵,

8、X是n×1列向量,Y是1×m行向量。【性质1】对称性:对偶问题的对偶是原问题。设原问题是(记为LP)：3.2对偶性质Dualproperty3.2.1对偶性质【性质2】弱对偶性:设X*、Y*分别为LP(max)与DP(min)的可行解，则3.2对偶性质Dualproperty由这个性质可得到下面几个结论：(LP)的任一可行解的目标值是(DP)的最优值下界；(DP)的任一可行解的目标是(LP)的最优值的上界；(2)在互为对偶的两