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

第四章线性规划本章内容?线性规划问题及其数学模型?线性规划的图解法?线性规划解的基本性质?单纯形算法?初始基本可行解求法?对偶性及对偶单纯形方法?线性规划灵敏度分析?线性规划的建模实例?用数学软件求解线性规划模型介绍运筹学线性规划线性规划研究的主要问题一类是已有一定数量的资源(人力、物质、时间等), 研究如何充分合理地使用它们,才能使完成的任务量为最大。另一类是当一项任务确定以后,研究如何统筹安排,才能使完成任务所耗费的资源量为最少。——实际上,上述两类问题是一个问题的两个不同的方面, 都是求问题的最优解( max 或 min )。线性规划( Linear Programming) 创始人: 1947 年美国人 . 丹齐克( Dantzing ) 1951 年提出单纯形算法( Simpler method ) 线性规划运筹学一、线性规划问题的提出例 生产计划问题(资源分配问题):某工厂生产门窗两种产品,已知的条件如表所示,试制订总利润最大的生产计划。§ 线性规划问题及数学模型问题分析运筹学线性规划模型运筹学线性规划用 Excel 软件求解: 产品门生产 2件产品窗生产 6件最大利润 3600 (元) 例 投资问题: 某公司有 100 万元资金要投资(要求全部用完)。该公司有六个投资项目可选,已知的条件如表所示,该公司希望投资风险最小,每年红利至少为 万,最低平均增长率为 12% ,最低平均信用度为 7。试解该问题。运筹学线性规划问题分析运筹学线性规划????????????????????????????????????????6,,2,1,0 700 6410 210 4 12 08 .015 .008 .012 .007 .022 .0 .006 .007 .009 .005 .004 .0 100 .. 08 .012 .004 .010 .006 .018 .0 min 654321 654321 654321 654321 654321? ix xxxxxx xxxxxx xxxxxx xxxxxxts xxxxxxi模型用 Excel 软件求解: 项目 1投资 25万元项目 2投资 0万元项目 3投资 万元项目 4投资 万元项目 5投资 0万元项目 6投资 0万元平均总风险 % 例 运输问题: 运筹学线性规划 A1 A2 … A3 B 1c 11c 21…c m1B 2c 12c 22…c m2…………… B nc 1nc 2n…c mn 单位运价表(cij) A 1A 2…A 3销量 B 1x 11X 21…x m1b 1 B 2x 12X 22…x m2b 2 B 3…………… B 4x 1nX 2n…x mnb n 产量 a 1a 2…a m产销平衡表(决策变量 xij=0 或1)