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

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