《数学》基础模块上册课件5.3解线性规划问题的表格法

1、第五章第五章 线性规划线性规划 对于多于两个决策变量的线性规划问题，可以用什么方法呢？求线性规划问题的图解法虽然直观简便，求线性规划问题的图解法虽然直观简便，但对多于两个变量的情况就不能适用了但对多于两个变量的情况就不能适用了. 这就是我们要学习的用表格法表格法解线性规划问题.1.线性规划问题的标准形式线性规划问题的标准形式:nnxcxcxcxcZ.max332211jjnjxcZ1max( 用和式表示为 ), 3 , 2 , 1( , 0), 3 , 2 , 1( ,1njxmibxajijijnj满足 目标函数目标函数资源系数资源系数决策变量决策变量目标函数系目标函数系数数2.线性规划模型

2、化为标准型步骤线性规划模型化为标准型步骤 ：第一步：化目标函数第一步：化目标函数若 nnxcxcxcxcZ.min332211可转化为： ).(max332211nnxcxcxcxcZ第二步：化决策变量第二步：化决策变量(1)若约束条件不等式是“”加一个松弛变量加一个松弛变量(2)若约束条件不等式是“”减一个多余变量减一个多余变量 (3)若有一个变量kxslkxxxlxsx可令其中0，0.非负变量非负变量非负变量非负变量.例例1 将5.1节问题1中的线性规划问题化为标准型 0, 0210534001041802621212121xxxxxxxx约束条件目标函数 212231maxxxZ 解 分

3、别对前三个约束条件引入松弛变量，得标准型. 5 , 2 , 1, 02100053400001041800026543215432154321jxxxxxxxxxxxxxxxxj 目标函数 212231maxxxZ约束条件 1.标准型中的约束条件方程转换成表格的形式标准型中的约束条件方程转换成表格的形式. 5 , 2 , 1, 02100053400001041800026543215432154321jxxxxxxxxxxxxxxxxjx1x2x3x4x5bi6210018041001040035001210表格中的列数为变量个数加表格中的列数为变量个数加1，行数为方程个数加，行数为方程个数

4、加1 5.3.2表格法表格法 2.找初始解组找初始解组 jcBcBX3x4x5x4x5xib1x2x3x21010053040001010401800012600002231当当 ， ，时，时， ， ， 显然这是一组可行解显然这是一组可行解.我们把它他叫作出初始解组我们把它他叫作出初始解组. 01x02x1803x4004x2105x初始解组初始解组各约束方程的各约束方程的系数系数 增加1行(叫做检验行)和1列(叫做比值列) jcBcBX1x2x3x4x5xibi3x4x5xj21010053040001010401800012600002231检验数行检验数行比值列比值列检验数计算公式检验数

5、计算公式,1ijmiijjacc 选取检验数最大的正数所在列(记作k列，表中用 表示)然后计算比值i312200003010070 3.调整初始解组调整初始解组 换入 ，换出1x3x21010(4)004000100180001310002231jcBcBX1x2x3x4x5xibi4x5xj 03350013420301x3132661322193063190换入 ，换出2x5x 0300102220100020001310002231jcBcBX1x2x3x4x5xibi4xj 006131x24512581128024891215x411235所以 0 ，当前可行解 ， 为最优解.j201x,302x0, 0, 0543xxx删去松弛变量 原线性规划当 最优解为 0, 0, 0543xxx,201x,302x.1280Z jkikakxkx用表格法解题的步骤：用表格法解题的步骤：第一步：建立初始表格；第二步：检验所有的0，则当前有可行解；否则0,且0，则无最优解；否则，将重复第二步，第三步，第四步直到找到最优解.