《线性规划》ppt课件

《《线性规划》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、OPERATIONSRESEARCH运筹学——怎样把事情做到最好张朝伦绪论Operations汉语翻译工作、操作、行动、手术、运算OperationsResearch日本——运用学港台——作业研究中国大陆——运筹学OperationalResearch原来名称，意为军事行动研究——历史渊源运筹学的历史军事运筹学阶段德军空袭防空系统Blackett运输船编队空袭逃避深水炸弹轰炸机编队运筹学在中国：50年代中期引入华罗庚推广优选法、统筹法中国邮递员问题、运输问题学科性质应用学科Morse&Kimball定义：运筹学是为决策机构在对其控制的业务活动进行决策时提供的数量化为基础的

2、科学方法。Churchman定义：运筹学是应用科学的方法、技术和工具，来处理一个系统运行中的问题，使系统控制得到最优的解决方法。中国定义：运筹学是应用分析、试验、量化的方法，对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。运筹学的工作步骤确定问题搜集数据建立模型检验模型求解模型结果分析结果实施运筹学与计算机计算机为运筹学提供解题工具。要学会解题的思路与方法，建立模型很重要。线性规划（LinearProgramming，简称LP）线性规划的发展1939年，前苏联数学家康托洛维奇用线性模型研究提高组织和生产效率问题194

3、7年，Dantzig提出求解线性规划的单纯形法1950-1956年，主要研究线性规划的对偶理论1958年，发表整数规划的割平面法1960年，Dantzig和Wolfe研究成功分解算法，奠定了大规模线性规划问题理论和算法的基础。1979年，Khachiyan，1984年，Karmarkaa研究成功线性规划的多项式算法。线性规划研究的主要问题一类是已有一定数量的资源（人力、物质、时间等），研究如何充分合理地使用它们，才能使完成的任务量为最大。——实际上，上述两类问题是一个问题的两个不同的方面，都是求问题的最优解（max或min）。另一类是当一项任务确定以后，研究如何统筹安排，

4、才能使完成任务所耗费的资源量为最少。线性规划例1.1某厂生产两种产品，下表给出了单位产品所需资源及单位产品利润问：应如何安排生产计划，才能使总利润最大？线性规划的基本概念一、问题的提出解：1.决策变量：设产品I、II的产量分别为x1、x22.目标函数：设总运费为z，则有：maxz=2x1+3x23.约束条件：x1+2x2≤84x1≤164x2≤12x1，x2≥0例1.2某厂生产三种药物，这些药物可以从四种不同的原料中提取。下表给出了单位原料可提取的药物量要求：生产A种药物至少160单位；B种药物恰好200单位，C种药物不超过180单位，且使原料总成本最小。解：1.决策变量

5、：设四种原料的使用量分别为：x1、x2、x3、x42.目标函数：设总成本为z，则有：minz=5x1+6x2+7x3+8x43.约束条件：x1+2x2+x3+x4≥1602x1+4x3+2x4＝2003x1＋x2+x3+2x4≤180x1、x2、x3、x4≥0药物原料ABC单位成本（元／吨）甲1235乙2016丙1417丁1228例3、合理下料问题例3、合理下料问题设xj分别代表采用切割方案1~8的套数，二、数学模型1.决策变量：X=(x1,x2,…..,xn)T2.目标函数：max(minz)=c1x1+c2x2+…….+cnxn3.约束条件：a11x1+a12x2+

6、……..+a1nxn≤(=≥)b1a21x1+a22x2+……..+a2nxn≤(=≥)b2…………………………………………am1x1+am2x2+……..+amnxn≤(=≥)bmx1,x2,……xn≥0三、模型特点1都用一组决策变量X=(x1,x2,…,xn)T表示某一方案，且决策变量取值非负；———满足以上三个条件的数学模型称为线性规划2都有一个要达到的目标，并且目标要求可以表示成决策变量的线性函数；3都有一组约束条件，这些约束条件可以用决策变量的线性等式或线性不等式来表示。其它形式其中：①求和形式②矩阵形式决策变量常数项系数矩阵价值系数其中：线性规划数学模型的建立

7、一、建模条件1优化条件：问题所要达到的目标能用线型函数描述，且能够用极值（max或min）来表示；2限定条件：达到目标受到一定的限制，且这些限制能够用决策变量的线性等式或线性不等式表示；3选择条件：有多种可选择的方案供决策者选择，以便找出最优方案。线性规划图解法一、解题步骤4将最优解代入目标函数，求出最优值。1在直角平面坐标系中画出所有的约束等式，并找出所有约束条件的公共部分，称为可行域，可行域中的点称为可行解。2标出目标函数值增加的方向。3若求最大（小）值，则令目标函数等值线沿（逆）目标函数值增加的方向平行移动，找与可行域最