表格法解线性规划问题

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

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

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

4、先介绍线性规划问题的标准形式.一般的线性规划问题中目标函数可能是求最大 (或最小 )值，而线性约束条件中可能是线性方程， 也可能是线性不等式， 约束条件中约束方程（或不等式）的个数也未必就比决策变量的个数少，这些问题对于线性规划的求解，带来极大的不便，为此，引入下述标准形式：求目标函数最大值max Z c1 x1 c2 x2 c3 x3 . cn xnn(用和式表示为 max Zc j x j )j 1Word 资料.a11 x1a12 x2.a1n xnb1a21 x1a22 x2.a2n xnb2满足.am1 x1am2 x2.amn xnbmx1 0, x20,., xn0n用和式表示为

5、满足aijxibi, (i1,2,3, , m)j1xj0,( j1,2,3, n)其中， 各 aij , bi , c j (i1,2,3, m; j1,2, n) 都是确定的常数，x j ( j1,2, n) 是决策变量 ，Z 是目标函数 ， aij 叫做技术系数， bi 0（ i1,2,m) 叫做资源系数 ， c j 叫做目标函数系数 .特点：1、目标函数为极大化；2、除决策变量的非负约束外， 所有的约束条件都是等式， 且右端常数均为非负；3、所有决策变量均非负如果根据实际问题建立起来的线性规划模型不是标准型的，可以用下述方法将它化为标准型 .（1）若目标函数是 min Z c1 x1

6、c2 x2 c3 x3. cn xn可令 zz' , 将目标函数转化为 max Z '(c1 x1 c2 x2 c3 x3 . cn xn )（2）若约束条件不等式中是 “”,可在不等式左边加上非负变量，将不等式转化为方程 .如 6x1 2x2 180 可转化为 6x1 2x2 x3 180, 其中 x3 0.这里的 x3 叫做松弛变量 . 表示没有用完的资源 .（3）若约束条件不等式是“”，可在不等式左边减去非负变量，将Word 资料.不等式转化为等式方程，如 2x1 2x2 10 可转化为 2x12x2 x4 10 ，其中， x4 0.这里的 x4 叫做多余变量 ，表示不存

7、在的资源 .一般地，松弛变量和多余变量的目标函数系数为0.（4）若有一个变量 xk 没有非负约束（叫做自由变量 ），可令 xkxlxs ，其中 xl 0， xs 0.知识巩固例 1 将 5.1 节问题 1 中的线性规划问题化为标准型6x12x2180约束条件求目标函数最大值4 x110x24003x15x2210x10, x20max Z31x122 x2解分别对前三个约束条件引入松弛变量x3 , x4 , x5 ，得标准型：约束条件求目标函数最大值6x12x2x31804x110x2x44003x15x2x5210x j 0, j1,2,3, 5.max Z31x1 22 x2表格法下面我们

8、通过实例来介绍表格法.首先要列出初始表格为了得到初始表格，我们分几步来说明：先把标准型中的约束条件方程转换成表格（表5.4）的形式如:5.1 问题 1 转化的结果为：Word 资料.6x12x2x30x40x51804x110x20x3x40x5400列成表格为：3x15x20x30x4x5210x j0, j1,2,5.表 5.4x1x2x3x4x5bi6210041001040035001210(表格中的列数为变量个数加1，行数为方程个数加1)从约束方程中，很容易得到，当 x1 0 ，x20 时，x3 180 ，x4 400 ，x5 210 ，显然这是一组可行解（我们把它叫作初始解组 ），

9、将其中三个取非 0 值的变量 x3 , x4 , x5 列成一列对应地加在上表的最左侧，然后再在所得表的左侧添加一列对应于该初始解组变量的目标函数系数，在表的上侧添加一行对应于各变量的目标函数系数，得如下表：Word 资料.其中在初始解组中的变量必须满足在对应行的约束条件方程中系数为 1，而同列其他系数为0，（如果约束条件方程中不满足这要求，可以通过对线性约束条件方程作加减消元法而得到.）再在上表的基础上，增加1 行(叫做检验数行j )和 1 列(叫做比值列 i )得下面形式：按下面的计算公式在表中依次填上检验数行j和比值列 i ,其中m检验数计算公式jc jci aij , 例如 j 31

10、，即为 x1所在列的目标函i1数系数行中的 c1值减去该列系数与第一列初始解组的目标函数系数的对应乘积和，131 (06 0403)31.选取检验数最大的正数所在列(记作 k 列，表中用 表示 )然后计算比值 i 比值的计算公式bi, aik 0,180.i，例如 1aik6选取最小的 i 值，记所在行为i 行(表中用 表示 )，如下表 (i 1 ）Word 资料.最后填上目标函数Z 值一格，其中目标函数Z 为第一列 C B 与 b 所在列对应乘积和得下表：表 5.7可行解比值c j3122000CBX Bx1x2x3x4x5bii0x3(6)2100300x44100104001000x53

11、500121070j31220000检验数目标函数 Z这样我们得到了初始表格（表5.7）显然，前面的初始解组并不能产生最优目标函数值，因此，必须要对初始解组中的变量进行替换，以求更好的解.通常，我们按下述方法进行变量的替换：根据上面所选的第k 列第 i 行(如上表中 x3 所在行和 x1 所在列，我们将两者的交叉点用 ( )表示 )，对初始解组作调整，将变量xk 换入，替代第 i 行中的初始变量 (即表中换入 x1 ，换出 x3 )，根据表格法的要求，必须同时将换入变量xk 在( )中的系数通过加减消元法化为1，且同列其他系数为 0，而初始解组中其他未换出变量所在列的系数不变，通常可用加减消元

12、法来求得Word 资料.下面我们具体来说明表格的转换框中 <A> 行除以 6 得<A / > 行；<B> 行减 <A / > ×4 得<B / > 行；<C>行减 <A / > ×3 得<C / > 行(表 5.8 转换到表 5.9)表 5.8c j3122000CBXBx1x2x3x4x5bii0x3(6)2100<A>0x4410010400<B>0x535001210<C>表 5.9c j3122000BX Bx1x2x3x4x5biCi

13、31x11110030<A />360x40262330x50(4)1210280<B/>01120<C />再依次填上检验数行j 和比值列i ，得下表 (表 5.10)Word 资料.表 5.10c j3322000CBX Bx1x2x3x4x5bii31x1111003090360x402621028042033130x50(4）101120302j035310093036如果检验数全为非正数，那么，所得解就是最优解否则，继续按前方法修改可行解， 直至不能继续为止 显然，上表中 x2 换入，变量 x5 换出转下表 (表 5.11)表 5.11c j312

14、0002CBX Bx1x2x3x4x5bii31x1105012024120x40051132012622x2011013084j008903512802412因为所有的检验数j 0，故当前可行解 x120，x230，x30 ，x40 ， x50 为最优解，删去松弛变量，即得原线性规划最优解为x120， x230，Word 资料.最优值为Z=1280 通过上面的例子，可以归纳一般的表格法的计算步骤如下：第一步：建立初始表格第二步：检查：若所有的j 0，则当前可行解即为最优解；否则转入(3)第三步：检查：若存在k>0, 且aik0，(i=1,2,m)，则无最优解；否则转入 (4) 第四步：

15、选取检验数行中最大的正数所在的列，(记作 k 列，表中用表示 )然后计算比值 i，比值的计算公式 bi,aik 0 iaik选取最小的 i 值，记所在行为 i 行(表中用 表示 )，确定 x ，将kxk 换入，将松弛变量xh 换出，用加减消元法化xk 的系数 aik 为 1，且同列其他系数为 0以 xk 取代 xh 得新表，转入 (2).巩固知识典型例题例 2 用表格法解 5.1 节中的例 1：某工厂用钢与橡胶生产 3 种产品 A、B、C,有关资料如表 5.3 所示 .已知每天可获得 100 单位的钢和 120 单位的橡胶，问每天应按排生产 A、B、C 三种产品各多少，能使总利润最大？试写出问

16、题的线性约束条件和目标函数.表 5.3产品单位产品钢消耗量单位产品橡胶消耗量单位产品利润A2340B3345Word 资料C122x13x2x3100则可得约束条件3x13x22x3120x10, x20, x3 0目标函数为 max Z40x1 45x224 x3解引入松弛变量 x4 , x5 ，得标准型：max Z40 x1 45x2 24x32x13x2x3x4100满足3x13x22 x3x5120x j0, j1,2,3,5列初始表格 (表 5.12)表 5.12c j40452400C BX Bx1x2x3x4x50x42(3)1100x533201j40452400因为2为最大正数，转下表 (表 5.13)表 5.13c j40452400C BX Bx1x2x3x4x545x2211103330x5(1)0111.24bii100 1