线性规划概念与数学模型.ppt

《线性规划概念与数学模型.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章、线性规划1、线性规划问题及其数学模型2、线性规划的几何意义3、线性规划的求解－－单纯形法一、线性规划问题：生产计划问题（例1）甲乙设备128台时原材料A4016千克原材料B0412千克甲、乙产品每件获利分别为2、3元，如何安排获利最多？第一节、线性规划问题及其数学模型如何制定生产计划，使两种产品总利润最大？问题讨论何为生产计划？总利润如何描述？还要考虑什么因素？有什么需要注意的地方（技巧）？最终得到的数学模型是什么？二、线性规划的定义和数学描述（模型）1．定义：对于求取一组变量xj(j=1,2,..

2、....,n)，使之既满足线性约束条件，又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题，简称线性规划。2.线性规划模型的特点：用一组未知变量表示要求的方案，这组未知变量称为决策变量；存在一定的限制条件，且为线性表达式；有一个目标要求（最大化，当然也可以是最小化），目标表示为未知变量的线性表达式，称之为目标函数；对决策变量有非负要求。三．LP的数学描述(数学模型)：一般形式二、线性规划的图解法－－－解的几何表示1．什么是图解法？线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程

3、。求解的思路是：先将约束条件加以图解，求得满足所有约束条件的解的集合（即可行域），然后结合目标函数的要求从可行域中找出最优解。可行解：满足所有约束条件的解图解法举例实施图解法，以求出最优生产计划（最优解）例1maxZ=2x1+3x2s.t.工时原材料由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就可进行图解.第一步：建立平面直角坐标系，标出坐标原点,坐标轴的指向和单位长度。用x1轴表示产品甲的产量，用x2轴表示产品乙的产量。第二步：对约束条件加以图解。第三步：画出目标函数等值线，结合目标函数的要求求出

4、最优解－－最优生产方案。约束条件的图解:每一个约束不等式在平面直角坐标系中都代表一个半平面，只要先画出该半平面的边界，然后确定是哪个半平面。?以第一个约束条件（工时）x1+2x28为例说明约束条件的图解过程。怎么画边界怎么确定半平面如果全部的劳动工时都用来生产甲产品而不生产乙产品，那么甲产品的最大可能产量为8吨，计算过程为：x1+2×08x18这个结果对应着下图中的点B(8,0),同样我们可以找到B产品最大可能生产量对应的点A(0,4)。连接A、B两点得到约束x1+2x28所代表的半平面的边界:x1+2x2

5、＝8，即直线AB。12345678912345x1+2x2=8ABAB三个约束条件及非负条件x1,x20所代表的公共部分－－图中阴影区，就是满足所有约束条件和非负条件的点的集合，即可行域。在这个区域中的每一个点都对应着一个可行的生产方案。第二、三个约束条件的边界－－直线CD，EF:4x1=16,4x2=1212345678912345EF4x2=124x1=16ABCDx1+4x2=8令Z=2x1+3x2=c,其中c为任选的一个常数，在图中画出直线2x1+3x2=c,这条直线上的点即对应着一个可行的生产方案，即使

6、两种产品的总利润达到c。这样的直线有无数条，而且相互平行，称这样的直线为目标函数等值线。只要画出两条目标函数等值线，比如令c＝0和c=6，就能看出目标函数值递增的方向，用箭头标出这个方向。图中两条虚线l1和l2就分别代表目标函数等值线2x1+3x2=0和2x1+3x2=6,箭头表示使两种产品的总利润递增的方向。12345678912345x1+2x2=8ABDC4x1=16l1l2l3FEBA4x1=12沿着箭头的方向平移目标函数等值线，使其达到可行域中的最远点Q2,Q2点就是要求的最优点，它对应的相应坐标x1=4,

7、x2=2就是最有利的产品组合，即生产甲产品4件，乙产品2件能使两种产品的总利润达到最大值Zmax=24+32=14(元)，x1=4,x2=2就是线性规划模型的最优解，Zmax=14就是相应的目标函数最优值尽管最优点的对应坐标可以直接从图中给出，但是在大多数情况下，对实际问题精确地看出一个解答是比较困难的。所以，通常总是用解联立方程的方法求出最优解的精确值。比如Q2点对应的坐标值我们可以通过求解下面的联立方程，即求直线AB和CD的交点来求得。直线AB:x1+2x2=8直线CD:4x1=160123456789x15

8、4321x2（8，0）C=6（0，4）C=0s.t.Q2（4，2）一般线性规划解的几种不同情形：无穷多最优解（多重最优解）无界解无可行解0123456789x154321x2-2-14x1=124x1=16x1+2x2=8-2x1+x2=4二、线性规划的标准型1、LP标准型的概念（1）什么是LP的标准型？——标准格式！（2）LP标准型的特点目