线性规划基本性质.ppt

,第 1 章,Linear Programming,L P,线性规划,基本性质,第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,x1 x2,决策变量,z=3x1+5x2,max,0,目标函数,x1 8,2x2 12,3x1+4x2 36,函数约束,x1，x2 0,非负性约束,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,min z=3x1+2x2 12 x1+3x2 4 2 x1+3x2 2s.t.3 x1+15x2 5 x1+x2=1 x1,x2 0,配料平衡条件,z,第1章 线性规划的基本性质,7,1.1 线性规划的一般模型,1.1.2 线性规划的一般模型,一般LP模型的三类参数：价值系数c j，消耗系数a ij，右端常数b i.LP模型的三要素：决策变量，目标函数，约束条件.,s.t.,opt z=c1 x1+c2 x2+c3 x3+cn xn a11x1+a12 x2+a1n xn b1 a21x1+a22 x2+a2n xn b2 am1x1+am2x2+amn xn bm xj(或)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 线性规划问题的标准形式,max z=c1x1+c2x2+c3x3+cnxn,s.t.,a11x1+a12x2+a1nxn=b1(0)a21x1+a22x2+a2nxn=b2(0)am1x1+am2x2+amnxn=bm(0)x1,x2,xn 0,简记为：,s.t.,xj 0,j=1,2,n,max z=CTX,s.t.,AX=b,X 0,(M1):,(M2):,(M3):,(M),第1章 线性规划的基本性质,13,1.3 线性规划的标准形式,1.3.2 非标准形LP问题的标准化 一、目标函数 min z=CTX 令 z=z max z=CTX 例：min z=3x1 2x2 max z=3x1 2x2 二、函数约束 bi0 两边同时乘以-1 约束为形式 加上松弛变量 约束为形式 减去剩余变量 三、决策变量 若xk 0,令 xk=xk,则 xk 0 若xk为自由变量,令 xk=xk xk且 xk,xk 0,-f(x),第1章 线性规划的基本性质,14,1.3 线性规划的标准形式,x1+x3=8,2x2+x4=12,3x1+4x2+x5=36,x1，x2，x3，x4，x5 0,s.t.,范例,+0 x3+0 x4+0 x5,第1章 线性规划的基本性质,15,1.3 线性规划的标准形式,解:,max z=x1 2x2 3x3,s.t.,x1 2x2 x3+x4=5 2x1 3x2 x3-x5=6 x1 x2 x3+x6=2 x1,x4,x5,x6 0,x3 0,例4 将下述LP问题化成标准形,第1章 线性规划的基本性质,16,1.3 线性规划的标准形式,令,x2=x2 x2，且 x2，x2 0,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=,x1 x2 x3 x4 x5,a1 a2 a3 a4 a5,可取 B0=（a3,a4,a5）为基（|B0|0）,这时称 a3,a4,a5 为基向量，而 a1,a2 为非基向量；称x3,x4,x5 为基变量，而 x1,x2 为非基变量。,第1章 线性规划的基本性质,19,1.4 线性规划的解及其性质,(2)基本解 范例的标准形,max z=3x1+5x2,s.t.,x1+x3=8 2 x2+x4=12 3x1+4x2+x5=36 x1,x2,x3,x4,x5 0,取 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 线性规划的解及其性质,非退化的基本(可行)解，并恰有 n m 个 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 凸性的几个基本概念一、凸集 设S En，对任意两点XS，YS，若对满足0 1的一切实数，都有 X+(1-)Y S则称S为凸集。,凸集,凸集,非凸集,非,表示S 中两点 X，Y 连线上的任一点,凸集的几何意义：凸集S中任意两点 X，Y 连线上的点，都在凸集S中。,第1章 线性规划的基本性质,23,1.4 线性规划的解及其性质,二、极点 设凸集S En,XS，如果X不能用S中不同的两点Y和Z表示为 X=Y+(1-)Z(01)则称X为S的一个极点。三、凸组合 设XiEn,实数i 0,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,X 0 是凸集。性质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种产品的计划产量 二、约束条件 指标约束 xj ej,j=1,2,n 需求约束 xj dj,j=1,2,n 资源约束 三、目标函数 总产值,1.5 线性规划的应用模型,总成本,第1章 线性规划的基本性质,28,1.5 线性规划的应用模型,令,xj ej,j=1,2,nxj dj,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.,0 xj dj,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 x31 0,z-30 x12-30 x22-24x32 0,第1章 线性规划的基本性质,33,1.5 线性规划的应用模型,则该问题的数学模型为:,max z,s.t.,x11+x12=1 x21+x22=1 x31+x32=1,z 35x11 35x21 20 x31 0,z 30 x12 30 x22 24x32 0,z,x11,x12,x21,x22,x31,x32 0,制造某种机床，需要 A,B,C三种轴件，其规格与数量如表所示，各类轴件都用5.5米长的同一种圆钢下料。若计划生产100台机床，最少需要用多少根圆钢？,1.5.4 下料问题,第1章 线性规划的基本性质,34,1.5 线性规划的应用模型,余料j 1.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 线性规划的应用模型,min z=x1+x2+x3+x4+x5,s.t.,x1+x2 100 x1+2x3+x4 200 2x2+x3+2x4+4x5 400 x1，x2，x3，x4，x5 0,则该问题的数学模型为:,设第 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.25,0.25,0.50,第1章 线性规划的基本性质,38,1.5 线性规划的应用模型,改写成,-x11+x12+x13 0-x11+3 x12-x13 0-3 x21+x22+x23 0 x21+x22-x23 0,资源约束(据表1-11),x11+x21+x31 100 x12+x22+x32 100 x13+x23+x33 60,第1章 线性规划的基本性质,39,1.5 线性规划的应用模型,三、目标函数,总产值(据表1-10),产品A的产值:50(x11+x12+x13)产品B的产值:35(x21+x22+x23)产品C的产值:25(x31+x32+x33),以上三项之和即总产值。,总成本(据表1-11),原料D的成本:65(x11+x21+x31)原料P的成本:25(x12+x22+x32)原料H的成本:35(x13+x23+x33),以上三项之和即总成本。,第1章 线性规划的基本性质,40,1.5 线性规划的应用模型,目标函数为：总利润=总产值-总成本,max z=-15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33,该问题的数学模型为:,s.t.,-x11+x12+x13 0-x11+3x12-x13 0-3x21+x22+x23 0 x21+x22-x23 0,x11+x21+x31 100 x12+x22+x32 100 x13+x23+x33 60,xij 0，i=1,2,3；j=1,2,3,