运筹学与最优化方法第4章课件.ppt

《运筹学与最优化方法第4章课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章线性规划本章内容线性规划问题及其数学模型线性规划的图解法线性规划解的基本性质单纯形算法初始基本可行解求法对偶性及对偶单纯形方法线性规划灵敏度分析线性规划的建模实例用数学软件求解线性规划模型介绍运筹学线性规划线性规划研究的主要问题一类是已有一定数量的资源（人力、物质、时间等），研究如何充分合理地使用它们，才能使完成的任务量为最大。另一类是当一项任务确定以后，研究如何统筹安排，才能使完成任务所耗费的资源量为最少。——实际上，上述两类问题是一个问题的两个不同的方面，都是求问题的最优解（max或min）。线性规划（LinearProgramm

2、ing)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simplermethod）线性规划运筹学一、线性规划问题的提出例4.1生产计划问题(资源分配问题):某工厂生产门窗两种产品，已知的条件如表所示，试制订总利润最大的生产计划。§4.1线性规划问题及数学模型问题分析运筹学线性规划模型运筹学线性规划用Excel软件求解：产品门生产2件产品窗生产6件最大利润3600（元）例4.2投资问题：某公司有100万元资金要投资（要求全部用完）。该公司有六个投资项目可选，已知的条件如表所示，该公司希望投资风险最小，每年

3、红利至少为6.5万，最低平均增长率为12%，最低平均信用度为7。试解该问题。运筹学线性规划问题分析运筹学线性规划模型用Excel软件求解：项目1投资25万元项目2投资0万元项目3投资12.5万元项目4投资62.5万元项目5投资0万元项目6投资0万元平均总风险8.25%例4.3运输问题：运筹学线性规划B1B2…BnA1A2…A3c11c21…cm1c12c22…cm2…………c1nc2n…cmn单位运价表(cij)B1B2B3B4产量A1A2…A3x11X21…xm1x12X22…xm2…………x1nX2n…xmna1a2…am销量b1b2…

4、bn产销平衡表（决策变量xij=0或1)问题分析运筹学线性规划模型运筹学线性规划两个例子的特点是：1都用一组决策变量X=(x1,x2,…,xn)T表示某一方案，且决策变量取值非负；2都有一个要达到的目标，并且目标要求可以表示成决策变量的线性函数；3都有一组约束条件，这些约束条件可以用决策变量的线性等式或线性不等式来表示。这样的数学模型称线性规划模型。一般形式约束条件目标函数运筹学线性规划(4-1)Opt.=Optimize(使最优化)表示min或max其中运筹学线性规划规范形式运筹学线性规划标准形式(4-2）(4-3)当p=0，q=n时，模

5、型(4-1)为：当p=m，q=n时，模型(4-1)为：解的概念运筹学线性规划运筹学线性规划非标准形式标准化方法：线性规划标准模型的一般表达式：非标准形式标准化或规范化的方法：1.目标函数转换3.约束条件为不等式:引进松驰变量xs:引进剩余变量xs:5.决策变量为自由变量:6.约束等式化不等式:两端乘-1:≥04.约束条件为不等式:2.约束右端项为负:例4.4把下列线性规划问题转化为标准形式利用上述转换一般LP模型可化为规范型：见基P10例4maxz=x1+3x2s.t.x1+x2≤6-x1+2x2≤8x1≥0,x2≥0可行域目标函数等值线最

6、优解64-860x1x2运筹学线性规划一、图解法对于只有两个变量的线性规划问题可以用图解法求解：§4.2线性规划的图解法例4.5用图解法求解例4.1产品门生产2件产品窗生产6件最大利润3600（元）B是直线交点解之得例4.6运筹学线性规划4.3线性规划解的基本性质运筹学线性规划一、四种结局:x1x2唯一最优解x2x1无穷多最优解x1x2无界解x2x1无可行解Ex1、化标准形2、用图解法求解基本假设运筹学线性规划二、可行域的几何结构凸集♂返回运筹学线性规划xy可行域的凸性运筹学线性规划问题♂返回运筹学线性规划三、基本可行解与基本定理运筹学线性

7、规划基本可行解定义：运筹学线性规划♂返回运筹学线性规划运筹学线性规划运筹学线性规划基本定理运筹学线性规划运筹学线性规划§4.4单纯形法一、单纯形方法的原理和步骤运筹学线性规划运筹学线性规划线性规划运筹学找出一个初始可行解是否最优转移到另一个目标函数（找更大的基本可行解）最优解是否循环结束线性规划运筹学线性规划运筹学二、表格单纯形法用一种类似矩阵的表格操作来示单纯形方法，这种表称为单纯形表.1、初始单纯形表的建立(1)表格结构：（2）表格设计依据：将-Z看作不参与基变换的基变量，把目标函数表达式改写成方程的形式，和原有的m个约束方程组成一个具

8、有n+m+1个变量、m+1个方程的方程组：运筹学线性规划2、用单纯形表计算，作新单纯形表例1.8求解线性规划见基P33和38例1例2σ≦0,已是最优单纯形表x1=6/5,x2=0