第2章：线性规划的对偶理论和灵敏度分析l.ppt

《第2章：线性规划的对偶理论和灵敏度分析l.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性规划的对偶理论和灵敏度分析2.1单纯性法的矩阵描述和改进的单纯性法***2.2对偶问题的提出与线性规划的对偶理论**2.3影子价格与对偶单纯性法***2.4灵敏度分析2.1单纯形法的矩阵描述为了便于利用计算机求解大规模的线性规划问题，所以需要讨论单纯形法的矩阵描述。2.1单纯形法的矩阵描述不妨设基为基变量非基变量设线性规划问题则单纯形法的矩阵描述令得当前的基解为：当前基解约束方程组当前目标值目标函数令得当前的目标函数值为：单纯形法的矩阵描述单纯形法的矩阵描述检验数计算连续进行迭代运算直到所有的检验数≤0为止，见下表所示。…

2、…检验数矩阵0系数矩阵谁知道矩阵单纯形法的迭代终止条件和解的几种不同情况？改进/矩阵单纯形法的求解步骤*****课堂练习我们也来练习练习矩阵单纯形法@@@@@例如将例1.1化成标准形目标函数MaxZ=2x1+3x2约束条件x1+2x284x1164x212x1，x20线性规划的一般模型线性规划的标准模型加入了松弛变量x3,,x4,x5表示没有被利用的资源，所以没有利润，故相应的价值系数均为零。2.2对偶问题的提出与线性规划的对偶理论对偶问题是指对同一事物从不同的角度（立场）观察的两种相互对立的表述，如“平面中矩形的面积与周长

3、的关系”：周长一定时，面积最大的矩形是正方形——面积一定时，周长最短的矩形是正方形。2.2.1对偶问题的提出对于例1.1生产计划的线性优化问题，现从它的对偶角度来分析，即假设该工厂的决策者决定不生产产品Ⅰ和Ⅱ，而是将其所有的资源出租或外售，这时就要考虑给每种资源如何定价的问题：如果用分别表示出租单位设备台时的租金和出让单位原材料A,B的附加额；约束条件为“用1个单位设备台时和4个单位原材料A可以生产一件产品I，可获利2元，因此生产每件产品I的设备台时和原材料的出租（或出让）的收入应不低于生产一件产品I的利润，其数学表述为同理，对于Ⅱ

4、可得出租或出让的收入函数为对于决策者而言，愈大愈好，但接受者当然是支付愈少愈好，所以决策者要想实现其目的，就必须在满足大于等于所有产品的利润条件下，提出一个尽可能低的出租或出让价格，这样就得到一个与例1.1对偶的线性规划模型如下：线性规划原问题线性规划原问题的对偶线性规划原问题线性规划原问题的对偶有何规律？对偶问题收购原问题厂家再如非对称形式下二者之间的关系如何？对偶问题收购目标函数的右端目标函数的变量系数目标函数的变量系数目标函数的右端原线性规划问题（或对偶）原线性规划问题（或对偶）一对对偶问题对偶问题原问题直接法求上述线性规划问

5、题的对偶还难吗？对偶问题还难吗？原问题直接法求上述线性规划问题的对偶对偶问题原问题直接法求上述线性规划问题的对偶还难吗？对偶问题还难吗？原问题直接法求上述线性规划问题的对偶对偶问题请同学们利用间接法和直接法求例1.3线性规划问题的对偶原问题对偶问题原问题请同学们利用间接法和直接法求例1.3线性规划问题的对偶对偶问题原问题2.2.2线性规划的对偶理论与基本性质*对称性弱对偶性无界性最优性对偶定理（强对偶性）互补松弛性对偶关系在单纯形表中的关系还原了对偶问题对称性的一个实例——试求例1.1的对偶的对偶，你会发现什么？还原了对偶问题的基本

6、性质一、对称定理：对偶问题的对偶是原问题。设原问题（1）对偶问题（2）对称定理揭示了线性规划的对偶运算满足幂等律线性规划对偶的对偶是什么？二、弱对偶性定理：若和分别是原问题及对偶问题的可行解，则有三、互对偶最优解性质若和分别是原线性规划和其对偶的可行解，且满足四、对偶定理（强对偶性）：若原问题（对偶问题）存在最优解对偶问题（原问题）必存在最优解，且它们最优解的目标函数值相等。五、互补松弛性若分别是原问题与其对偶问题的可行解，则，其中分别为原问题及其对偶问题的松弛变量。为最优解六：对偶问题的无界性若原问题（//对偶问题）为无界解，则其

7、对偶问题（//原问题）无可行解或具有无界解。（逆命题不成立）利用对偶定理和互补松弛定理求解线性规划的实例图像法对偶无可行解例2.4：利用线性规划的对偶性质求解下面问题可行域为空集原问题存在可行解（0，0）若有最优解，则其对偶必有最优解。例2.5：已知线性规划问题及其对偶问题的最优解为请利用对偶性质求原问题的最优解？在单纯形法的每步迭代中，目标函数取值，和检验数中都有乘子，那么Y的经济意义是什么？影子价格——对偶问题的经济解释对偶变量的意义——代表在资源最优利用条件下对单位第种资源的估价，这种估价不是资源的市场价格，而是根据资源在生产

8、中作出的贡献而作的估价，为区别起见，称为影子价格（shadowprice)。影子价格的定义1．资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子