《第1章线性规划与单纯形法电子教案》由会员分享，可在线阅读，更多相关《第1章线性规划与单纯形法电子教案（243页珍藏版）》请在金锄头文库上搜索。
1、,（本科版） 运筹学 运筹学教材编写组 编 清华大学出版社,第1章 线性规划与单纯形法 第2章 对偶理论与灵敏度分析 第3章 运输问题 第4章 目标规划,二. 线性规划与目标规划,第1章 线性规划与单纯形法,第1节 线性规划问题及其数学模型 第2节 线性规划问题的几何意义 第3节 单纯形法 第4节 单纯形法的计算步骤 第5节 单纯形法的进一步讨论 第6节 应用举例,第1节 线性规划问题及其数学模型,线性规划是运筹学的一个重要分支。线性规划在理论上比较成熟，在实用中的应用日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。从解决技
2、术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。它已是现代科学管理的重要手段之一。解线性规划问题的方法有多种，以下仅介绍单纯形法 。 1.1 问题的提出 从一个简化的生产计划安排问题开始,例 1,某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示。,续例1,该工厂 每生产一件产品可获利2元， 每生产一件产品可获利3元， 问应如何安排计划使该工厂获利最多?,如何用数学关系式描述这问题，必须考虑,数学模型,例2. 简化的环境保护问题 靠近某河流有两个化工厂(见图1-1)，流经第一化工厂的河流流
3、量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流。,图1-1,续例2,第一 化工厂每天排放含有某种有害物质的工业污水2万立方米，第二化工厂每天排放这种工业污水1.4万立方米。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可自然净化。根据环保要求，河流中工业污水的含量应不大于0.2%。这两个工厂都需各自处理一部分工业污水。第一化工厂处理工业污水的成本是1000元/万立方米。 第二 化工厂处理工业污水的成本是800元/万立方米。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。,建模型之前的分析和计算,设： 第一化工厂
4、每天处理工业污水量为x1万立方米， 第二化工厂每天处理工业污水量为x2万立方米,数学模型,补充例1. 生产计划问题 某厂生产甲乙两种产品，各自的零部件分别在A、B车间生产，最后都需在C车间装配，相关数据如表所示： 问如何安排甲、乙两产品的产量，使利润为最大。,(1)决策变量。要决策的问题是甲、乙两种产品的产量，因此有两个决策变量：设x1为甲产品产量，x2为乙产品产量。 (2)约束条件。生产这两种产品受到现有生产能力的制约，用量不能突破。 生产单位甲产品的零部件需耗用A车间的生产能力1工时， 生产单位乙产品不需耗用A车间的生产能力， A车间的能力总量为8工时，则A车间能力约束条件表述为 x1 8
5、 同理，B和C车间能力约束条件为 2x2 12 3x1 +4 x2 36,建立模型,(3)目标函数。目标是利润最大化，用Z表示利润，则 maxZ= 3x1 +5 x2 (4)非负约束。甲乙产品的产量不应是负数，否则没有实际意义，这个要求表述为 x1 0， x2 0,共同的特征,每一个线性规划问题都用一组决策变量 表示某一方案，这组决策变量的值就代表一个具体方案。一般这些变量取值是非负且连续的； (2)要有各种资源和使用有关资源的技术数据 ，创造新价值的数据；,共同的特征（继续）,(3) 存在可以量化的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示; (4) 要有一个达到目标的要求，
6、它可用决策变量的线性函数(称为目标函数)来表示。按问题的不同，要求目标函数实现最大化或最小化。,它们的对应关系可用表格表示：,用一组非负决策变量表示一个决策问题， 存在一定的等式或不等式的线性约束条件， 有一个希望达到的目标，可表示成决策变量的线性函数。可能是最大化，也可能是最小化。,线性规划的一般形式,线性规划的一般模型形式,1.2 图解法,一个二维的线性规划问题，可以在平面图上求解，三维的线性规划则要在立体图上求解，这就比较麻烦，而维数再高以后就不能图示了。 例1是二维空间（平面）线性规划问题，可用作图法直观地来表述它的求解。 因存在 必须在直角坐标的第1象限内作图，求解。,图1-2,图1
7、-3 目标值在（4，2）点，达到最大值14,目标函数,可能出现的几种情况,（1）无穷多最优解(多重最优解)，见图1-4 （2）无界解，见图1-5-1 （3）无可行解，见图1-5-2,图1-4 无穷多最优解(多重最优解),目标函数 max z=2x1+4x2,图1-5-1 无界解,无可行解,当存在矛盾的约束条件时，为无可行域。,如果在例1的数学模型中增加一个约束条件:,该问题的可行域为空集，即无可行解，,图1-5-2 不存在可行域,增加的约束条件,线性规划的图解法补充,1. 可行域的确定,五边形OABCD内(含边界)的任意一点 (x1，x2) 都是满足所有约束条件的一个解，称之可行解 。,满足所
8、有约束条件的解的集合，称之为可行域。即所有约束条件共同围城的区域。,2. 最优解的确定,目标函数 Z= 3x1 +5 x2 代表以Z为参数的一族平行线。,等值线：位于同一直线上的点的目标函数值相同。 最优解：可行解中使目标函数最优(极大或极小)的解,三 、解的可能性,唯一最优解：只有一个最优点。 多重最优解：无穷多个最优解。若在两个顶点同时得到最优解，则它们连线上的每一点都是最优解。,由线性不等式组成的可行域是凸集(凸集的定义是：集合内部任意两点连线上的点都属于这个集合)。 可行域有有限个顶点。设规划问题有n个变量，m个约束，则顶点的个数不多于Cnm个。 目标函数最优值一定在可行域的边界达到，
9、而不可能在其内部。,二、几点说明,无界解：线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏必要的约束条件）,三 、解的可能性（续）,无可行解：若约束条件相互矛盾，则可行域为空集,三 、解的可能性（续）,线性规划问题的数学模型有各种不同的形式，如 目标函数有极大化和极小化； 约束条件有“”、“”和“”三种情况； 决策变量一般有非负性要求，有的则没有。 为了求解方便，特规定一种线性规划的标准形式，非标准型可以转化为标准型。标准形式为： 目标函数极大化， 约束条件为等式， 右端常数项bi0， 决策变量非负。,一 、标准型,1.3 线性规划问题的标准型式,1. 代数式,二、标准型的表达方式
10、有代数式、矩阵式：,简记,2. 矩阵式,目标函数极小化问题 minZ=CTX，只需将等式两端乘以 -1 即变为极大化问题。因为minZ=-max (-Z)=CTX，令Z= -Z，则maxZ=-CX 右端常数项非正 两端同乘以 -1 约束条件为不等式 当约束方程为“”时，左端加入一个非负的松弛变量，就把不等式变成了等式； 当约束条件为“”时，不等式左端减去一个非负的剩余变量(也可称松弛变量)即可。 决策变量xk没有非负性要求 令xk=xk-x k， xk=xk，x k 0，用xk、x k 取代模型中xk,非标准型向标准型转化,例3 将例1的数学模型化为标准型。 例1的数学模型,加松驰变量后,(3
11、) 若存在取值无约束的变量xk,可令,其中。,例4 将下述线性规划问题化为标准型,处理的步骤：,(1) 用x4-x5替换x3，其中x4，x50； (2) 在第一个约束不等式号的左端加入松弛变量x6； (3) 在第二个约束不等式号的左端减去剩余变量x7； (4) 令z= -z，把求min z 改为求max z，即可得到该问题的标准型,例4的标准型,标准型,x1 +x3 =8 2x2 +x4 = 12 3x1 +4 x2 +x5= 36 x1, x2 , x3 , x4 , x5 0,maxZ= 3x1 +5 x2 +0 x3 +0 x4+0 x5,minZ= x1 +2 x2 +3 x3 x1
12、+2 x2 + x35 2x1 +3 x2 + x36 -x1 - x2 - x3 -2 x1 0, x30,标准化2 minZ= x1 +2 (x2-x 2) +3 x3 x1 +2 (x2-x 2) + x35 2x1 +3 (x2-x 2) + x36 - x1 - (x2-x 2) - x3 -2 x1, x2,x 2 , x3 0 标准化3 minZ= x1 +2 (x2-x 2 ) +3 x3 x1 +2 (x2-x 2 ) + x35 2x1 +3 (x2-x 2 ) + x36 x1 + (x2-x 2 ) + x3 2 x1, x2, x 2, x3 0,标准化4 minZ=
13、 x1 +2 (x2-x 2) +3 x3 x1 +2 (x2-x 2) + x3+ x4 =5 2x1 +3 (x2-x 2) + x36 x1 + (x2-x 2 ) + x3 2 x1, x2, x 2, x3, x4 0 标准化5 minZ= x1 +2 (x2-x 2) +3 x3 x1 +2 (x2-x 2) + x3+ x4 =5 2x1 +3 (x2-x 2) + x3 - x5 = 6 x1 + (x2-x 2 ) + x3 2 x1, x2, x 2, x3, x4 , x5 0,标准化6 minZ= x1 +2 (x2-x 2) +3 x3 x1 +2 (x2-x 2)
14、+ x3+ x4 =5 2x1 +3 (x2-x 2) + x3 - x5 = 6 x1 + (x2-x 2 ) - x3 + x6= 2 x1, x2, x 2, x3, x4 , x5 , x6 0 标准化7 maxZ= -x1 -2 (x2-x 2) - 3x3+0 x4+0 x5+0 x6 x1 +2 (x2-x 2) + x3+ x4 =5 2x1 +3 (x2-x 2) + x3 - x5 = 6 x1 + (x2-x 2 ) - x3 + x6 = 2 x1, x2, x 2, x3, x4 , x5 , x6 0,1.4 线性规划问题的解的概念,1.可行解 2.基 3.基可行解
15、 4.可行基,可行解： 满足约束条件AX=b, X0的解。 所有可行解的集合称为可行域。 最优解： 使目标函数最优的可行解，称为最优解。 基 mn，且m个方程线性无关，即矩阵A的秩为m；根据线性代数定理可知，nm，则方程组有多个解，这也正是线性规划寻求最优解的余地所在。,一、线性规划解的概念,基变量： 与基向量Pj相对应的m个变量xj称为基变量， 其余的m-n个变量为非基变量。 基解： 令所有非基变量等于零，对m个基变量所求的解， 对应一个特定的基矩阵能求得一组唯一解，这个对应于基的解称为基解。 结合图解来看，基解是各约束方程及坐标轴之间交点的坐标。 满足约束条件的基解称为基可行解。基可行解对应可行域的顶点。,线性方程组的增广矩阵,LP标准型 maxZ= 3x1 +5 x2 +0 x3 +0 x4+0 x5 x1 +x3 =8 2x2 +x4 = 12 3x1 +4 x2 +x5= 36 x1, x2 , x3 , x4 , x5 0,单位矩阵,基
