《表格法解线性规划问题》由会员分享，可在线阅读，更多相关《表格法解线性规划问题（14页珍藏版）》请在金锄头文库上搜索。
1、表格法解线性规划问题【教学目标】知识目标:理解用表格法解线性规划问题的方法与步骤、能力目标:通过例子详细地介绍了表格法解线性规划问题的过程,并引入了线性规划标准型的概念,归纳总结了表格法解线性规划问题的步骤、理解用表格法解线性规划问题的方法与步骤、理解用表格法解线性规划问题的方法与步骤、【教学设计】1、表格法也称单纯形法,就是解线性规划问题的常用方法,使用该方法时,首先要将一般的线性规划问题化为标准型、在教材中给出了化标准型的方法、讲解时一定要注意b0以及变量的非负性、2、表格法解线性规划问题的过程,教材中归纳为五个步骤,这实际上就是一个算法,可以利用前面介绍过的算法知识来学习、3、初始表格中
2、初始解组的确定就是关键,一般可取松弛变量,但当标准型中没有这样的变量满足初始解组的要求时,通常要通过添加人工变量来解决,本教材没有就这方面的问题进行深入讨论（一般的运筹学教材中都可找到该内容）、4、表格在转换时（通常称为转轴）,教材中提到用加减消元法来转轴、教师可就这部分内容作适当的讲解、5、由于通常的表格转换要进行多次,而表头部分就是不变的,因此可以将多张表格合并起来,具体样式可参见5、5节表5-16、【教学过程】5.3.1线性规划问题的标准形式求线性规划问题的图解法虽然直观简便,但对多于两个变量的情况就不能适用了,对于多于两个决策变量的线性规划问题,可以用什么方法呢？下面介绍一种用表格的方
3、法来求解线性规划问题的解、表格法就是根据单纯形法而专门设计的一种计算表格、单纯形法（SimpleMethod）就是求解线性规划问题的主要方法,该法由丹赛（Dantzig）于1947年提出,后经过多次改进而成,就是求解线性规划问题的实用算法、由上节的叙述可知,如果线性规划问题的最优解存在,则必定可以在其可行解集合的顶点（极点）中找到.因此,寻求一个最优解就就是在其可行域的各个极点中搜索最优点、单纯形法实质上就是一个迭代过程,该迭代即就是从可行域的一个极点移到另一个近邻的极点,直到判定某一极点为最优解为止、为使用表格法,首先介绍线性规划问题的标准形式、一般的线性规划问题中目标函数可能就是求最大（或
4、最小）值,而线性约束条件中可能就是线性方程,也可能就是线性不等式,约束条件中约束方程（或不等式）的个数也未必就比决策变量的个数少,这些问题对于线性规划的求解,带来极大的不便,为此,引入下述标准形式:求目标函数最大值maxZxnn（ 用与式表示为 maxZcjxj )a11 x1a12 x2a1nxnb1a21x1a22x2.a2nxn满足b2am1x1am2x2.amnxnbmx10,x20,.,xn0n用与式表示为满足j1aijxibi,(i1,2,3,m)xj0,(j1,2,3,n)其中，各a。，bi,Cj(i1,2,3,m;j1,2,n)都就是确定的常数Xj(j1,2,n)就是决策变量，
5、Z就是目标函数，aj叫做技术系数，biA0(i1,2,m)叫做资源系数，Cj叫做目标函数系数、特点:1、目标函数为极大化;2、除决策变量的非负约束外,所有的约束条件都就是等式,且右端常数均为非负;3、所有决策变量均非负.如果根据实际问题建立起来的线性规划模型不就是标准型的,可以用下述方法将它化为标准型、(1)若目标函数就是minZC1x1C2x2C3x3.Cnxn可令zz,将目标函数转化为maxZ(C1x1C2x2C3x3.Cnxn)(2)若约束条件不等式中就是，可在不等式左边加上非负变量，将不等式转化为方程、如6x12x2W180可转化为6x12x2x3180，其中x3A0、这里的x3叫做松
6、弛变量、表示没有用完的资源、(3)若约束条件不等式就是，可在不等式左边减去非负变量，将不等式转化为等式方程，如2xi2x2A10可转化为2xi2x2X410,其中，X4A0、这里的x4叫做多余变量，表示不存在的资源、一般地,松弛变量与多余变量的目标函数系数为0、（4）若有一个变量xk没有非负约束（叫做自由变量）,可令xkxlxs,其中xi0,xs0知识巩固例1将5、1节问题1中的线性规划问题化为标准型6x12x2180约束条件4x110x24003x15x2210x10,x20求目标函数最大值maxZ31x122x2解分别对前三个约束条件引入松弛变量x3,x4,x5，得标准型：6x12x2x3
7、180约束条件求目标函数最大值4x110x2x44003x15x2x5210xj0,j1,2,3,5.maxZ31x122x25.3.2表格法F面我们通过实例来介绍表格法、首先要列出初始表格.为了得到初始表格,我们分几步来说明先把标准型中的约束条件方程转换成表格（表5、4）的形式.如:5、1问题1转化的结果为:表5、4x1又2x3x4x5bi62100180410010400350012106x1 2x2 x3 0x44x1 10x2 0x3 x43x1 5x2 0x3 0x4xj0, j 1,2, ,5.0x50x5*5180Z列成表格为：（表格中的列数为变量个数加1,行数为方程个数加1）从
8、约束方程中，很容易得到，当x10,x20时，x3180,x4400,x5210，显然这就是一组可行解（我们把它叫作初始解组），将其中三个取非0值的变量x3,x4,x5列成一列对应地加在上表的最左侧，然后再在所得表的左侧添加一列对应于该初始解组变量的目标函数系数，在表的上侧添加一行对应于各变量的目标函数系数，得如下表：各约束方 程的系数一目标函数系敏，表5门C3k22/0平0/JC出卡XP荒/覆第x4,b/10守6口200/180/10-h0/400/kOp0ch210/初始解组其中在初始解组中的变量必须满足在对应行的约束条件方程中系数为1,而同列其她系数为0,（如果约束条件方程中不满足这要求，
9、可以通过对线性约束条件方程作加减消元法而得到、）按下面的计算公式在表中依次填上检验数行j与比值列i,其中再在上表的基础上，增加1行（叫做检验数行j）与1歹U（叫做比值列i）得下面形式:q一3h22j00/0/应户题。国r4户0/2卓hOh0+1800口可4U1。口0甲L0平400&p守3/5/0炉0/1-210门p(7,JJpQ心p表5.6比值列，检嗡放行m检验数计算公式jCjqaij,例如j31,即为X1所在列的目标函i1数系数行中的C1值减去该列系数与第一列初始解组的目标函数系数的对应乘积与，131（060403）31、选取检验数最大的正数所在列（记作k歹U,表中用表示）然后计算比值i.比
10、值的计算公式i旦,aik0,例如1竺0、aik6选取最小的i值，记所在行为i行（表中用表示），如下表（i1）最后填上目标函数Z值一格，其中目标函数Z为第一列Cb与b所在列对应乘积与.得下表：5f3122000lrCbXBXiX2X3X4X5bi0X3(6)210018030X400X531220000N表5、7可行解比值检验数目标函数Z这样我们得到了初始表格（表5、7）显然,前面的初始解组并不能产生最优目标函数值，因此，必须要对初始解组中的变量进行替换，以求更好的解、通常，我们按下述方法进行变量的替换:根据上面所选的第k列第i行（如上表中X3所在行与xi所在列，我们将两者的交叉点用（）表示），
11、对初始解组作调整，将变量Xk换入，替代第i行中的初始变量（即表中换入”,换出X3）,根据表格法的要求，必须同时将换入变量Xk在（）中的系数通过加减消元法化为1,且同列其她系数为0,而初始解组中其她未换出变量所在列的系数不变，通常可用加减消元法来求得.下面我们具体来说明表格的转换.框中人亍除以6得A/行;B行减A/X4得B/行;C行减A/X3得C/彳f（表5、8转换到表5、9）.表5、8cj-3122000CbXBXiX2X3X4X5bii0X3(6)21001800X44100104000X535001210表5、9cj3122000CbXBX1X2X3X4X5bii31X1113160030
12、0X4026323102800X50(4)1201120再依次填上检验数行j与比值列i,得下表（表5、10）.表5、10cj-3322000CbXbX1X2X3X4X5bii31X1113160030900X402632310280420130X50(4)120112030j035331600930如果检验数全为非正数，那么，所得解就就是最优解.否则，继续按前方法修改可行解，直至不能继续为止.显然，上表中X2换入，变量X5换出.转下表（表5、11）.表5、11cj-k3122000CbXbXiX2X3X4X5bii31Xi105240112200X40051211362022X2011801430j008924035121280因为所有的检验数j三0,故当前可行解X20,X230,X30,X40,X5。为最优解，删去松弛变量，即得原线性规划最优解为x120,x230,最优值为Z=1280.通过上面的例子，可以归纳一般的表格法的计算步骤如下：第一步:建立初始表格.第二步:检查:若所有
