表格法解线性规划问题23534.pdf

《表格法解线性规划问题23534.pdf》由会员分享，可在线阅读，更多相关《表格法解线性规划问题23534.pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、表格的方法来求解线性规划问题的解.表格法是根据单纯形法而专门设计的一种计算表格.单纯形法Simple Method是求解线性规划问题的主要方法，该法由丹赛Dantzig于 1947 年提出，后经过屡次改良而成，是求解线性规划问题的实用算法.由上节的表达可知，如果线性规划问题的最优解存在，则必定可以在其可行解集合的顶点极点中找到因此，寻求一个最优解就是在其可行域的各个极点中搜索最优点.单纯形法实质上是一个迭代过程，该迭代即是从可行域的一个极点移到另一个近邻的极点，直到判定*一极点为最优解为止.为使用表格法，首先介绍线性规划问题的标准形式.一般的线性规划问题中目标函数可能是求最大(或最小)值，而线

4、性约束条件中可能是线性方程，也可能是线性不等式，约束条件中约束方程或不等式的个数也未必就比决策变量的个数少，这些问题对于线性规划的求解，带来极大的不便，为此，引入下述标准形式：求目标函数最大值 nnxcxcxcxcZ.max332211(用和式表示为jjnjxcZ1max)用和式表示为满足),3,2,1(,0),3,2,1(,1njxmibxajiiijnj.其中，),2,1;,3,2,1(,njmicbajiij各都是确定的常数，),2,1(njxj是决策变量，Z 是目标函数，ija叫做技术系数，ib0),2,1mi叫做资源系数，jc叫做目标函数系数.特点：1、目标函数为极大化；2、除决策变

5、量的非负约束外，所有的约束条件都是等式，且右端常数均为非负；3、所有决策变量均非负 如果根据实际问题建立起来的线性规划模型不是标准型的，可以用下述方法将它化为标准型.1假设目标函数是nnxcxcxcxcZ.min332211 可令,zz将目标函数转化为).(max332211nnxcxcxcxcZ 2 假设约束条件不等式中是,可在不等式左边加上非负变量，将不等式转化为方程.如2126xx 180 可转化为,18026321xxx其中3x0.这里的3x叫做松弛变量.表示没有用完的资源.3假设约束条件不等式是，可在不等式左边减去非负变量，将不等式转化为等式方程，如2122xx 10 可转化为102

6、2421xxx，其中，4x0.这里的4x叫做多余变量，表示不存在的资源.一般地，松弛变量和多余变量的目标函数系数为 0.4假设有一个变量kx没有非负约束叫做自由变量，可令slkxxx，其中lx0，sx0.知识稳固.例 1 将 5.1 节问题 1 中的线性规划问题化为标准型 约束条件 0,0210534001041802621212121xxxxxxxx 求目标函数最大值212231maxxxZ 解 分别对前三个约束条件引入松弛变量543,xxx，得标准型：约束条件.5,3,2,1,02105340010418026521421321jxxxxxxxxxxj 求目标函数最大值212231maxx

7、xZ 表格法 下面我们通过实例来介绍表格法.首先要列出初始表格为了得到初始表格，我们分几步来说明：先把标准型中的约束条件方程转换成表格表 5.4的形式 如:5.1 问题 1 转化的结果为：.5,2,1,02100053400001041800026543215432154321jxxxxxxxxxxxxxxxxj列成表格为：表 5.4 1x 2x 3x 4x 5x ib 6 2 1 0 0 180 4 10 0 1 0 400 3 5 0 0 1 210.(表格中的列数为变量个数加 1，行数为方程个数加 1)从约束方程中，很容易得到，当01x，02x时，1803x，4004x，2105x，显然

8、这是一组可行解我们把它叫作初始解组，将其中三个取非 0 值的变量543,xxx列成一列对应地加在上表的最左侧，然后再在所得表的左侧添加一列对应于该初始解组变量的目标函数系数，在表的上侧添加一行对应于各变量的目标函数系数，得如下表：其中在初始解组中的变量必须满足在对应行的约束条件方程中系数为 1，而同列其他系数为 0，如果约束条件方程中不满足这要求，可以通过对线性约束条件方程作加减消元法而得到.再在上表的根底上，增加 1 行(叫做检验数行j)和 1 列(叫做比值列i)得下面形式：按下面的计算公式在表中依次填上检验数行j和比值列i,其中检验数计算公式,1ijmiijjacc例如31j，即为1x所在

9、列的目标函数系数行中的1c值减去该列系数与第一列初始解组的目标函数系数的对应乘积和，31)304060(311.选取检验数最大的正数所在列(记作k列，表中用 表示)然后计算比值i 比值的计算公式,0,ikikiiaab，例如61801.选取最小的i值，记所在行为i行(表中用 表示)，如下表(1i 最后填上目标函数 Z 值一格，其中目标函数 Z 为第一列BC与b所在列对应乘积和.得下表：表 5.7 jc 31 22 0 0 0 CB BX 1x 2x 3x 4x 5x ib i 0 3x(6)2 1 0 0 180 30 0 4x 4 10 0 1 0 400 100 0 5x 3 5 0 0

10、1 210 70 j 31 22 0 0 0 0 这样我们得到了初始表格表 5.7 显然，前面的初始解组并不能产生最优目标函数值，因此，必须要对初始解组中的变量进展替换，以求更好的解.通常，我们按下述方法进展变量的替换：根据上面所选的第 k 列第 i 行(如上表中3x所在行和1x所在列，我们将两者的穿插点用()表示)，对初始解组作调整，将变量kx换入，替代第 i 行中的初始变量(即表中换入1x，换出3x)，根据表格法的要求，必须同时将换入变量kx在()中的系数通过加减消元法化为 1，且同列其他系数为 0，而初始解组中其他未换出变量所在列的系数不变，通常可用加减消元法来求得 下面我们具体来说明表

11、格的转换 框中行除以 6 得行；行减4 得行；行减3 得行(表 5.8 转换到表 5.9)可行解 比值 检验数 目标函数 Z.表 5.8 jc 31 22 0 0 0 CB*B 1x 2x 3x 4x 5x ib i 0 3x(6)2 1 0 0 180 0 4x 4 10 0 1 0 400 0 5x 3 5 0 0 1 210 表 5.9 jc 31 22 0 0 0 CB BX 1x 2x 3x 4x 5x ib i 31 1x 1 31 61 0 0 30 0 4x 0 326 32 1 0 280 0 5x 0(4)21 0 1 120 再依次填上检验数行j和比值列i，得下表(表 5

12、.10)表 5.10 jc 33 22 0 0 0 CB BX 1x 2x 3x 4x 5x ib i 31 1x 1 31 61 0 0 30 90 0 4x 0 326 32 1 0 280 13420 0 5x 0(4 21 0 1 120 30 j 0 335 631 0 0 930 如果检验数全为非正数，则，所得解就是最优解否则，继续按前.方法修改可行解，直至不能继续为止显然，上表中2x换入，变量5x换出转下表(表 5.11)表 5.11 jc 31 22 0 0 0 CB BX 1x 2x 3x 4x 5x ib i 31 1x 1 0 245 0 121 20 0 4x 0 0

13、125 1 136 20 22 2x 0 1 81 0 41 30 j 0 0 2489 0 1235 1280 因为所有的检验数j0，故当前可行解201x，302x，03x，04x，05x为最优解，删去松弛变量，即得原线性规划最优解为 201x，302x，最优值为 Z=1280 通过上面的例子，可以归纳一般的表格法的计算步骤如下：第一步：建立初始表格 第二步：检查：假设所有的j0，则当前可行解即为最优解；否则转入(3)第三步：检查：假设存在k0,且aik0，(i=1,2,m)，则无最优解；否则转入(4)第四步：选取检验数行中最大的正数所在的列，(记作k列，表中用 表示)然后计算比值i，比值的

14、计算公式0,ikikiiaab 选取最小的i值，记所在行为i行(表中用 表示)，确定*k，将.*k换入，将松弛变量*h换出，用加减消元法化*k的系数aik为 1，且同列其他系数为 0以*k取代*h得新表，转入(2).稳固知识 典型例题 例 2 用表格法解 5.1 节中的例 1：*工厂用钢与橡胶生产 3 种产品A、B、C,有关资料如表 5.3 所示.每天可获得 100 单位的钢和 120 单位的橡胶，问每天应按排生产A、B、C三种产品各多少，能使总利润最大？试写出问题的线性约束条件和目标函数.表 5.3 产品 单位产品钢消耗量 单位产品橡胶消耗量 单位产品利润 A 2 3 40 B 3 3 45

15、 C 1 2 24 则可得约束条件0,0,012023310032321321321xxxxxxxxx 目标函数为321244540maxxxxZ 解 引入松弛变量54,xx，得标准型：满足5,3,2,1,01202331003253214321jxxxxxxxxxj 列初始表格(表 5.12)表 5.12 jc 40 45 24 0 0 BC BX 1x 2x 3x 4x 5x ib i.0 4x 2(3)1 1 0 100 3100 0 5x 3 3 2 0 1 120 40 j 40 45 24 0 0 0 因为2为最大正数，转下表(表 5.13)表 5.13 jc 40 45 24 0

16、 0 BC BX 1x 2x 3x 4x 5x ib i 45 2x 32 1 31 31 0 3100 50 0 5x(1)0 1 1 1 20 20 j 10 0 9-15 0 1500 将1x换入，5x换出，得表 5.14 表 5.14 jc 40 45 24 0 0 BC BX 1x 2x 3x 4x 5x ib i 45 2x 0 1 31 1 23 20 40 1x 1 0 1 1 1 20 j 0 0 1 5-10 1700 因为所有的检验数j0，故当前可行解201x,202x,03x，04x，05x为最优解，删去松弛变量，即得原线性规划最优解为 201x,202x,03x，目标函数最优值为1700Z.