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

-(1.13)非基变量的检验数用分别为基变量检验数都为0，得初始单纯形表如表1.8所示。表1.82-11-2112020101-11011002-2303001370008表1.8所对应的基本可行解为，因为，所以不是最优解，仍需求新的基本可行解，根据Bland法则选取为入基变量，，由Bland法则取定为出基变量，换基迭代得表1.9。表1.9所对应的基本可行解为，因为所有检验数非正，所以为最优解。最优目标函数值。

表1.92-11-21100-210-321011002-200-301-30-700-6例1.10中换基迭代中采用了Bland法则来避免循环现象的出现。其实到目前为止在实际问题的线性规划模型中还未曾出现过循环现象。因此在退化现象出现时，实际上可以随意决定哪一个变量作为出基变量，不必考虑理论上有可能出现循环的后果。例1.11求解下列线性规划问题：解：化为标准型后用单纯形法计算，得初始单纯形表如表1.10所示。表1.102400004-1210001012010021-100124000表1.10中，，，选定为入基变量，由法则，，选定为出基变量，为主元素。换基迭代得表1.11。表1.112400042-1/211/2000620-110041/201/20140-20047/2011/41/402310-1/21/2005/2003/4-1/41000-20经过两次初等变换迭代得基本可行解，所有检验数都小于等于0，故为最优解。最优目标函数值。其中非基变量的检验数，若增加，目标函数值不变，即当进基时目标函数值仍为最优值20。以为入基变量，继续迭代，如表1.12所示，得到另一个基本可行解仍为最优解，目标函数值。是线性规划问题的两个最优基本可行解，它们连线上的所有点（凸组合）都是问题的最优解，从而原问题有无穷多最优解。表1.122400048/30101/3-1/3214/31001/32/3010/3001-1/34/3000-20定理1.5无穷多最优解判定定理当所有的检验数全部小于等于零时,若有某个非基变量的检验数也是零,则该线性规划有无穷多最优解。例1.12求解下列线性规划问题：解：化为标准型后用单纯形法计算，如表1.13所示表1.13-2300024-210042-301-2300，为入基变量，但，没有符合条件的最小比值，说明当非基变量保持为0时，只要就能保证非负，即可以无限增大，此时目标函数值也无限增大且满足约束条件，从而问题具有无界解。用图解法也可看出问题有无界解，定理1.6无界解判定定理在单纯形表中，若某个检验数且在中的系数均为负，则线性规划问题具有无界解。3．大法前面讨论的线性规划问题，其标准型中系数矩阵中都有单位子阵，作为初始基，很容易就可以得到初始基本可行解。但在实际问题中，有些规划问题的标准型中不含单位子阵，此时需要在约束方程中添加虚拟变量，构造单位子阵作为初始基。这种人为添加的变量称为人工变量。在一个线性规划问题中添加人工变量，要求不改变原问题，这就要求人工变量的取值对目标函数值不影响，为此在极大化目标函数中使人工变量的系数为“”（为足够大的正数），这样目标函数要实现极大化，必需把人工变量从基变量中换出。否则目标函数不可能实现最大化。我们将这种方法称为大法。例1.13求解下列线性规划问题：解：在问题中，添加松弛变量，人工变量，得到在用单纯形表求解的过程中，只需将看成一个足够大的正数，其它都和前面的方法一样。表1.143-1-100-M-M0111-211000-M3-4120-110-M1-2010001-6M+3M-13M-10-M000103-20100-1-M10100-11-2-11-20100011M-100-M01-3M0123001-22-5-110100-11-2-11-20100011000-11-M-1-M341001/3-2/32/3-5/3-110100-11-2-190012/3-4/34/3-7/3000-1/3-1/31/3-M2/3-M得到最优解最优目标函数值。说明：终止表可能出现下面三种情况：eq\o\ac(○,1)基变量中无人工变量；eq\o\ac(○,2)基变量中含有人工变量但取值为0；eq\o\ac(○,3)基变量中含有人工变量且取值非0。在前两种情况下，原问题有最优解，但在第三种情况下中，最优解含有不为0的人工变量，则原问题无可行解。第六节用WinQSB解线性规划问题QSB是QuantitativeSystemsforBusiness的缩写，WinQSB是QSB在Windows操作系统下运行的版本。WinQSB是一种教学软件，里面有大量的运筹学模型，对于非大型的问题一般都能计算，较小的问题还能演示中间的计算过程，特别适合多媒体课堂教学。该软件可应用于求解运筹学中的各种问题。本节主要介绍运用WinQSB求解线性规划问题。安装WinQSB软件后，在系统程序中自动生成WinQSB应用子程序，用户可以根据不同的问题选择相应的子程序进行求解。求解线性规划问题采用子程序“LinearandIntegerProgramming”。下面结合例题介绍WinQSB求解线性规划问题的操作步骤及应用。例1.14用WinQSB求解下列线性规划问题解：WinQSB软件求解的线性规划问题不必化为标准型，不等式约束可以在输入数据时直接输入，对于单个决策变量的约束，例如非负约束或无约束等，可以直接通过修改系统变量类型即可。第1步：启动子程序“LinearandIntegerProgramming”。点击开始程序WinQSBLinearandIntegerProgramming，如图1.8所示。图1.8第2步：建立新问题。选择FileNewProgram”，出现图1.9所示的问题选项输入界面。图1.9问题题头（ProblemTitle）：没有可不输入；决策变量数（NumberofVariables）：本例中有两个决策变量，填入2；约束条件数（NumberofConstraints）：本例中不计非负约束共有3个约束条件，填入3；目标函数准则（ObjectiveCriterion）：本例目标函数选最小化（Minimization）；数据输入格式（DataEntryFormat）：一般选择矩阵式电子表格式（SpreadsheetMatrixForm），另一个选项为自由格式输入标准模式（NormalModelForm）；变量类型（DefaultVariableType）：一共有以下四个选项非负连续变量选择第1个单选按钮（Nonnegativecontinuous）；非负整型变量选择第2个单选按钮（Nonnegativeinteger）；二进制变量选择第3个按钮（Binary[0,1]）；自由变量选择第4个按钮（Unsigned/unrestricted）。本例中选非负连续变量。第3步：输入数据。单击“OK”，生成表格并输入数据如表1.15：表1.15系统默认变量名为，约束条件名为。在表中第1行输入价值系数；第2-4行列对应输入约束方程系数，“Direction”列输入约束符，“R.H.S”列输入右端项；第5行输入变量下限，第6行输入变量上限，由于之前选择变量类型为非负连续变量，因此默认变量下限为0，变量上限为Ｍ，这里Ｍ表示正无穷大；第7行为变量类型，可以通过双击修改。第4步：求解点击“SolveandAnalyze”菜单，下拉菜单中有三个选项：求解但不显示迭代过程“SolvetheProblem”、求解并显示迭代过程“SolveandDisplaySteps”及图解法“GraphicMethod”显示单纯形法迭代步骤，选择“SimplexIteration”直到最终单纯形表。若选择“SolvetheProblem”，生成如下运行结果：表1.16决策变量（DecisionVariable）：x1、x2最优解（SolutionValue）：x1=60,x2=30；价值系数（UnitCostorProfitc(j)）：c1=4000,c2=3000；最优函数值（Totalcontribution）：x1贡献240000、x2贡献90000,共计330000；检验数（ReducedCost）：0，0。即当变量增加一个单位时，目标函数值的改变量。价值系数的允许最小值（AllowableMin.c[j]）和允许最大值（AllowableMax.c[j]）：价值系数在此范围变动时时，最优解不变。约束条件（Constraint）：C1、C2、C3左端取值（LeftHandSide）：12000、30000、15000右端取值（RightHandSide）：12000、20000、15000松驰变量或剩余变量的取值（SlackorSurplus）：该值等于约束左端与约束右端之差。为0表示资源已达到限制值，大于0表示未达到限制值。影子价格（ShadowPrice）：6.6667、0、16.6667，即为对偶问题的最优解。约束右端的允许最小值（AllowableMin.RHS）和允许最大值（AllowableMax.RHS）：表示约束右端在此范围变化时最优解不变。第5步：结果显示及分析。点击菜单栏result，存在最优解决时，下拉菜单有（1）-（9）9个选项，无最优解时有（10）和（11）两个选项只显示最优解（SolutionSummary）约束条件结果（ConstraintSummary），比较约束条件两端的值对价值系数进行灵敏度分析（SensitivityAnalysisofOBJ）对约束条件右端常数项进行灵敏度分析（SensitivityAnalysisofRHS）详细结果报告（CombinedReport）参数分析（PerformParametricAnalysis）最终单纯形表（FinalSimplexTableau）另一个基本最优解（ObtainAlternateOptimal），存在无穷多最优解时，系统给出另一个基本最优解。显示运行时间以及迭代次数（ShowRunTimeandIteration）不可行性分析（InfeasibilityAnalysis）无界性分析（UnboundednessAnalysis）表1.17中列出了WinQSB中常用术语。表1.17常用术语含义Alternativesolutionexists存在替代解，有多重解Basicandnonbasicvariable基变量和非基变量Basis基Basisstatus基变量状态，提示是否为基变量Branch-and-boundmethod分支定界法Cj-Zj检验数Combinedreport组合报告Constraintsummary约束条件摘要Constraint约束条件Constraintdirection约束方向Constraintstatus约束状态Decisionvariable决策变量Dualproblem对偶问题Enteringvariable入基（进基）变量Feasiblearea可行域Feasiblesolution可行解Infeasible不可行Infeasibilityanalysis不可行性分析Leavingvariable出基变量Left-handside左端Lowerorupperbound下界或上界MinimumandmaximumallowableCj最优解不变时，价值系数允许变化范围MinimumandmaximumallowableRHS最优基不变时，资源限量允许变化范围Objectivefunction目标函数Optimalsolution最优解Parametricanalysis参数分析Rangeandslopeofparametricanalysis参数分析的区间和斜率Reducedcost约简成本（价值），检验数，即当非基变量增加一个单位是目标函数的改变量Rangeoffeasibility可行区间Rangeofoptimality最优区间Relaxedproblem松弛问题Relaxedoptimum松弛最优Right-handside右端常数SensitivityanalysisofOBJcoefficients目标函数系数的灵敏度分析SensitivityanalysisofRight-handside右端常数的灵敏度分析Shadowprice影子价格Simplexmethod单纯形法Slack,surplusorartificialvariable松弛变量、剩余变量或人工变量Solutionsummary最优解摘要Subtract(Add)morethanthisfromA(i,j)减少（增加）约束系数，调整工艺系数Totalcontribution总体贡献，目标函数cjxj的值Unboundedsolution无界解Unbounded无界

习题一A1.1对于下面每一个约束，画出一个单独的图形表示出满足这些约束的非负解。（a）（b）（c）（d）画出满足上面所有约束以及非负约束的可行域。1.2考虑目标函数（a）分别画出表示和相应的目标函数等值线。（b）写出上面三条等值线的斜截式方程，比较它们的斜率以及在轴上的截距。1.3用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。（a）（b）（c）1.4工厂利用原材料Q、R、S每月生产A、B两种产品，每吨产品的原材料消耗量、每月可用原材料量及单件产品利润如表1.18所示。表1.18原材料每吨产品所需原材料可用原材料量产品A产品BQ212R122S334单件产品利润32（a）建立这个问题的线性规划模型，使每月利润最大。(b)用图解法求解该模型。1.5将下列线性规划问题化为标准形式。（a）（b）（c）1.6设线性规划取基，分别指出和所对应的基变量和非基变量，求出基本解，并说明是不是可行解。1.7分别用图解法和单纯形法求解下面的线性规划问题，指出单纯形法迭代的每一步对应于图形上的哪一个极点。1.8用单纯形法求下列线性规划。（a）（b）（c）（d）1.9用大法求解下列线性规划问题。（a）（b）1.10已知线性规划的最优单纯形表如表1.19所示，求原问题中的参数以及最优基B。表1.1