课件下部分2015对偶

1、OPERATIONS RESEARCH (运筹学/管理科学)光华管理学院 雷 明 第五章 对偶问题Dual Problem【例1】 某企业用四种资源生产三种产品，工艺系数、资源限量及利润系数如下表： 产品资源A B C 资源限量9 8 6 5005 4 7 4508 3 2 3007 6 4 550每件产品利润100 80 70企业如何决策。 【解】设x1，x2，x3分别为产品A，B，C的产量，则线性规划数学模型为： 这是一个线性规划数学模型，称这一线性规划问题是前面问题的对偶线性规划问题或对偶问题。原问题称为原始线性规划问题或原问题。【例2】某人根据医嘱，每天需补充A、B、C三种营养，A不少

2、于80单位，B不少于150单位，C不少于180单位。此人准备每天从六种食物中摄取这三种营养成分。已知六种食物每百克的营养成分含量及食物价格如下表，试建立此人在满足健康需要的基础上花费最少的数学模型。营养成分一二三四五六需要量A1325144081180B24930251215150C1872134100180食物单价（元/100g）0.50.40.80.90.30.2含量 食物【解】设xj为每天第j种食物的用量，数学模型为设原问题是（记为LP）： 对偶问题是（记为DP）： 根据对偶性质6，可以构造一个求线性规划的另一种方法，即对偶单纯形法。对偶单纯形法的条件是：初始表中对偶问题可行，即极大化问

3、题时j0，极小化问题时j0。原问题和对偶问题是互为对偶的两个线性规划问题，已知一个问题就可写出另一个问题。 六个对偶性质: 这些性质是研究原问题与对偶问题解的对应关系性质2通过解方程无可行解无界解（有可行解）性质4有最优解有最优解性质6性质5性质4求得基本解求最优解无界解（有可行解）无最优解另一个问题min检验数乘以1已知检验数已知最优解无可行解无最优解一个问题max应用无最优解【例3】写出下列线性规划的对偶问题【例4】 写出下列线性规划的对偶问题若给出的线性规划不是对称形式，可以先化成对称形式再写对偶问题。也可直接写出。例如，原问题是求最小值1. 第i个约束是“ ”约束时，第i个对偶变量yj

4、0 2第i个约束是“ = ”约束时，第i个对偶变量yi无约束；3当xj0时，第j个对偶约束为“ ”约束，当xj无约束 时 ，第j个对偶约束为“ = ”约束。 （1）将线性规划的约束化为等式，求出一组基本解，（2）先确定出基变量。 （3）再选进基变量。（4）求新的基本解，得到新的基本解，转到第一步重复运算。 对偶单纯形法的计算步骤：介绍了如何写对称与非对称问题的对偶问题;1. 应该会写任意线性规划的对偶问题；2.深刻领会影子价格的含义，学会用影子价格作经济活动分析。2.4 影子价格(Shadow price)即yi是第i种资源的变化率，说明当其它资源供应量bk(ki)不变时，bi增加一个单位时目

5、标值Z增加yi个单位。影子价格的经济含义 (1)影子价格是对现有资源实现最大效益时的一种估价（2）影子价格表明资源增加对总效益产生的影响 2.6 灵敏度分析1灵敏度分析： 当某一个参数发生变化后，引起最优解如何改变的分析。 可以改变的参数有：bj；cj ；pj ； 其他的变化有：增加一种新产品、增加一道新的工序等。2 图 解 法例目标函数： Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E)得到最优解： x1 = 50， x2 = 250 最优目标值 z = 275003.1 目标函数中的系数 ci 的灵敏度分析3.2 约束条件中右边系数 bj 的灵敏度分析百分之一百法则：例： 某大学教授利用部分业余时间从事咨询工作。现有三个A、B、C企业欲聘请，各自每小时的咨询费用分别为10，12，16元。教授每月可用于外出咨询的时间为40小时，但对每个企业而言，用于准备的时间与咨询所花的时间的比例分别为0.1，0.5，0.8，教授每月可用于准备的时间应不超过24小时。若假定三个企业每月要求的咨询时间可分别达到80，60，20小时。现问：教授应作何种决策，才能使收益最大？ 从目前看，教授