表格法解线性规划问题

1、文档来源为 :从网络收集整理 .word 版本可编辑 .欢迎下载支持表格法解线性规划问题教学目标】知识目标： 理解用表格法解线性规划问题的方法和步骤 .能力目标： 通过例子详细地介绍了表格法解线性规划问题的过程， 并引入了线性规划标准型的概念，归纳总结了表格法 解线性规划问题的步骤 .教学重点】 理解用表格法解线性规划问题的方法和步骤 .教学难点】 理解用表格法解线性规划问题的方法和步骤 .教学设计】1、表格法也称 单纯形法 ，是解线性规划问题的常用方法，使用该 方法时，首先要将一般的线性规划问题化为标准型 .在教材中给出了 化标准型的方法讲解时一定要注意b0以及变量的非负性.2、表格法解线性

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

3、于两个变量的情 况就不能适用了， 对于多于两个决策变量的线性规划问题， 可以用什 么方法呢？下面介绍一种用表格的方法来求解线性规划问题的解 . 表格法是根据 单纯形法 而专门设计的一种计算表格 .单纯形法(Simple Method)是求解线性规划问题的主要方法，该 法由丹赛( Dantzig )于 1947 年提出，后经过多次改进而成，是求解 线性规划问题的实用算法 . 由上节的叙述可知，如果线性规划问题的 最优解存在，则必定可以在其可行解集合的顶点(极点)中找到因 此，寻求一个最优解就是在其可行域的各个极点中搜索最优点 . 单纯 形法实质上是一个迭代过程， 该迭代即是从可行域的一个极点移到

4、另 一个近邻的极点，直到判定某一极点为最优解为止 .为使用表格法，首先介绍线性规划问题的标准形式 .一般的线性规划问题中目标函数可能是求最大 (或最小 )值，而线 性约束条件中可能是线性方程， 也可能是线性不等式， 约束条件中约 束方程(或不等式)的个数也未必就比决策变量的个数少，这些问题 对于线性规划的求解，带来极大的不便，为此，引入下述标准形式：求目标函数最大值 max Z c1x1 c2 x2 c3 x3. cnxnn( 用和式表示为 maxZ c j xj ) j1用和式表示为满足aij xibi ,(i1,2,3, ,m)j1xj 0,( j 1,2,3, ,n)其中，各abi,Cj

5、(i 1,2,3, ,m; j 1,2,n)都是确定的常数, Xj(j 1,2, , n)是决策变量，Z是目标函数，aj叫做技术系数，bi 0 (i 1,2, m)叫做资源系数，Cj叫做目标函数系数.特点：1、目标函数为极大化；2、除决策变量的非负约束外， 所有的约束条件都是等式， 且右端 常数均为非负；3、所有决策变量均非负 如果根据实际问题建立起来的线性规划模型不是标准型的，可以用下述方法将它化为标准型.( 1)若目标函数是 min Z c1X1 c2 X2 c3X3 . cn Xn可令 z z, 将目标函数转化为 maXZ (c1X1 c2X2 c3X3 . cnXn )(2) 若约束条

6、件不等式中是“W”,可在不等式左边加上非负变量， 将不等式转化为方程如6治2x2 0.这里的x3叫做松弛变量.表示没有用完的资源.(3) 若约束条件不等式是“”，可在不等式左边减去非负变量，将 不等式转化为等式方程，如2X1 2X2 10可转化为2X1 2X2 X4 10 , 其中，X4 0.这里的X4叫做多余变量，表示不存在的资源.一般地，松弛变量和多余变量的目标函数系数为 0.(4) 若有一个变量Xk没有非负约束(叫做自由变量)，可令Xk Xi Xs , 其中 xl 0, xs 0.知识巩固例1 将 5.1 节问题 1 中的线性规划问题化为标准型3文档来源为 :从网络收集整理 .word

7、版本可编辑 .文档来源为：从网络收集整理.word版本可编辑.欢迎下载支持6x12x2180约束条件4%10x24003x15x2210為OK0求目标函数最大值max Z31x122x2解 分别对前三个约束条件引入松弛变量X3,X4,X5，得标准型:6x12x2X3180约束条件4x110x2X44003x15x2X5210Xj0, j1,2,3,5.求目标函数最大值maxZ 31x122x2下面我们通过实例来介绍表格法.首先要列出初始表格.为了得到初始表格，我们分几步来说明：先把标准型中的约束条件方程转换成表格（表5.4 ）的形式.如:5.1问题1转化的结果为：6x12x2X30x40x51

8、804x110X20x3X40x5列成表格为:3x15x20X30X4X5210XjQ j1,2,5.表5.46210018041001040035001210（表格中的列数为变量个数加1,行数为方程个数加1）从约束方程中，很容易得到，当x1 0 , x2 0时，x3 180 , x4 400 ,X5 210 ,显然这是一组可行解（我们把它叫作 初始解组），将其中三 个取非0值的变量X3,X4,X5列成一列对应地加在上表的最左侧，然后 再在所得表的左侧添加一列对应于该初始解组变量的目标函数系数， 在表的上侧添加一行对应于各变量的目标函数系数，得如下表：其中在初始解组中的变量必须满足在对应行的约

9、束条件方程中系数为1,而同列其他系数为0，（如果约束条件方程中不满足这要求，可以通过对线性约束条件方程作加减消元法而得到 .）再在上表的基础上，增加1行（叫做检验数行j）和1列（叫做比值 列i）得下面形式：按下面的计算公式在表中依次填上检验数行j和比值列i,其中m检验数计算公式j CjWij,例如j 31，即为Xi所在列的目标函i 1数系数行中的G值减去该列系数与第一列初始解组的目标函数系数的对应乘积和，1 31 （0 6 0 4 0 3） 31.选取检验数最大的正数所在列（记作k列，表中用表示）然后 计算比值i.比值的计算公式i也,aik 0,，例如1型.aik6选取最小的i值，记所在行为i

10、行（表中用表示），如下表（i 1 ）最后填上目标函数Z值一格，其中目标函数Z为第一列Cb与b所 在列对应乘积和.得下表：表 5.7-可行解比值厂3122000Cb0(6)2100180300410010400100035001210703122000检验数目标函数Z这样我们得到了初始表格（表5.7）显然，前面的初始解组并不能产生最优目标函数值，因此，必须 要对初始解组中的变量进行替换，以求更好的解 .通常，我们按下述 方法进行变量的替换：根据上面所选的第k列第i行（如上表中X3所在行和xi所在列，我 们将两者的交叉点用（）表示），对初始解组作调整，将变量xk换入， 替代第i行中的初始变量（即表

11、中换入Xi，换出X3），根据表格法的要 求，必须同时将换入变量Xk在（）中的系数通过加减消元法化为 1, 且同列其他系数为0,而初始解组中其他未换出变量所在列的系数不 变，通常可用加减消元法来求得.下面我们具体来说明表格的转换.框中Af除以6得A/行；B减vAx 4得vB，行；C亍减 A/X 3得C行（表5.8转换到表5.9）.表5.83122000CbXB0(6)21001800410010400035001210表5.93122000Cb311003000102800001120再依次填上检验数行j和比值列i，得下表（表5.10）.表 5.103322000Cb31100309000102

12、8000(4 )01120300乎300930如果检验数全为非正数，那么，所得解就是最优解.否则，继续按前方法修改可行解，直至不能继续为止.显然，上表中X2换入，变量X5换出.转下表（表5.11）.表 5.113122000Cb311002000012022010300001280因为所有的检验数j三0,故当前可行解Xi 20 ,X2 30 ,X3 0 ,X4 0 , X5 0为最优解，删去松弛变量，即得原线性规划最优解为x120, x230,最优值为 Z=1280.通过上面的例子，可以归纳一般的表格法的计算步骤如下：第一步：建立初始表格.第二步：检查：若所有的j0,且aik 0, (i=1,

13、2,m)，则无最优解；否 则转入(4).第四步：选取检验数行中最大的正数所在的列，(记作k列，表中 用表示)然后计算比值i，比值的计算公式q ,aik 0 .aik选取最小的i值，记所在行为i行(表中用表示)，确定Xk, 将Xk换入，将松弛变量Xh换出，用加减消元法化Xk的系数aik为1, 且同列其他系数为0.以Xk取代Xh得新表，转入(2).巩固知识典型例题例2用表格法解5.1节中的例1:某工厂用钢与橡胶生产3种产品A、 B、C,有关资料如表5.3所示.已知每天可获得100单位的钢和120单 位的橡胶，问每天应按排生产 A、B、C三种产品各多少，能使总利 润最大？试写出问题的线性约束条件和目标函数.表5.3产品单位产品钢消耗量单位产品橡胶消耗量单位产品利润A2340B3345C12242x1 3x2 x3 100则可得约束条件3x1 3x2 2x3 120x10, x20, x30目标函数为 max Z 40x145x224x3解 引入松弛变量x4, x5，得标准型:2x1 3x2 X3 X4 100满足3x1 3x2 2x3 x5 120Xj 0, j 1,2,3,5列初始表格(表5.12).表 5.124045240002(3)1101000003320112040404524000因为02为最大正数，转下表（表5.13）.表 5.1340452