5.3解线性规划问题的表格法

线性规划的单纯形法表格方法 Max. z=5x 1+2x 2+3x 3 -x 4 +x 5 s.t. x 1+2x 2+2x 3 +x 4 =8 3x 1+4x 2+x 3 +x 5 =7 x j ≥0 j=1,2,3,4,5表1由表的中间行可求出基本可行解，令x1=x2=x3=0,由约束条件得 x4=8,x5=7. 表中最后一行分别为：()1787811-=+-=⎪⎪⎭⎫ ⎝⎛-=z ()3)31(53111511=+--=⎪⎪⎭⎫ ⎝⎛--=-z c ()0)42(24211222=+--=⎪⎪⎭⎫ ⎝⎛--=-z c ()4)12(31211333=+--=⎪⎪⎭⎫⎝⎛--=-z c 因为c j -z j 行中存在正值，所以当前基本可行解不是最优解。

c j -z j 行中的4最大因而非基变量X 3使z 有最大的单位增量，把X 3选作新的（换入）基变量。

为确定被换出的基变量，采用最小比值法。

用X 3列的值除以约束条件的常数（8/2=4，7/1=7）。

第一行有最小比值，把它叫做旋转行。

第一行原来的基变量是X 4 ，此时X 4为换出基变量，新的基变量为X 3、X 5。

为此需要把表中X 3对应在约束条件中系数变为单位值（1，0）。

在表1中：1）用2除旋转行使X 3系数为1；2）用-1/2乘旋转行加到第二行消去X 3。

()153123413=+=⎪⎪⎭⎫ ⎝⎛=z ()1455/2/2113511=-=⎪⎪⎭⎫ ⎝⎛-=-z c ()-4623113222=-=⎪⎪⎭⎫ ⎝⎛-=-z c ()-21-11/2-21/13-133=-=⎪⎪⎭⎫⎝⎛-=-z c 因为c j -z j 行中仍存在正值，所以当前基本可行解不是最优解。

c j -z j 行中的1最大因而非基变量X 1使z 有最大的单位增量，把X 1选作新的（换入）基变量。

为确定被换出的基变量，采用最小比值法。

用X 1列的值除以约束条件的常数（4/(1/2)=8，3/(5/2)=6/5）。

线性规划问题的两种求解方式线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。

线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好。

一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。

解决线性规划问题常用的方法是图解法和单纯性法，而图解法简单方便，但只适用于二维的线性规划问题，单纯性法的优点是可以适用于所有的线性规划问题，缺点是单纯形法中涉及大量不同的算法，为了针对不同的线性规划问题，计算量大，复杂繁琐。

在这个计算机高速发展的阶段，利用Excel建立电子表格模型，并利用它提供的“规划求解”工具，能轻松快捷地求解线性模型的解。

无论利用哪种方法进行求解线性规划问题，首先都需要对线性规划问题建立数学模型，确定目标函数和相应的约束条件，进而进行求解。

从实际问题中建立数学模型一般有以下三个步骤；1、根据所求目标的影响因素找到决策变量；2、由决策变量和所求目标的函数关系确定目标函数；3、由决策变量所受的限制条件确定决策变量所要满足的约束条件。

以下是分别利用单纯形法和Excel表格中的“规划求解”两种方法对例题进行求解的过程。

例题：某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时分别为1台时、2台时，所需原材料A分别为4单位、0单位，所需原材料B分别为0单位、4单位，工厂中设备运转最多台时为8台时，原材料A、B的总量分别为16单位、12单位。

每生产出I、II产品所获得的利润为2和3，问I、II两种产品的生产数量的哪种组合能使总利润最大？问题的决策变量有两个：产品I的生产数量和产品II的生产数量；目标是总利润最大；需满足的条件是：(1)两种产品使用设备的台时<= 台时限量值(2) 生产两种产品使用原材料A、B的数量<= 限量值(3)产品I、II的生产数量均>=0。

线性规划问题计算机解法本节将简要介绍几种软件求解线性规划问题的方法．1.6.1应用EXCEL求解线性规划问题以EXCEL2007为例，首先加载EXCEL规划求解加载项，具体操作步骤为：Office按钮——EXCEL选项——加载项——转到——加载宏——规划求解加载项，此时在“数据”选项卡中出现带有“规划求解”按钮的“分析”组．下面仍然以例１．５为例，说明其求解过程：１设计电子表格将模型中的数据直接输入到工作表中并保存文档．其中，Ａ列为说明性文字，Ａ3为决策变量的初始值，可以任意给定，本例均设为０；在Ｄ4其中键入“=SUMPRODUCT (B$3:C$3,B4:C4)”或者从直接从函数中选择，SUMPRODUCT是EXCEL的一个内置函数，,x x初始其功能是两个向量或者矩阵对应元素乘积的和，因此表示表示目标函数值，由于12值设为０，因而显示０；同理在Ｄ5其中键入“=SUMPRODUCT(B$3:C$3,B5:C5)”，以此类推，其显示值均为０．２设置规划求解参数点击“分析”组中的“规划求解”按钮即可弹出如下对话框：在设计目标目标单元格中键入$D$4，或者直接点击单元格D4，并选择“最大值”选项，如下图所示点击对话框中“添加”，弹出如下对话框在“单元格引用位置”栏中键入“$D$ 5”（或点击单元格D5），选择“<=”(点击出现下拉菜单，可以选择其他约束形式)，在约束值栏中键入“$F$5”（或点击单元格F5），确定后弹出下面对话框：类似于上一步操作，添加所有的约束条件后如下图所示：3 应用规划求解工具：点击“求解”弹出如下对话框，选择“保存规划求解结果”与“运算结果报告”确定后则形成一张新的工作表：如果想得到价值系数、资源向量等条件对最优值的影响，可以在步骤3中选择输出“敏感性报告”．1.6.1应用LINGO求解线性规划问题从上面的介绍中看出，用EXCEL求解线性规划问题时操作简单，而其在输入数据方面有其方便之处．但如果决策变量和约束条件很多的话，其运行速度就不及专业的优化软件了．本节介绍一种专业的优化软件－－LINGO的使用方法．LINDO 是 Linear Interactive Discrete Optimizer的缩写，是一个线性和整数规划的软件系统. LINDO /386 5.3以上版本，最大规模的模型的非零系数可以达到1,000,000个，最大变量个数可以达到100,000个，最大目标函数和约束条件个数可以达到32000个，最大整数变量个数可以达到100,000个。

表格法解线性规划问题【教学目标】知识目标:理解用表格法解线性规划问题得方法与步骤、能力目标:通过例子详细地介绍了表格法解线性规划问题得过程,并引入了线性规划标准型得概念,归纳总结了表格法解线性规划问题得步骤、【教学重点】理解用表格法解线性规划问题得方法与步骤、【教学难点】理解用表格法解线性规划问题得方法与步骤、【教学设计】1、表格法也称单纯形法,就是解线性规划问题得常用方法,使用该方法时,首先要将一般得线性规划问题化为标准型、在教材中给出了化标准型得方法、讲解时一定要注意b≥0以及变量得非负性、2、表格法解线性规划问题得过程,教材中归纳为五个步骤,这实际上就是一个算法,可以利用前面介绍过得算法知识来学习、3、初始表格中初始解组得确定就是关键,一般可取松弛变量,但当标准型中没有这样得变量满足初始解组得要求时,通常要通过添加人工变量来解决,本教材没有就这方面得问题进行深入讨论(一般得运筹学教材中都可找到该内容)、4、表格在转换时(通常称为转轴),教材中提到用加减消元法来转轴、教师可就这部分内容作适当得讲解、5、由于通常得表格转换要进行多次,而表头部分就是不变得,因此可以将多张表格合并起来,具体样式可参见5、5节表5-16、【教学过程】5.3.1线性规划问题得标准形式求线性规划问题得图解法虽然直观简便,但对多于两个变量得情况就不能适用了,对于多于两个决策变量得线性规划问题,可以用什么方法呢？下面介绍一种用表格得方法来求解线性规划问题得解、 表格法就是根据单纯形法而专门设计得一种计算表格、 单纯形法(Simple Method)就是求解线性规划问题得主要方法,该法由丹赛(Dantzig)于1947年提出,后经过多次改进而成,就是求解线性规划问题得实用算法、由上节得叙述可知,如果线性规划问题得最优解存在,则必定可以在其可行解集合得顶点(极点)中找到.因此,寻求一个最优解就就是在其可行域得各个极点中搜索最优点、单纯形法实质上就是一个迭代过程,该迭代即就是从可行域得一个极点移到另一个近邻得极点,直到判定某一极点为最优解为止、为使用表格法,首先介绍线性规划问题得标准形式、一般得线性规划问题中目标函数可能就是求最大(或最小)值,而线性约束条件中可能就是线性方程,也可能就是线性不等式,约束条件中约束方程(或不等式)得个数也未必就比决策变量得个数少,这些问题对于线性规划得求解,带来极大得不便,为此,引入下述标准形式:求目标函数最大值 n n x c x c x c x c Z ++++=...m ax 332211 (用与式表示为j j nj x c Z ∑==1max )⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥≥=+++=+++=+++0,...,0,0.....................2122112222212111212111n mn mn m m n n n n x x x b x a x a x a b x a x a x a b x a x a x a 满足用与式表示为满足⎪⎩⎪⎨⎧=≥==∑=),,3,2,1(,0),,3,2,1(,1n j x m i b x a j i i ij nj 其中,),,2,1;,,3,2,1(,,n j m i c b a j i ij ==各都就是确定得常数,),,2,1(n j x j =就是决策变量,Z 就是目标函数,ij a 叫做技术系数,i b ≥0(),2,1m i =叫做资源系数,j c 叫做目标函数系数、 特点:1、目标函数为极大化;2、除决策变量得非负约束外,所有得约束条件都就是等式,且右端常数均为非负;3、所有决策变量均非负.如果根据实际问题建立起来得线性规划模型不就是标准型得,可以用下述方法将它化为标准型、(1)若目标函数就是n n x c x c x c x c Z ++++=...m in 332211可令,'z z -=将目标函数转化为)...(max 332211'n n x c x c x c x c Z ++++-= (2)若约束条件不等式中就是“≤”,可在不等式左边加上非负变量,将不等式转化为方程、如2126x x +≤180可转化为,18026321=++x x x 其中3x ≥0、这里得3x 叫做松弛变量、 表示没有用完得资源、(3)若约束条件不等式就是“≥”,可在不等式左边减去非负变量,将不等式转化为等式方程,如2122x x +≥10可转化为1022421=-+x x x ,其中,4x ≥0、这里得4x 叫做多余变量,表示不存在得资源、一般地,松弛变量与多余变量得目标函数系数为0、 (4)若有一个变量k x 没有非负约束(叫做自由变量),可令s l k x x x -=,其中l x ≥0,s x ≥0、 知识巩固例1 将5、1节问题1中得线性规划问题化为标准型约束条件 ⎪⎪⎩⎪⎪⎨⎧≥≥≤+≤+≤+0,0210534001041802621212121x x x x x x x x 求目标函数最大值 212231m ax x x Z +=解 分别对前三个约束条件引入松弛变量543,,x x x ,得标准型:约束条件 ⎪⎪⎩⎪⎪⎨⎧=≥=++=++=++.5,3,2,1,02105340010418026521421321 j x x x x x x x x x x j 求目标函数最大值 212231m ax x x Z +=5.3.2表格法下面我们通过实例来介绍表格法、首先要列出初始表格.为了得到初始表格,我们分几步来说明: 先把标准型中得约束条件方程转换成表格(表5、4)得形式. 如:5、1问题1转化得结果为:⎪⎪⎩⎪⎪⎨⎧=≥=++++=++++=++++.5,,2,1,02100053400001041800026543215432154321 j x x x x x x x x x x x x x x x x j 列成表格为: 表5、4(表格中得列数为变量个数加1,行数为方程个数加1) 从约束方程中,很容易得到,当01=x ,02=x 时,1803=x ,4004=x ,2105=x ,显然这就是一组可行解(我们把它叫作初始解组),将其中三个取非0值得变量543,,x x x 列成一列对应地加在上表得最左侧,然后再在所得表得左侧添加一列对应于该初始解组变量得目标函数系数,在表得上侧添加一行对应于各变量得目标函数系数,得如下表:其中在初始解组中得变量必须满足在对应行得约束条件方程中系数为1,而同列其她系数为0,(如果约束条件方程中不满足这要求,可以通过对线性约束条件方程作加减消元法而得到、)再在上表得基础上,增加1行(叫做检验数行j σ)与1列(叫做比值列i θ)得下面形式:按下面得计算公式在表中依次填上检验数行j σ与比值列i θ,其中检验数计算公式,1ij mi i j j a c c ∑=-=σ例如31=j σ,即为1x 所在列得目标函数系数行中得1c 值减去该列系数与第一列初始解组得目标函数系数得对应乘积与,31)304060(311=⨯+⨯+⨯-=σ、选取检验数最大得正数所在列(记作k 列,表中用[ ]表示)然后计算比值i θ.比值得计算公式,0,>=ik ik i i a a b θ,例如61801=θ、 选取最小得i θ值,记所在行为i 行(表中用[ ]表示),如下表(1=i ) 最后填上目标函数Z 值一格,其中目标函数Z 为第一列B C 与b 所在列对应乘积与. 得下表:这样我们得到了初始表格(表5、7)显然,前面得初始解组并不能产生最优目标函数值,因此,必须要对初始解组中得变量进行替换,以求更好得解、通常,我们按下述方法进行变量得替换:根据上面所选得第k 列第i 行(如上表中3x 所在行与1x 所在列,我们将两者得交叉点用( )表示),对初始解组作调整,将变量k x 换入,替代第i 行中得初始变量(即表中换入1x ,换出3x ),根据表格法得要求,必须同时将换入变量k x 在( )中得系数通过加减消元法化为1,且同列其她系数为0,而初始解组中其她未换出变量所在列得系数不变,通常可用加减消元法来求得.下面我们具体来说明表格得转换.框中<A>行除以6得<A />行;<B>行减<A />×4得<B />行;<C>行减<A />×3得<C />行(表5、8转换到表5、9).表5、8表5、9再依次填上检验数行j σ与比值列i θ,得下表(表5、10).表5、10如果检验数全为非正数,那么,所得解就就是最优解.否则,继续按前方法修改可行解,直至不能继续为止.显然,上表中2x 换入,变量5x 换出.转下表(表5、11).表5、11因为所有得检验数j σ≦0,故当前可行解201=x ,302=x ,03=x ,04=x ,05=x 为最优解,删去松弛变量,即得原线性规划最优解为201=x ,302=x ,最优值为 Z=1280.通过上面得例子,可以归纳一般得表格法得计算步骤如下: 第一步:建立初始表格. 第二步:检查:若所有得j≤0,则当前可行解即为最优解;否则转入(3).第三步:检查:若存在k>0,且a ik ≤0,(i =1,2,…,m ),则无最优解;否则转入(4) .第四步:选取检验数行中最大得正数所在得列,(记作k 列,表中用[ ]表示)然后计算比值i θ,比值得计算公式0,>=ik ikii a a b θ.选取最小得i θ值,记所在行为i 行(表中用[ ]表示),确定x k ,将x k换入,将松弛变量x h 换出,用加减消元法化x k 得系数a ik 为1,且同列其她系数为0.以x k 取代x h 得新表,转入(2)、巩固知识 典型例题例2 用表格法解5、1节中得例1:某工厂用钢与橡胶生产3种产品A 、B 、C ,有关资料如表5、3所示、已知每天可获得100单位得钢与120单位得橡胶,问每天应按排生产A 、B 、C 三种产品各多少,能使总利润最大？试写出问题得线性约束条件与目标函数、表5、3产品 单位产品钢消耗量 单位产品橡胶消耗量 单位产品利润A2340则可得约束条件⎪⎩⎪⎨⎧≥≥≥≤++≤++0,0,012023310032321321321x x x x x x x x x目标函数为321244540m ax x x x Z ++= 解 引入松弛变量54,x x ,得标准型:321244540m ax x x x Z ++=满足 ⎪⎩⎪⎨⎧=≥=+++=+++5,3,2,1,01202331003253214321 j x x x x x x x x x j列初始表格(表5、12).表5、12因为2σ 为最大正数,转下表(表5、13).表5、13将1x 换入,5x 换出,得表5、14.表5、14因为所有得检验数j σ≦0,故当前可行解201=x ,202=x ,03=x ,04=x ,05=x 为最优解,删去松弛变量,即得原线性规划最优解为201=x ,202=x ,03=x ,目标函数最优值为 1700=Z 、。

表格法解线性规划问题【教学目标】知识目标：理解用表格法解线性规划问题的方法和步骤.能力目标：通过例子详细地介绍了表格法解线性规划问题的过程，并引入了线性规划标准型的概念，归纳总结了表格法解线性规划问题的步骤.【教学重点】理解用表格法解线性规划问题的方法和步骤.【教学难点】理解用表格法解线性规划问题的方法和步骤.【教学设计】1、表格法也称单纯形法，是解线性规划问题的常用方法，使用该方法时，首先要将一般的线性规划问题化为标准型.在教材中给出了化标准型的方法.讲解时一定要注意b≥0以及变量的非负性.2、表格法解线性规划问题的过程，教材中归纳为五个步骤，这实际上是一个算法，可以利用前面介绍过的算法知识来学习.3、初始表格中初始解组的确定是关键，一般可取松弛变量，但当标准型中没有这样的变量满足初始解组的要求时，通常要通过添加人工变量来解决，本教材没有就这方面的问题进行深入讨论（一般的运筹学教材中都可找到该内容）.4、表格在转换时（通常称为转轴），教材中提到用加减消元法来转轴.教师可就这部分内容作适当的讲解.5、由于通常的表格转换要进行多次，而表头部分是不变的，因此可以将多张表格合并起来，具体样式可参见5.5节表5-16.【教学过程】5.3.1线性规划问题的标准形式求线性规划问题的图解法虽然直观简便，但对多于两个变量的情况就不能适用了，对于多于两个决策变量的线性规划问题，可以用什么方法呢？下面介绍一种用表格的方法来求解线性规划问题的解. 表格法是根据单纯形法而专门设计的一种计算表格.单纯形法（Simple Method ）是求解线性规划问题的主要方法，该法由丹赛（Dantzig ）于1947年提出，后经过多次改进而成，是求解线性规划问题的实用算法.由上节的叙述可知，如果线性规划问题的最优解存在，则必定可以在其可行解集合的顶点（极点）中找到．因此，寻求一个最优解就是在其可行域的各个极点中搜索最优点.单纯形法实质上是一个迭代过程，该迭代即是从可行域的一个极点移到另一个近邻的极点，直到判定某一极点为最优解为止. 为使用表格法，首先介绍线性规划问题的标准形式.一般的线性规划问题中目标函数可能是求最大(或最小)值，而线性约束条件中可能是线性方程，也可能是线性不等式，约束条件中约束方程（或不等式）的个数也未必就比决策变量的个数少，这些问题对于线性规划的求解，带来极大的不便，为此，引入下述标准形式：求目标函数最大值 n n x c x c x c x c Z ++++=...m ax 332211 (用和式表示为j j nj x c Z ∑==1max )⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥≥=+++=+++=+++0,...,0,0.....................2122112222212111212111n mn mn m m n n n n x x x b x a x a x a b x a x a x a b x a x a x a 满足用和式表示为满足⎪⎩⎪⎨⎧=≥==∑=),,3,2,1(,0),,3,2,1(,1n j x m i b x a j i i ij nj 其中，),,2,1;,,3,2,1(,,n j m i c b a j i ij ==各都是确定的常数，),,2,1(n j x j =是决策变量，Z 是目标函数，ij a 叫做技术系数，i b ≥0（),2,1m i =叫做资源系数，j c 叫做目标函数系数. 特点：1、目标函数为极大化；2、除决策变量的非负约束外，所有的约束条件都是等式，且右端常数均为非负；3、所有决策变量均非负．如果根据实际问题建立起来的线性规划模型不是标准型的，可以用下述方法将它化为标准型.（1）若目标函数是n n x c x c x c x c Z ++++=...m in 332211可令,'z z -=将目标函数转化为)...(max 332211'n n x c x c x c x c Z ++++-= （2）若约束条件不等式中是“≤”,可在不等式左边加上非负变量，将不等式转化为方程.如2126x x +≤180可转化为,18026321=++x x x 其中3x ≥0.这里的3x 叫做松弛变量. 表示没有用完的资源.（3）若约束条件不等式是“≥”，可在不等式左边减去非负变量，将不等式转化为等式方程，如2122x x +≥10可转化为1022421=-+x x x ， 其中，4x ≥0.这里的4x 叫做多余变量，表示不存在的资源.一般地，松弛变量和多余变量的目标函数系数为0.（4）若有一个变量k x 没有非负约束（叫做自由变量），可令s l k x x x -=，其中l x ≥0，s x ≥0. 知识巩固例1 将5.1节问题1中的线性规划问题化为标准型约束条件 ⎪⎪⎩⎪⎪⎨⎧≥≥≤+≤+≤+0,0210534001041802621212121x x x x x x x x 求目标函数最大值 212231m ax x x Z +=解 分别对前三个约束条件引入松弛变量543,,x x x ，得标准型：约束条件 ⎪⎪⎩⎪⎪⎨⎧=≥=++=++=++.5,3,2,1,02105340010418026521421321 j x x x x x x x x x x j 求目标函数最大值 212231m ax x x Z +=5.3.2表格法下面我们通过实例来介绍表格法.首先要列出初始表格．为了得到初始表格，我们分几步来说明： 先把标准型中的约束条件方程转换成表格（表5.4）的形式． 如:5.1问题1转化的结果为：⎪⎪⎩⎪⎪⎨⎧=≥=++++=++++=++++.5,,2,1,02100053400001041800026543215432154321 j x x x x x x x x x x x x x x x x j 列成表格为： 表5.41x2x 3x 4x 5x i b6 2 1 0 0 180 4 10 0 1 0 400 351210(表格中的列数为变量个数加1，行数为方程个数加1) 从约束方程中，很容易得到，当01=x ，02=x 时，1803=x ，4004=x ，2105=x ，显然这是一组可行解（我们把它叫作初始解组），将其中三个取非0值的变量543,,x x x 列成一列对应地加在上表的最左侧，然后再在所得表的左侧添加一列对应于该初始解组变量的目标函数系数，在表的上侧添加一行对应于各变量的目标函数系数，得如下表：其中在初始解组中的变量必须满足在对应行的约束条件方程中系数为1，而同列其他系数为0，（如果约束条件方程中不满足这要求，可以通过对线性约束条件方程作加减消元法而得到.）再在上表的基础上，增加1行(叫做检验数行j σ)和1列(叫做比值列i θ)得下面形式：按下面的计算公式在表中依次填上检验数行j σ和比值列i θ,其中检验数计算公式,1ij mi i j j a c c ∑=-=σ例如31=j σ，即为1x 所在列的目标函数系数行中的1c 值减去该列系数与第一列初始解组的目标函数系数的对应乘积和，31)304060(311=⨯+⨯+⨯-=σ.选取检验数最大的正数所在列(记作k 列，表中用[ ]表示)然后计算比值i θ． 比值的计算公式,0,>=ik ik i i a a b θ，例如61801=θ. 选取最小的i θ值，记所在行为i 行(表中用[ ]表示)，如下表(1=i ）最后填上目标函数Z 值一格，其中目标函数Z 为第一列B C 与b 所在列对应乘积和． 得下表：这样我们得到了初始表格（表5.7）显然，前面的初始解组并不能产生最优目标函数值，因此，必须要对初始解组中的变量进行替换，以求更好的解.通常，我们按下述方法进行变量的替换：根据上面所选的第k 列第i 行(如上表中3x 所在行和1x 所在列，我们将两者的交叉点用( )表示)，对初始解组作调整，将变量k x 换入，替代第i 行中的初始变量(即表中换入1x ，换出3x )，根据表格法的要求，必须同时将换入变量k x 在( )中的系数通过加减消元法化为1，且同列其他系数为0，而初始解组中其他未换出变量所在列的系数不变，通常可用加减消元法来求得．下面我们具体来说明表格的转换．框中<A>行除以6得<A />行；<B>行减<A />×4得<B />行；<C>行减<A />×3得<C />行(表5.8转换到表5.9)．表5.8表5.9再依次填上检验数行j σ和比值列i θ，得下表(表5.10)．表5.10如果检验数全为非正数，那么，所得解就是最优解．否则，继续按前方法修改可行解，直至不能继续为止．显然，上表中2x 换入，变量5x 换出．转下表(表5.11)．表5.11因为所有的检验数j σ≦0，故当前可行解201=x ，302=x ，03=x ，04=x ，05=x 为最优解，删去松弛变量，即得原线性规划最优解为201=x ，302=x ，最优值为 Z=1280．通过上面的例子，可以归纳一般的表格法的计算步骤如下： 第一步：建立初始表格．第二步：检查：若所有的σj ≤0，则当前可行解即为最优解；否则转入(3)．第三步：检查：若存在σk >0,且a ik ≤0，(i =1,2,…,m )，则无最优解；否则转入(4) ．第四步：选取检验数行中最大的正数所在的列，(记作k 列，表中用[ ]表示)然后计算比值i θ，比值的计算公式0,>=ik ikii a a b θ． 选取最小的i θ值，记所在行为i 行(表中用[ ]表示)，确定x k ，将x k 换入，将松弛变量x h 换出，用加减消元法化x k 的系数a ik 为1，且同列其他系数为0．以x k 取代x h 得新表，转入(2). 巩固知识 典型例题例2 用表格法解5.1节中的例1：某工厂用钢与橡胶生产3种产品A 、B 、C ,有关资料如表5.3所示.已知每天可获得100单位的钢和120单位的橡胶，问每天应按排生产A 、B 、C 三种产品各多少，能使总利润最大？试写出问题的线性约束条件和目标函数.表5.3则可得约束条件⎪⎩⎪⎨⎧≥≥≥≤++≤++0,0,012023310032321321321x x x x x x x x x目标函数为321244540m ax x x x Z ++= 解 引入松弛变量54,x x ，得标准型：321244540m ax x x x Z ++=满足 ⎪⎩⎪⎨⎧=≥=+++=+++5,3,2,1,01202331003253214321 j x x x x x x x x x j列初始表格(表5.12)．表5.12因为2σ 为最大正数，转下表(表5.13)．表5.13将1x 换入，5x 换出，得表5.14．表5.14因为所有的检验数j σ≦0，故当前可行解201=x ,202=x ,03=x ，04=x ，05=x 为最优解，删去松弛变量，即得原线性规划最优解为201=x ,202=x ,03=x ，目标函数最优值为 1700=Z .。

Excel规划求解功能操作说明以Microsoft Excel2003为例，说明使用Excel的求解线性规划问题功能的使用方法。

一、加载规划求解功能1.点击【工具】按钮，在下拉菜单中选择【加载宏】功能。

2.在弹出的【可加载宏】选项卡中勾选【规划求解】，点击确定按钮。

此时，【工具】下拉菜单中增加规划求解功能，表示加载成功。

二、构造表格Excel表格并填入各项数据以教材18页【例题2-8】为例，构造表格如下：标题栏约束条件区目标函数区计算结果显示区1.录入约束条件系数约束条件（1）为5x 1+x 2-x 3+x 4=3，则在约束系数的第一行的x 1,x 2,x 3,x 4,x 5，限制条件，常数b 列下分别录入5,1，-1,1,0，=，3如下图所示。

约束系数区的第二行录入约束条件（2）的系数、限制符号及常数b ，即-10,6,2,0,1，=，2；约束系数区的第三行录入约束条件（3）（x1≥0）的系数、限制符号及常数b ，即1,0,0,0,0，≥，0；约束系数区的第四行录入约束条件（4）（x2≥0）的系数、限制符号及常数b ，即0,1,0,0,0，≥，0；约束系数区的第五行录入约束条件（5）（x3≥0）的系数、限制符号及常数b ，即0,0,1,0,0，≥，0；约束系数区的第六行录入约束条件（6）（x4≥0）的系数、限制符号及常数b ，即0,0,0,1,0，≥，0；约束系数区的第七行录入约束条件（7）（x5≥0）的系数、限制符号及常数b ，即0,0,0,0,1，≥，0。

如下图所示。

2.录入目标函数系数目标函数为maxZ=4x 1-2x 2-x 3，则在目标函数的x 1,x 2,x 3,x 4,x 5列下分别录入4，-2，-1,0,0，如下图所示。

3. 录入约束条件的计算公式双击约束条件（1）行的“总和”单元格，录入以下内容：“=B3*B12+C3*C12+D3*D12+E3*E12+F3*F12”说明：录入的内容即是约束条件（1）的计算公式，其中“B3*B12”代表5x1;“C3*C12”代表1x2；“D3*D12”代表-1x3；“E3*E12”代表1x4；“F3*F12”代表0x5。