用WinQSB解线性规划问.doc

* 用WinQSB解线性规划问题QSB是Quantitative Systems for Business的缩写，WinQSB是QSB在Windows操作系统下运行的版本。WinQSB是运筹学软件，里面有大量的运筹学模型，对于非大型的问题一般都能计算，较小的问题还能演示中间的计算过程，特别适合多媒体课堂教学。该软件可应用于求解运筹学中的各种问题。下面介绍运用WinQSB求解线性规划问题。安装WinQSB软件后，在系统程序中自动生成WinQSB应用子程序，用户可以根据不同的问题选择相应的子程序进行求解。求解线性规划问题采用子程序“Linear and Integer Programming”。下面结合例题介绍WinQSB求解线性规划问题的操作步骤及应用。例。 用WinQSB求解下列线性规划问题解：WinQSB软件求解的线性规划问题不必化为标准型，不等式约束可以在输入数据时直接输入，对于单个决策变量的约束，例如非负约束或无约束等，可以直接通过修改系统变量类型即可。第1步：启动子程序“Linear and Integer Programming”。点击开始程序WinQSB Linear and Integer Programming，如图1.8所示。图1.8第2步：建立新问题。选择FileNew Program”，出现图1.9所示的问题选项输入界面。图1.9问题题头（Problem Title）：没有可不输入；决策变量数（Number of Variables）：本例中有两个决策变量，填入2；约束条件数（Number of Constraints）：本例中不计非负约束共有3个约束条件，填入3；目标函数准则（Objective Criterion）：本例目标函数选最小化（Minimization）；数据输入格式（Data Entry Format）：一般选择矩阵式电子表格式（Spreadsheet Matrix Form），另一个选项为自由格式输入标准模式（Normal Model Form）；变量类型（Default Variable Type）：一共有以下四个选项非负连续变量选择第1个单选按钮（Nonnegative continuous）；非负整型变量选择第2个单选按钮（Nonnegative integer）；二进制变量选择第3个按钮（Binary0,1）；自由变量选择第4个按钮（Unsigned/unrestricted）。本例中选非负连续变量。第3步：输入数据。单击“OK”，生成表格并输入数据如表1.15：表1.15系统默认变量名为，约束条件名为。在表中第1行输入价值系数；第2-4行列对应输入约束方程系数，“Direction”列输入约束符，“R.H.S”列输入右端项；第5行输入变量下限，第6行输入变量上限，由于之前选择变量类型为非负连续变量，因此默认变量下限为0，变量上限为，这里表示正无穷大；第7行为变量类型，可以通过双击修改。第4步：求解点击“Solve and Analyze”菜单，下拉菜单中有三个选项：求解但不显示迭代过程“Solve the Problem”、求解并显示迭代过程“Solve and Display Steps”及图解法“Graphic Method”显示单纯形法迭代步骤，选择“Simplex Iteration”直到最终单纯形表。若选择“Solve the Problem”，生成如下运行结果：表1.16决策变量（Decision Variable）：x1、x2最优解（Solution Value）：x1=60,x2=30；价值系数（Unit Cost or Profit c(j)）：c1=4000,c2=3000；最优函数值（Total contribution）：x1贡献240000、x2贡献90000,共计330000；检验数（Reduced Cost）：0，0。即当变量增加一个单位时，目标函数值的改变量。价值系数的允许最小值（Allowable Min.cj）和允许最大值（Allowable Max.cj）：价值系数在此范围变动时时，最优解不变。约束条件（Constraint）：C1、C2、C3左端取值（Left Hand Side）：12000、30000、15000右端取值（Right Hand Side）：12000、20000、15000松驰变量或剩余变量的取值（Slack or Surplus）：该值等于约束左端与约束右端之差。为0表示资源已达到限制值，大于0表示未达到限制值。影子价格（Shadow Price）：6.6667、0、16.6667，即为对偶问题的最优解。约束右端的允许最小值（Allowable Min.RHS）和允许最大值（Allowable Max.RHS）：表示约束右端在此范围变化时最优解不变。第5步：结果显示及分析。点击菜单栏result，存在最优解决时，下拉菜单有（1）-（9）9个选项，无最优解时有（10）和（11）两个选项（1） 只显示最优解（Solution Summary）（2） 约束条件结果（Constraint Summary），比较约束条件两端的值（3） 对价值系数进行灵敏度分析（Sensitivity Analysis of OBJ）（4） 对约束条件右端常数项进行灵敏度分析（Sensitivity Analysis of RHS）（5） 详细结果报告（Combined Report）（6） 参数分析（Perform Parametric Analysis）（7） 最终单纯形表（Final Simplex Tableau）（8） 另一个基本最优解（Obtain Alternate Optimal），存在无穷多最优解时，系统给出另一个基本最优解。（9） 显示运行时间以及迭代次数（Show Run Time and Iteration）（10） 不可行性分析（Infeasibility Analysis）（11） 无界性分析（Unboundedness Analysis）表1.17中列出了WinQSB中常用术语。表1.17常用术语含义Alternative solution exists存在替代解，有多重解Basic and nonbasic variable基变量和非基变量Basis基Basis status基变量状态，提示是否为基变量Branch-and-bound method分支定界法Cj-Zj检验数Combined report组合报告Constraint summary约束条件摘要Constraint约束条件Constraint direction约束方向Constraint status约束状态Decision variable决策变量Dual problem对偶问题Entering variable入基（进基）变量Feasible area可行域Feasible solution可行解Infeasible不可行Infeasibility analysis不可行性分析Leaving variable出基变量Left-hand side左端Lower or upper bound下界或上界Minimum and maximum allowable Cj最优解不变时，价值系数允许变化范围Minimum and maximum allowable RHS最优基不变时，资源限量允许变化范围Objective function目标函数Optimal solution最优解Parametric analysis参数分析Range and slope of parametric analysis参数分析的区间和斜率Reduced cost约简成本（价值），检验数，即当非基变量增加一个单位是目标函数的改变量Range of feasibility可行区间Range of optimality最优区间Relaxed problem松弛问题Relaxed optimum松弛最优Right-hand side右端常数Sensitivity analysis of OBJ coefficients目标函数系数的灵敏度分析Sensitivity analysis of Right-hand side右端常数的灵敏度分析Shadow price影子价格Simplex method单纯形法Slack, su