运筹学第一章ppt课件.ppt

OR1,1,第一章 线性规划与单纯形法,重点与难点： 1、线性规划的概念和模型，线性规划问题的标准型，线性规划问题的标准化； 2、线性规划问题解的概念，图解法(解的几何表示)，基本可行解的几何意义，线性规划求解思路(单纯形法思想)； 3、单纯形法的一般描述，表格单纯形法，一般线性规划问题的处理，单纯形迭代过程中的注意事项； 4、线性规划建模，决策变量，约束不等式、等式，目标函数，变量的非负限制。,OR1,2,第一章 线性规划与单纯形法,1.1 LP(linear programming)的基本概念 LP是在有限资源的条件下，合理分配和利用资源，以期取得最佳的经济效益的优化方法。 LP有一组有待决策的变量，（决策变量） 一个线性的目标函数， 一组线性的约束条件。,OR1,3,1.1.1 LP的数学模型 例题1：生产计划问题,某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：问题：如何安排生产计划，使得获利最多？,OR1,4,例题1建模,步骤： 1、确定决策变量：设生产A产品x1kg,B产品x2kg 2、确定目标函数：maxZ=70X1+120X2 3、确定约束条件：人力约束 9X1+4X2360 设备约束 4X1+5X2 200 原材料约束3X1+10X2 300 非负性约束X10 X20 综上所述，该问题的数学模型表示为：,OR1,5,例题2：人员安排问题,医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计：,请问该医院至少需要多少名护士？,OR1,6,例题2建模,目标函数：min Z=x1+x2+x3+x4+x5+x6 约束条件： x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30 非负性约束：xj 0,j=1,2,6,OR1,7,例题3：运输问题,三个加工棉花的加工厂，并且有三个仓库供应棉花，各供应点到各工厂的单位运费以及各点的供应量与需求量分别如下表所示：问如何运输才能使总的运费最小？,OR1,8,例题3建模,设Xij为第i个仓库运到底j座工厂的运输量。 目标函数：总运费最省：minZ=2x11+x12+3x13+2x21+2x22+4x23+3x31+4x32+2x33 约束条件： 供给要求：x11+x12+x13 50需求要求：x11+x21+x31=40 x21+x22+x23 30 x12+x22+x32=15 x31+x32+x33 10 x13+x23+x33=35 非负要求： Xij 0,OR1,9,例题4：连续投资问题（书P42页）,某投资者有资金10万元，考虑在今后5年内给下列4个项目进行投资，已知： 项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115。 项目B：第三年初需投资，到第五年末能回收本利125。但规定投资额不超过4万元。 项目C：第二年初需要投资，到第五年末能回收本利140，但规定最大投资额不超过3万元。 项目D：5年内每年初可购买公债，于当年末归还，并加利息6。 问该投资者应如何安排他的资金，确定给这些项目每年的投资额，使到第五年末能拥有的资金本利总额为最大？,OR1,10,建模,解：记xiA,xiB,xiC,xiD(i=1,2,3,4,5)分别表示第i年年初给项目A,B,C,D的投资额，它们都是决策变量，为了便于书写数学模型，我们列表如下：,OR1,11,例题5：合理下料问题,将长8m的圆钢，截取成长2.5m的毛坯100根、长1.3m的毛坯200根，问应该怎样选择下料方式，才能既满足需要，又使总的用料最少? 各种搭配方案如下：,OR1,12,例题5建模,设Xj表示采用第j种方案下料的根数。 目标函数：minZ=x1+x2+x3+x4 约束条件：3x1+2x2+x3 100 2x2+4x3+6x4 200 xj 0且为整数 (j=1,2,3,4),OR1,13,课堂练习：营养配餐问题,养海狸鼠 饲料中营养要求：VA每天至少700克，VB每天至少30克，VC每天刚好200克。现有五种饲料，搭配使用，饲料成分如下表:,OR1,14,建 模,设抓取饲料I x1kg;饲料II x2kg;饲料III x3kg 目标函数：最省钱 minZ=2x1+7x2+4x3+9x4+5x5 约束条件：3x2+2x2+x3+6x4+18x5 700 营养要求： x1+0.5x2+0.2x3+2x4+0.5x5 30 0.5x1+x2+0.2x3+2x4+0.8x5 =200 用量要求： x1 50,x2 60,x3 50,x4 70,x5 40 非负性要求：x1 0,x2 0,x3 0,x4 0,x5 0,OR1,15,总 结,从以上5个例子可以看出，它们都属于优化问题，它们的共同特征： 1、每个问题都用一组决策变量表示某一方案；这组决策变量的值就代表一个具体方案，一般这些变量取值是非负的。 2、存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。 3、都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。 满足以上三个条件的数学模型称为线性规划的数学模型。,OR1,16,线性规划模型的一般模式,目标函数：max(min)Z=c1x1+c2x2+c3x3+cnxn 约束条件：a11x1+a12x2+a13x3+a1nxn (= )b1 a21x1+a22x2+a23x3+a2nxn (= )b2 am1x1+am2x2+am3x3+amnxn (= )bm 非负性约束：x1 0,x2 0,xn 0 .,OR1,17,线性规划的标准型,代数式maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm xj 0 j=1,2,n,OR1,18,线性规划的标准型,和式：maxZ=cjxj aijxj=bi i=1,2,m xj 0 j=1,2,n,j=1,n,n,j=1,OR1,19,线性规划的标准型,向量式：maxZ=CX pjxj=bi i=1,2,m xj 0 j=1,2,n C=(c1,c2,c3,cn) X=(X1,X2,X3,Xn) T,n,j=1,OR1,20,线性规划的标准型,矩阵式： maxZ=CX AX=b X 0 其中： b=(b1,b2,bm)T a11 a12 .a1n A= a21 a22 a2n am1 am2 amn,OR1,21,标准型的特征,目标函数极大化（也有的版本选择极小化） 约束条件为等式 决策变量非负,OR1,22,非标准型转化为标准型,目标函数极小化转为极大化： minZ=max(Z) ，一个数的极小化等价于其相反数的极大化。 不等式约束的转化： aijxjbi 加入松弛变量 aijxjbi 减去剩余变量 非正变量：即xk 0 则令xk = xk 自由变量：即xk无约束，令xk= xkx”k,OR1,23,非标准型转化举例,minZ=x1+2x2-3x3 maxZ=x12x2+3(x3x”3) x1+x2+x3 9 x1+x2+x3 x”3 + x4=9 -x1-2x2+x3 2 x12x2+x3 x”3 - x5= 2 3x1+x2-3x3=5 3x1+x23(x3 x”3 )=5 x1 0 x2 0 x3无约束 x1 0 x2 0 x3 0 x”3 0 x40 x50,OR1,24,课堂练习：将下列非标准型化为标准型,1、minZ=x1-2x2+3x3 2，maxZ=x1+x2 s.t. x1+x2+x3 7 s.t. x1-x2 0 x1-x2+x3 2 3x1-x2 -3 -3x1+x2+2x3= -5 x1,x2 0 x1,x2 0,x3无约束。,OR1,25,1.1.2线性规划问题的图解法,一、图解法的步骤 1、在平面上建立直角坐标系； 2、图示约束条件，找出可行域； 3、图示目标函数，即为一直线； 4、将目标函数直线沿其法线方向其最优化方向平移，直至与可行域第一次相切为止，这个切点就是最优点。 二、几种可能结局： 1、有唯一最优解，2、有无穷多个最优解，3、无界解，4、无解。,26,线性规划图解法例题（唯一最优解）,maxZ=70X1+120X2 s.t. 9X1+4X2360 4X1+5X2 200 3X1+10X2 300 X10 X20,OR1,27,线性规划图解法例题（无穷多最优解）,OR1,28,线性规划图解法例题（无界解）,OR1,29,线性规划图解法例题（无解）,OR1,30,利用图解法的常识,1、若存在唯一最优解，则此最优解在可行域的顶点上取得。 2、若存在无穷多最优解，则最优解在可行域的边界上取得。 3、若可行域为空集，则没有可行解，也就没有最优解。 4、若可行域无界，目标函数取值可以增大到无穷大，称这种情况为无界解或无最优解。 5、若有可行解，则可能有最优解，也可能无最优解（最优解无界）。,OR1,31,1.1.3解的概念,概念： 1、可行解：满足所有约束条件的解。 2、可行域：即可行解的集合。所有约束条件的交集，也就是各半平面的公共部分。满足所有约束条件的解的集合，称为可行域。 3、凸集：集合内任意两点的连线上的点均属于这个集合。如：实心球、三角形。线性规划的可行域是凸集。,OR1,32,基的概念,基：如前所述LP标准型 和式：maxZ= cjxj aijxj=bi xj 0 j=1,2,n 矩阵式：maxZ=CX AX=b X 0 约束方程的系数矩阵A的秩为m，且mn。设A=B+N ，B是A中mm阶满秩子矩阵，则称B是该LP问题的一个基，即：B是A中m个线性无关向量组。,n,j=1,n,j=1,OR1,33,基本概念,秩：mn矩阵A的所有不为零的子式的最高阶数称为矩阵A的秩。记作R(A)。 线性无关向量组：对于向量组a1,a2,an，如果存在一组不全为零的实数k1,k2,kn,使 k1 a1+k2 a2+knan=0,则称向量组a1,a2,an线性相关，否则称它们线性无关。（向量线性无关的充要条件是向量组的秩等于向量组所含向量个数。）,OR1,34,基解的概念,不失一般性，设B是A的前m列,即B=(p1,p2,pm）,其相对应的变量XB=(x1,x2,xm)T,称为基变量；其余变量XN=(Xm+1,Xn)T称为非基变量。令所有非基变量等于零时得出的解, 即X=（x1,x2,xm,0,0)T称为基解 。 （注：基解不一定就是可行解，因为基解不一定满足非负的约束条件。也即基解中可能存在负值的情况。）,OR1,35,基可行解的概念,基可行解：基解可正可负，负则不可行（违背非负性约束条件），满足非负约束条件的基解为基可行解。 对应于基可行解的基称为可行基。 退化的基可行解：若某个基变量取值为零，则称之为退化的基可行解。 基解的数目：最多Cmn=n!/m!(n-m)!,OR1,36,几种解之间的关系,部分基解是非可行解。,OR1,37,例题8 基可行解说明,maxZ=70X1+120X2 P1 P2 P3 P4 P5 9X1+4X2+X3=360 9 4 1 0 0 4X1+5X2 +x4=200 A= 4 5 0 1 0 3X1+10X2+x5 =300 3 10 0 0 1 Xj0 j=1,2,5 这里m=3,n=5。 Cmn=10,OR1,38,例题8 基可行解说明,基（p3,p4,p5） ，令非基变量x1,x2=0，则基变量x3=360, x4=200, x5=300, 可行解 基（p2,p4,p5）,令非基变量x1=0,x3=0基变量x2=90,x4=250,x5=600. 非可行解 基（ p2,p3,p4 ），令非基变量x1,x5=0，则基变量x2=30, x3=240, x4=50,可行解,OR1,39,基本定理介绍（P16-19）,定理1：若线性规划问题存在可行域，则其可行域D 是凸集。 引理1：LP问题的可行解X（x1,x2,xn）T 为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的。,OR1,40,基本定理介绍,定理2：LP问题的基可行解X对应于可行域的顶点。 顶点：设K是凸集，X属于K；若X不能用不同的两点 的线性组合表示为 则称X为K的一个顶点（或极点）。 引理2：若K是有界凸集。则任何一点X属于K可表示为K的顶点的凸组合。,OR1,41,基本定理介绍,定理3 若可行域有界，LP问题的目标函数一定可以在其可行域的顶点上达到最优。 另外，若可行域为无界，则可能无最优解，也可能有最优解，若有也必定在某顶点上得到。,OR1,42,1.2单纯形法,1.2.1单纯形法的初步讨论(自学内容） 如： maxZ=70X1+120X2 s.t. 9X1+4X2360 4X1+5X2 200 3X1+10X2 300 X10 X20,OR1,43,1.2.2单纯形表,单纯形表的格式：,OR1,44,OR1,45,单纯形法的计算步骤 (P30),1、找到初始可行基，建立单纯形表 2、计算检验数，若所有j 0 则得最优解，结束。否则转下步。 若某K 0而PK 0 ，则最优解无界，结束。否则转下步。 3、根据max j = K 原则确定XK 为进基变量；根据规则 ： = min bi / aik aik 0 = bL/ aLk 确定XL为出基变量。 4、以aLk 为枢轴元素进行迭代，回到第二步。,OR1,46,解的判别定理(P24),1、最优解的判别定理：若X(0)为对应于基B的一个基可行解，且对于一切非基变量，有 ，则 X*为最优解。称 为检验数。 2、无穷多最优解的判别定理：若X(0)为对应于基B的一个基可行解，且对于一切非基变量，有 ，又存在某个非基变量的检验数为0，则称该LP问题有无穷多最优解。,OR1,47,解的判别定理,3、无界解的判别：若X(0)为对应于基B的一个基可行解，有某个正检验数的非基变量对应的列向量其分量均为非正，则该问题无界。,OR1,48,1.3单纯形法的进一步探讨,2.3.1极小化LP的解法。 2.3.2人工变量法之一：大M法。 2.3.3人工变量法之二：两阶段法。,OR1,49,1.3.1极小化LP问题的解法,方法一：将最小化问题化为最大化问题，再对该最大化问题进行求解。 方法二：最小化问题直接求解：检验数的判别由所有j (cj-zj)0 即为最优，变为所有j 0则为最优。(选择最小的负的j 所对应的变量为进基变量。其余同最大化求解方法。),OR1,50,极小化问题的直接解法,例：求解线性规划问题：,OR1,51,解：该规划的基变量为x1,x3,x6。直接 按最小问题单纯形法的求解过程如下：,cj,1,-1,1,0,-3,0,cB,xB,b,x1,x2,x3,x4,x5,x6,1 0 0,2 1 2,0 1 0,-2 -1 1,0 2 3,0 0 1,5 6 8,x1 x3 x6,1 1 0,z,11,1,3,1,-3,2,0,0,-4,0,3,-5,0,3 8/3, ,x1 x3 x5,1 1 -3,1 0 0,2 -1/3 2/3,0 1 0,-2 -5/3 1/3,0 0 1,0 -2/3 1/3,5 2/3 8/3,5/2,0,0,-2/3,0,14/3,0,5/3,x2 x3 x5, 1/6 -1/3,1 0 0,0 1 0,-1 -2 1,0 0 1,0 -2/3 1/3,5/2 3/2 1,0,0,4,0,5/3,4,-1 1 -3,OR1,52,1.3.2人工变量法之一：大M法,首先看下面例题：,OR1,53,大M法,对于这种无初始可行基的问题可以大M法求解。方法：化为标准型的同时，将以及的约束条件中，加入人工变量（虚拟变量），将目标函数中，虚拟变量的系数定为M。 注：当目标函数为最大化时，虚拟变量的系数为M,当目标函数为最小化时，虚拟变量的系数为+M。(目的是迫使人工变量为0）该问题的解法同LP问题的一般解法。例同上。解法见书P33。,OR1,54,解法,解:在上述问题的约束条件中加入松弛变量，剩余变量，人工变量，得到：,OR1,55,用单纯形表计算：,cj,-3,1,1,0,0,M,M,x1,x2,x3,x4,x5,x6,x7,cB,XB,b,1 -4 -2,-2 1 0,1 2 1,1 0 0,0 -1 0,0 1 0,0 0 1,x4 x6 x7,0 M M,11 3 1,-3+6M,1-M,1-3M,0,M,0,0,11 3/2 1,x4 x6 x3,0 M 1,3 0 -2,-2 1 0,0 0 1,1 0 0,0 -1 0,0 1 0,-1 -2 1,10 1 1,-1,1-M,0,0,M,0,3M-1,1,x1 x2 x3,-3 1 1,1 0 0,0 1 0,0 0 1,1/3 0 2/3,-2/3 -1 -4/3,2/3 1 4/3,-5/3 -2 -7/3,4 1 9,2,0,0,0,1/3,1/3,M-1/3,M-2/3,OR1,56,人工变量法:两阶段法,大M法如果在计算机上运作，M就只能用很大的数来代替，这样可能会出现错误。故介绍两阶段法。