大学教案—线性规划

渭南师范学院数学系讲稿2012~2013学年第二学期教研室计算数学课程名称线性规划授课对象数专升本12级授课教师路玉麟职称讲师教材名称《线性规划》•武汉大学出版社•张干宗2013年3月10日渭南师范学院数学系教师教案纸第页《线性规划》课程教案讲稿授课题目（教学章节或主题）：前言线性规划概述授课类型课堂讲授授课时间第1周第1节教材分析：本章主要介绍了线性规划的基本概念。教学目的与要求：要求学生掌握线性规划的作用和意义。重点与难点：重点：线性规划的基本概念难点：常见线性规划问题教学内容与过程（设想、方法、手段）启发式教学、课堂精讲、讲练结合思考题、讨论题、作业：参考资料（含参考书、文献等）：渭南师范学院数学系教师教案纸第页教学内容与过程课后分析前言线性规划的英文全称为：LinearProgramming，可简称为LP．一、线性规划所属学科线性规划是“运筹学”中应用最广泛、理论最成熟的一个分支．模型论存储论图论排队论决策论对策论动态规划多目标规划规划整数规划非线性规划线性规划静态规划规划论运筹学10二、线性规划发展简史三十年代末，苏联数学家康托洛维奇开始研究生产组织中的线性规划问题．1947年美国数学家丹捷格提出了单纯形(Simplex)方法及有关理论，为线性规划奠定了理论基础．五十年代，线性规划成为经济学家分析经济问题的重要工具．随着计算机的迅猛发展，线性规划现被广泛应用于工业、农业、商业等各个领域．三、用线性规划方法解决实际问题的两大特点1、全局性——从全局出发，将全局目标作为追求目标；2、定量性——通过建立数学模型，对实际问题进行定量分析，而不是只做定性分析．数学模型指：将实际问题用一系列数学表达式(函数、方程、不等式等)表示出来，称这一系列数学表达式为该实际问题的数学模型．同时应注意全局的相对性，即对于车间，企业是全局；但对于集团公司，企业是局部，集团公司才是全局．渭南师范学院数学系教师教案纸第页教学内容与过程课后分析四、线性规划方法解决的两类问题1、任务一定，如何安排，可使人、财、物最省；2、人、财、物一定，如何安排，可使任务完成量最多．五、线性规划可解决以下几方面的问题１、运输问题：某产品有若干个产地、若干个销地，如何运输，使总运费最省；2、生产组织问题：产，使成本最低产值一定，如何安排生最高或利润产，使产值资源一定，如何安排生)(3、配料问题：如何搭配各种原料，既符合质量(营养)要求，又使成本最低；4、投资问题：资金一定，投向谁、投多少、期限多长，使若干年后本利和最高；5、库存问题：在仓库容量有限情况下，如何确定库存物资的品种、数量、期限，使库存效益最佳；6、合理播种问题：在土地资源有限的情况下，种什么、种多少，使效益最高；……六、用线性规划方法解决实际问题的步骤1、提出问题，收集资料；2、建立线性规划数学模型；3、用线性规划方法解模型；4、给出最优决策方案．七、讲授内容1、建模；2、用图解法解线性规划问题；3、用计算机软件解线性规划模型；4、写最优决策方案．八、考试方式：渭南师范学院数学系教师教案纸第页教学内容与过程课后分析渭南师范学院数学系教师教案纸第页《线性规划》课程教案讲稿授课题目（教学章节或主题）：第一章线性规划数学模型的建立授课类型课堂讲授授课时间第周第节教材分析：本章通过例题说明线性规划数学模型的形式、三要素及建立数学模型的方法．教学目的与要求：通过本章学习，使学生理解线性规划数学模型的概念及一般表示形式；掌握线性规划数学模型的三要素；掌握建立线性规划数学模型的步骤和方法；能熟练的建立一些问题的线性规划数学模型；理解线性规划数学模型解的含义．重点与难点：重点：线性规划数学模型的建立难点：建立线性规划数学模型教学内容与过程（设想、方法、手段）启发式教学、课堂精讲、讲练结合1、供求平衡条件下的运输问题模型的建立；2、线性规划数学模型的三要素；3、建立线性规划数学模型的步骤；4、线性规划问题解的概念（可行解、可行解集、最优解、最优值）；5、线性规划的概念；6、线性规划数学模型的一般形式．思考题、讨论题、作业：参考资料（含参考书、文献等）：渭南师范学院数学系教师教案纸第页教学内容与步骤备注本章通过例题说明线性规划数学模型的形式、三要素及建立数学模型的方法．一、建立线性规划数学模型的例例1供求平衡状态下的运输问题有两个农场1A和2A，产粮量分别为23万吨和27万吨，要将粮食运往1B，2B，3B三个城市，三个城市的粮食需求量分别为17、18和15万吨．农场到各城市的运价如下表运价表单位：元/万吨运价城市农场1B2B3B1A5060702A60110160问：应如何调运，可使总运费最省？试建立该问题的数学模型．分析此问题有两个供应方1A和2A，三个需求方1B，2B，3B，假设这五者组成一个封闭系统，两个供应者的粮食只能提供给这三个需求方，同时三个需求方的粮食也只能从这两个供应者处获得．要建立该问题数学模型，必须首先从问题出发．该题问“应如何调运，使总运费最省”．“应如何调运”指从农场1A分别向三个城市运多少万吨粮食(三个量)，从农场2A分别向三个城市运多少万吨粮食(三个量)，共计6个量．上述6个量是可以变化的，在计算前是未知的，是有待决策的，称其为决策变量．在建立数学模型时应首先将其设出．为便于区分供应方和需求方，将其设为双下标变量．设：从农场)2,1(iAi运往城市)3,2,1(jBj的调运量为)3,2,1;2,1(jixji万吨．渭南师范学院数学系教师教案纸第页教学内容与步骤备注注意，此时的jix既表示从农场iA发往城市jB的发出量，同时也表示城市jB从农场iA处的接收量．如31x表示从农场1A运往城市3B的粮食量，同时表示城市3B从农场1A处的接收量．为方便讨论问题，运输问题通常先列出如下调运表．调运表调运量城市农场1B2B3B产粮量(可供应量)1A11x21x31x232A12x22x23x27需求量171815供求平衡在这五个部门组成的封闭系统中，所有供应方的可供应量之和(23+27=50)为整个系统的可供应量，整个系统中所有城市粮食需求量之和(17+18+15=50)构成系统的总需求量．由于该系统的总供应量和总需求量都是50，相等，故在调运表最后一个单元格中填写“供求平衡”．此问题即为供求平衡状态下的运输问题．上述所设的6个决策变量(调运量)应满足一定要求，这些要求就应从供求平衡开始．由于供求平衡，供应方和需求方均恰好得到满足，即：两个供应方的粮食恰好全部运出，三个需求方所需要的粮食也恰好全部得到满足，下面通过列表将文字语言转化为数学表达式．供应方：调出量恰好等于产粮量供应方调出量恰好等于产粮量1A131211xxx=232A232212xxx=27需求方：调入量恰好等于需求量渭南师范学院数学系教师教案纸第页教学内容与步骤备注需求方调入量恰好等于需求量1B2111xx=172B2221xx=183B2331xx=15于是，所设决策变量同时满足以上五个方程，且由于jix为调运量，必须非负．所以)3,2,1;2,1(jixji应满足：)3,2,1;2,1(01518172723231322122111232221131211jixxxxxxxxxxxxxji称上述条件为约束条件，满足约束条件的解称为可行解．分析可行解的情况．由于方程组中无矛盾方程，且有效方程的个数(4个)少于未知量的个数(6个)，方程组有无穷多个解，进一步满足非负条件的解也有无穷多个，即可行解有无穷多个，每个可行解对应着一个调运方案(可执行方案)．如：解65169131232221131211xxxxxx解561610121232221131211xxxxxx方案11B2B3B1A1139232A165627171815对应方案21B2B3B1A11210232A166527171815对应渭南师范学院数学系教师教案纸第页教学内容与步骤备注显然，应有无穷多种调运方案．每个调运方案都对应着一个总运费．方案1对应的总运费为：39301606110560167096013501(元)；方案2对应的总运费为：389016051106601670106012501(元)．即该题有无穷多个调运方案，不同调运方案对应不同运费，该问题要从无穷多个调运方案中找出一个使总运费最省的方案，即使总运费函数23222113121116011060706050xxxxxxS取得最小值的一组变量)3,2,1;2,1(jixji的取值．综上，该问题数学模型列写如下：解设：由农场)2,1(iAi运往城市)3,2,1(jBj的调运量为)3,2,1;2,1(jixji万吨．则该问题的数学模型为：求一组变量)3,2,1;2,1(jixji的值，使其满足：)3,2,1;2,1(01518172723231322122111232221131211jixxxxxxxxxxxxxji并使23222113121116011060706050xxxxxxS最小．此问题充分体现了全局观念．需求方不能仅考虑自己运费是否最低，而必须从整个封闭系统总运费最低的角度出发，做到局部利益服从整体利益．该题属第一类问题，即任务一定，如何安排，使人、财、物最省．通过例1对线性规划数学模型有关问题作如下归纳．渭南师范学院数学系教师教案纸第页教学内容与步骤备注二、线性规划数学模型的三要素所有线性规划数学模型都要求一组变量的值，称该组变量为决策变量；该组决策变量都要满足一组条件，称该组条件为约束条件．一般，约束条件由两部分组成：一部分为非负约束，剩下部分为数量约束；通常，满足约束条件的解若存在有无穷多个，我们最终不是求这无穷多个解分别是什么，而要寻求一个目标．这个目标由函数表示，称为目标函数，线性规划问题最终要使目标函数取得最大值或最小值．决策变量、约束条件、目标函数分别构成了线性规划数学模型的三大要素．即目标函数非负约束数量约束约束条件决策变量素线性规划数学模型三要三、建立线性规划数学模型的步骤建立实际问题线性规划数学模型的过程，实际是“翻译”的过程，即将实际问题翻译成数学表达式的过程．通常先用文字将实际问题表示出来，再将文字转化为数学表达式．具体步骤如下：1、设决策变量——根据题目的“问题”，设决策变量；2、列写约束条件——根据题目要求(字面或隐含)列出约束条件，约束条件中通常包含非负限制．3、写目标函数，并注明求最大或最小．通常目标函数要求在题目的问中提出．四、线性规划问题解的概念1、可行解：满足约束条件的解称为线性规划问题的可行解．2、可行解集：全体可行解组成的集合．3、最优解：使目标函数实现最优的可行解．4、最优值：最优解对应的目标函数值．由上述分析知，线性规划问题最终就是要求最优解和最优值，该过程称作解线性规划问题的过程，或求线性规划问题的解的过程．通常人们靠经验、靠想象求最优解，如上述例1，人们通常从当今的最低运费开始设计，直至满足所有需求方的需求，具体操作如下：渭南师范学院数学系教师教案纸第页教学内容与步骤备注由于1A到1B的运费最低，因而1B的需求17万吨全部从1A处获得，1A得到满足；在余下的运费中，1A到2B的运费最低，将1A剩余的6万吨给2B，2B所需的另12吨只能从运费相对较低的2A处获得；由于此时1A的粮食已全部运出，尽管运费较高，3B所需要的15万吨粮食也只能从2A处获得．于是调运表如下方案1B2B3B1A1760232A0121527171815该调运方案所对应的总运费为4930元．显然不是最优方案．因而必须有专用的、科学的方法解线性规划问题．解线性规划问题的方法有图解法、单纯形