【问题】表格法解线性规划问题

1、【关键字】问题表格法解线性规划问题【教学目标】知识目标：理解用表格法解线性规划问题的方法和步骤能力目标：通过例子详细地介绍了表格法解线性规划问题的过程，并引入了线性规划标准型的概念，归纳总结了表格法解线性规划问题的步骤【教学重点】理解用表格法解线性规划问题的方法和步骤【教学难点】理解用表格法解线性规划问题的方法和步骤【教学设计】1、表格法也称单纯形法，是解线性规划问题的常用方法，使用该方法时，首先要将一般的线性规划问题化为标准型,在教材中给出了化标准型的方法,讲解时一定要注意bRO以及变量的非负性.2、表格法解线性规划问题的过程，教材中归纳为五个步骤，这实际上是一个算法，可以利用前面介绍过的算

2、法知识来学习.3、初始表格中初始解组的确定是关键，一般可取松弛变量，但当标准型中没有这样的变量满足初始解组的要求时，通常要通过添加人工变量来解决，本教材没有就这方面的问题进行深入讨论（一般的运筹学教材中都可找到该内容）4、表格在转换时（通常称为转轴），教材中提到用加减消元法来转轴,教师可就这部分内容作适当的讲解.5、由于通常的表格转换要进行多次，而表头部分是不变的，因此可以将多张表格合并起来，具体样式可参见5,5节表5-16.【教学过程】求线性规划问题的图解法虽然直观简便，但对多于两个变量的情况就不能适用了，对于多于两个决策变量的线性规划问题，可以用什么方法呢？下面介绍一种用表格的方法来求解线

3、性规划问题的解表格法是根据单纯形法而专门设计的一种计算表格单纯形法（SimpleMethod）是求解线性规划问题的主要方法，该法由丹赛（Dantzig）于1947年提出，后经过量次改进而成，是求解线性规划问题的实用算法,由上节的叙述可知，如果线性规划问题的最优解存在，则必定可以在其可行解集合的顶点（极点）中找到.因此，寻求一个最优解就是在其可行域的各个极点中搜索最优点,单纯形法实质上是一个迭代过程，该迭代即是从可行域的一个极点移到另一个近邻的极点，直到判定某一极点为最优解为止,为使用表格法，首先介绍线性规划问题的标准形式一般的线性规划问题中目标函数可能是求最大（或最小）值，而线性约束条件中可能

4、是线性方程，也可能是线性不等式，约束条件中约束方程（或不等式）的个数也未必就比决策变量的个数少，这些问题对于线性规划的求解，带来极大的不便，为此，引入下述标准形式：求目标函数最大值（用和式表示为）用和式表示为满足其中，都是确定的常数，是决策变量，Z是目标函数，叫做技术系数，R0（叫做资源系数，叫做目标函数系数.特点：1、目标函数为极大化；2、除决策变量的非负约束外，所有的约束条件都是等式，且右端常数均为非负；3、所有决策变量均非负.如果根据实际问题建立起来的线性规划模型不是标准型的，可以用下述方法将它化为标准型.（1）若目标函数是可令将目标函数转化为（2）若约束条件不等式中是“W可在不等式左边

5、加上非负变量，将不等式转化为方程,如W180可转化为其中里的叫做松弛变量,表示没有用完的资源.（3）若约束条件不等式是“年”可在不等式左边减去非负变量，将不等式转化为等式方程，如10可转化为，其中，西里的叫做多余变量，表示不存在的资源.一般地，松弛变量和多余变量的目标函数系数为0.（4）若有一个变量没有非负约束（叫做自由变量），可令，其中0,0.知识巩固例1将5.1节问题1中的线性规划问题化为标准型约束条件求目标函数最大值解分别对前三个约束条件引入松弛变量，得标准型：约束条件求目标函数最大值下面我们通过实例来介绍表格法.首先要列出初始表格.为了得到初始表格，我们分几步来说明：先把标准型中的约束

6、条件方程转换成表格（表5.4）的形式.如:5.1问题1转化的结果为：列成表格为：表5.46210018041001040035001210（表格中的列数为变量个数加1,行数为方程个数加1）从约束方程中，很容易得到，当，时，显然这是一组可行解（我们把它叫作初始解组），将其中三个取非0值的变量列成一列对应地加在上表的最左侧，然后再在所得表的左侧添加一列对应于该初始解组变量的目标函数系数，在表的上侧添加一行对应于各变量的目标函数系数，得如下表：其中在初始解组中的变量必须满足在对应行的约束条件方程中系数为1,而同列其他系数为0,（如果约束条件方程中不满足这要求，可以通过对线性约束条件方程作加减消元法而

7、得到.）再在上表的基础上，增加1行（叫做检验数行j）和1歹|（叫做比值列i）得下面形式:按下面的计算公式在表中依次填上检验数行j和比值列i,其中m检验数计算公式jCj阴，例如j31,即为X1所在列的目标函i1数系数行中的Ci值减去该列系数与第一列初始解组的目标函数系数的对应乘积和，131（060403）31.选取检验数最大的正数所在列（记作k列，表中用表示）然后计算比值i.比值的计算公式i2,aik0,例如1竺0.aik6选取最小的i值，记所在行为i行（表中用表示），如下表（i1）最后填上目标函数Z值一格，其中目标函数Z为第一列Cb与b所在列对应乘积和.得下表：这样我们得到了初始表格（表5.7

8、）显然，前面的初始解组并不能产生最优目标函数值，因此，必须要对初始解组中的变量进行替换，以求更好的解.通常，我们按下述方法进行变量的替换：根据上面所选的第k列第i行（如上表中X3所在行和“所在列，我们将两者的交叉点用（）表示），对初始解组作调整，将变量Xk换入，替代第i行中的初始变量（即表中换入xi,换出X3）,根据表格法的要求，必须同时将换入变量Xk在（）中的系数通过加减消元法化为1,且同列其他系数为0,而初始解组中其他未换出变量所在列的系数不变，通常可用加减消元法来求得.下面我们具体来说明表格的转换.框中A亍除以6得A行；B亍减AX4得8，行；C亍减A/X3得。彳f（表5.8转换到表5.9

9、）.表5.83122000CbXb0(6)21001800410010400035001210表5.93122000Cb3110030表5.103322000Cb311003090001028000(4)01120300声300930如果检验数全为非正数，那么，所得解就是最优解.否则，继续按前方法修改可行解，直至不能继续为止.显然，上表中X2换入,变量X5换出.转下表（表5.11）.表5.113122000Cb311002000012022010300001280因为所有的检验数上至0,故当前可行解X120,X230,X30,X40,X50为最优解，删去松弛变量，即得原线性规划最优解为X20,

10、X230,最优值为Z=1280.通过上面的例子，可以归纳一般的表格法的计算步骤如下：第一步：建立初始表格.第二步：检查：若所有的jW0,则当前可行解即为最优解；否则转入(3).第三步：检查：若存在k0,且aik00,(i=1,2,m),则无最优解；否则转入(4).第四步：选取检验数行中最大的正数所在的列，(记作k列，表中用表示)然后计算比值一比值的计算公式0且,aik0.aik选取最小的i值，记所在行为i行(表中用表示)，确定Xk,将Xk换入，将松弛变量Xh换出，用加减消元法化Xk的系数aik为1,且同列其他系数为0.以Xk取代Xh得新表，转入(2).巩固知识典型例题例2用表格法解5.1节中的

11、例1:某工厂用钢与橡胶生产3种产品A、B、C,有关资料如表5.3所示,已知每天可获得100单位的钢和120单位的橡胶，问每天应按排生产A、B、C三种产品各多少，能使总利润最大？试写出问题的线性约束条件和目标函数.表5.3产品单位产品钢消耗量单位产品橡胶消耗量单位产品利润A2340B3345C12242x13x2x3100则可得约束条件3xi3x22x3120x10,x20,x30目标函数为maxZ40x145x224x3解引入松弛变量乂4?5,得标准型：2xi3x2x3x4100满足3xi3x22x3x5120xj0,j1,2,3,5列初始表格(表5.12).表5.124045240002(3)110100苧03320112040404524000因为为最大正数，转下表（表5.13）.表5.13404524004510500(1)01120201009-150