《运筹学第一章线性规划》由会员分享，可在线阅读，更多相关《运筹学第一章线性规划（87页珍藏版）》请在金锄头文库上搜索。
1、1,运筹学,管理科学与工程系 关叶青 ,2,授课教材：党耀国等,运筹学,科学出版社绪论第一章 线性规划的数学模型与单纯形法第二章 线性规划的对偶理论与灵敏度分析第三章 运输问题第四章 整数规划第五章 动态规划第六章 图论与网络计划第七章 存储论第八章 决策分析,3,绪 论,运筹学释义与发展简史 operational research, operations research, 简写O.R.运筹学研究的基本特征 系统的整体性，多学科的综合性，模型方法的应用性运筹学在工商管理中的应用运筹学的主要分支 目录,4,O.R.在工商管理中的应用,生产计划：生产作业的计划、日程表的编排、合理下料、配料问题
2、、物料管理等。 库存管理：多种物资库存量的管理，库存方式、库存量等。 运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等。,5,人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等。 市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等。,O.R.在工商管理中的应用,6,财务和会计：包括预测、贷款、成本分析、定价、证券管理、现金管理等。 其他： 设备维修、更新，项目选择、评价，工程优化设计与管理等。,O.R.在工商管理中的应用,7,一、线性规划问题的数学模型主要解决以下两类问题：1、任务确定后，如何统筹安排，做到应用尽量少的人
3、力和物力资源来完成任务；2、在一定量的人力、物力资源的条件下，如何安排、使用他们，使完成的任务最多。,第1章 线性规划的数学模型与单纯形法 1.1 线性规划问题及其数学模型,8,解:设 计划期内生产产品I、II的数量x1、x2 则该问题的数学模型为：,max S= 2x1 +3x2,例1.1：（计划安排问题）,9,例1.2 (成本问题),某炼油厂根据每季度需供应给合同单位汽油15万吨、煤油12万吨、重油12万吨。该厂计划从A，B两处运回原油提炼，已知两处的原油成分含量见表12；又已知从A处采购的原油价格为每吨（包括运费）200元，B处采购的原油价格为每吨（包括运费）290元, 问：该炼油厂该如
4、何从A，B两处采购原油，在满足供应合同的条件下，使购买成本最小。,10,线性规划模型特点:,决策变量：向量(x1 xn)T , xi非负约束条件：线性等式或不等式目标函数：Z=(x1 xn) 线性式， 求Z极大或极小,满足以上三个条件的数学模型称为 -线性规划数学模型,11,（资源利用问题）,某食品厂主要生产I型饼干和I I型饼干。根据销售部门提供的信息可知，目前这两种饼干在市场上都很畅销，该厂能生产多少，市场就能卖出多少。但从生产部门得知，有三种关键设备即搅拌机、成型机、烘箱的生产能力限制了该厂的饼干生产。因为两种饼干的生产都要共用这三种设备，所以每种饼干究竟应该生产多少才能充分利用现有设备
5、资源，这是一个值得认真研究的重要问题。,12,（货物调度问题）,某企业是一家新鲜柑橘产品的种植商和经营商，有I、II、II块大的柑橘林及甲乙丙三个柑橘加工厂（柑橘林到加工厂的距离公里信息如红色字体数据）。现该企业与一家地方货车运输公司联系，从柑橘林向加工厂运输柑橘。运输公司按照每蒲式耳柑橘运输每公里（记为蒲式耳-公里）的统一价格收费，该企业希望确定从各个柑橘林到各个加工厂运输多少蒲式耳，以使所运输的柑橘蒲式耳-公里的总数最小。,13,max(min) Z=c1x1+ c2x2+cnxn,C=(C1 C2 Cn ),一般形式：,14,二、线性规划问题的标准型,目标函数 max 变量 非负 约束条
6、件 等式 约束常数 非负,15,解：引进3个新非负变量x3，x4，x5使不等式变为等式，标准型为： max Z=2x1+3x2+0x3+0x4+0x5 3x2+x3=15 4x1+x4 =12 2x1+2x2+x5=14 x1，x2，x3，x4，x50,例1.3将例1.1的数学模型化为标准型。,max Z=2x1+3x2 3x2 15 4x1 12 2x1+2x2 14 x1，x20,16,解： 令x3 =x4 - x5, 添加松弛变量x6, 添加剩余变量x7, 令S= -S,maxS= x1 2x2 +3x4 3x5,例1.4,17,将 min S = x1+2x2 +3x3,化为标准型。,
7、练习：,18,max S=40x1+ 50x2,一、线性规划问题的图解法,解：(1) 确定可行域 x1 0 x1 =0 (横轴) x2 0 x2=0 (纵轴),x1+2x2 30 x1+2x2 =30 l1 (0,15) (30,0),3x1+2x2 =60 l2(0,30) (20,0),2x2 =24,1.2 线性规划问题的图解法及几何意义,19,(2) 求最优解“等值线法”,解：X* = (15 7.5) Smax =975,S=40x1+50x2 =x2 = 0.8x10.02 S,20,max Z = 2x1 +3x2,例1.5,解得：最优解B点（2，5）。 最优值 Z=22+35=
8、19,唯一最优解,21,用图解法求解线性规划问题 maxZ=40x1+ 80x2 s.t. x1+2x2 30 3x1+2x2 60 2x2 24 x1 , x2 0,例1.6,解：最优解：BC线段B点 X(1)= (6,12)；C点 X(2)= (15,7.5) X= X(1)+(1-) X(2) (0 1) maxZ=1200 整理得：x1 =15-9 x2 =7.5+4.5 (0 1),无穷多解,22,maxZ=2x1+ 4x2 s.t. 2x1+x2 8 -2 x1+ x2 2 x1，x2 0,例1.7,若目标函数由 min Z =2 x1 +4 x2 ,最优解 x1 = 4，x2 =
9、 0 ，即 (4,0)点,解：由于可行域无界 无有限最优解-无界解,23,无可行解,总结,例,24,通过以上各题图解法所得结论可以看出： （1）线性规划的所有可行解构成的可行域一般是凸多边形，有些可行域可能是无界的； （2）若存在最优解，则一定在可行域的某顶点得到； （3）若在两个顶点上同时得到最优解，则在这两点的连线上的任一点都是最优解。 （4）若可行域无界，则可能发生最优解无界的情况； （5）若可行域是空集，此时无最优解。 上述理论具有普遍意义，对于两个以上变量的线性规划问题都是成立。,25,二、线性规划问题的解的概念,1.2 线性规划问题的图解法及几何意义,26,(m n) r(A)=m
10、 , 至少有一个m 阶子式不为0不失一般性,不妨假设P1 Pm线性无关,基阵A中一个子矩阵B是可逆矩 阵， 则方阵B称为LP问题的一个基阵。,Pm+1 Pn,A= B N ,27,定义：基向量 非基向量,=(XB XN)T,有：AX=P1 x1+ P2 x2 + +Pn xn=b,定义：基变量 非基变量,BXB +NXN=bBXB =b-NXN,XB = B-1 b - B-1N XN,AX=b 求解过程：,A=(B N)X=(XB XN )T,目标函数：S=CX=CB B-1 b+(CN -CB B-1 N)XN,28,1. 可行解: 满足约束条件的解 X = ( x1, x2, , xn)
11、 称为线性规划问题的可行解；所有可行解的集合称为可行解集或可行域。 2. 最优解: 满足约束条件及目标函数的可行解称为线性规划问题的最优解。 最优值 3. 基阵: 假设 A 是约束方程组的系数矩阵，其秩数为 m ，B是矩阵 A 中由 m 列构成的非奇异子矩阵(B的行列式的值不为0)，则称 B 是线性规划问题的一个基。这就是说，矩阵 B 是由 m 个线性无关的列向量组成，不失一般性，可假设: 称 Pj ( j = 1,2,m )为基向量，与基向量 Pj 相对应的变量xj ( j = 1,2,m )称为基变量，否则称为非基变量。,T,若令非基变量 xm+1 = = xn = 0 ,用高斯消元法可求
12、出LP标准型的一个解 X = ( x1 x2 xm 0 0 )T 称 X 为基本解.,29,为了进一步讨论线性规划问题的解，下面研究约束方程组(1.7)的求解问题。假设该方程组系数矩阵 A 的秩为 m，因 m n，所以它有无穷多个解。假设前 m 个变量的系数列向量是线性无关的，这时(1.7)式可改写为： 方程组(1.9)的一个基是B=(P1, P2, ,Pm), Pj=(a1j, ,amj), (j = 1,2, , m )，设 XB 是对应于这个基的基变量，即： XB = ( x1, x2, , xm ) 现若令(1.9)式中的非基变量xm+1= =xn=0，并用高斯消去法求出一个解X=(x
13、1,x2, ,xm,0, , 0 ) ，这个解的非0分量的数目不大于方程的个数m，这时称X为基本解。,T,T,T,30,4. 基本可行解 : 满足非负条件(1.8)的基本解称为基本可行解。由此可见，基本可行解的非0分量的数目不大于m，并且都是非负的。 5. 可行基阵: 对应于基本可行解的基称为可行基。由此可见，满足约束方程组(1.7)的基本解的数目至多是 Cnm 个。一般地讲，基本可行解的数目要小于基本解的数目，至多相等。 以上提到的几种解的概念，可用图14来表示：,31,1. 凸集：假设K是n维欧氏空间的一个点集，若对于K中的任意两点X1、X2，其连线上的所有点X1+(1-)X2，( 0 1
14、)都在集合K中，即：X1+(1-)X2 K ( 0 1) 则称K为凸集。从直观上讲，凸集无凹入部分，其内部没有洞。如实心圆、实心球、实心立方体等都是凸集。两个凸集的交集仍是凸集。 2. 凸组合：设X1，X2，Xk是n维欧氏空间En中的k个点，若存在1，2，k，且0 i 1，i = 1,2, , k， i = 1，使X = 1X1 + 2X2 + + kXk，则称X为由X1，X2，Xk所构成的凸组合。按照定义，凡是由x，y的凸组合表示的点都在x，y的连线上，而且反之亦然。 3. 顶点： 假设K是凸集，X K；X若不能用不同的两个点X1、X2 K的线性组合表示为： X = X1+(1-)X2 ， ( 0 1) 则称X为凸集K的一个顶点（或称为极点）。 顶点不位于凸集K中的任意不同两点的连线内。,
