教学材料《运筹学》-第2章

第2章线性规划概念、建模与求解学习目标通过本章的学习，认识线性规划的特征、解的基本概念和性质，熟悉线性规划模型及建模方法，掌握图解法和单纯形法。上一页下一页返回第2章线性规划概念、建模与求解关键词汇线性规划(LinearProgramming)目标函数(ObjectiveFunction)约束集合(ConstraintSet)可行域(FeasibleRegion)可行解(FeasibleSolution)右端项(Right-handSide)图解法(GraphicalSolution)基(Basin)基变量(BasicVariable)上一页下一页返回第2章线性规划概念、建模与求解非基变量(Non-basicVariable)基本解(BasicSolution)基本可行解(BasicFeasibleSolution)最优解(OptimalSolution最优值(OptimalValue)单纯形法(SimplexMethod)决策变量(DecisionVariable)大M法(TheBidMMethod)两阶段法(TheTwo-phaseMethod)上一页下一页返回第2章线性规划概念、建模与求解案例导引例一企业生产A1，A2，···，An几种产品，市场需求旺盛，各产品售出后每件可获得利润分别为c1，c2，···，cn生产这些产品需要m种资源(可以是原料、设备、时间、能源等)b1，b2，···，bm产品所需资源及产品利润、资源限制情况如表2-1所示。求使得总利润最高的生产方案。把此典型问题简化为下列问题:某工厂拥有A,B,C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数、每件产品可以获得的利润及三种设备可利用的时数如表2-2所示。上一页下一页返回第2章线性规划概念、建模与求解问:工厂应如何安排生产可获得最大的总利润?例二合理配料问题:由多种原料制成含有m,种成分的产品，已知产品单价、产品中所含各种成分的比例要求、各种原料的单位价格，以及各原料所含成分的数量。考虑的问题是:应如何配料，可使产品的成本最低?把此典型问题简化为下列问题:某公司计划要用A,B,C三种原料混合调制出三种不同规格的产品甲、乙、丙，产品的规格要求、单位价格(元/单位)，原料的供应量，原料的单位价格(元/单位)等数据如表2-3所示。上一页下一页返回第2章线性规划概念、建模与求解问:该公司应如何安排生产，可使利润收入为最大?案例思考题:上面的例题如何求解?难点是什么?关键在哪里?从这里体会线性规划模型特征。上一页返回下一页2.1线性规划模型结构与建模2.1.1线性规划问题的提出在实践中，常常遇到与下列问题类似的情况，这时可以建立线性规划问题数学模型。我们首先分析开篇案例提到的问题。例2.1某工厂拥有A,B,C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数、每件产品可以获得的利润以及三种设备可利用的时数如表2-2所示。问:工厂应如何安排生产可获得最大的总利润?分析设变量xi为第i种(甲、乙)产品的生产件数(i=1,2)。根据题意知道两种产品的生产受到设备能力(机时数)的限制:对设备A，两种产品生产所占用的机时数不能超过65，于是可以得到不等式:3x1+2x2≤65;下一页返回上一页2.1线性规划模型结构与建模对设备B，两种产品生产所占用的机时数不能超过40，于是可以得到不等式:2x1+x2≤40;对设备C，两种产品生产所占用的机时数不能超过75，于是可以得到不等式:3x2≤75;另外，注意到产品数不可能为负，即应有x1≥0,x2≥0。同时，我们有一个追求目标，即获取最大利润。针对利润可写出目标函数

z=1500x1+2500x2为相应的生产计划可以获得的总利润。上一页下一页返回2.1线性规划模型结构与建模

解综合上述讨论，在加工时间及利润与产品产量呈线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型。目标函数 maxz=1500x1+2500x2约束条件 s.t 3x1+2x2≤65 2x1+x2≤40

3x2≤75

x1≥0,x2≥0上一页下一页返回2.1线性规划模型结构与建模

这是一个典型的利润最大化的生产计划问题。其中，“max”是英文单词“maximize”的缩写，含义为“最大化”;“S.t.”是“subjectto”的缩写，表示“满足于……”。因此，上述模型的含义是:在给定的条件限制下，求使得目标函数z达到最大的x1，x2的取值。例2.2某工厂熔炼一种新型不锈钢，需要用四种合金T1,T2,T3和T4为原料，经测量，这四种原料中元素铬(Cr),锰(Mn)和镍(Ni)的含量(%)、单价，以及这种不锈钢所需铬(Cr)、锰(Mn)和镍(Ni)的最低含量(%)如表2-4所示。上一页下一页返回2.1线性规划模型结构与建模假设熔炼时重量没有损耗。问:要熔炼成100吨这样的不锈钢，应选用原料T1,T2,T3和T4各多少吨才能使成本最小?分析设选用原料T1,T2,T3和T4分别为二x1,x2,x3,x4吨。根据题目条件，该工厂熔炼不锈钢的量是已知的100吨，它将由四种合金T1,T2,T3和T4为原料熔炼而成，构成一个等式约束:x1+x2+x3+x4=100;该不锈钢所需铬(Cr)、锰(Mn)和镍(Ni)的最低含量由四种合金T1,T2,T3和T4对相应元素的含量构成，于是可以得到:关于铬含量的不等式:0.0321x1+0.0453x2+0.0291x3+0.0176x4≥3.20;关于锰含量的不等式:0.0204x1+0.0112x2+0.0357x3+0.0433x4≥2.10;关于镍含量的不等式:0.0582x1+0.0306x2+0.0427x3+0.0273x4≥4.30;上一页下一页返回2.1线性规划模型结构与建模解综合上述讨论，把目标函数和约束条件放在一起，可以建立如下的线性规划模型。目标函数 minf=11.5x1+9.7x2+8.2x3+7.6x4约束条件 s.t 0.0321x1+0.0453x2+0.0291x3+0.0176x4≥3.20 0.0204x1+0.0112x2+0.0357x3+0.0433x4≥2.10 0.0582x1+0.0306x2+0.0427x3+0.0273x4≥4.30 x1+x2+x3+x4=100

x1,x2,x3,x4≥0这是一个典型的成本最小化的问题。其中，"min”是英文单词“minimize”的缩写，含义为“最小化”。因此，上述模型的含义是:在给定的条件限制下，求使得目标函数f达到最小的x1,x2,x3,x4取值。上一页下一页返回2.1线性规划模型结构与建模2.1.2线性规划的一般模型结构从以上两个例子中可以归纳出线性规划问题的一般形式。对干一组变量xj，j=1，2，…，n，取上一页下一页返回2.1线性规划模型结构与建模上一页下一页返回这是线性规划数学模型的一般形式。其中，式(2-1)称为目标函数，它一般只有两种形式:max或thin;式(2-2)与式(2-3)合称为约束条件，它们表示问题所受到的各种限制，一般有三种形式:“大于或等于”“小于或等于”(这两种情况又称不等式约束)或“等于”(又称等式约束);其中由于式(2-3)有特殊性(很多情况下决策变量都蕴含了这个假设，但是在问题提出时，它们常常不明确指出，建模时需要特别关注)，可称为非负约束条件。在实际中，也有些决策变量允许取任何实数，如温度变量、资金变量等，这时不能人为地强行限制其为非负。2.1线性规划模型结构与建模在线性规划模型中，也直接称z(或.f)为目标函数;称xj(j=1,2,…，n)为决策变量;称cj(j=1,2,…，n)为目标函数系数或价值系数或费用系数;称xi(i=1,2,…，m)为约束右端常数或简称右端项，也称资源常数;称aij(i=1,2,…，m;j=1,2,…，n)耐为约束系数或技术系数。这里cj,bi,aij均为常数。线性规划的数学模型可以表示为下列简洁的形式。上一页下一页返回2.1线性规划模型结构与建模

线性规划的数学模型表示为矩阵形式(式2-5)或向量形式(式2-6)则更为简洁。记向量和矩阵为上一页下一页返回2.1线性规划模型结构与建模为了书写方便，可把列向量记为行向量的转置，如x=(x1,x2,…,xn)，“T”表示转置，是Transform的缩写;对于n维列向量x，用符号表示为:x∈Rn;A是m行n列的矩阵，称m×n矩阵。在这里，矩阵A有时表示为:A=(D1,D2,…,Dn),其中Dj=(a1i,a2i,…,ami)T∈Rm

。于是，当所有约束是一致的(均为大于或等于、均为小于或等于或均为等于)，决策变量均非负时，线性规划问题的矩阵形式为:上一页下一页返回2.1线性规划模型结构与建模向量形式为上一页下一页返回2.1线性规划模型结构与建模这里，向量的等式与不等式表示所有分量有一致的关系，即当x,y∈Rn时，x≤y表示对所有i=1，2,…，n有二xi≤

yi;其他x≥y,x<y,x>y，x=y也类似。在线性规划模型中，也称c为目标函数系数向量或价值系数向量或费用系数向量;称b为约束右端常数向量或简称右端项，也称资源常数向量;称A为约束系数矩阵或技术系数矩阵。线性规划模型有如下特点：1)决策变量想x1,x2,…,xn表示要寻求的方案，每一组值就是一个方案。2)约束条件是用等式或不等式表述的限制条件。(3)有一个目标，希望最大或最小。(4)所有函数都是线性的。上一页下一页返回2.1线性规划模型结构与建模2.1.3线性规划建模在实践中，经常遇到一类因素之间呈比例关系的优化问题。例如，确定有限投资额的最优分配，使得收益最大或者见效最快;在生产计划安排过程中，需确定生产的品种和数量，使得产值或利润最大;分配不同的工作给各个对象(劳动力或机床)，使产量最多、效率最高;如何下料，使得边角料损失最小;在物资调运过程中，确定最经济的调运方案;如何确定最佳库存量，做到既保证生产又节约资金等。建立线性规划模型的过程可以分为以下四个部分。(1)明确问题，设立决策变量。(2)分析、列出约束条件，并用决策变量的线性等式或不等式表示。根据决策变量的物理性质研究变量是否有非负性。上一页下一页返回2.1线性规划模型结构与建模(3)用决策变量的线性函数表示目标，并确定优化方向(一般是求最大或最小)。(4)收集资料，设定参数，建立模型。建立模型过程中最关键的是设立决策变量，如果决策变量设定恰当，则后面三步工作就比较容易进行。另一关键是明确问题、确定目标，在建立模型过程中花时间、花精力最大的是收集资料。要重视积累经验，学会充分利用建立相关约束的方法来尝试通过增加一些决策变量来解决建模问题。一般情况下，设定决策变量没有严格的规律可以遵循，必须具体问题具体分析。数学规划的建模有许多共同点，要遵循下列原则:上一页下一页返回2.1线性规划模型结构与建模(1)容易理解。建立的模型不但要求建模者理解，还应当让有关人员理解。这样便于考察实际问题与模型的关系，增加将来得到的结论在实际应用中的作用。(2)容易查找模型中的错误。这个原则的目的显然与(1)相关。常出现的错误有:书写错误和公式错误。(3)容易求解。对线性规划来说，使问题容易求解主要是控制问题的规模，包括使决策变量的个数和约束的个数尽量少。这条原则的实现往往会与(1)发生矛盾，在实现时需要对两条原则进行统筹考虑。线性规划建模过程具有相当的灵活性，需要通过大量的实例，掌握一定的经验，结合对问题本身的深入研究来提高建模的能力。下面就一些常见的问题给出线性规划建模的例子。上一页下一页返回2.1线性规划模型结构与建模本章作为对线性规划的讨论，着重强调线性规划的建模。读者应认识到，建模中有些内容(如建模过程、步骤、原则等)是不仅仅限于线性规划的。1)生产计划问题生产计划问题是企业生产过程中时常遇到的问题，生产计划问题中最简单的一种形式的描述如引例所示。类似这样的问题，可以采用问什么就设什么的方法设定决策变量，但有些问题会有稍微复杂的一些情况出现，下面举例来看几种产品生产计划问题。例2.3某工厂生产A,B两种产品，均需经过两道工序，每生产1吨A产品需要经第一道工序加工2小时，第二道工序加工3小时;每生产1吨B产品需要经过第一道工序加工3小时，第二道工序加工4小时。可供利用的第一道工序工时为15小时，第二道工序工时为25小时。上一页下一页返回2.1线性规划模型结构与建模

生产产品B的同时可产出副产品C，每生产1吨产品B，可同时得到2吨产品C而不需要外加任何费用。这副产品C一部分可以盈利，但剩下的只能报废，报废需要有一定的费用。各项费用的情况为:出售产品A，每吨能盈利400元;出售产品B，每吨能盈利800元;每销售1吨副产品C能盈利300元;当剩余的产品C报废时，每吨损失费为200元。经市场预测，在计划期内产品C的最大销量为5吨。试列出本问题的线性规划模型，决定如何安排A,B两种产品的产量，可使工厂总的盈利为最大?上一页下一页返回2.1线性规划模型结构与建模

分析由于副产品C的出现而使问题复杂化了。如果只设A,B,C产品的产量分别为x1,x2,…，x3则由于产品C的单位利润是在盈利300元(+300)或损失200元(-200)之间变化，因此目标函数中二3的系数不是常数。但是，如果把C的销售量和报废量区分开来，设作两个变量，则可以容易地建立问题的线性规划模型。解:设A,B产品的产量分别为x1,x2,C产品的销售量和报废量分别为x3,x4。根据问题的条件和限制容易建立下述线性规划模型(为了方便，取利润或损失金额的单位为百元)。目标函数:maxz=4x1+8x2+3x3-2x4约束:产品C是产品B的副产品，1吨产品B产生2吨产品C，即有2x2=x3+x4上一页下一页返回2.1线性规划模型结构与建模产品A的限制2x1+3x2

≤15产品B的限制3x1+4x2

≤25产品C的限制x3≤5于是可得到如下线性规划模型: maxz=4x1+8x2+3x3-2x4上一页下一页返回2.1线性规划模型结构与建模2)合理下料问题下料问题是加工业中常见的一种问题，它的一般提法是:某种原材料有已知的固定规格，要切割成给定尺寸的若干种零件的毛坯，在各种零件数量要求给定的前提下，考虑设计一切割方案使用料最少(浪费最小)。合理下料问题有一维下料问题(线材下料)、二维下料问题(面材下料)和三维下料问题(积材下料)等，其中线材下料问题最简单。例2.4某工厂要制作100套专用钢架，每套钢架需要用长为2.9米，2.1米和1.5米的圆钢各一根。已知原料每根长7.4米，现考虑应如何下料，可使所用原料最省?

分析利用7.4米长的圆钢裁成2.9米、2.1米、1.5米的圆钢共有下列8种下料方案，如表2-5所示。上一页下一页返回2.1线性规划模型结构与建模

解:一般情况下，我们可以设x1,x2,x3,x4,x5,x6,x7,x8分别为上面8种方案下料的原材料根数。根据目标的要求，可以建立两种形式的目标函数:材料根数最少:minx1+x2+x3+x4+x5+x6+x7+x8(2-7)

剩余料头最少:min0.1x1+0.3x2+0.9x3+0x4+1.1x5+0.2x6+0.8x7+1.4x8(2-8)约束是要使满足各种方案裁得的2.9米、2.1米、1.5米三种圆钢各自不少于100个，即2.9米 2x1+x2+x3+x4

≥1002.1米 2x2+x3+3x5+2x6+x7≥1001.5米 x1+x3+3x4+2x6+3x7+4x8≥100非负条件 x1，x2，x3，x4，x5，x6，x7，x8

≥0上一页下一页返回2.1线性规划模型结构与建模这样我们可以建立两个线性规划模型。模型1用目标函数(2-7)可建立如下的数学模型。

minx1+x2+x3+x4+x5+x6+x7+x8

上一页下一页返回2.1线性规划模型结构与建模利用线性规划单纯形法求解可得:x*={10,50,0,30,0,0,0,0}T，最少使用的材料数为90(根)，各种圆钢数均正好是100。模型2用目标函数(2-8)，可建立如下的数学模型: minx1+x2+x3+x4+x5+x6+x7+x8

上一页下一页返回2.1线性规划模型结构与建模利用线性规划单纯形法求解可得:x*={0,0,0,100,0,50,0,0}T,最少的剩余料头为10(米)，2.9米和2.1米的圆钢数正好为100,而1.5米的圆钢数要300个。显然，模型2的最优解不合理，为什么会出现误差呢?仔细观察一下会发现，原因出现在方案4的剩余料头为零，求解过程中目标函数最小对它失去了作用。由此得到提示:在实际使用线性规划解决问题时，隐含的逻辑错误往往很难发现，必须进行解的分析才能够找到问题。例2.5某钢窗厂要制作50套某种规格的钢窗，这种钢窗每付需要用长为1.5米的料2根、1.45米的料2根、1.3米料6根和0.35米的料12根。已知供切割用的角钢长度为8米，现考虑应如何切割，可使所用的角钢数最少?上一页下一页返回2.1线性规划模型结构与建模

分析看起来本题与例2.4完全类似，但在考虑方案时，发现可能的方案非常多。虽然直接建模计算可以用上述方法求得精确的解，但是这样做(人工列方案)的代价是否太大?在序言中提到过，运筹学解决问题除要考虑精确度之外，还要考虑其复杂性、可行性等因素。这里，无妨借此例的讨论给读者一个实践中的有益提示。根据数据情况，我们可以考虑对此问题进行化简。把1根1.3米的料与2根0.35米的料绑在一起考虑，看成一根2米的料;再简化一点，还可以把1.45米的料也近似视为1.5米。上一页下一页返回2.1线性规划模型结构与建模

显然，如此化简后问题变得非常简单了。请有兴趣的读者自己计算两种情况的结果。需注意的是，任何问题的化简都是有条件的，必须深入分析数据才能够构造出比较理想的简化问题。本例中，之所以考虑这样化简，是由于前一组合得到的长度刚好是原材料的四分之一;而后一种近似，每根的误差只有0.OS米，在可以承受的范围内。

3)合理配料问题这类问题的一般提法是:由多种原料制成含有m种成分的产品，已知产品中所含各种成分的比例要求、各种原料的单位价格及各原料所含成分的数量。考虑的问题是:应如何配料，可使产品的成本最低?上一页下一页返回2.1线性规划模型结构与建模

例2.6某公司计划要用A,B,C三种原料混合调制出三种不同规格的产品甲、乙丙，产品的规格要求、单位价格，原料的供应量，原料的单位价格等数据如表2-6所示。问:该公司应如何安排生产，可使利润收入最大?

分析本例的难点在于给出的数据为非确定数值，而且各产品与原料的关系较为复杂。为了方便，设xij表示第i种(i=1为甲、i=2为乙、i=3为丙)产品中原料j(j=1为A,j=2为B,j=3为C)的含量。这样我们建立数学模型时，要考虑如下变量:上一页下一页返回2.1线性规划模型结构与建模解：对于甲：x11,x12,x13;

对于乙：x21,x22,x33;

对于丙：x31,x32,x33;

对于原料A：x11,x21,x31;

对于原料B：x12,x22,x32;

对于原料C：x13,x23,x33;

目标函数:求利润最大，利润=收人一原料支出 收入三项:甲150(x11+x12+x13),乙85(x21+x22+x23),丙65(x31+x32+x33)

支出三项:原料A：60(x11+x21+x31),原料B：35(x12+x22+x32),原料C：30(x13+x23+x33)上一页下一页返回2.1线性规划模型结构与建模于是得到目标函数maxz=150(x11+x12+x13)+85(x21+x22+x23)+65(x31+x32+x33)- 60(x11+x21+x31)-35(x12+x22+x32)-30(x13+x23+x33)=90x11+115x12+120x13+25x21+50x22+55x23+5x31+30x32+35x33约束条件:规格要求7个，供应量限制3个和决策变量的非负条件。规格要求:甲对原料A的规格要求: ，整理后得 。甲对原料B的规格要求: ，整理后得 。上一页下一页返回2.1线性规划模型结构与建模乙对原料A的规格要求: ，整理后得 。乙对原料B的规格要求: ，整理后得 。丙对原料A的规格要求: ，整理后得 。丙对原料B的规格要求: ，整理后得 。丙对原料C的规格要求: ，整理后得 。上一页下一页返回2.1线性规划模型结构与建模原料供应量限制:原料A： ；原料B： ；原料C： 。决策变量的非负条件:

。于是，可以得到下列线性规划模型:上一页下一页返回2.1线性规划模型结构与建模上一页下一页返回2.1线性规划模型结构与建模4)连续投资问题例2.7某企业现有资金200万元，计划在今后5年内给A,B,C,D4个项目投资。根据有关情况的分析得知:

项目A:从第1年到第5年每年年初都可进行投资，当年年末就能收回本利110%;

项目B:从第1年开始，每年年初都可进行投资，次年年末能收回本利125%，但是要求每年最大投资额不能超过30万元;

项目C:若投资则必须在第3年年初投资，到第5年年末能收回本利140%，但是限制最大投资额不能超过80万元;

项目D:若投资则需在第2年年初投资，到第5年年末能收回本利155%，但是规定最大投资额不能超过100万元;

问题:应如何确定这些项目的每年投资额，使得第5年年末拥有资金的本利金额最大？上一页下一页返回2.1线性规划模型结构与建模

解首先进行分析。①考虑确定决策变量。本题是一个连续投资的问题，由于需要考虑每年年初对不同项目的投资数，为了便于理解，建立双下标决策变量。设xij(i=1,2,3,4,5,.j=1,2,3,4)表示第i年初投资于项目A(j=1)、项目B(j=2)、项目C(j=3}、项目D(j=4)的金额。根据题意，我们建立如下的决策变量:上一页下一页返回2.1线性规划模型结构与建模②考虑约束条件。由于项目A的投资当年年末就可以收回本息，因此在每一年的年初必然把所有的资金都投入到各项目中，否则一定不是最优的。下面，我们分年来考虑:

第1年年初:由于只有项目A和项目B可以投资，又应把全部200万元资金投出去，于是有 。第2年年初:由于项目B要次年年末才可收回投资，故第2年年初的资金只有第1年年初对项目A投资收回的本利110%x11，而投资项目为A,B和D，于是有  ，整理后得

。上一页下一页返回2.1线性规划模型结构与建模第3年年初:年初资金为第2年年初对项目A投资收回的本利110%x21,第1年年初对项目B投资收回的本利125%x22。可投资项目有A,B和C，于是有 ，整理后得 。第4年年初:年初的资金为第3年年初对项目A投资收回的本利110%x31,第2年年初对项目B投资收回的本利125%x22。可投资项目只有A和B，于是有 ，整理后得 。上一页下一页返回2.1线性规划模型结构与建模第5年年初:年初的资金为第4年年初对项目A投资收回的本利110%x41,第3年年初对项目B投资收回的本利125%x32。可进行投资项目 只有A一个，于是有 ,整理后得 。其他的还有项目B,C,D的投资限制以及各决策变量的非负约束。项目B的投资限制 ;项目C的投资限制: ;项目D的投资限制: 。上一页下一页返回2.1线性规划模型结构与建模各决策变量的非负约束:

。③建立目标函数。问题要求在第5年年末公司这200万元用于4个项目投资的运作获得本利最大，而第5年年末的本利获得有4项:

第5年年初对项目A投资收回的本利110%x51;第4年年初对项目B投资收回的本利125%x42;第3年年初对项目C投资收回的本利140%x33;第2年年初对项目D投资收回的本利155%x24。于是得到目标函数为:上一页下一页返回2.1线性规划模型结构与建模根据上面的分析得到线性规划模型上一页下一页返回2.1线性规划模型结构与建模思考题(1)线性规划的各种形式结构是怎样的?它们的共同点和区别是什么?各自优势是什么?(2)线性规划建模的主要步骤有哪些?其中的关键是什么?建模遵循的原则有哪些?(3)通过建模例题的分析介绍，谈谈你有哪些体会和收获？上一页返回下一页2.2线性规划的图解法2.2.1两个变量线性规划问题的作图求解下面讨论一个只有两个变量的简单情况下，线性规划模型的求解方法。这种方法虽然只能解决两个决策变量的问题，但是它得出的结论却有助于我们直观地理解线性规划解的性质及本质特征。对于只有两个变量的线性规划问题，可以在二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。根据解析几何的知识，我们知道，在平面直角坐标系中，两个变量的代数式与几何图形的关系是:等式表示一条直线;不等式表示一个半空间(半平面);函数在平面直角坐标系中表示为一组相互平行的等值线(对函数给定一个实数就确定一条直线)，当函数的取值取遍-∞到+∞时，这些等值线覆盖整个平面。

上一页下一页返回2.2线性规划的图解法

根据上述性质，作图求解线性规划问题的步骤如下。(1)分别取决策变量x1，x2为坐标向量建立平面直角坐标系。(2)对每个约束(包括非负约束)条件，取其等式在坐标系中作出直线。如果是不等式，则通过分析，判断确定不等式所决定的半平面。各约束直线(等式约束)或半平面(不等式约束)交出来的区域，若存在，其中的点表示的解称为此线性规划的可行解。这些符合约束限制的点集合，称为可行集或可行域。进行(3)；否则，若所交的集合为空集，那么该线性规划问题无可行解，显然无最优解。上一页下一页返回2.2线性规划的图解法(3)由于目标函数可表示为一组相互平行的等值线，于是我们可以先任意给定目标函数一个值，作出一条目标函数的等值线，并确定该等值线平移后这条直线对应的数值增加的方向。平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置(有时交于无穷远处，此时称无有限最优解)。若有交点，此目标函数等值线与可行域的交点即最优解(一个或无穷多个)，此目标函数对应的数值即最优值。考虑例2.1，用图解法求解。解：设变量xi为第i种(甲、乙)产品的生产件数(i=1,2)。根据前面的分析，可以建立如下的线性规划模型。上一页下一页返回2.2线性规划的图解法

按照图解法的步骤在以决策变量x1，x2为坐标向量的平面直角坐标系上对每个约束(包括非负约束)条件作出直线(A,B,C,D,E)，并通过判断确定不等式所决定的半平面。各约束半平面交出来的区域即可行集(可行域)如图2-1中阴影所示。上一页下一页返回2.2线性规划的图解法

任意给定目标函数一个值(如22500），然后作一条目标函数的等值线(z')，并确定该等值线平移后值增加的方向，平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置(z)，得到交点(5,25)T，此目标函数的值为z=70000。于是，我们得到这个线性规划的最优解x1=5，x2=25最优值z=70000，即最优方案为生产甲产品5件、乙产品25件，可获得最大利润为70000元。上一页下一页返回2.2线性规划的图解法2.2.2线性规划解的有关情况例2.8在例2.1的线性规划模型中，如果目标函数变为:那么，通过图解可得到:最优情况下目标函数的等值线与直线(A)重合。这时，最优解有无穷多个，是从点(5,25)T到点(15,10)T线段上的所有点，最优值为32500。如图2-2所示。例2.9在例2.1的线性规划模型中，如果约束条件(A)、(C)变为:上一页下一页返回2.2线性规划的图解法并且去掉(D,E)的非负限制。那么，可行域成为一个上无界的区域。这时，无有限最优解，如图2-3所示。例2.10在例2.1的线性规划模型中，如果增加约束条件(F)为:那么，可行域成为空的区域。这时，没有可行解，显然线性规划问题无解，如图2-4所示。根据以上的讨论，进一步分析可知，线性规划的可行域和最优解有下列几种可能的情况。(1)可行域为封闭的有界区域。①有唯一的最优解。②有无穷多个最优解。(2)可行域为非封闭的无界区域。①有唯一的最优解。上一页下一页返回2.2线性规划的图解法②有无穷多个最优解。③目标函数无界(即虽有可行解，但在可行域中，目标函数可以无限增大或无限减小)，因而无有限最优解。(3)可行域为空集。没有可行解，原问题无最优解。以上几种情况的图示如下(见图2-5).

有时人们从求解的角度，把无有限最优解和无可行解都称为无解。但在实践中两者有本质上的差别。上一页下一页返回2.2线性规划的图解法2.2.3线性规划可行域与解的特征(1)凸集、多面体与极点概念定义2.1设S是n维空间中的一个点集。若对任意n维向量 以及任意实数 ,有 。则称S为n维空间中的凸集。点x称为点x(1)和x(2)的凸组合。以上定义有明显的几何意义，它表示凸集S中的任意两点的连线都位于凸集S之中。图2-6所示为二维平面中一些凸集和非凸集的例子。通过前面两个决策变量的例题，我们看到，如果线性规划的可行域非空，那么是一个多边形(包括无界的情况)。把这种多边形的概念推广，称n维空间中，有限半闭空间的交(如果非空)为多面体。显然，多面体是凸集。上一页下一页返回2.2线性规划的图解法

根据上文分析，我们了解到有2个决策变量的线性规划问题的下列明显特征。进一步可以证明，对于n维空间的线性规划问题，其可行域以及最优解同样有以下性质。

(1)若线性规划的可行域非空，则可行域必定为一凸集。

(2)若线性规划的可行域非空，则至多有有限个极点。

(3)若线性规划有最优解，则至少有一个极点是最优解。这一关于线性规划的解的性质的总结，使我们在求解线性规划问题的道路上前进了一大步。通过图解法的分析与推论，可知求线性规划最优解的问题，从在可行域内无限个可行解中搜索的问题转化为在其可行域的有限个极点上搜索的问题。思考题(1)两个变量的线性规划作图求解有哪些步骤?(2)从图解法可以看出线性规划的可行域和解有哪些情况?上一页返回下一页2.3线性规划解的概念与性质2.3.1线性规划问题的规范形式和标准形式线性规划模型(2-1)~模型(2-3)的形式是多样化的，难于建立线性规划问题的一般求解方法。为了建模和计算两个角度的方便与可行，下面提出线性规划问题的规范形式和标准形式。(l)规范形式:下一页返回上一页2.3线性规划解的概念与性质矩阵形式:

线性规划的规范形式有四个特点:目标最大化、约束为小于等于、决策变量均非负、右端项非负。(2)标准形式:上一页下一页返回2.3线性规划解的概念与性质矩阵形式:上一页下一页返回2.3线性规划解的概念与性质

线性规划的标准形式有四个特点:目标最大化、约束为等式、决策变量均非负、右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下的变换将其转化为标准形式。(1)目标函数极小化的情况:

设目标函数为则可以令z=-f，以上极小化问题和这个极大化问题有相同的最优解，即但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即上一页下一页返回2.3线性规划解的概念与性质(2)约束条件不是等式的情况:设约束条件为 ，可以引进一个新的变量、，使它等于约束右边与左边之差显然，、也具有非负性质，即s≧0，这时新的约束条件成为当约束条件为 ,时，类似地令为了使约束由不等式成为等式而引进的变量‘称为“松弛变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。上一页下一页返回2.3线性规划解的概念与性质例2.11将以下线性规划问题转化为标准形式。解:首先，将目标函数转换成极大化:令其次考虑约束，有2个不等式约束，引进松弛变量x4,x5≧0于是，我们可以得到以下标准形式的线性规划问题:上一页下一页返回2.3线性规划解的概念与性质(3)变量无符号限制的情况:

在标准形式中，必须每一个变量均有非负约束。当某一个变量二没有非负约束时，可以用两个非负变量之差来表示这个无符号限制的变量， ，令上一页下一页返回2.3线性规划解的概念与性质显然，xj的任何取值均可以通过xj‘和xj“这两个非负变量的取值决定。特别注意到，如果能够保证xj’;和x”中至少有一个为零，那么xj‘和xj“分别表示二的正、负分量值。读者可以进一步思考，在标准化的线性规划模型中是否能保证xj’和xj;中至少有一个为零。

(4)右端项有负值的问题:

在标准形式中，要求右端项均非负。当某一个右端项系数为负时，如bi<0，则把该等式约束两端同时乘以一1，得到例2.12将下列线性规划问题转化为标准形式上一页下一页返回2.3线性规划解的概念与性质解首先，将目标函数转换成极大化:令其次考虑约束，有3个不等式约束，引进松弛变量由于二2无非负限制，可以令 ，其中 上一页下一页返回2.3线性规划解的概念与性质由于第3个约束右端项系数为-58，于是把该式两端乘以-1。于是，我们可以得到以下标准形式的线性规划问题:上一页下一页返回2.3线性规划解的概念与性质2.3.2线性规划的基、基本解与基本可行解线性规划的图解法虽然简便、明了，并且可以从理论上告诉我们线性规划的一些基本特征，但在实际上，一般问题都有两个以上的决策变量无法用图解法求解，所以必须探寻另外的求解途径。通过图解法看到一般线性规划的特征，可得到启示:线性规划的最优解如果存在，必定可以在可行域的某个极点上达到，问题可转化为如何找到并确定这些极点。在一般情况下，对于n个变量的线性规划问题，我们可以通过求解代数方程的方法来求得可行域的极点。通过进一步考察例2.1来进行研究。上一页下一页返回2.3线性规划解的概念与性质例2.13把例2.1的线性规划模型标准化，引入松弛变量 ,得到

用(D),(E),(F),(G),(H)分别表示 。 上一页下一页返回2.3线性规划解的概念与性质这里一共有8个约束条件，其中3个等式约束(一般情况下，等式约束的个数少于决策变量的个数)，5个变量非负约束(与决策变量个数相同)。根据线性代数理论可知，每5个方程，若系数矩阵线性无关可解得一个点。理论上3个等式必须满足，与(D),(E),(F),(G),(H)中的任2个可构成5个方程的线性方程组，若系数矩阵线性无关可解得一个点。由于(A)，(B)，(C)，(E),(H)系数矩阵线性相关，无解，因此我们可得到9个点。(1)约束条件(A),(B),(C),(D),(G)的解:(2)约束条件(A),(B),(C),(D),(F)的解:(3)约束条件(A),(B),(C),(D),(H)的解:(4)约束条件(A),(B),(C),(D),(E)的解:(5)约束条件(A),(B),(C),(D),(F)的解:上一页下一页返回2.3线性规划解的概念与性质(6)约束条件(A),(B),(C),(G),(H)的解:(7)约束条件(A),(B),(C),(F),(G)的解:(8)约束条件(A),(B),(C),(E),(G)的解:(9)约束条件(A),(B),(C),(E),(F)的解:

我们考察例2.1图解法得到的区域，区域中每两条直线的交点共有9个与此对应，实际上是这个标准形式模型在由x1,x2构成的平面上的投影。这9个点分为两类，如图2-7所示。其中， ，是可行解，不可行，因为含有负分量。上一页下一页返回2.3线性规划解的概念与性质

分析上述线性方程组的求解过程，可以得到一种更简洁的思路:上述约束方程组中，除(A)}(B)}(C)外，其余s个方程实质上是s个变量的非负约束，在选择约束条件构成线性方程组的过程中，选择两个非负约束构成的方程，实质上相当于令这两个变量为零。所以上述线性方程组的求解实质就是令其中某两个变量为零，得到其他变量的唯一解，这个解就是相应交点的坐标。如果某一交点 的所有分量均满足非负条件，可以证明，该交点就对应于线性规划可行域的一个极点，如点(3),(4),(5),(7),(8)。这样，可以将s维线性方程组的求解转化为三维方程组的求解，后面将看到这一思路更有价值。由图2-7可知，点(7)对应于x3=0,x4=0。在等式约束中令x3=0,x4=0,得到x1=15,x2=10,x5=45，即对应于极点上一页下一页返回2.3线性规划解的概念与性质下面讨论线性规划标准形式的基、基本解、基本可行解的概念。把例2.13的结论推广到一般情况。考虑线性规划标准形式的约束条件:其中A为mxn的矩阵n>m, ,在约束等式中，令n维空间的解向量:中n一m,个变量为零，如果剩下的m,个变量在线性方程组中有唯一解，则这n个变量的值组成的向量x就对应于n维空间R中若干个超平面的一个交点。当这n个变量的值都非负时，这个交点就是线性规划可行域的一个极点。根据以上分析，我们建立以下概念。(1)线性规划的基。对于线性规划的约束条件上一页下一页返回2.3线性规划解的概念与性质设B是A矩阵中的一个非奇异(可逆)的mxm子矩阵，则称B为线性规划的一个基。用前文的记号， ，其中 ,任取A中的m个线性无关列向量 构成矩阵 。那么B为线性规划的一个基。我们称对应于基B的变量 为基变量，而其他变量称为非基变量。不失一般性，可以用矩阵来描述这些概念如下:设B是线性规划的一个基，则A可以表示为x也可相应地分成上一页下一页返回2.3线性规划解的概念与性质其中xB。为m维列向量，它的各分量称为基变量，与基B的列向量对应;xN为n一m维列向量，它的各分量称为非基变量，与非基矩阵N的列对应。这时约束等式Ax=b可表示为 或如果对非基变量xN取确定的值，则xB有唯一的值与之对应特别，当取xN=0，这时有 。上一页下一页返回2.3线性规划解的概念与性质(2)线性规划问题的基本解、基本可行解和可行基。对于线性规划问题，设矩阵 为一个基，令所有非基变量为零，可以得到m个关于基变量 的线性方程，解这个线性方程组得到基变量的值。我们称这个解为一个基本解;若得到的基变量的值均非负，则称为基本可行解，同时称这个基B为可行基。矩阵描述为，对于线性规划的解称为线性规划与基B对应的基本解。若 ，则称以上的基本解为一基本可行解，相应的基B称为可行基。上一页下一页返回2.3线性规划解的概念与性质我们可以证明这个结论:线性规划的基本可行解就是可行域的极点。这个结论被称为线性规划的基本定理，它的重要性在于把可行域的极点这一几何概念与基本可行解这一代数概念联系起来，因而可以通过求基本可行解的线性代数的方法得到可行域的一切极点，从而有可能进一步获得最优极点。这是在求解线性规划问题的道路上又一重大进展，通过图解法我们知道，线性规划的最优解一般在极点上得到，而现在通过求解线性方程组可以求得这些极点的值及相应的目标函数值。例2.14考虑例2.13的线性规划模型:上一页下一页返回2.3线性规划解的概念与性质讨论其基本解、基本可行解(极点)和可行基。注意，线性规划的基本解、基本可行解(极点)和可行基只与线性规划问题标准形式的约束条件有关。上一页下一页返回2.3线性规划解的概念与性质A矩阵包含以下10个3x3的子矩阵:其中 上一页下一页返回2.3线性规划解的概念与性质其行列式 ，因而B4不是线性规划的基。其余均为非奇异方阵，因此该问题共有9个基。对于基 ，令非基变量 ，在等式约束中令 ，解线性方程组:得到 ，对应于基本可行解于是对应于基B3是一个可行基。上一页下一页返回2.3线性规划解的概念与性质类似可得到 , , ,是基本可行解；而 ， ， ， ，是基本解。因此，对应基本可行解(极点)的B2,，B3,，B5，B7，B10)都是可行基。由此，我们可以找到一种求解线性规划问题的可能途径:就是先确定线性规划问题的基，如果是可行基，则计算相应的基本可行解以及相应解的目标函数值。由于基的个数是有限的(最多个)，因此必定可以从有限个基本可行解中找到最优解。上一页下一页返回2.3线性规划解的概念与性质

但是，存在一个不可忽视的问题:线性规划基的个数随着问题规模的增大而很快增加，以至在实际上成为(在有限时间内)不可穷尽的。例如，一个有50个变量，20个约束等式的线性规划问题，其最多可能有个基。为了说明计算所有基本解的计算量有多大，我们假定计算一个基本解(即求解一个20x20的线性方程组)只需要一秒钟，那么计算以上所有的基本解需要即约150万年。显然，这种思路对于求解较大规模的问题是不可行的。下面将介绍单纯形法，可以极为有效地解决大规模的线性规划问题。上一页下一页返回2.3线性规划解的概念与性质思考题(1)线性规划的规范形式和标准形式的特点是什么?两者有什么不同?(2)如何把一般的线性规划问题化为规范形式或标准形式?(3)对于线性规划的标准形式，深入理解墓、墓变量、非墓变量、墓本解、墓本可行解的概念。如何找到这些量?他们与线性规划求解的关系是什么?上一页返回下一页2.4线性规划单纯形法2.4.1单纯形法的基本思路及其实现

1)单纯形法的基本思路上文介绍的通过求线性规划问题基本可行解(极点)寻找最优解的方法属于穷举法或枚举方法，但是对于规模较大的问题，实现起来有困难。一种自然的想法就是不一定要求所有的基本可行解，只选择性地求部分基本可行解来找到最优解，但问题是如何选择。目标是寻找一个思路，使得只要有最优解存在，就一定能够找到。单纯形法提供了这样的思路和准则。基本思路是:有选择地取基本可行解，从可行域的一个极点出发，沿着可行域的边界移到另一个相邻的极点，要求新极点的目标函数值不比当前极点的目标函数值差。单纯形法的基本过程如图2-8所示。下一页返回上一页2.4线性规划单纯形法由上节的讨论可知，对于线性规划的一个基，当非基变量确定以后，基变量和目标函数的值也随之确定。因此，一个基本可行解向另一个基本可行解的移动，以及移动时基变量和目标函数值的变化，可以分别由基变量和目标函数用非基变量的表达式来表示。同时，在可行解从可行域的一个极点沿着可行域的边界移动到一个相邻的极点的过程中，所有非基变量中只有一个变量的值从0开始增加，而其他非基变量的值都保持0不变。2)线性规划的典式形式上一页下一页返回2.4线性规划单纯形法考虑标准形式的线性规划问题:记上一页下一页返回2.4线性规划单纯形法这里，矩阵A表示为: ，其中 。若找到一个可行基，不妨设 ，则m个基变量为 ，个非基变量为通过运算，所有的基变量都可以用非基变量来表示：把它们代入目标函数，上一页下一页返回2.4线性规划单纯形法其中，我们把由非基变量表示的目标函数形式称为基B相应的目标函数典式。3)初始基本可行解采用单纯形法求解线性规划问题，首先需要确定一个初始基本可行解，确定这一初始基本可行解的原则是要容易得到，最好能够直接观察，不需计算即得到。对规范形式的线性规划问题，确定初始基本可行解的方法是:在化为标准形式时，在每个约束条件的左端增加一个松弛变量，这些松弛变量的系数正好构成一单位矩阵，以这些松弛变量为基变量，其余变量为非基变量。令非基变量全部为零，求解这一线性方程组，各松弛变量的取值就是其对应的右端项的值，而右端项始终大于零，所以这一基本解是可行解，即极点。上一页下一页返回2.4线性规划单纯形法4)单纯形法的基本步骤线性规划单纯形法的基本过程可描述如下。

(a)寻找一个初始的可行基和相应基本可行解(极点)，确定基变量、非基变量以及基变量、非基变量(全部等于0)和目标函数的值，并将目标函数和基变量分别用非基变量表示，即得到对应初始可行基的目标函数典式。

(b)在用非基变量表出的目标函数表达式(2-14)中，我们称非基变量二的系数(或其负值)为检验数，记为o-。若};>0，那么相应的非基变量二，它的值从当前值0开始增加时，目标函数值随之增加。这个选定的非基变量二称为“进基变量”，转(c)。如果任何一个非基变量的值增加都不能使目标函数值增加，即所有o-非正，则当前的基本可行解就是最优解，计算结束。上一页下一页返回2.4线性规划单纯形法(C)在基变量用非基变量表出的表达式(2-13)中，观察进基变量增加时各基变量变化情况，确定基变量的值在进基变量增加过程中首先减少到0的变量r，满足这个基变量x,称为“出基变量”。当进基变量的值增加到a，出基变量x,的值降为0时，可行解就移动到了相邻的基本可行解(极点)，转(d)。如果进基变量的值增加时，所有基变量的值都不减少，即所有心永远非正，则表示可行域是不封闭的，且目标函数值随进基变量的增加可以无限增加，此时不存在有限最优解，计算结束。

(d)将进基变量作为新的基变量，出基变量作为新的非基变量，确定新的基、新的基本可行解和新的目标函数值。在新的基变量、非基变量的基础上重复(a)-(d)。上一页下一页返回2.4线性规划单纯形法例2.15用单纯形法的基本思路解例2.11的线性规划问题:解：第一次迭代:(a)取初始可行基 ，那么x3,x4,x5为基变量x1,x2为非基变量。上一页下一页返回2.4线性规划单纯形法将基变量和目标函数用非基变量表出:当非基变量x1,x2=0时，相应的基变量和目标函数值为x3=65,x4=40,x5=75,z=0得到当前的基本可行解: 。这个解对应于图2-7的交点(4)。

(})选择进基变量。在目标函数z=1500x1+2500x2中，非基变量x1,x2的系数都是正数，因此x1,x2进基都可以使目标函数z增大，但x2的系数为2500，绝对值比x1的系数1500大，因此x2进基可以使目标函数z增加更快。选择x2进基，使x2的值从0开始增加，另一个非基变量x1保持零值不变。上一页下一页返回2.4线性规划单纯形法(C)确定出基变量。在约束条件中，由于进基变量x2在3个约束条件中的系数都是负数，当x2的值从0开始增加时，基变量x3,x4,x5的值分别从当前的值65,40和75开始减少，当x2增加到25时,x5首先下降为0成为非基变量。这时，新的基变量为x3,x4,x2

新的非基变量x1,x5当前的基本可行解和目标函数值为:

，这个解对应于图2-7的交点(3)。第二次迭代:(a)当前的可行基为 ，那么 为基变量， 为非基变量。将基变量和目标函数用非基变量表出:上一页下一页返回2.4线性规划单纯形法(b)选择进基变量。在目标函数z=62500+1500x1-(2500/3)x5中非基变量x1的系数是正数，因此x1进基可以使目标函数z增大，于是选择x1进基，使x1的值从0开始增加，另一个非基变量x5保持零值不变。(c)确定出基变量。在约束条件上一页下一页返回2.4线性规划单纯形法由于进基变量x1，在两个约束条件中的系数都是负数，当x1的值从0开始增加时，基变量x3,x4的值分别从当前的值15，15开始减少，当x1增加到5时，x3首先下降为0成为非基变量。这时，新的基变量为x1,x2,x4,新的非基变量为x3,x5，当前的基本可行解和目标函数值为: ,这个解对应于图2-7的交点(5)。第三次迭代:(a)当前的可行基为 ，那么 为基变量， 为非基变量。将基变量和目标函数用非基变量表出:上一页下一页返回2.4线性规划单纯形法(b)选择进基变量。在目标函数 中，非基变量 的系数均不是正数，因此进基都不可能使目标函数z增大，于是得到最优解， ，最优目标值为 。这个解对应于图2-7的交点(5)。我们也称相应的基

B2= 为最优基。计算结束。 例2.16用单纯形法的基本思路解下列线性规划问题:

上一页下一页返回2.4线性规划单纯形法这里，(A)，(B)，(C)，(D)，(E)分别表示作二维图形时，各约束边界直线。解：标准化后得到我们记上一页下一页返回2.4线性规划单纯形法A矩阵包含以下10个3x3的子矩阵:第一次迭代:(a)取初始可行基 ，那么 为基变量， 为非基变量。将基今量和目标I-Ikl数用非基今量夫出:上一页下一页返回2.4线性规划单纯形法当非基变量 ，时，相应的基变量和目标函数值为 ，得到当前的基本可行解和目标函数值为: ，这个解对应于直线B,C的交点。(b)选择进基变量。在目标函数 中,非基变量x4的系数是正数，因此x4进基可以使目标函数z增大，于是选择x4进基，使x4的值从0开始增加，另一个非基变量x4保持零值不变。(c)确定出基变量。在约束条件上一页下一页返回2.4线性规划单纯形法中，由于进基变量x4在所有约束条件中的系数均是非负数，当x4的值增加时，所有基变量的值都不减少，则说明此可行域是不封闭的，且目标函数值随进基变量的增加可以无限增加。因此，不存在有限最优解，计算结束。考虑规范形式的线性规划问题，其中上一页下一页返回2.4线性规划单纯形法加入松弛变量，化为标准形式:1)构造初始单纯形表考虑(2-15)，显然 ，对应一个基是单位矩阵，得到一个基本可行解为:上一页下一页返回2.4线性规划单纯形法用非基变量来表示基变量如下:对于一般情况，如果标准形式的目标函数为:把(2-16)代入，可以得到其中上一页下一页返回2.4线性规划单纯形法

为了便于计算，可以利用一种合理的表格形式来描述上述计算的量，把这种表格称为单纯形表。显然，当 ，是一个基本可行解时，对应的基是单位矩阵。可以构造如下的初始单纯形表(见表2-7)。其中， ，为检验数，同时这一变化过程的实质，相当于利用消元法把目标函数中的基变量消去，用非基变量来表示目标函数。因此，所得到的最后一行中非基变量的系数即为检验数σi，而常数列则是-z的取值-z'。把这些信息设计成表格，即为初始单纯形表。上一页下一页返回2.4线性规划单纯形法表中，xB列填入基变量，这里是 ; cB列填入基变量，这里是 ;b列中填入约束方程右端的常数，代表基变量的取值;第2行填入所有的变量名作为标识，第1行填入相应变量的价值系数;第4列至倒数第2列、第3行至倒数第2行之间填入整个约束系数矩阵;末行称为检验数行，这一行中对应于各个非基变量的检验数为σi，而对应于基变量的检验数均为零。在运算过程中，cB列的基变量相对应的价值系数随基变量的变化而改变。填入这一列的目的是为了便于在表格中计算目标函数值(相反数)、检验数σi

，由表中检验数行(最后一行)可以看出上一页下一页返回2.4线性规划单纯形法恰好是由0(b列)及xj的价值系数cj减去cB列的各元素与b、xj二列各对应元素的乘积。

θi列的数字:在确定了换入变量xk以后，当xk列的对应元素aik>0时，是由b列的元素bi除以aik计算出来的;当xk列的对应元素aik≤0时，不计算或记θi=∞。即在初始单纯形表第3列至倒数第2列中，从第3行开始的m,行是用非基变量表示基变量的函数表达式，也是所有的约束条件(除非负约束外)的左端函数。最后一行是用非基变量表示的目标函数的系数，而原来的目标函数系数可由第一行得到。当前基变量是xB。列的变量时，上一页下一页返回2.4线性规划单纯形法当前xB的取值在b列。因此该表中既包含原问题的信息，也包含了当前基本可行解的信息，以及最优性检验所需的信息，因而可以利用它来进行单纯形法的迭代。值得注意的是，由于标准形式假设了b非负，因而可保证初始单纯形表代表的必然是基本可行解。

2)单纯形法的迭代在上述初始单纯形表的基础上，按下列规则过程进行迭代，可以得到如表2-8所示的一般形式的单纯形表。经过有限步迭代，将寻求到线性规划问题的解。上一页下一页返回2.4线性规划单纯形法其中： ，为检验数，同时

我们有下面结论:(1)若在单纯形表中，所有σj≤0，则当前基本可行解是最优解;否则，若存在σk＞0则可选xk进基。