线性规划及其求解研讨.ppt

第1页线性规划方法线性规划方法第2页?线性规划,是数学规划中发展较快、应用较广和比较成熟的一个分支。早在 20世纪 30年代末,就有人从运输问题开始研究应用线性规划的方法。自 1947 年丹泽( )提出求解线性规划问题的一般方法--单纯形法之后,线性规划在理论上趋于成熟,应用日益广泛与深入。随着电子计算机的发展和计算速度的不断提高, 其适用的领域更加广泛,它已成为必不可少的重要手段之一。本章将结合有关实例,介绍和讨论线性规划方法在地理研究中的应用问题第3页?线性规划在实际应用中日益广泛与深入,已经被广泛地应用到工业、农业、商业与交通运输规划,工程技术的优化设计,以及企业管理等各个领域。?在地理学领域,线性规划,作为传统的计量地理学方法之一,是解决有关规划、决策和系统优化问题的重要手段。第4页线线性性规规划划问问题题?线性规划实例生产计划问题运输问题?线性规划模型一般形式规范形式标准形式形式转换概念第5页某工厂用三种原料生产三种产品,已知的条件如表某工厂用三种原料生产三种产品,已知的条件如表 所示,试制订总利润最大的生产计划所示,试制订总利润最大的生产计划单位产品所需原料数量(公斤) 产品 Q1 产品 Q2 产品 Q3 原料可用量(公斤/日) 原料 P12301500 原料 P2024800 原料 P33252000 单位产品的利润(千元) 354 生产计划问题第6页问问题题分分析析可控因素: 每天生产三种产品的数量,分别设为 321,,xxx 目标: 每天的生产利润最大利润函数 321453xxx??受制条件: 每天原料的需求量不超过可用量: 原料1P :1500 32 21??xx 原料2P :800 42 32??xx 原料3P :2000 523 321???xxx 蕴含约束: 产量为非负数 0,, 321?xxx 第7页模模型型 321453 max xxx??1500 32 21??xx 42 32??xx2000 523 321???xxx0,, 321?xxx第8页计计算算结结果果 OBJECTIVE FUNCTION VALUE VARIABLE VALUE REDUCED COST X1 X2 X3 ROW SLACK OR SUR PLUS DUAL PRICES 1) 2) 3) 2,1;?iA i 发送到零售点 4,3,2,1;?jB j ,仓库 iA 能供应的产品数量为 2,1;?ia i ,零售点 jB 所需的产品的数量为4,3,2,1;?jb j 。假设供给总量和需求总量相等,且已知从仓库 iA 运一个单位产品往 jB 的运价为 ijc 。问应如何组织运输才能使总运费最iA 小? 第10页问问题题分分析析可控因素:从仓库 iA 运往jB 的产品数量设为4,3,2,1,2,1;??jix ij 目标:总运费最小费用函数???? 21 41ij ij ijxc 受控条件: 从仓库运出总量不超过可用总量,运入零售点的数量不低于需求量。由于总供给量等于总需求量,所以都是等号。即 2,1; 4321?????iaxxxx iiiii4,3,2,1; 21???jbxx jjj 蕴含约束:数量非负4,3,2,1,2,1;0???jix ij