线性规划的概念.ppt

《线性规划的概念.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、线性规划内容框架第一章、线性规划1.1线性规划的概念一、线性规划问题的导出1．(引例)配比问题——用浓度为45%和92%的硫酸配置100t浓度为80%的硫酸。取45%和92%的硫酸分别为x1和x2t,则有：求解二元一次方程组得解。目的相同，但有5种不同浓度的硫酸可选（30%，45%，73%，85%，92%）会出现什麽情况？取这5种硫酸分别为x1、x2、x3、x4、x5t,则有：有多少种配比方案？为什麽？何为最好？5种硫酸价格分别为：400，700，1400，1900，2500元/t，则有：2.生产计划问题：生产单位产品产品所需资源资源ABC每天可利用资源量工时（单位）1113材料

2、（t）1479产品利润（元/t）200030001000如何制定生产计划，使三种产品总利润最大？问题讨论何为生产计划？总利润如何描述？还要考虑什麽因素？有什麽需要注意的地方（技巧）？最终得到的数学模型是什麽？二、线性规划的定义和数学描述（模型）1．定义：对于求取一组变量xj(j=1,2,......,n)，使之既满足线性约束条件，又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题，简称线性规划。2.配比问题和生产计划问题的线性规划模型的特点：用一组未知变量表示要求的方案，这组未知变量称为决策变量；存在一定的限制条件，且为线性表达式；有一个目标要求

3、（最大化，当然也可以是最小化），目标表示为未知变量的线性表达式，称之为目标函数；对决策变量有非负要求。3．LP的数学描述(数学模型)：（1）一般形式（2）紧缩形式（3）矩阵形式其中:（4）向量—矩阵形式：其中：（1）P39习题1（一）1.（1）加深理解线性规划的定义（2）复习线性规划定义及数学描述以《生产计划问题》为例，写出线性规划的4种模型课堂练习1-1三、LP的标准型：1、LP标准型的概念（1）什麽是LP的标准型？（2）LP标准型的特点目标函数约定是极大化Max(或极小化Min);约束条件均用等式表示;决策变量限于取非负值;右端常数均为非负值;（3）数学表达式:有几种形式

4、?为什麽?如何书写?2、LP问题的标准化（1）目标函数的标准化MinZ=CXMaxZ’=-CXZ’=-Z目标函数标准化示意图***********************（2）约束条件的标准化&约束条件是≤类型——左边加非负松弛变量,变为等式；&约束条件是≥类型——左边减非负剩余变量,变为等式；&变量符号不限——引入新变量将下面的线性规划问题化为标准型：讨论：如何下手？标准化过程排序-------课堂练习1-2①x3；②约束1引松弛变量；约束2引剩余变量；约束3变号；③目标函数标准化，引入变换Z’=-Z；④整理；提问、答疑、讨论总结，看最终结果令