线性规划问题及灵敏度分析.doc

实验一 线性规划问题及灵敏度分析 实验目的：了解WinQSB软件在Windows环境下的文件管理操作，熟悉软件界面内容，掌握操作命令。用WinQSB软件求解线性规划，掌握winQSB软件写对偶规划，灵敏度分析和参数分析的操作方法。实验每组人数及学时：组人数1人，学时数：4学时实验环境：装有WinQSB软件的个人电脑实验类型：验证性实验内容：一、 用WinQSB软件求解线性规划的方法：操作步骤：1.将WinQSB文件复制到本地硬盘；在WinQSB文件夹中双击setup.exe。2.指定安装WinQSB软件的目标目录（默认为C: WinQSB）。3. 安装过程需输入用户名和单位名称（任意输入），安装完毕之后，WinQSB菜单自动生成在系统程序中。4.熟悉WinQSB软件子菜单内容及其功能，掌握操作命令。5求解线性规划。启动程序 开始程序WinQSBLinear and Integer Programming 。6学习例题 点击FileLoad Problemlp.lpp, 点击菜单栏Solve and Analyze或点击工具栏中的图标用单纯形法求解，观赏一下软件用单纯形法迭代步骤。用图解法求解，显示可行域，点击菜单栏Option Change XY Ranges and Colors，改变X1、X2的取值区域（坐标轴的比例），单击颜色区域改变背景、可行域等8种颜色，满足你的个性选择。下面结合例题介绍WinQSB软件求解线性规划的操作步骤及应用。 用WinQSB软件求解下列线性规划问题：s.t. 解：应用WinQSB软件求解线性规划问题不必化为标准型，如果是可以线性化的模型则先线性化，对于有界变量及无约束变量可以不用转化，只需要修改系统的变量类型即可，对于不等式约束可以在输入数据时直接输入不等式符号。（1）启动线性规划（LP）和整数规划（ILP）程序点击开始程序WinQSBLinear and Integer Programming，显示线性规划和整数规划工作界面（注意菜单栏、工具栏和格式栏随主窗口内容变化而变化）。这一程序解决线性规划（LP）以及整数线性规划（ILP）问题。IP-ILP的特殊性能包括：LP的单纯形法与图形法ILP的分枝定界法显示单纯形表显示分枝定界法解决方案执行灵敏性或参数分析寻求可选择的解决对不可行问题进行不可行分析用电子表格矩阵式输入问题用普通模型形式输入问题定制变量边界与类型图1-1 LP-ILP模块的主要功能自动生成对偶问题（2）建立新问题或者打开磁盘中已有的文件点击FileNew Problem建立一个新问题。输入本问题的文件名称lp1（读者可以任意取名），决策变量个数4和约束条件个数5，由于本问题是一个最大化问题，所以选择Maximization，同时可以确定数据的输入形式，一种为表单形式，一种为模型形式。如果我们选择了表单形式，如图2-1所示。（3）输入数据按照例1以表格或模型形式输入变量系数和右端常数数据。决策变量个数目标函数取极大还是极小进行选择数据输入方式选择：表单式、一般模型形式数据类型定义约束条件个数图1-2 LP-ILP模型基础设定（4）修改变量类型图1-3种给出了非负连续、非负整数、0-1型和无符号限制或者无约束4种变量类型选项，当选择了某一种类型后系统默认所有变量都属于该种类型。在例1中，直接将中的下界（Lower Bound）改为10，上界（Upper Bound）改为20。把设定为无约束（Unrestricted），M是一个任意大的正数。 得到如表1-1所示的表格。 表1-1 初始单纯型表（5）修改变量名和约束名。系统默认变量名为X1，X2，Xn，约束名为C1，C2，Cm。默认名可以修改，点击菜单栏Edit后，下拉菜单有四个修改选项：修改标题名(Problem Name)、变量名(Variable Name)、约束名(Constraint Name)和目标函数准则(max或min)。由于WinQSB软件支持中文，读者可以输入中文名称。（6）求解点击菜单栏Solve and Analyze，下拉菜单有三个选项：求解不显示迭代过程（Solve the Problem）、求解并显示单纯形法迭代步骤(Solve and Display Steps)及图解法(Graphic Method，限两个决策变量)。如选择Solve the Problem，系统直接显示求解的综合报告如表1-2所示，表中的各项含义见表1-5。线性规划问题有最优解或无最优解（无可行解或无界解），系统会给出提示。表1-2 winqsb线性规划求解的综合报告由表1-2得到例1的最优解为，最优值。同时由表2的第6行提示Alternate Solution Exists!知原线性规划问题有多重解。（7）显示结果分析点击菜单栏result或者点击快捷方式图标，存在最优解时，下拉菜单有9个选项（如下1）9），无最优解时有两个选项（如下10）11）。只显示最优解(Solution Summary)。约束条件摘要(Constraint Summary)，比较约束条件两端的值。对目标函数进行灵敏度分析(Sensitivity Analysis of OBJ)。对约束条件右端常数进行灵敏度分析(Sensitivity Analysis of RHS)。求解结果组合报告(Combined Report)，显示详细综合分析报告。进行参数分析(Perform Parametric Analysis)，某个目标函数系数或约束条件右端常数带有参数，计算出参数的变化区间及其对应的最优解，属于参数规划内容。显示最后一张单纯性表(Final Simplex Tableau)。显示另一个基本最优解(Obtain Alternate Optimal)，存在多重解时，系统显示另一个基本最优解，然后考虑对基本最优解进行组合可以得到最优解的通解。显示系统运算时间和迭代次数(Show Run Time and Itration)。不可行性分析(Infeasibility Analysis)，线性规划问题无可行解时，系统指出存在无可行解的原因，如将例1的第5个约束改为，系统显示无可行解并且给出这样的显示报告：表1-3 winqsb线性规划求解不可行性分析表这说明第5个约束不可能小于等于零，右端常数至少等于117.1429才可行。（11）无界性分析(Unboundedness Analysis)，线性规划问题存在无界解时，系统指出存在无界解的可能原因。如将目标函数系数改为，系统显示无界并且显示：表1-4 winqsb线性规划求解无界性分析表系统提示要使线性规划问题有解，应该改变第二个约束条件。（12）保存结果。求解后将结果显示在顶层窗口，点击FileSave As，系统以文本格式存储计算结果。（13）将计算表格转换成Excel表格。在计算结果界面中点击FileCopy to Clipboard，系统将计算结果复制到剪贴板，再粘贴到Excel表格中即可。（8）单纯形表选择求解并显示单纯形法迭代步骤，系统显示初始单纯性表如表1- 1所示可以发现，系统将X4无约束改写成X4Neg_X4，即两个非负变量之差；系统将改写成约束C6：，令，则有，将代入约束条件并整理，在表中的实际上是，如约束C1：X1+2X2+6(X3+10)+9X4Neg_X4+Slack_C1=260整理后得到表1-5第一行（Slack_C1）。 约束C1，C4，C5，C6加入4个松弛变量Slack_C1，Slack_C4，Slack_C5以及Slack_UB_X3，约束C2减去剩余变量Surplus_C2，然后C2与C3加入2个人工变量Artificial_C2和Artificial_C3，共6个约束12个变量。 表2最后两行为检验数，如X1的检验数C(1)Z(1)*Big M=615M。选X1进基，表2-1最后一列为比值，变量Artificial_C3出基，主元素A(3,1)=7。 下一步点击菜单栏Simplex Iteration选择Next Iteration继续迭代，还可以人工选择进基变量，或直接显示最终单纯形表。（9）模型形式转换点击菜单栏FormatSwitch to Normal Model Form，将表1-5电子表格转换成表1-6的模型形式，再点击一次转换成表1-5的电子表格。（10）写出对偶模型点击菜单栏FormatSwitch to Dual Form，系统自动给出线性规划的对偶模型，再点击一次给出原问题模型。表1-5 初始单纯形表图1-3 标准模型输入形式附录： 线性规划常用术词汇及其含义常用术语含义常用术语含义Alternative Solution ExistsBasic and Nonbasic Variable BasisBasis StatusBranch-and-Bound MrthodCj-ZjCombined ReportConstraint SummaryConstraintConstraint DirectionConstraint StatusDecision VariableDual ProblemEntering VariableFeasible AreaFeasible SolutionInfeasibleInfeasibility AnalysisLeaving VariableLeft-hand sideLower or Upper BoundMinimum and Maximum Allowable Cj有多重解基变量和非基变量基基变量状态分支定界法检验数组合报告约束条件摘要约束条件约束方向约束状态决策变量对偶问题入基变量可行域可行解不可行不可行分析出基变量左端上界或下界最优解不变时，价值系数允许变化范围Minimum and Maximum AllowableRHSObjective FunctionOptimal SolutionParametric AnalysisRange and Slope of Parametric AnalysisReduced CostRange of FeasibilityRange of OptimalityRelaxed ProblemRelaxed OptimumRight-hand SideSensitivity Analysis of OBJ CoefficientsSensitivity Analysis of Right-Hand-sidesShadow PriceSimplex MethodSlack, Surplus or Artificial VariableSolution SummarySubtract(Add) More Than This From A(i,j)Total ContributionUnbounded Solution最优基不变时，资源限量允许变化范围；右端系数目标函数最优解参数分析参数分析的区间和斜率约简成本（价值）可行区间最优区间松弛问题松弛最优右端常数目标函数的灵敏度分析右端常数的灵敏度分析影子价格单纯形法松弛变量、剩余变量或人工变量最优解摘要减少（增加）约束系数总体贡献无界解二、对偶线性规划的WinQSB应用例2：已知线性规划s.t.写出对偶线性规划，变量用表示；求原问题及对偶问题的最优解；分别写出价值系数及右端常数的最大允许变化范围；目标函数系数改为，同时常数改为，求最优解；删除第四个约束同时删除第三个变量，求最优解；增加一个变量，系数为，求最优解。解：启动线性规划与整数规划（Linear and Integer Programming），建立新问题，取名为dual1（可任意取名），输入数据得到表2-1，存盘。表2-1（1）点击FormatSwitch to Dual Form，得到对偶问题的数据表，点击FormatSwitch to Normal Model Form，得到对偶模型，点击EditVariable Name，分别修改变量名，得到以为变量名的对偶模型，如图2-1所示。图2-1（2）再求一次对偶返回到原问题，求解显示结果如表2-2，此时最优解为，最优值。表中影子价格(Shadow Price)对应列的数据就是对偶问题的最优解为。表2-2 最优解详细综合分析报告（3）由表2-2最后两列可知：价值系数()最大允许变化范围分别是0.8333,4.1667，1.333,5.7778，1.1667,4.5，(,3.4917；右端常数的最大允许变化范围分别是5,27.4719，16.6667,50，0，33.3333，30.75,)。（4）直接修改表2-1的数据，求解后得到最优解为，最优值。（5）将数据修改回原问题，点击EditDelete a Constraint，选择要删除的约束C4，ok。点击EditDelete a Variable，选择要删除的变量X3，ok。得到如表2-3的模型，求解得到最优解为，最优值。表2-3（6）调用原问题数据表，点击EditInsert a Variable，选择变量名和变量插入的位置，如图2-2，在显示的电子表格中输入数据(6,5,4,2,3)，得到最优解为，最优值。