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

运筹学 主讲：贾晓霞 Tel学习资料 秦裕瑗 秦明复. 运筹学简明教程. 高等教育出版社,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为 这两种产品每天总的利润。可得数学模型简记为: 1.2 线性规划的一般模型 （1）可用一些变量表示这类问题的待定方案，这些变量的一组定值就代表一个具体方案。因此可将这些变量称为决策变量，并要求它们为非负。（2）存在一定的约束条件，这些约束条件都能用关于决策变量的线性不等式或等式来表示。（3）有一个期望达到的目标，这些目标能以某种确定的数量指标刻画出来，而这种数量指标可表示为关于决策变量的线性函数，按所考虑问题的不同，要求该函数值最大化或最小化。这类问题就是线性规划问题。一般LP模型可表示如下：其中opt是英文optimize(最优化)的缩写。按问题要求不同，可表示为max或min。 第二节 关于解的几种可能结果 线性规划问题的解可能出现以下几种情况 唯一解 有且仅有一个既在可行域内，又使目标值达到最优的解。 无穷解 有无穷多个既在可行域内、又使目标值达到最优的解。 无可行解 约束条件不能同时满足，将出现无可行域的情况。 有可行解但无最优解(无界解) 是指最大化问题中目标函数值可以无限增大，或最小化问题中目标函数值可以无限减小 第三节 非标准形LP问题的标准化 1、目标函数。如LP问题的目标函数是：  可以将原目标函数化为 2、函数约束。 (1) 的情形。 (2) 约束为 形式的情形。 (3) 约束为 形式的情形。  3、决策变量 1） 小于零时 2） 自由变量时 非标准形LP问题的标准化  例题 将如下LP问题化成标准形： Answer: 第四节 线性规划的解及其性质 4.1 线性规划的解的概念1 可行解。 满足LP问题所有的约束条件的向量X称为可行解，所有可行解构成的集合称为可行域，记为R。 2 最优解。 满足目标要求的可行解称为最优解，记为 ；它所对应的目标函数值称为最优值，记为 。有时把 统称为最优解，简称为解。 第四节 线性规划的解及其性质 3 基本解。其概念只适用于标准形LP问题。 就范例的标准形进行研讨： 其增广阵为： 4 基本可行解。 满足非负性约束(1-6)的基本解，称为标准形LP问题(M)的基本可行解。若基本可行解中有一个或更多个基变量为0，则称为退化基本可行解。    表 标准形LP问题解的概念与关系  * * 5 3 利润（元/件） 36 4 3 C 12 2 0 B 8 0 1 A 生产能力 （工时/天） 乙 （工时/件） 甲 （工时/件） 车间 其中max是英文maximize(最大化)的缩写；s.t.是subject to(受约束于)的缩写。 (1-1)式称为最优化目标函数，其中 称为目标函数，opt称为其优化，也可称为目标要求；(1-2)式称为函数约束；(1-3)式中的 称为非负性约束； 称为非正性约束；(1-2)、(1-3)式统称为约束条件，简称约束。 称为决策变量。 称为LP模型的参数。 其系数阵A中有一个三阶子阵为单位阵，其行列式不为0，故r(A)=r( )=r=3=m,方程组相容。又因r=3＜5=n,故方程组有无穷多解。取A中单位阵对应的变量x3,x4,x5为基本变量，则x1,x2为自由变量，