表格法解线性规划问题剖析

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

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

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

4、首先介绍线性规划问题的标准形式 .一般的线性规划问题中目标函数可能是求最大 （或最小）值，而线 性约束条件中可能是线性方程，也可能是线性不等式，约束条件中约 束方程（或不等式）的个数也未必就比决策变量的个数少，这些问题 对于线性规划的求解，带来极大的不便，为此，弓I入下述标准形式：求目标函数最大值 max Z = C|Xj +c2X2 +C3X3 +. + CnXnn（用和式表示为 maxZ = 7 CjXj ）a11X1 - a12X2 . a1nxn = b1 a2X + a?%?* . + a?n x* = b?满足16am1X1am2X2 amnX bmXi 一 0,X2 - 0,Xn

5、 - 0n用和式表示为满足' ajXi =bi,(i =1,2,3,m)j丄Xj 一 0,( j =1,2,3,n)其中，各aj,bi，Cj(i = 1,2,3厂，m; j2，n)都是确定的常数，Xj (j =1,2，n)是决策变量,Z是目标函数,aj叫做技术系数,b0(i =1,2,-m)叫做资源系数，Cj叫做目标函数系数特点：1、目标函数为极大化；2、除决策变量的非负约束外，所有的约束条件都是等式，且右端 常数均为非负；3、所有决策变量均非负.如果根据实际问题建立起来的线性规划模型不是标准型的，可以 用下述方法将它化为标准型.(1)若目标函数是 min Z “必 + c2x2 +

6、c3x3 + + cnxn可令 Z - -z ,将目标函数转化为 maxZ' - -(g/ C2X2 C3X3 . c*x*)(2) 若约束条件不等式中是“W”,可在不等式左边加上非负变量，将不等式转化为方程.如6X1 2X2 < 180可转化为6X1 2X2 X3二180,其 中X3 > 0.这里的X3叫做松弛变量.表示没有用完的资源.(3) 若约束条件不等式是“”，可在不等式左边减去非负变量，将不等式转化为等式方程，如2xi 2x2 > 10可转化为2xi 2x2 - X4 =10 , 其中，X4 >0.这里的X4叫做多余变量，表示不存在的资源.一般地，松弛

7、变量和多余变量的目标函数系数为0.（4）若有一个变量Xk没有非负约束（叫做自由变量），可令Xk=X|Xs , 其中 X| > 0, x > 0.知识巩固 例1将5.1节问题1中的线性规划问题化为标准型6禺 +2x2 兰 180约束条件4X1 +10X2 兰 4 0 03x1 5x2 _ 2 1 0捲 _ 0, X2 _ 0求目标函数最大值maxZ =31花 22x2解 分别对前三个约束条件引入松弛变量 X3.X4.X5，得标准型:6捲十 2x2 + x3 = 180约束条件4x1 +10x2 + x4 = 4 0 03x1 5X2 X52 1 0Xj -0, j =1,2,3,5.

8、求目标函数最大值maxZ = 31x22x25.3.2表格法F面我们通过实例来介绍表格法首先要列出初始表格.为了得到初始表格，我们分几步来说明：先把标准型中的约束条件方程转换成表格（表5.4 ）的形式.如:5.1问题1转化的结果为：6x<! +2x2 +X3 +0x4 十OX5 =180列成表格为:4x_j +10x2 +OX3 +x4 +OX5 =4003x! +5x2 +0x3 +0x4 +x5 =210 Xj 2 0, j =1,2,5.表5.4X1X2X3X4Xbi6210018041001040035001210（表格中的列数为变量个数加1,行数为方程个数加1）从约束方程中，很

9、谷易得到，当X"! = 0 , x2 = 0时，x3 =180 , x4 = 400,X5 =210，显然这是一组可行解（我们把它叫作 初始解组），将其中三个取非0值的变量X3,X4,X5列成一列对应地加在上表的最左侧，然后 再在所得表的左侧添加一列对应于该初始解组变量的目标函数系数,在表的上侧添加一行对应于各变量的目标函数系数，得如下表：目标函数系数鼻 H 表5乐3“22扶Opth0期匸X严x2+>it旳护花卩10卩6p2pIp0心180p 114100心23400卜S+30应0农1卩213心d自解组"各约束方 程的系数d其中在初始解组中的变量必须满足在对应行的约束

10、条件方程中系 数为1,而同列其他系数为0，（如果约束条件方程中不满足这要求，可以通过对线性约束条件方程作加减消元法而得到 .）再在上表的基础上，增加1行（叫做检验数行j）和1列（叫做比值列刁）得下面形式:31心22戸OpOpOqX屮Xi P->方严6中2心0心1800卩4心10Op0心400*羊0屮x53心50心0心24p比值列屮表5. 6检验数行存按下面的计算公式在表中依次填上检验数行 和比值列九其中m检验数计算公式匚j =Cjcaij,例如-31，即为Xi所在列的目标函=1数系数行中的C1值减去该列系数与第一列初始解组的目标函数系数的对应乘积和，；.=31 -（0 6 0 4 0 3

11、）=31.选取检验数最大的正数所在列（记作k列，表中用表示）然后 计算比值4 .比值的计算公式耳二直© 0,，例如十180.aik6选取最小的哥值，记所在行为i行（表中用表示），如下表（"1 ）最后填上目标函数Z值一格，其中目标函数Z为第一列Cb与b所 在列对应乘积和.得下表：Cj3122000rCBXbXiX2X3X4X5bi日i0X3(6)2100180300X44100104001000X53500121070巧3122000Vb表5.7比值可行解目标函数Z检验数这样我们得到了初始表格（表5.7 ）显然，前面的初始解组并不能产生最优目标函数值，因此，必须 要对初始解组

12、中的变量进行替换，以求更好的解 .通常，我们按下述 方法进行变量的替换：根据上面所选的第k列第i行（如上表中X3所在行和xi所在列，我 们将两者的交叉点用（）表示），对初始解组作调整，将变量xk换入， 替代第i行中的初始变量（即表中换入xi,换出X3）,根据表格法的要 求，必须同时将换入变量Xk在（）中的系数通过加减消元法化为 1, 且同列其他系数为0,而初始解组中其他未换出变量所在列的系数不 变，通常可用加减消元法来求得.F面我们具体来说明表格的转换.框中Af除以6得vA、行；B减A/X 4得vB、行；C亍减A/x 3得C行（表5.8转换到表5.9）.表5.8Cj3122000CbXBXiX

13、2X3X4X5bi9i0X3(6)2100180<A>0X4410010400<B>0X535001210<C>表5.9cj3122000CbXbX1X2X3X4X5b31X1113160030<A/>0&0263_2310280<B/>0X50(4)1201120<C>再依次填上检验数行和比值列片，得下表（表5.10）.表 5.10Cj 3322000CBXBXiX2X3X4X5bq31Xi113160030900X402632310280420130X50(4 )120112030bj0乎331600930如果

14、检验数全为非正数，那么，所得解就是最优解.否则，继续按前方法修改可行解，直至不能继续为止.显然，上表中X2换入，变量X5换出.转下表（表5.11）.表 5.11Cj 3122000CBXBX1X2X3X4X5bi31X110_5_012024120X40051132012622X201丄013084008903512802412因为所有的检验数三0,故当前可行解x 20 , X2 = 30 , X3 = 0 ,X4=0 , X5=0为最优解，删去松弛变量，即得原线性规划最优解为Xi = 20, X2 = 30 ,最优值为Z=1280.通过上面的例子，可以归纳一般的表格法的计算步骤如下：第一步：

15、建立初始表格.第二步：检查：若所有的Cj < 0,则当前可行解即为最优解；否则转 入.第三步：检查：若存在九>0,且aik< 0, (i=1,2,m)，则无最优解；否 则转入(4).第四步：选取检验数行中最大的正数所在的列，(记作k列，表中 用表示)然后计算比值耳，比值的计算公式Q二邑,aik 0 .aik选取最小的可值，记所在行为i行(表中用表示)，确定Xk, 将Xk换入，将松弛变量Xh换出，用加减消元法化Xk的系数aik为1, 且同列其他系数为0.以Xk取代Xh得新表，转入(2).巩固知识典型例题例2用表格法解5.1节中的例1:某工厂用钢与橡胶生产3种产品A、B、C,有关

16、资料如表5.3所示.已知每天可获得100单位的钢和120单 位的橡胶，问每天应按排生产 A、B、C三种产品各多少，能使总利 润最大？试写出问题的线性约束条件和目标函数.表5.3产品单位产品钢消耗量单位产品橡胶消耗量单位产品利润A2340B3345C1224I 2x1 3x2 x3 _100则可得约束条件3xi 3x2 2x3叮20x_0, x2 亠 0,x3 亠 0目标函数为 maxZ = 40x145x2 - 24x3解 引入松弛变量x4,x5，得标准型： maxZ =40为 45x224x3'2捲 +3x2 +x3+x4 =100 满足* 3捲 +3x2+2x3 + x5 = 120、Xj 3 0, j =1,2,3,5列初始表格（表5.12）.表 5.12Cj i40452400CBXb花X2X3X4X5bi30X42110100100 30X53320112040aj404524000因为勺为最大正数，转下表（表5.13）.表 5.13Cj 40452400CbXbX1X2X3X4X5bi日i45211