第一章 线性规划与单纯形法(6)

时需要在约束方程中添加虚拟变量，构造单位子阵作为初始基。这种人为添加的变量称为人工变量。在一个线性规划问题中添加人工变量，要求不改变原问题，这就要求人工变量的取值对目标函数值不影响，为此在极大化目标函数中使人工变量的系数为“?M”（M为足够大的正数），这样目标函数要实现极大化，必需把人工变量从基变量中换出。否则目标函数不可能实现最大化。我们将这种方法称为大M法。

例1.13 求解下列线性规划问题：

maxz?3x1?x2?x3?x1?2x2?x3?11??4x?x?2x?3 ?123??x3?1??2x1??x1,x2,x3?0解：在问题中，添加松弛变量x4,x5，人工变量x6,x7，得到

maxz?3x1?x2?x3?0x4?0x5?Mx6?Mx7?11?x1?2x2?x3?x4??4x?x?2x?x5?x6?3 ?123??x3?x7?1??2x1??x1,x2,x3,x4,x5,x6,x7?0在用单纯形表求解的过程中，只需将M看成一个足够大的正数，其它都和前面的方法一样。

表1.14 cj? CB 0 -M -M 3 -1 -1 0 0 -M -M XB b 11 3 1 10 1 1 12 1 1 4 1 9 x1 1 -4 -2 -6M+3 3 0 -2 1 3 0 -2 1 1 0 0 0 x2 -2 1 0 M-1 -2 1 0 M-1 0 1 0 0 0 1 0 0 x3 1 2 1 3M-1 0 0 1 0 0 0 1 0 0 0 1 0 x4 1 0 0 0 1 0 0 0 1 0 0 0 1/3 0 2/3 -1/3 x5 0 -1 0 -M 0 -1 0 -M -2 -1 0 -1 -2/3 -1 -4/3 -1/3 x6 0 1 0 0 0 1 0 0 2 1 0 1-M 2/3 1 4/3 1/3-M x7 0 0 1 0 -1 -2 1 1-3M -5 -2 1 -1-M -5/3 -2 -7/3 2/3-M x4 x6 x7 ?j 0 -M -1 x4 x6 x3 ?j 0 -1 -1 x4 x2 x3 ?j 3 -1 -1 x1 x2 x3 ?j - 30 -

得到最优解X?(4,1,9,0,0,0,0)T最优目标函数值z?2。

说明：终止表可能出现下面三种情况：○1基变量中无人工变量；○2基变量中含有人工变量但取值为0；3基变量中含有人工变量且取值非0。在前两种情况下，原问题有最优解，○但在第三种情况下中，最优解含有不为0的人工变量，则原问题无可行解。

*第六节 用WinQSB解线性规划问题

QSB是Quantitative Systems for Business的缩写，WinQSB是QSB在Windows操作系统下运行的版本。WinQSB是一种教学软件，里面有大量的运筹学模型，对于非大型的问题一般都能计算，较小的问题还能演示中间的计算过程，特别适合多媒体课堂教学。该软件可应用于求解运筹学中的各种问题。本节主要介绍运用WinQSB求解线性规划问题。

安装WinQSB软件后，在系统程序中自动生成WinQSB应用子程序，用户可以根据不同的问题选择相应的子程序进行求解。求解线性规划问题采用子程序“Linear and Integer Programming”。下面结合例题介绍WinQSB求解线性规划问题的操作步骤及应用。

例1.14 用WinQSB求解下列线性规划问题

minz?4000x1?3000x2?100x1?200x2?12000?300x?400x?20000?12s..t??200x1?100x2?15000??x1,x2?0

解：WinQSB软件求解的线性规划问题不必化为标准型，不等式约束可以在输入数据时直接输入，对于单个决策变量的约束，例如非负约束或无约束等，可以直接通过修改系统变量类型即可。

第1步：启动子程序“Linear and Integer Programming”。

点击开始?程序?WinQSB? Linear and Integer Programming，如图1.8所示。

图1.8

第2步：建立新问题。

选择File?New Program”，出现图1.9所示的问题选项输入界面。

- 31 -

图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个按钮（Binary[0,1]）；

自由变量选择第4个按钮（Unsigned/unrestricted）。本例中选非负连续变量。 第3步：输入数据。

单击“OK”，生成表格并输入数据如表1.15：

表1.15

系统默认变量名为X1,X2,?,Xn，约束条件名为C1,C2,?,Cn。

在表中第1行输入价值系数；第2-4行X1,X2列对应输入约束方程系数，“Direction”列输入约束符，“R.H.S”列输入右端项；第5行输入变量下限，第6行输入变量上限，由于之前选择变量类型为非负连续变量，因此默认变量下限为0，变量上限为Ｍ，这里Ｍ表示正无穷大；第7行为变量类型，可以通过双击修改。

- 32 -

第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.c[j]）和允许最大值（Allowable Max.c[j]）：价值系数在此范围变动时时，最优解不变。

约束条件（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）

- 33 -

（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 含义 存在替代解，有多重解 基变量和非基变量 基 基变量状态，提示是否为基变量 分支定界法 检验数 组合报告 约束条件摘要 约束条件 约束方向 约束状态 决策变量 对偶问题 入基（进基）变量 可行域 可行解 不可行 不可行性分析 出基变量 左端 下界或上界 最优解不变时，价值系数允许变化范围 最优基不变时，资源限量允许变化范围 目标函数 最优解 参数分析 参数分析的区间和斜率 - 34 -

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第一章 线性规划与单纯形法(6)在线全文阅读。