资源描述：
《表格法解线性规划问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、表格法解线性规划问题【教学目标】知识目标：理解用表格法解线性规划问题的方法和步骤.能力目标：通过例子详细地介绍了表格法解线性规划问题的过程,并引入了线性规划标准型的概念，归纳总结了表格法解线性规划问题的步骤.【教学重点】理解用表格法解线性规划问题的方法和步骤.【教学难点】理解用表格法解线性规划问题的方法和步骤.【教学设计】1、表格法也称单纯形法，是解线性规划问题的常用方法，使用该方法时，首先要将一般的线性规划问题化为标准型.在教材中给出了化标准型的方法.讲解时一定要注意b20以及变量的非负性.2、表格法解线性规划问题的过程，教材中归纳为五
2、个步骤，这实际上是一个算法，可以利用前面介绍过的算法知识来学习.3、初始表格中初始解组的确定是关键，一般可取松弛变量，但当标准型中没有这样的变量满足初始解组的要求时，通常要通过添加人工变量来解决，本教材没有就这方面的问题进行深入讨论（一般的运筹学教材中都可找到该内容）.4、表格在转换时（通常称为转轴），教材中提到用加减消元法来转轴•教师可就这部分内容作适当的讲解.5、由于通常的表格转换要进行多次，而表头部分是不变的，因此可以将多张表格合并起来，具体样式可参见5.5节表5-16.【教学过程】5.3.1线性规划问题的标准形式求线性规划问题的图
3、解法虽然直观简便，但对多于两个变量的情况就不能适用了，对于多于两个决策变量的线性规划问题，可以用什么方法呢？卜'面介绍一种用表格的方法来求解线性规划问题的解.表格法是根据单纯形法而专门设计的一种计算表格•单纯形法（SimpleMethod）是求解线性规划问题的主要方法，该法市丹赛（Dantzig）于1947年提出，后经过多次改进而成，是求解线性规划问题的实用算法.由上节的叙述可知，如果线性规划问题的最优解存在，则必定可以在其中可行解集合的顶点（极点）中找到。因此，寻求一个最优解就是在其可行域的各个极点中搜索最优点•单纯形法实质上是一个迭代
4、过程，该迭代即是从可行域的一个极点移到另一个近邻的极点，直到判定某一极点为最优解为止.为使用表格法，首先介绍线性规划问题的标准形式.一般的线性规划问题中口标函数可能是求最人（或最小）值，而线性约束条件中可能是线性方程，也可能是线性不等式，约束条件中约束方程（或不等式）的个数也未必就比决策变量的个数少，这些问题对于线性规划的求解，带来极大的不便，为此，引入下述标准形式：求目标函数最大值maxZ=q兀1+c2x2+c3x3+...+cnxn（用和式表示为maxZ=£c/.p）7=11兀］+a2X2+…+aXn=56Z9
5、Xj+兀•？+…
6、+满足佥內+佥2兀2+・・・+。如心=hmX］>0,x2>。，…，百>0用和式表示为满足丿工n勺兀=bj,(i=1,2,3,…，加)7=1Xj>(),(>=1,2,3,其中，各ciij,bj,Cj（i=1,2,3,…，加;丿=1,2,・・・,〃）都是确定的常数,x7（y=1,2,•••,«）是决策变量,Z是目标函数，a”•叫做技术系数，勺$0（心1,2,・・"）叫做资源系数，勺叫做目标函数系数.特点:1、目标函数为极大化；2、除决策变量的非负约束外，所有的约束条件都是等式，且右端常数均为非负；3、所有决策变量均非负.如果根据实际问题建立起
7、来的线性规划模型不是标准型的，可以用下述方法将它化为标准型.（1）若目标函数是minZ=c內+c2x2+c3x3+・・・+c“x“可令z=-z',将目标函数转化为maxZ=一（c】兀］+c2x2+c3x3+...+C屁）（2）若约束条件不等式中是“W”，可在不等式左边加上非负变量，将不等式转化为方程.如6xj+2兀2W180可转化为6兀］+2*2+勺=180,其屮兀3上0・这里的®叫做松弛变量.表示没有用完的资源.（3）若约束条件不等式是“2”，可在不等式左边减去非负变量，将不等式转化为等式方程,如2xl+2勺210可转化为2xl+2兀2
8、-x4=10,其屮,X4$0.这里的兀4叫做多余变量,表示不存在的资源.一般地，松弛变量和多余变量的冃标函数系数为0.（4）若有一个变量忑没有非负约束（叫做自由变量），可令忑=心-耳,其中兀/20,x$20.知识巩固例1将5.1节问题1中的线性规划问题化为标准型6兀］+2x2<180约朿条件4X［+10x2<4003兀］+5x2<210X］>0,x2>0求冃标函数最大值=+22兀2解分别对前三个约束条件引入松弛变量勺，兀,“，得标准型:6兀］+2x2+x3=180约束条件4%j+10x2+x4=4003兀］+5x2+兀5=210>0,j=
9、l,2,3,---5.求口标函数最人值maxZ=31Xj+22x25.3.2表格法下面我们通过实例来介绍表格法.首先要列出初始表格.为了得到初始表格，我们分几步来说明:先把标准型屮的约束条件方
