运筹学01-线性规划基本性质及建模.ppt

运筹学,主讲：贾晓霞 Tel：50938017,学习资料,秦裕瑗 秦明复. 运筹学简明教程. 高等教育出版社,2006.12 韩大卫.管理运筹学.大连理工大学出版社,2006.6,第一章 线性规划基本性质及建模,线性规划主要用于研究解决有限资源的最佳分配问题，即如何对有限的资源做出最佳方式的调配和最有利的使用，以便最充分的发挥资源的效能去获取最佳经济效益。为叙述简便，以后我们把“线性规划”用LP代替 。,第一节 线性规划的一般模型,1.1产品结构优化问题 1、范例1 某厂拟生产甲乙两种适销产品，每件利润为3、5百元。甲乙产品的部件各自在A、B两个车间分别生产，每件甲乙产品的部件分别需要A、B车间的生产能力1、2工时；两种产品的部件最后都要在C车间装配，装配每件甲乙产品分别需要3、4工时,A、B、C三个车间每天可用于生产这两这种产品的工时分别为8、12、36，应如何安排生产才能获利最多？,列出数据表,解：这是一个典型的产品结构优化问题，现在建立这个问题的数学模型。设 分别为甲、乙产品的日产量，z为 这两种产品每天总的利润。可得数学模型简记为:,其中max是英文maximize(最大化)的缩写；s.t.是subject to(受约束于)的缩写。,1.2 线性规划的一般模型,（1）可用一些变量表示这类问题的待定方案，这些变量的一组定值就代表一个具体方案。因此可将这些变量称为决策变量，并要求它们为非负。 （2）存在一定的约束条件，这些约束条件都能用关于决策变量的线性不等式或等式来表示。 （3）有一个期望达到的目标，这些目标能以某种确定的数量指标刻画出来，而这种数量指标可表示为关于决策变量的线性函数，按所考虑问题的不同，要求该函数值最大化或最小化。这类问题就是线性规划问题。一般LP模型可表示如下： 其中opt是英文optimize(最优化)的缩写。按问题要求不同，可表示为max或min。,(1-1)式称为最优化目标函数，其中 称为目标函数，opt称为其优化，也可称为目标要求；(1-2)式称为函数约束；(1-3)式中的 称为非负性约束； 称为非正性约束；(1-2)、(1-3)式统称为约束条件，简称约束。 称为决策变量。 称为LP模型的参数。,第二节 关于解的几种可能结果,线性规划问题的解可能出现以下几种情况 唯一解 有且仅有一个既在可行域内，又使目标值达到最优的解。 无穷解 有无穷多个既在可行域内、又使目标值达到最优的解。 无可行解 约束条件不能同时满足，将出现无可行域的情况。 有可行解但无最优解(无界解) 是指最大化问题中目标函数值可以无限增大，或最小化问题中目标函数值可以无限减小,第三节 非标准形LP问题的标准化,1、目标函数。如LP问题的目标函数是： 可以将原目标函数化为 2、函数约束。 (1) 的情形。 (2) 约束为 形式的情形。 (3) 约束为 形式的情形。 3、决策变量 1） 小于零时 2） 自由变量时,非标准形LP问题的标准化,例题 将如下LP问题化成标准形：,Answer:,第四节 线性规划的解及其性质,4.1 线性规划的解的概念 1 可行解。 满足LP问题所有的约束条件的向量X称为可行解，所有可行解构成的集合称为可行域，记为R。 2 最优解。 满足目标要求的可行解称为最优解，记为 ；它所对应的目标函数值称为最优值，记为 。有时把 统称为最优解，简称为解。,第四节 线性规划的解及其性质,3 基本解。其概念只适用于标准形LP问题。 就范例的标准形进行研讨：,其增广阵为：,其系数阵A中有一个三阶子阵为单位阵，其行列式不为0，故r(A)=r( )=r=3=m,方程组相容。又因r=35=n,故方程 组有无穷多解。 取A中单位阵对应的变量x3,x4,x5为基本变量，则x1,x2为自由变量，令x1= c1, x2=c2 ,容易得到一个通解：,当取C1=C2=0 时，可得方程组一个特解： X0=（0，0，8，12，36）T 称之为方程组的一个基本解。其中x3,x4,x5为基本变量，则x1,x2为不再自由，改称非基本变量。 由此可见，基本解是由r 个基本变量与n-r个非基本变量构成的。由于总是规定标准形LP问题的系数阵A满秩，即r(A)=m n,因此可以说，基本解是由m个基本变量与n-m 个非基本变量构成的，其中基本变量对应的系数列向量构成一个m阶非奇异方阵。基本变量一般不为0，而非基本变量都须为0。,现在考虑一般LP问题的标准形。设B是由方程组(1-5)的m个线性无关的系数列向量构成的m阶方阵( )，则称B为LP问题的一个基矩阵(简称基)。 为叙述简便，不妨设,这个解的非零分量的数目不大于阶数m，称之为约束方程组(1-5)的一个关于基B的基本解，简称基本解。也称之为标准形LP问题的一个基本解。若基本解中有一个或更多个基变量，,则