53解线性规划问的表格法

第5章线性规划（教案）【课题】5．3解线性规划问题的表格法【教学目标】知识目标：理解用表格法解线性规划问题的方法和步骤.能力目标：通过例子详细地介绍了表格法解线性规划问题的过程，并引入了线性规划标准型的概念，归纳总结了表格法解线性规划问题的步骤.【教学重点】理解用表格法解线性规划问题的方法和步骤.【教学难点】理解用表格法解线性规划问题的方法和步骤.【教学设计】1、表格法也称单纯形法，是解线性规划问题的常用方法，使用该方法时，首先要将一般的线性规划问题化为标准型.在教材中给出了化标准型的方法.讲解时一定要注意b≥0以及变量的非负性.2、表格法解线性规划问题的过程，教材中归纳为五个步骤，这实际上是一个算法，可以利用前面介绍过的算法知识来学习.3、初始表格中初始解组的确定是关键，一般可取松弛变量即可，但当标准型中没有这样的变量满足初始解组的要求时，通常要通过添加人工变量来解决，本教材没有就这方面的问题进行深入讨论（一般的运筹学教材中都可找到该内容）.4、表格在转换时（通常称为转轴），教材中提到用加减消元法来转轴.教师可就这部分内容作适当的讲解.5、由于通常的表格转换要进行多次，而表头部分是不变的，因此可以将多张表格合并起来，具体样式可参见5.5节表5-16.【教学备品】教学课件．【课时安排】2课时．(90分钟)【教学过程】教学过程教师行为学生行为教学意图时间*新阶段学习导入语求线性规划问题的图解法虽然直观简便，但对多于两个变量的情况就不能适用了，对于多于两个决策变量的线性规划问题，可以用什么方法呢？介绍说明讲解倾听了解学生了解新阶段的学习的重点3*揭示课题第5章线性规划（教案）教学过程教师行为学生行为教学意图时间如果线性规划问题的最优解存在，则必定可以在其中可行解集合的顶点（极点）中找到.因此，寻求一个最优解就是在其可行区域的各个极点中搜索最优点.单纯形法是指上是一个迭代过程，该迭代即是从可行域的一个极点移到另一个近邻的极点，直到判定某一极点为最优为止.这就是我们要学习的5．3解线性规划问题的表格法介绍说明了解引入教学内容5*创设情景兴趣导入问题15.3.1线性规划问题的标准形式下面介绍一种用表格的方法来求线性规划问题的解.表格法是根据单纯形法而专门设计的一种计算表格.单纯形法（SimpleMethod）是求解线性规划问题的主要主要方法，该法由丹赛（Dantzig）于1947年提出，后经过多次改进而成，是求线性规划问题的实用算法.由上节的叙述可知，如果线性规划问题的最优解存在，则必定可以在其中可行解集合的顶点（极点）中找到。因此，寻求一个最优解就是在其可行区域的各个极点中搜索最优点.单纯形法是指上是一个迭代过程，该迭代即是从可行域的一个极点移到另一个近邻的极点，直到判定某一极点为最优为止.为使用表格法，首先介绍线性规划问题的标准形式.一般的线性规划问题中目标函数可能是求最大，也有可能求最小，而线性约束条件中可能是线性方程，也可能是线性不等式，约束条件中约束方程或者不等式的个数也未必就比决策变量的个数少，这些问题对于线性规划的求解，带来极大的不便，为此，引入下属标准形式：nnxcxcxcxcZ...max332211(用和式表示为jjnjxcZ1max)满足),,3,2,1(,0),,3,2,1(,1njxmibxaiiiijnj其中，各jiijcba,,（njmi,,2,1;,,3,2,1）都是确定的常数，),,2,1(njxj是决策量，Z是目标函数，ija叫做播放课件引导分析指导建构观看课件思考从实际问题出发，学生自然的学习知识点启发学生分析15第5章线性规划（教案）教学过程教师行为学生行为教学意图时间技术系数，ib≥0（),2,1mi叫做资源系数，jc叫做目标函数系数.*动脑思考探索新知如果根据实际问题建立起来的线性规划模型不是标准型的，可以用下述方法将它化为标准型.（1）若目标函数是nnxcxcxcxcZ...min332211可令,'zz将目标函数转化为)...(max332211'nnxcxcxcxcZ（2）若约束条件不等式中是“≤”,可在不等式左边加上非负变量，将不等式转化为方程.如问题1中（2）式2126xx≤180可转化为3321,18026xxxx≥0.这里的3x叫做松弛变量.表示没有用完的资源.（3）若约束条件不等式是“≥”，可在不等式左边减去非负变量，将不等式转化为等式方程，如问题2中的2122xx≥10（已用1x代替x，2x代替y）可转化为4421,1022xxxx≥0.这里的4x叫做多余变量，表示不存在的资源.一般地，松弛变量和多余变量的目标函数的系数为0.（4）若有一个变量kx没有非负约束（叫做自由变量），可令slkxxx，其中lx≥0，sx≥0.*巩固知识典型例题例1将5.1节问题1中的线性规划问题化为标准型引导学生具体问题具体分析通过具体例题示范学会根据具体问题如何转化标准型真实的体会解题过具体问题具体分析25第5章线性规划（教案）教学过程教师行为学生行为教学意图时间约束条件0,0210534001041802621212121xxxxxxxx目标函数212231maxxxZ解分别引入松弛变量543,,xxx，得标准型：约束条件.5,3,2,1,02105340010418026521421321jxxxxxxxxxxj目标函数212231maxxxZ*动脑思考探索新知5.3.2表格法下面我们通过实例来介绍表格法.首先要列出表格，为了得到初始表格，我们分几个步骤来说明.首先把标准型中的约束条件方程转换成表格的形式(表格中的列数为变量个数加1，行数为方程个数加1)如:5.1问题1转化的结果为：.5,,2,1,02100053400001041800026543215432154321jxxxxxxxxxxxxxxxxj列成表格为：表5.41x2x3x4x5xib6210018041001040035001210教学生从标准型到表格的转化程学习表格法例题示范教学生如何把标准型转化成表格35第5章线性规划（教案）教学过程教师行为学生行为教学意图时间从约束方程中，很容易得到，当01x，02x时，1803x，4004x，2105x，显然这是一组可行解.我们把它他叫作出初始解组.将其中三个取非0值变量543,,xxx列成一列对应地加在上表的最左侧，然后再在所得表的左侧添加一列对应于该初始解组变量的目标函数系数，在表上侧添加一行对应于各变量的目标函数系数，得如下表：表5.5jc3122000BcBX1x2x3x4x5xib03x6210018004x41001040005x35001210其中在初始解组中的变量必须满足在对应行的约束条件方程中系数为1，而同列其他系数为0，（如果约束条件方程中不满足这要求，可以通过对线性约束条件方程加减消元法而得到.）再在上表的基础上，增加1行(叫做检验行j)和1列(叫做比值列i)得下面形式：指导学生求初始解表格运算学习求初始解得办法学习表格运算如何找初始解表格45目标函数系数各约束方程的系数初始解组第5章线性规划（教案）教学过程教师行为学生行为教学意图时间表5.6jc3122000BcBX1x2x3x4x5xibi03x6210018004x41001040005x35001210j按下面的计算公式在表中依次填上检验数行j和比值列i,其中检验数计算公式,1ijmiijjacc例如31j即为1x所在列的目标函数系数行中的1c值减去该列系数与第一列初始解组的目标函数系数的对应乘积和，31)304060(311.选取检验数最大的正数所在列(记作k列，表中用[]表示)然后计算比值i比值的计算公式,0,ikikiiaab，例如61801.选取最小的i值，记所在行为i行(表中用[]表示)，如下表(1i）中的运算55比值列检验数行第5章线性规划（教案）教学过程教师行为学生行为教学意图时间表5.7jc3122000CBBX1x2x3x4x5xibi03x(6)2100180[30]04x41001040010005x3500121070j[31]220000最后填上目标函数Z值一格，其中目标函数Z为第一列BC与b所在列对应乘积和这样我们得到了初始表格显然前面的初始解组并不能产生最优目标函数值，因此必须要对初始解组中的变量进行替换，以求更好的解.通常我们按下述方法进行替换.表5.8jc3122000CBXB1x2x3x4x5xibi03x(6)2100180A04x410010400B05x35001210C学生按教带领6570可行解比值检验数目标函数Z第5章线性规划（教案）教学过程教师行为学生行为教学意图时间表5.9jc3122000CBBX1x2x3x4x5xibi311x131610030A/04x03263210280B/05x0(4)2101120C/表5.10jc3322000CBBX1x2x3x4x5xibi311x1316100309004x032632102801342005x0(4）2101120[30]j033563100930表5.11jc3122000CBBX1x2x3x4x5xibi311x10245012120讲解指导示范师要求一步步转化学生做转化第5章线性规划（教案）教学过程教师行为学生行为教学意图时间04x00125113620222x018104130j00248901235128075归纳：用表格法解题的步骤：第一步：建立初始表格；第二步：检验所有的j≤0，则当前有可行解；否则转入(3)第三步：检验k0,且aik≤0，(i=1,2,…,m)则无最优解；否则转入(3)第四步：确定xk，将xk换入，将松弛变量换出，否则重复第二步，第三步，第四步直到找到最优解.*巩固知识典型例题例2表格法解5.1节中的例1.某工厂用钢与橡胶生产3种产品A、B、C,有关资料如表5.3所示.已知每天可获得100单位的钢和120单位的橡胶，问每天应按排生产A、B、C三种产品各多少，能使总利润最大？试写出问题的线性约束条件和目标函数.表5.3产品单位产品钢消耗量单位产品橡胶消耗量单位产品利润A2340B3345C1224总结归纳理解领会记忆思考鼓励学生自己分析鼓励学生自己第5章线性规划（教案）教学过程教师行为学生行为教学意图时间则可得约束条件0,0,012023310032321321321xxxxxxxxx目标函数为321244540maxxxxZ解引入松弛变量54,xx，得标准型321244540maxxxxZ满足5,3,2,1,01202331003253214321jxxxxxxxxxj列初始表格jc40452400BCBX1x2x3x4x5xibi04x2(3)110100310005x3320112040j40[45]24000jc40452400BCBX1x2x3x4x5xibi452x3213131031005005x(1)011120[20]j[10]09-1501500鼓励学生自己分析在教师的鼓励下积极思考按要求按步骤完成分析解题过程中发现问题及时解决第5章线性规划（教案）教学过程教师行为学生行为教学意图时间jc40452400BCBX1x2x3x4x5xibi452x113112320401x0011120j1015101700所以当201x,202x,,03x是最优解为1700Z.80*运用知识强化练习练习5.3.2用表格法解5.1节中的问题2.炼钢厂生产某种钢材，以