北京交通大学 高级运筹学-线性规划基础.ppt

数据决策与模型傅少川经管学院物流所oh)）第一章线性规划基础线性规划问题及其数学模型线性规划图解法及其几何意义单纯形法原理单纯形法步骤及过程*四、运筹学的主要内容及学习方法学习运筹学应着重培养以下三方面的能力：善于运用所学知识，为各种实际问题建立数学模型；掌握各种模型的优化方法和解题技巧；正确理解和应用数学运算中各种参数的经济管理意义。运筹学包含的主要内容数学规划（线性规划、非线性规划、整数规划、目标规划、动态规划、随机规划、模糊规划）、图论与网络、存贮论、排队论、对策论、决策论、有哪些信誉好的足球投注网站论、系统仿真。红色为教学内容线性规划问题及其数学模型1问题提出在生产管理和经营活动中经常提出一类问题，即如何合理地利用有限的人、财、物等资源，得到最好的经济效果。线性规划以数学为工具，研究在一定的人、财、物等资源条件下，用最少的资源耗费，取得最大的经济效果。【例1--1】（线性规划问题引题）某企业生产甲、乙两种产品，要用A、B、C三种不同的原料。从工艺资料知道：每生产1吨甲产品，需耗用三种原料分别为1，1，0单位；生产1吨乙产品，需耗用三种原料分别为1，2，1单位。每天原料供应的能力分别为6，8，3单位。又知道每生产1吨甲产品，企业利润收入为300元，每生产1吨乙产品，企业利润收入为400元。386供应量34011211甲乙单位利润（百元）CBA原料产品问企业应如何安排生产计划，使一天的总利润最大？建立数学模型（建模）：①假设所求甲、乙产品每天的生产数量分别为x1，x2，称为决策变量，（简称变量）因为产量一般是一个非负数，所以有x1，x2≥0，称非负约束。②假设该企业在生产x1，x2的甲、乙产品后所得总利润为Z，显然Z=3x1+4x2。我们希望总利润值Z能达到最大，这个关系可用下面的公式表达：maxZ=3x1+4x2③给出的规划问题往往讲明了一些限制条件。三种原料每天的耗用量分别不能超过其每天的供应量6，8，3，就约束了产品的生产量x1，x2。生产x1，x2的甲、乙产品，其原料约束如下：A原料：x1+x2≤6B原料：x1+2x2≤8C原料：x2≤3把上述所有数学公式归纳如下：MaxZ=3x1+4x2x1+x2≤6x1+2x2≤8x2≤3x1,x2≥0s.t.(1—1)引例的线性规划模型2线性规划模型一般形式线性规划模型由三部分组成：①一组决策变量；②一个线性目标函数；③一组线性约束方程。线性规划问题的三要素满足这三要素的问题称为线性规划问题。（1—1）式中，目标函数是求最大值（maximum),有些问题希望目标函数最小（minimum),如目标函数表示生产费用，则希望生产费用最小。无论最大还是最小，总之希望目标函数达到最优。（1—1）式的约束条件的约束符号均为“≤”，但实际问题中有许多约束条件的约束符号要求是“≥”或“=”。一般，设有n个决策变量，m个约束方程，则线性规划问题的一般表达形式如下：线性规划问题一般表达式：①（1—2）②目标函数约束条件cj价值系数bi右边（端）常数aij约束方程系数可行解：满足②式的解可行界域：所有可行解的集合最优解：①的可行解3线性规划问题的建模建成一个正确的数模，标志着问题的解决已接近完成，答案在计算机上由线性规划程序运行很快获得。正确的建模要求建模者：熟悉规划问题的生产和管理问题，明确目标和错综复杂的约束条件，通过调查和统计资料获取原始可靠的数据。建模过程的规律：①通过对实际问题的分析、理解，明确那些是决策变量，目标要求是什么，有那些资源限制条件；②把变量、常数、约束条件、目标要求的相互关系联系起来列出相应的方程式；③注意变量、系数、常数的计量单位要统一。3．1资源合理利用问题资源合理利用是企业经常考虑的实际问题。企业（地区、国家）如何规划和调配它的有限资源以达到生产的目的