《管理运筹学》课件01-线性规划基本性质

,第1章,LinearProgramming,LP,线性规划,基本性质,第1章线性规划的基本性质,2,1.1线性规划的一般模型1.2线性规划的图解法1.3线性规划的标准形式1.4线性规划的解及其性质1.5线性规划的应用模型,第1章线性规划的基本性质,第1章线性规划的基本性质,3,1.1线性规划的一般模型,1.1.1引例例1产品配比问题（范例）某厂拟生产甲、乙两种产品，每件利润分别为3、5百元。甲、乙产品的部件各自在A、B两个车间分别生产，每件甲、乙产品的部件分别需要A、B车间的生产能力1、2工时。两件产品的部件最后都要在C车间装配，装配每件甲、乙产品分别需要3、4工时，三车间每天可用于生产这两种产品的工时分别为8、12、36，问应如何安排生产这两种产品才能获利最多？,第1章线性规划的基本性质,4,1.1线性规划的一般模型,z,x1x2,决策变量,z=3x1+5x2,max,0,目标函数,x18,2x212,3x1+4x236,函数约束,x1，x20,非负性约束,s.t.,第1章线性规划的基本性质,5,1.1线性规划的一般模型,例2配料问题某化工厂根据一项合同要为用户生产一种用甲、乙两种原料混合配制而成的特殊产品。甲、乙两种原料都含有A，B，C三种化学成分，其含量(%)是:甲为12，2，3；乙为3，3，15。按合同规定，产品中三种化学成分的含量(%)不得低于4，2，5。甲、乙原料成本为每千克3，2元。厂方希望总成本达到最小，则应如何配制该产品？,第1章线性规划的基本性质,6,1.1线性规划的一般模型,x1,x2,minz=3x1+2x212x1+3x242x1+3x22s.t.3x1+15x25x1+x2=1x1,x20,配料平衡条件,z,第1章线性规划的基本性质,7,1.1线性规划的一般模型,1.1.2线性规划的一般模型,一般LP模型的三类参数：价值系数cj，消耗系数aij，右端常数bi.LP模型的三要素：决策变量，目标函数，约束条件.,s.t.,optz=c1x1+c2x2+c3x3+cnxna11x1+a12x2+a1nxnb1a21x1+a22x2+a2nxnb2am1x1+am2x2+amnxnbmxj(或)0,或自由,j=1,2,n,第1章线性规划的基本性质,8,1.2线性规划的图解法,1.2.1图解法的基本步骤,X*=(4,6)T,z*=42,1画出可行域图形2画出目标函数的等值线及其法线3确定最优点,x1=8,A(8,0),2x2=12,D(0,6),3x1+4x2=36,z=15,z=30,z法向,z*=42,边界方程,第1章线性规划的基本性质,9,1.2线性规划的图解法,1.2.2几点说明实际运用时还须注意以下几点:(1)若函数约束原型就是等式,则其代表的区域仅为一直线,而且问题的整个可行域R(若存在的话)也必然在此直线上。(2)在画目标函数等值线时只须画两条就能确定其法线方向,为此,只须赋给z两个适当的值。(3)在找出最优点后,关于其坐标值有两种确定方法:在图上观测最优点坐标值通过解方程组得出最优点坐标值,第1章线性规划的基本性质,10,1.2线性规划的图解法,1.2.3几种可能结果一、唯一解如例1、例2都只有一个最优点，属于唯一解的情形。,二、多重解,z=12,z*=36,线段BC上无穷多个点均为最优解。,第1章线性规划的基本性质,11,1.2线性规划的图解法,x1,x2,z*,三、无界解,R2,R1R2=,四、无可行解,+,R1,第1章线性规划的基本性质,12,1.3线性规划的标准形式,1.3.1线性规划问题的标准形式,maxz=c1x1+c2x2+c3x3+cnxn,s.t.,a11x1+a12x2+a1nxn=b1(0)a21x1+a22x2+a2nxn=b2(0)am1x1+am2x2+amnxn=bm(0)x1,x2,xn0,简记为：,s.t.,xj0,j=1,2,n,maxz=CTX,s.t.,AX=b,X0,(M1):,(M2):,(M3):,(M),第1章线性规划的基本性质,13,1.3线性规划的标准形式,1.3.2非标准形LP问题的标准化一、目标函数minz=CTX令z=zmaxz=CTX例：minz=3x12x2maxz=3x12x2二、函数约束bi0两边同时乘以-1约束为形式加上松弛变量约束为形式减去剩余变量三、决策变量若xk0,令xk=xk,则xk0若xk为自由变量,令xk=xkxk且xk,xk0,-f(x),第1章线性规划的基本性质,14,1.3线性规划的标准形式,x1+x3=8,2x2+x4=12,3x1+4x2+x5=36,x1，x2，x3，x4，x50,s.t.,范例,+0 x3+0 x4+0 x5,第1章线性规划的基本性质,15,1.3线性规划的标准形式,解:,maxz=x12x23x3,s.t.,x12x2x3+x4=52x13x2x3-x5=6x1x2x3+x6=2x1,x4,x5,x60,x30,例4将下述LP问题化成标准形,第1章线性规划的基本性质,16,1.3线性规划的标准形式,令,x2=x2x2，且x2，x20,x3=-x3,代入上式中，得,第1章线性规划的基本性质,17,1.4线性规划的解及其性质,1.4.1线性规划的解的概念一、可行解:满足LP问题所有约束条件的X。二、最优解:满足目标要求的可行解X。三、基本解:只适用于标准形LP问题（M）。(1)基(矩阵)AX=b设B为A的一个m阶子矩阵，若|B|0,则称B为约束方程组AX=b或标准形LP问题(M)的一个基（矩阵）。,第1章线性规划的基本性质,18,1.4线性规划的解及其性质,范例,A=,x1x2x3x4x5,a1a2a3a4a5,可取B0=（a3,a4,a5）为基（|B0|0）,这时称a3,a4,a5为基向量，而a1,a2为非基向量；称x3,x4,x5为基变量，而x1,x2为非基变量。,第1章线性规划的基本性质,19,1.4线性规划的解及其性质,(2)基本解范例的标准形,maxz=3x1+5x2,s.t.,x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x50,取B0=（a3,a4,a5）为基，令一切非基变量x1=x2=0,可解得基变量x3=8，x4=12，x5=36则得一特解X0=(0，0，8，12，36)T,称为一个(关于B0为基的)基本解。,第1章线性规划的基本性质,20,1.4线性规划的解及其性质,也可取B1=(a2,a3,a4)为基,得X1=(0，9，8，-6，0)T还可取B2=(a1,a2,a3)为基,得X2=(4，6，4，0，0)T等等。四、基本可行解满足非负性约束的基本解。如X0，X2；而X1不可行。对基本(可行)解而言：在其分量中，若有一个或更多个基变量取值为0，则称其为一个退化的基本(可行)解，否则为非退化的。如设：X=(0，6，5，0，0)T是一个基本可行解，其中x5=0为基变量，则该X为退化的基本可行解。,第1章线性规划的基本性质,21,1.4线性规划的解及其性质,非退化的基本(可行)解，并恰有nm个0分量。,基本可行解对应的基，称为可行基；最优基本解对应的基，称为最优基。如：基B0=(a2,a3,a4)对应X0=(0，0，8，12，36)T可行基B1=(a2,a3,a4)对应X1=(0，9，8，-6，0)T不可行基B2=(a1,a2,a3)对应X2=(4，6，4，0，0)T,恰有m个非0分量，,为可行基,为非可行基,为最优基,x*,x*,B*,第1章线性规划的基本性质,22,1.4线性规划的解及其性质,1.4.2凸性的几个基本概念一、凸集设SEn，对任意两点XS，YS，若对满足01的一切实数，都有X+(1-)YS则称S为凸集。,凸集,凸集,非凸集,非,表示S中两点X，Y连线上的任一点,凸集的几何意义：凸集S中任意两点X，Y连线上的点，都在凸集S中。,第1章线性规划的基本性质,23,1.4线性规划的解及其性质,二、极点设凸集SEn,XS，如果X不能用S中不同的两点Y和Z表示为X=Y+(1-)Z(01)则称X为S的一个极点。三、凸组合设XiEn,实数i0,i=1,2,s,且i=1，则称X=1X1+2X2+sXs为点X1，X2，Xs的一个凸组合。,第1章线性规划的基本性质,24,1.4线性规划的解及其性质,1.4.3线性规划的解的性质性质1：LP问题(M)的可行域R=XAX=b,X0是凸集。性质2：LP问题(M)的一个基本可行解与可行域R的一个极点互相对应。性质3：线性规划的基本定理对于一个给定的标准型LP问题(M)来说：若(M)有可行解，则必有基本可行解；若(M)有最优解，则必有最优基本解。性质4：若LP问题的可行域R,则R至少有一极点。性质5：LP问题可行域R的极点数目必为有限个。,第1章线性规划的基本性质,25,1.4线性规划的解及其性质,仅就标准形LP问题(M)说明其合理性。因(M)是一个m阶n维的LP问题，则从其系数阵的n列中取出m列，所构成其基的个数不超过,基本可行解的个数,基本解的个数,而问题(M)的,枚举法:当m=50，n=100时，此时需要求解的50元50阶的线性方程组的个数为,=,1029,这是一个天文数字！故需另寻其他有效方法。,第1章线性规划的基本性质,26,1.5线性规划的应用模型,1.5.1生产计划问题,某企业拟用m种资源生产n种产品，已知第i种资源的数量为bi,其单价为pi,每生产一个单位第j种产品所提供的产值为vj,所消耗的第i种资源的数量为aij。第j种产品的合同与指令性计划的产量指标为ej,最高需求量为dj。该企业应如何拟定生产计划？,第1章线性规划的基本性质,27,一、决策变量设xj为第j种产品的计划产量二、约束条件指标约束xjej,j=1,2,n需求约束xjdj,j=1,2,n资源约束三、目标函数总产值,1.5线性规划的应用模型,总成本,第1章线性规划的基本性质,28,1.5线性规划的应用模型,令,xjej,j=1,2,nxjdj,s.t.,则,总利润,z=z1-z2,第1章线性规划的基本性质,29,1.5.2食谱问题有n种食品,每种食品中含有m种营养成分。食品用j=1,2,n表示，养分用i=1,2,m表示。已知第j种食品单价为cj,每天最大供量为dj;而每单位第j种食品所含第i种养分的数量为aij。假定某种生物每天对第i种养分的需求量至少为bi,而每天进食数量限定在h1,h2范围内。试求该生物的食谱，使总成本为最小。,1.5线性规划的应用模型,第1章线性规划的基本性质,30,1.5线性规划的应用模型,设xj为每天提供给该生物食用的第j种食品的数量，则该问题的数学模型为:,s.t.,0xjdj,j=1,2,n,某厂制造某种部件，由2个B1零件,3个B2零件配套组装而成。该厂有A1,A2,A3三种机床可加工这两种零件，每种机床的台数，以及每台机床的生产率如下表所示。求产量最大的生产方案。,1.5.3产品配套问题,第1章线性规划的基本性质,31,1.5线性规划的应用模型,一、决策变量设以xij表示每台Ai(i=1,2,3)机床每个工作日加工Bj(j=1,2)零件的时间(单位:工作日)；z为B1,B2零件按2:3的比例配套的数量(套/日)。,x11,x12,x21,x22,x31,x32,第1章线性规划的基本性质,32,1.5线性规划的应用模型,二、约束条件工时约束,配套约束,x11,x12,x21,x22,x31,x32,非线性，等价改写成：,或,x11+x12=1x21+x22=1x31+x32=1,z-35x11-35x21-20 x310,z-30 x12-30 x22-24x320,第1章线性规划的基本性质,33,1.5线性规划的应用模型,则该问题的数学模型为:,maxz,s.t.,x11+x12=1x21+x22=1x31+x32=1,z35x1135x2120 x310,z30 x1230 x2224x320,z,x11,x12,x21,x22,x31,x320,制造某种机床，需要A,B,C三种轴件，其规格与数量如表所示，各类轴件都用5.5米长的同一种圆钢下料。若计划生产100台机床，最少需要用多少根圆钢？,1.5.4下料问题,第1章线性规划的基本性质,34,1.5线性规划的应用模型,余料j1.2,找出全部省料截法,2,3,4,5,1,1,1,0,0.3,1,0,2,0,0,2,1,0.1,0,0,1,0,2,4,1,0.7,第1章线性规划的基本性质,35,1.5线性规划的应用模型,minz=x1+x2+x3+x4+x5,s.t.,x1+x2100 x1+2x3+x42002x2+x3+2x4+4x5400 x1，x2，x3，x4，x50,则该问题的数学模型为:,设第j种截法下料xj根。,第1章线性规划的基本性质,36,1.5线性规划的应用模型,某化工厂要用三种原料D，P，H混合配制三种不同规格的产品A，B，C。有关数据如下：,1.5.5配料问题,应如合配制，才能使利润达到最大？,表1-10,表1-11,第1章线性规划的基本性质,37,1.5线性规划的应用模型,一、决策变量设以xij表示每天生产的第j种产品中所含第i种原料的数量(kg，右表)。,二、约束条件,规格约束(据表1-10),0.50,0