实用线性代数与线性规划电子教案WORDCH.doc

PAGE 24 PAGE 1 第三章 线性规划数学模型的建立 教学目的 通过本章学习，使学生理解线性规划数学模型的概念及一般表示形式；掌握线性规划数学模型的三要素；掌握建立线性规划数学模型的步骤和方法；能熟练的建立一些问题的线性规划数学模型；理解线性规划数学模型解的含义． 教学重点 线性规划数学模型的建立． 教学难点 建立线性规划数学模型． 教学内容 供求平衡条件下的运输问题模型的建立； 线性规划数学模型的三要素； 建立线性规划数学模型的步骤； 线性规划问题解的概念（可行解、可行解集、最优解、最优值）； 线性规划的概念； 线性规划数学模型的一般形式．  本章通过例题说明线性规划数学模型的形式、三要素及建立数学模型的方法． 一、建立线性规划数学模型的例 供求平衡状态下的运输问题 有两个农场和，产粮量分别为23万吨和27万吨，要将粮食运往，，三个城市，三个城市的粮食需求量分别为17、18和15万吨．农场到各城市的运价如下表 运价表　　 　　单位：元/万吨 运价 城市 农场 50 60 70 60 110 160 问：应如何调运，可使总运费最省？试建立该问题的数学模型． 分析　此问题有两个供应方和，三个需求方，，，假设这五者组成一个封闭系统，两个供应者的粮食只能提供给这三个需求方，同时三个需求方的粮食也只能从这两个供应者处获得． 要建立该问题数学模型，必须首先从问题出发． 该题问“应如何调运，使总运费最省”． “应如何调运”指从农场分别向三个城市运多少万吨粮食(三个量)，从农场分别向三个城市运多少万吨粮食(三个量)，共计6个量． 上述6个量是可以变化的，在计算前是未知的，是有待决策的，称其为决策变量．在建立数学模型时应首先将其设出．为便于区分供应方和需求方，将其设为双下标变量． 设：从农场运往城市的调运量为万吨． 注意，此时的既表示从农场发往城市的发出量，同时也表示城市从农场处的接收量． 如表示从农场运往城市的粮食量，同时表示城市从农场处的接收量． 为方便讨论问题，运输问题通常先列出如下调运表． 调运表 调运量　 城市 农场 产粮量 (可供应量) 23 27 需求量 17 18 15 供求平衡 在这五个部门组成的封闭系统中，所有供应方的可供应量之和(23+27=50)为整个系统的可供应量，整个系统中所有城市粮食需求量之和(17+18+15=50)构成系统的总需求量．由于该系统的总供应量和总需求量都是50，相等，故在调运表最后一个单元格中填写“供求平衡”．此问题即为供求平衡状态下的运输问题． 上述所设的6个决策变量(调运量)应满足一定要求，这些要求就应从供求平衡开始． 由于供求平衡，供应方和需求方均恰好得到满足，即：两个供应方的粮食恰好全部运出，三个需求方所需要的粮食也恰好全部得到满足，下面通过列表将文字语言转化为数学表达式． 供应方：调出量恰好等于产粮量 供应方 调出量 恰好等于 产粮量 = 23 = 27 需求方：调入量恰好等于需求量 需求方 调入量 恰好等于 需求量 = 17 = 18 = 15 于是，所设决策变量同时满足以上五个方程，且由于为调运量，必须非负．所以应满足： ． 称上述条件为约束条件，满足约束条件的解称为可行解． 分析可行解的情况． 由于方程组中无矛盾方程，且有效方程的个数(4个)少于未知量的个数(6个)，方程组有无穷多个解，进一步满足非负条件的解也有无穷多个，即可行解有无穷多个，每个可行解对应着一个调运方案(可执行方案)．如： 方案11139 方案1 1 13 9 23 16 5 6 27 17 18 15 对应 方方案2 1 12 10 23 16 6 5 27 17 18 15 对应 显然，应有无穷多种调运方案．每个调运方案都对应着一个总运费． 方案1对应的总运费为： (元)； 方案2对应的总运费为： (元)． 即该题有无穷多个调运方案，不同调运方案对应不同运费，该问题要从无穷多个调运方案中找出一个使总运费最省的方案，即使总运费函数 取得最小值的一组变量的取值． 综上，该问题数学模型列写如下： 解 设：由农场运往城市的调运量为万吨． 则该问题的数学模型为： 求一组变量的值，使其满足： 并使最小． 此问题充分体现了全局观念．需求方不能仅考虑自己运费是否最低，而必须从整个封闭系统总运费最低的角度出发，做到局部利益服从整体利益． 该题属第一类问题，即任务一定，如何安排，使人、财、物最省． 通过例1对线性规划数学模型有关问题作如下归纳． 二、线性规划数学模型的三要素 所有线性规划数学模型都要求一组变量的值，称该组变量为决策变量；该组决策变量都要满足一组条件，称该组条件为约束条件．一般，约束条件由两部分组成：一部分为非负约束，剩下部分为数量约束；通