《管理运筹学01线性规划基本性质ppt课件》由会员分享，可在线阅读，更多相关《管理运筹学01线性规划基本性质ppt课件（40页珍藏版）》请在金锄头文库上搜索。
1、第第 1 1 章章Linear ProgrammingL P线性性规划划根本性根本性质1.1 线性规划的普通模型线性规划的普通模型1.2 线性规划的图解法线性规划的图解法1.3 线性规划的规范方式线性规划的规范方式1.4 线性规划的解及其性质线性规划的解及其性质1.5 线性规划的运用模型线性规划的运用模型第第1章章 线性规划的根本性质线性规划的根本性质1.1 线性规划的普通模型线性规划的普通模型1.1.1 引引 例例 例例1 产品配比品配比问题范例范例 某厂某厂拟消消费甲、乙两种甲、乙两种产品，每件利品，每件利润分分别为3、5百元。百元。甲、乙甲、乙产品的部件各自在品的部件各自在A、B两个两个
2、车间分分别消消费，每，每件甲、件甲、乙乙产品的部件分品的部件分别需求需求A、B车间的消的消费才干才干1、2工工时。两件。两件产品的部件最后都要在品的部件最后都要在C车间装配，装配每件甲、乙装配，装配每件甲、乙产品分品分别需求需求3、4工工时，三，三车间每天可用于消每天可用于消费这两种两种产品的品的工工时分分别为8、12、36，问应如何安排消如何安排消费这两种两种产品才干品才干获利最多？利最多？1.1 线性规划的普通模型线性规划的普通模型z z x1 x2决策决策变量量z = 3x1 +5x2z = 3x1 +5x2maxmax0目的函数目的函数x1 8 2x2 12 3x1 + 4x2 36
3、函数函数约束束 x1 ， x2 0 非非负性性约束束s.t.s.t.甲甲 乙乙1030 2 4 8 12 36A B C车间车间产品产品单耗工时单耗工时/ /件件最大消费才干最大消费才干工时工时/ /天天单位利润单位利润百元百元/ /件件 3 51.1 线性规划的普通模型线性规划的普通模型例例2 2 配料配料问题 某化工厂根据一某化工厂根据一项合同要合同要为用用户消消费一种用甲、乙一种用甲、乙两种原料混合配制而成的特殊两种原料混合配制而成的特殊产品。甲、品。甲、乙两种原料都乙两种原料都含有含有A A，B B，C C三种化学成分，其含量三种化学成分，其含量(%)(%)是是: :甲甲为1212，2
4、 2， 3 3；乙；乙为3 3，3 3，1515。按合同。按合同规定，定，产品中三种化学品中三种化学成分的含量成分的含量(%)(%)不得低于不得低于4 4，2 2，5 5。甲、乙。甲、乙原料本原料本钱为每千克每千克3 3，2 2元。元。 厂方希望厂方希望总本本钱到达最小，那么到达最小，那么应如如何配制何配制该产品？品？1.1 线性规划的普通模型线性规划的普通模型 成分含量成分含量(%)(%) 原原 料料 化学成分化学成分 甲甲 乙乙 产品成分产品成分 最低含量最低含量(%)(%)A B C 12 3 2 3 3 15 4 2 5 本钱元本钱元/ /千克千克 3 2 x1x2x2min z =
5、3x1+2x2 12 x1 +3x2 4 2 x1 +3x2 2s.t. 3 x1+15x2 5 x1 +x2 = 1 x1 , x2 0配料平衡条件配料平衡条件z z1.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
6、 +a22 x2+a2n xn b2 am1x1+am2x2+amn xn bm xj(或或) 0, 或自在或自在, j=1,2,n 1.2 线性规划的图解法线性规划的图解法1.2.1 图解法的根本步解法的根本步骤 X*= (4, 6)Tz* = 42 1画出可行域画出可行域图形形 2画出目的函数的画出目的函数的 等等值线及其法及其法线 3确定最确定最优点点max z = 3x1+5x2 x1 8 2 x2 12 3x1+ 4 x2 36 x1, x2 0s.t.x1x2O(0,0)x1= 8A(8,0)2x2= 12D(0,6)3x1 + 4x2 = 36O(0,0)x1x2RD(0,6)C
7、(4,6)B(8,3)A(8,0)z = 15z = 30z 法向法向z* = 42边边境方程境方程境方程境方程1.2 线性规划的图解法线性规划的图解法1.2.2 几点几点阐明明实践运用践运用时还须留意以下几点留意以下几点:(1)假假设函数函数约束原型就是等式束原型就是等式,那么其代表的区域那么其代表的区域仅为不断不断线,而且而且问 题的整个可行域的整个可行域R(假假设存在的存在的话)也必然在此直也必然在此直线上。上。(2)在画目的函数等在画目的函数等值线时只只须画两条就能确定其法画两条就能确定其法线方向方向,为此此, 只只须赋给z 两个适当的两个适当的值。(3)在找出最在找出最优点后点后,关
8、于其坐关于其坐标值有两种确定方法有两种确定方法: 在在图上上观测最最优点坐点坐标值 经过解方程解方程组得出最得出最优点坐点坐标值1.2 线性规划的图解法线性规划的图解法1.2.3 几种能几种能够结果果一、独一解一、独一解 如例如例1、例、例2都只需都只需一个一个最最优点，属于独一解的点，属于独一解的情形。情形。s.t.max z = 3x1+4x2 x1 8 2x2 12 3x1 + 4x2 36 x1 ， x2 0 二、多重解二、多重解z = 12z* = 36线段段BCBC上无上无穷多个多个点均点均为最最优解。解。O(0,0)x1x2R D(0,6)C(4,6)B(8,3)A(8,0)1.
9、2 线性规划的图解法线性规划的图解法x1x2z*三、无界解三、无界解3694812x1x2R R2 2R1R2 = R1R2 = 四、无可行解四、无可行解+R R1 11.3 线性规划的规范方式线性规划的规范方式1.3.1 线性性规划划问题的的规范方式范方式max z=c1x1+c2x2+c3x3+cnxns.t.a11x1 +a12x2+ +a1nxn = b1 (0)a21x1 +a22x2+ +a2nxn = b2 (0) am1x1+am2x2+amnxn = bm (0) x1 , x2 , , xn 0简记为：max z =cjxj j=1ns.t.aijxj = bi , i=1
10、, 2 , , mj=1nxj 0, j=1, 2 , , nmax z =CTX s.t.AX = b X 0(M1): (M2): (M3): (M) 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
11、 0 xx*f (x)- f (x)- f (x)1.3 线性规划的规范方式线性规划的规范方式z = 3x1+5x2z = 3x1+5x2maxx1 8 2x2 12 3x1+4x2 36 x1 ， x2 0 s.t.x1 +x3 = 8 2x2 +x4 = 12 3x1 + 4x2 +x5 = 36 x1 ， x2 ， x3 ，x4 ，x5 0 s.t.z = 3x1+5x2z = 3x1+5x2max范例范例范例范例+0x3+0 x4+0 x51.3 线性规划的规范方式线性规划的规范方式min z = x1 2 x2 3 x3 x1 2 x2 x3 5 2x1 3 x2 x3 6 x1 x
12、2 x3 2 x1 0, x3 0s.t.解:max z= x1 2x2 3x3s.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.3 线性规划的规范方式线性规划的规范方式令令x2 = x2 x2 ，且，且 x2，x2 0x3 = -x3代入上式中，得代入上式中，得 max z= max z= x1 x1 2 x2+ 2 x2 2 x2+ 2 x2 3x3 3x3 x1 +2x2 x1 +2x2 2x2 2x2+ x3+ x
13、4 + x3+ x4 = 5 = 5 2x1+3x2 2x1+3x2 3x2 3x2+ x3 + x3 x5 = x5 = 6 6 x1 + x2 x1 + x2 x2 x2 + x3 +x6 + x3 +x6 = 2 = 2 x1 , x2, x2 x1 , x2, x2, x3, x4 , x5 , x6 0, x3, x4 , x5 , x6 0s.t.1.4 线性规划的解及其性质线性规划的解及其性质1.4.1 线性性规划的解的概念划的解的概念 一、可行解一、可行解: 满足足LP问题一切一切约束条件的束条件的X。 二、最二、最优解解: 满足目的要求的可行解足目的要求的可行解X。 三、根本
14、解三、根本解: 只适用于只适用于规范形范形LP问题M。 (1) 基基(矩矩阵)AX = b 设B为A的一个的一个m阶子矩子矩阵，假，假设|B|0,那么称那么称B为约束方程束方程组AX=b或或规范形范形LP问题(M)的一个的一个基矩基矩阵。1.4 线性规划的解及其性质线性规划的解及其性质范范范范 例例例例A =1 0 1 0 0 0 2 0 1 03 4 0 0 1 x1 x2 x3 x4 x5a1 a2 a3 a4 a5 可取可取 B0=a3 ,a4 ,a5为基基| B0 |0,这时称称 a3 ,a4 ,a5 为基向量，而基向量，而 a1 ,a2 为非基向量；称非基向量；称x3 ,x4 ,x5
15、 为基基变量，而量，而 x1 ,x2 为非基非基变量。量。1.4 线性规划的解及其性质线性规划的解及其性质 (2) 根本解 范例的规范形max z = 3x1 + 5x2s.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 为基的基的)
16、 根本解。根本解。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，那么称其，那么称其为一个退化的根本一个退化的根本(可行可行)解，否
17、那么解，否那么为非退化的。非退化的。 如如设： X = ( 0，6，5， 0 ，0 )T 是一个根本可行解，其中是一个根本可行解，其中 x5 =0 为基基变量，那么量，那么该X为退化的根本可行解。退化的根本可行解。1.4 线性规划的解及其性质线性规划的解及其性质非退化的根本非退化的根本非退化的根本非退化的根本( (可行可行可行可行) )解，解，解，解， 并恰有并恰有并恰有并恰有 n m n m 个个个个 0 0 分量。分量。分量。分量。 根本可行解根本可行解对应的基，称的基，称为可行基；可行基； 最最优根本解根本解对应的基，称的基，称为最最优基。基。如：基如：基 B0= ( a2 ,a3 ,a
18、4 ) 对应 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.4 线性规划的解及其性质线性规划的解及其性质1.4.2 凸性的几个根本概念凸性的几个根本概念一、凸集一、凸集 设S En，对恣意两点恣意两点XS ，YS，假，假设对满足足0 1的一切的一切实数数 ，都有，都有 X+(1- )Y S那
19、么称那么称S为凸集。凸集。XY YXY Y 凸集凸集凸集凸集非凸集非凸集非非表示表示S 中两点中两点 X，Y 连线上的任一点上的任一点凸集的几何意凸集的几何意义：凸集：凸集S中恣意两点中恣意两点 X，Y 连线上的点，都在凸集上的点，都在凸集S中。中。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 =
20、1X1 + 2X2 + sXs为点点 X1，X2， ，Xs 的一个凸的一个凸组合。合。1.4 线性规划的解及其性质线性规划的解及其性质1.4.3 1.4.3 线性性规划的解的性划的解的性质 性性质1 1：LPLP问题(M)(M)的可行域的可行域 R = X R = XAX=b, X 0 AX=b, X 0 是凸集。是凸集。 性性质2 2：LPLP问题(M)(M)的一个根本可行解与可的一个根本可行解与可行域行域 R R 的一个极点的一个极点 相互相互对应。 性性质3 3：线性性规划的根本定理划的根本定理 对于一个于一个给定的定的规范型范型LPLP问题(M)(M)来来说： 假假设(M)(M)有可行
21、解，那么有可行解，那么必有根本可行解；必有根本可行解； 假假设(M)(M)有最有最优解，那么解，那么必有最必有最优根本解。根本解。 性性质4 4：假：假设LPLP问题的可行域的可行域 R R, , 那那么么 R R 至少有一极点。至少有一极点。 性性质5 5：LPLP问题可行域可行域 R R 的极点数目必的极点数目必为有限个。有限个。 1.4 线性规划的解及其性质线性规划的解及其性质仅就就规范形范形LP问题(M)阐明其合理性。明其合理性。 因因(M)是一个是一个m阶n维的的LP问题，那么从其系数，那么从其系数阵的的n列列中中取出取出m列，所构成其基的个数不超越列，所构成其基的个数不超越C mC
22、 mn= n！ m！(n-m)！ C mC mn根本可行解的个数根本可行解的个数 根本解的个数根本解的个数根本解的个数根本解的个数而而问题(M)(M)的的 枚枚举法法: 当当m=50，n=100时，此，此时需求求解的需求求解的50元元50阶的的线性方程性方程组的个数的个数为C 50C 50100 =100！ 50！50！ 1029 这是一个天文数字！故需另是一个天文数字！故需另寻其他有效方法。其他有效方法。1.5 线性规划的运用模型线性规划的运用模型 1.5.1 消费方案问题 某企业拟用m种资源消费n种产品，知第i种资源的数量为bi,其单价为pi,每消费一个单位第j种产品所提供的产值为vj,
23、所耗费的第i种资源的数量为aij。第j种产品的合同与指令性方案的产量目的为ej, 最高需求量为dj。 该企业应如何拟定消费方案？ 一、决策变量 设xj为第j种产品的方案产量 二、约束条件 目的约束 xj ej , j = 1,2, ,n 需求约束 xj dj , j = 1,2, ,n 资源约束 三、目的函数 总产值1.5 线性规划的运用模型线性规划的运用模型 j=1naijxj bi, i = 1,2,m j=1nm i=1z2=pi(aij xj) 总本本钱z1=vj xj nj=11.5 线性规划的运用模型线性规划的运用模型 i=1=vj xj -pi(aij xj)j=1nmj=1n=
24、(vj- pi aij ) xjj=1n i=1m令令 cj = vj- pi aij i=1mxj ej , j =1,2, ,nxj djaijxj bi, i =1,2,m j=1nmax z=cj xjj=1n s.t.那那么么 总利利润 z = z1 -z21.5.2 食食谱问题 有有n种食品种食品, 每种食品中含有每种食品中含有m种种营养成分。食养成分。食品用品用 j = 1,2, ,n表示，表示，营养用养用 i = 1,2, ,m表示。知第表示。知第 j 种种食品食品单价价为 cj, 每天最大供量每天最大供量为 dj; 而每而每单位第位第 j种种食品所含食品所含第第 i 种种营养
25、的数量养的数量为 aij。 假定某种生物每天假定某种生物每天对第第 i 种种营养的养的需求量至少需求量至少为 bi, 而每天而每天进食数量限定在食数量限定在 h1, h2 范范围内。内。 试求求该生物的食生物的食谱，使，使总本本钱为最小。最小。 1.5 线性规划的运用模型线性规划的运用模型1.5 线性规划的运用模型线性规划的运用模型 设 xj 为每天提供每天提供应该生物食用的第生物食用的第 j 种食品的数量，种食品的数量，那么那么该问题的数学模型的数学模型为: s.t. 0 xj dj , j=1,2,nmin z=cj xjj=1nj=1 h1 xj h2nj=1 aij xj bi , i
26、=1,2,m n 某厂制造某种部件，由2个B1零件, 3个B2零件配套组装而成。该厂有A1, A2, A3三种机床可加工这两种零件，每种机床的台数，以及每台机床的消费率如下表所示。 求产量最大的消费方案。1.5. 3 产品配套品配套问题1.5 线性规划的运用模型线性规划的运用模型 一、决策一、决策变量量 设以以xij表示每台表示每台Ai (i=1, 2, 3)机床每个任机床每个任务日加工日加工Bj( j = 1, 2 )零件的零件的时间(单位位:任任务日日)； z为B1, B2零件按零件按 2: 3 的比例配套的数量的比例配套的数量(套套/日日)。机床机床种类种类机床机床台数台数每台每台每台每
27、台机床生产率机床生产率( 件件/日日 )零件零件B1零件零件B2A1320203030A2235354545A3410101818x11x12x21x22x31x321.5 线性规划的运用模型线性规划的运用模型 二、二、约束条件束条件 工工时约束束 配套配套约束束机床机床种类种类总总总总生产率生产率( 件件/日日 )零件零件B1零件零件B2A160609090A270709090A340407272x11x12x21x22x31x32z=min (60x11+70x21+40x31), (90x12+90x22+72x32)1213z (60x11+70x21+40x31)12z (90x12
28、+90x22+72x32)13非非线性，等价改写成：性，等价改写成： 或或x11 + x12 = 1x21 + x22 = 1x31 + x32 = 1z -35x11-35x21-20x31 0z -30x12-30x22-24x32 01.5 线性规划的运用模型线性规划的运用模型那么那么该问题的数学模型的数学模型为:max z s.t. x11 + x12 = 1 x21 + x22 = 1 x31 + x32 = 1z 35x11 35x21 20x31 0z 30x12 30x22 24x32 0z, x11, x12, x21, x22, x31, x32 0 制造某种机床，需求 A
29、,B,C三种轴件，其规格与数量如表所示，各类轴件都用5.5米长的同一种圆钢下料。 假设方案消费100台机床，最少需求用多少根圆钢？1.5. 4 下料下料问题1.5 线性规划的运用模型线性规划的运用模型轴类轴类 规格：长度米规格：长度米 每台机床所需轴件数每台机床所需轴件数 A 3.1 1 B 2.1 2 C 1.21.2 4 余料余料j 1.2找出全部找出全部省料截法省料截法一根圆钢所截各类轴件数一根圆钢所截各类轴件数 截法截法轴类轴类 轴轴 件件 需求量需求量 A(3.1) 100 B(2.1) 200 C(1.2) 400 余料余料( (米米) ) 234511100.310200210.
30、1 0 0 1 0 2 4 1 0.71.5 线性规划的运用模型线性规划的运用模型min z = x1 + x2 + x3 + x4 + x5s.t.x1 +x2 100x1 +2x3 +x4 200 2x2 +x3 +2x4 +4x5 400 x1， x2 ， x3， x4， x5 0那么那么该问题的数学模型的数学模型为:设第第 j 种截法下料种截法下料 xj 根。根。1.5 线性规划的运用模型线性规划的运用模型 某化工厂要用三种原料某化工厂要用三种原料 D，P，H 混合配制三种不混合配制三种不同同规格格的的产品品 A，B，C。有关数据如下：。有关数据如下： 1.5. 5 配料配料问题产品产
31、品规规 格格单价单价(元元/kg)A原料原料D不少于不少于50%原料原料P不超过不超过25%50B原料原料D不少于不少于25%原料原料P不超过不超过50%35C不不 限限25原料原料最大供量最大供量(kg/天天)单价单价(元元/kg)D1006565P1002525H603535应如合配制，才干使利如合配制，才干使利润到达最大？到达最大？表表1-10表表1-111.5 线性规划的运用模型线性规划的运用模型一、决策变量 设以 xij 表示每天消费的第 j 种产品中所含第 i 种原料的数量(kg，右表)。ji D P HABCx11 x12 x13x21 x22 x23x31 x32 x33二、二
32、、约束条件束条件 规格格约束束(据表据表1-10)x11+ x12 + x13x11 0.50 0.50x11+ x12 + x13x12 0.25 0.25x11+ x12 + x13x21 0.25 0.25x11+ x12 + x13x22 0.50 0.501.5 线性规划的运用模型线性规划的运用模型改写成改写成 - x11 + x12 + x13 0 - x11+ 3 x12 -x13 0-3 x21 +x22 + x23 0 x21 +x22 - x23 0 资源源约束束(据表据表1-11)x11+ x21 + x31 100x12+ x22 + x32 100x13+ x23 +
33、 x33 601.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.5 线性规划的运用模型线性规划的运用模型 目的函数目的函数为： 总利利润 = 总产值 - 总本本钱max z =-15x11+25x12+15x13-30x21+10x22-40x31-10x33 该问题的数学模型的数学模型为: :s.t. - x11 +x12 + x13 0 - x11+3x12 - x13 0 -3x21+x22 +x23 0 x21+x22 - x23 0x11 +x21 +x31 100 x12 +x22 +x32 100 x13 +x23 +x33 60 xij 0， i = 1, 2, 3； j = 1, 2, 3
