运筹学-2对偶理论与灵敏度分析.ppt

* * * 现把对偶单纯形法的基本步骤总结如下 ? 第一? 把所给的线性规划问题转化为标准型； 第二? 找出一个初始正则基B0，要求对应的单纯形表中的全部检验数 ，但“右边”列中允许有负数； 第三? 若“右边”列中各数均非负，则B0已是最优基，于是，已求得最优解，计算终止。否则转为第四步； 第四? 换基：“右边”列中取值最小（即负的最多）的数所对应的变量为出基变量。为决定进基变量，必须按公式（2.14）计算最小比值θ。最小比值出现在末列，则该列所对应的变量即为进基变量，换基后得新基B1，以出基变量的行和进基变量列交点处的元素为主元进行单纯形迭代，再转入第三步。 * * * * * 显然，当线性规划问题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。当然可以用单纯形法从头计算，以便得到新的最优解。这样做很麻烦，而且也没有必要。因在单纯形法迭代时，每次运算都和基变量的系数矩阵B有关，因此可以把发生变化的个别系数，经过一定计算后直接填入最终计算表中，并进行检查和分析，可按表2-9中的几种情况 进行处理。 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 的最优单纯形表为： X1 X2 X3 X4 X5 X6 X7 常数项 X5 1/4 0 -13/4 0 1 1/4 -1 100 X4 2 0 -2 1 0 1 -1 200 X2 -3/4 1 11/4 0 0 -3/4 1 100 检验数 -13/4 0 -11/4 0 0 -1/4 -1 -1300 1、为保持现有最优解不变，分别求出C1， C2的变化范围。 2、当C1变为5时，求新的最优解。 3、当C2变为2， C4变为6时，求新的最优解。 上机练习 EXCEL WINQSB LINGO/LINDO MATLAB 目的：充分发挥WinQSB软件的强大功能和先进的计算机工具，改变传统的教学手段和教学方法，将软件的应用引入到课堂教学，理论与应用相结合。丰富教学内容，提高学习兴趣。使学生能基本掌握WinQSB软件常用命令和功能。 要求：熟悉WinQSB软件子菜单。能用WinQSB软件求解运筹学中常见的数学模型。 实验一：线性规划 （一）实验目的：安装WinQSB软件，了解WinQSB软件在Windows环境下的文件管理操作，熟悉软件界面内容，掌握操作命令。用WinQSB软件求解线性规划。 （二）内容和要求：安装与启动软件，建立新问题，输入模型，求解模型，结果的简单分析。 WinQSB软件求解LP不必化为标准型，如果是可以线形化的模型则先线性化，如绝对值约束。 （三）操作步骤： 1.将WinQSB文件复制到本地硬盘；在WinQSB文件夹中双击setup.exe。 2.指定安装WinQSB软件 3.熟悉WinQSB软件子菜单内容及其功能，掌握操作命令。 4．求解线性规划。启动程序 开始→程序→WinQSB→Linear and Integer Programming 。 5．学习例题 点击File→Load Problem→lp.lpp, 点击菜单栏Solve and Analyze或点击工具栏中的图标用单纯形法求解，学习软件用单纯形法迭代步骤。 用图解法求解，显示可行域，点击菜单栏Option →Change XY Ranges and Colors，改变X1、X2的取值区域（坐标轴的比例），单击颜色区域改变背景、可行域等8种颜色，满足你的个性选择。 * * * * * * * * * * * * * * * * * * * * * 所以， X*=（2 . 2 . 2 . 0 . 0 . 0）， Z′* =－72， 原问题 Z* =72 其对偶问题的最优解为： Y*= (1/3 . 3 . 7/3)，W*= 72 总 结 第五节 灵敏度分析 以前讨论线性规划问题时，假定αij，bi,cj都是常数。但实际上这些系数往往是估计值和预测值。 如市场条件一变，cj值就会变化；αij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。 引言 (1)当这些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化； (2)或者这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变。 因此提出这样两个问题： 灵敏度分析一词的含义是：指对系统