《管理运筹学》02-1线性规划的数学模型及相关概念ppt课件

1、一、现实中的线性规划问题及数学模型一、现实中的线性规划问题及数学模型二、线性规划的规范方式二、线性规划的规范方式三、线性规划的几何解释三、线性规划的几何解释 四、线性规划的基及根本可行解四、线性规划的基及根本可行解第第1节节 线性规划的数学模型及相关概念线性规划的数学模型及相关概念一一 现实中的线性规划问题及模型现实中的线性规划问题及模型例例2-1 2-1 消费方案问题消费方案问题某工厂拥有某工厂拥有A A、B B、C C三种类型的设备，消费甲、乙、三种类型的设备，消费甲、乙、丙、丁四种产品。每件产品在消费中需求占用的设备丙、丁四种产品。每件产品在消费中需求占用的设备机时数，每件产品可以获得的

2、利润以及三种设备可利机时数，每件产品可以获得的利润以及三种设备可利用的时数如表用的时数如表2-12-1所示，试用线性规划制定使总利润所示，试用线性规划制定使总利润最大的消费方案。最大的消费方案。第1节 线性规划的数学模型及相关概念产品甲产品甲 产品乙产品乙 产品丙产品丙 产品丁产品丁1.51.01.52000 8000 5000设备设备A 设备设备B 设备设备C单位产品耗单位产品耗费的机时数费的机时数产品产品设备才干设备才干小时小时利润利润元元/ /件件 5.24 7.30 8.34 4.181.05.03.02.41.03.51.03.51.0一一 现实中的线性规划问题及模型现实中的线性规划

3、问题及模型 x1 x2 x3 x4 决策变量决策变量0目的函数目的函数1.5x1 + 1.0 x2 + 2.4x3 + 1.0 x4 2000 函数约束函数约束非负性约束非负性约束1.0 x1 + 5.0 x2 + 1.0 x3 + 3.5x4 8000 1.5x1 + 3.0 x2 + 3.5x3 + 1.0 x4 8000 x1 ， x2 ， x3 ， x4 0 产品甲产品甲 产品乙产品乙 产品丙产品丙 产品丁产品丁1.51.01.52000 8000 5000设备设备A 设备设备B 设备设备C单位产品耗单位产品耗费的机时数费的机时数产品产品设备才干设备才干小时小时利润利润元元/ /件件

4、5.24 7.30 8.34 4.181.05.03.02.41.03.51.03.51.0一一 现实中的线性规划问题及模型现实中的线性规划问题及模型求解这个线性规划，可以得到最优解为：求解这个线性规划，可以得到最优解为：x1=294.12x1=294.12件件 x2=1500 x2=1500 件件 x3=0 x3=0件件 x4=58.82 x4=58.82 件件 最大利润为最大利润为z=12737.06z=12737.06元元 请留意最优解中利润率最高的产品丙在最优消费请留意最优解中利润率最高的产品丙在最优消费方案中不安排消费。阐明按产品利润率大小为优先次方案中不安排消费。阐明按产品利润率大

5、小为优先次序来安排消费方案的方法有很大局限性。尤其当产品序来安排消费方案的方法有很大局限性。尤其当产品种类很多，设备类型很多的情况下，用手工方法安排种类很多，设备类型很多的情况下，用手工方法安排消费方案很难获得称心的结果。消费方案很难获得称心的结果。一一 现实中的线性规划问题及模型现实中的线性规划问题及模型例例2-2 2-2 配料问题配料问题某工厂要用四种合金某工厂要用四种合金T1T1，T2T2，T3T3和和T4T4为原料，经熔炼为原料，经熔炼成为一种新的不锈钢成为一种新的不锈钢G G。这四种原料含元素铬。这四种原料含元素铬CrCr，锰锰MnMn和镍和镍NiNi的含量的含量% %，这四种原料的

6、单，这四种原料的单价以及新的不锈钢资料价以及新的不锈钢资料G G所要求的所要求的CrCr，MnMn和和NiNi的最低的最低含量含量% %如下表所示：如下表所示：设熔炼时分量没有损耗，要熔炼成设熔炼时分量没有损耗，要熔炼成100100公斤不锈钢公斤不锈钢G G，应选用原料应选用原料T1T1，T2T2，T3T3和和T4T4各多少公斤，使本钱最小。各多少公斤，使本钱最小。第1节 线性规划的数学模型及相关概念T1 T2 T3 T1 T2 T3 T4T43.212.045.823.20 2.10 4.30CrMnNiG G单价元单价元/ /公斤公斤 115 97 82 764.531.123.06 2.

7、193.574.271.764.332.73 x1 x2 x3 x4 0.0321x1 + 0.0453x2 + 0.0219x3 + 0.0176x4 3.20 x1 ， x2 ， x3 ， x4 00.0204x1 + 0.0112x2 + 0.0357x3 + 0.0433x4 2.100.0582x1 + 0.0306x2 + 0.0427x3 + 0.0273x4 4.30 x1 + x2 + x3 + x4 = 100求解这个线性规划，可以得到最优解为：求解这个线性规划，可以得到最优解为：x1=26.58 x2=31.57 x3=41.84 x4=0 x1=26.58 x2=31.

8、57 x3=41.84 x4=0 最大利润为最大利润为z=9549.87z=9549.87元元一一 现实中的线性规划问题及模型现实中的线性规划问题及模型一一 现实中的线性规划问题及模型现实中的线性规划问题及模型例例2-3 2-3 背包问题背包问题一只背包最大装载分量为一只背包最大装载分量为5050公斤。现有三种物品，每公斤。现有三种物品，每种物品数量无限。每种物品每件的分量、价值如下表种物品数量无限。每种物品每件的分量、价值如下表所示：所示： 要在背包中装入这三种物品各多少件，使背包中的要在背包中装入这三种物品各多少件，使背包中的物品价值最高。物品价值最高。第1节 线性规划的数学模型及相关概念

9、物品物品1 1 物品物品2 2 物品物品3 3 1017分量公斤分量公斤/件件价值元价值元 / 件件4172 2035 x1 x2 x310 x1 + 41x2 + 20 x3 50 x1 ， x2 ， x3 0 且为整数且为整数求解这个线性规划，可以得到最优解为：求解这个线性规划，可以得到最优解为：x1=1 x2=0 x3=2 x1=1 x2=0 x3=2 最高价值为最高价值为 z= 87 z= 87元元一一 现实中的线性规划问题及模型现实中的线性规划问题及模型一一 现实中的线性规划问题及模型现实中的线性规划问题及模型例例2-4 2-4 最小费用流问题最小费用流问题 某公司下设两个分工厂，两

10、个仓库及一个配某公司下设两个分工厂，两个仓库及一个配送中心。其中送中心。其中F1F1和和F2F2是两个工厂，是两个工厂，W1W1和和W2W2是两个仓库。是两个仓库。D D是一个分销中心。由工厂消费的产品经由图所示的是一个分销中心。由工厂消费的产品经由图所示的运输网络运往仓库。每一条道路运输的单位本钱在线运输网络运往仓库。每一条道路运输的单位本钱在线段上给出，其中，段上给出，其中，F1F2F1F2与与DW2DW2道路由于遭到道路道路由于遭到道路中的桥梁承重上限的要求，因此有最大运输量限制。中的桥梁承重上限的要求，因此有最大运输量限制。其他道路有足够的运输才干来运输两个工厂消费的货其他道路有足够的

11、运输才干来运输两个工厂消费的货物。需求制定的决策是关于每一条道路应该运输多少，物。需求制定的决策是关于每一条道路应该运输多少，目的是总体的运输本钱最小化。目的是总体的运输本钱最小化。第1节 线性规划的数学模型及相关概念一一 现实中的线性规划问题及模型现实中的线性规划问题及模型例例2-4 2-4 最小费用流问题最小费用流问题 第1节 线性规划的数学模型及相关概念900元元/单位单位x6100元元/单位单位x7最多最多80单位单位x4x5x2x3x1300元元/单位单位300元元/单位单位F1需求需求30单单位位W1消费消费40单单位位F2需求需求60单单位位W2200元元/单位单位D最多最多10

12、单位单位200元元/单位单位400元元/单位单位图图2-1公司的配送网络公司的配送网络消费消费50单位单位x1 + x2 + x3 =50 x1 ， ， x7 0- x1 +x4 =40 -x2 - x4 +x5 = 0 -x3 + x6 x7 = -30求解这个线性规划，可以得到最优解为：求解这个线性规划，可以得到最优解为：x1 x1 ， x2 x2 ， x3 x3 ， x4 x4 ， x5 x5 ， x6 x6 ， x7 x7 = = 0 0，4040，1010，4040，8080，0 0，2020z=49000z=49000元元一一 现实中的线性规划问题及模型现实中的线性规划问题及模型

13、-x5 - x6 + x7 = -60 x1 10， x5 80线性规划的普通方式线性规划的普通方式 普通普通LP模型的三类参数：模型的三类参数：价值系数价值系数c j，耗费系数，耗费系数a ij，右端常数，右端常数b i . LP模型的三要素：决策变量，目的函数，约束条件模型的三要素：决策变量，目的函数，约束条件.s.t.max(min) 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, 或自在或自

14、在, j=1,2,n 一一 现实中的线性规划问题及模型现实中的线性规划问题及模型线性规划的向量和矩阵的表达方式线性规划的向量和矩阵的表达方式记向量和矩阵记向量和矩阵一一 现实中的线性规划问题及模型现实中的线性规划问题及模型mnmmnnmnTnaaaaaaaaaAbbbbxxxXcccC212222111211212121,那么线性规划问题可以表示为：那么线性规划问题可以表示为：maxmin) z =CX s.t.AX (= ) b X 0二、线性规划的规范方式二、线性规划的规范方式称以下线性规划的方式为规范方式称以下线性规划的方式为规范方式max z=c1x1+c2x2+c3x3+cnxns.

15、t.a11x1 +a12x2+ +a1nxn = b1 (0)a21x1 +a22x2+ +a2nxn = b2 (0) am1x1+am2x2+amnxn = bm (0) x1 , x2 , , xn 0简记为：简记为：max z =CX s.t.AX = b X 0(M1): (M2): 非规范形非规范形LP问题的规范化问题的规范化 一、极小化目的函数的问题一、极小化目的函数的问题 min z = CX 令令 z= z max z= CX 例：例：min z = 3x1 2x2 max z= 3x1 2x2 二、约束条件不是等式的问题二、约束条件不是等式的问题 bi0 两边同时乘以两边同

16、时乘以 -1 约束为约束为方式方式 加上松弛变量加上松弛变量 约束为约束为方式方式 减去剩余变量减去剩余变量 三、变量符号无限制或小于等于零的问题三、变量符号无限制或小于等于零的问题 假设假设xk为自在变量为自在变量, 令令 xk = xk xk且且 xk,xk 0 假设假设xk 0, 令令 xk = xk,那么那么 xk 0 二、线性规划的规范方式二、线性规划的规范方式xzzzminz = - zz maxx*min z = 2x1 3 x2 x3 x1 x2 2 x3 3 2x1 3 x2 x3 5 x1 x2 x3 = 4 x1 0, x2 无约束，无约束， x3 0s.t.解：令解：令

17、z= -z ， x2= x2 x2 ，x3= -x3 s.t.二、线性规划的规范方式二、线性规划的规范方式min z = x1 2 x2 3 x3 x1 2 x2 x3 5 2x1 3 x2 x3 6 x1 x2 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练习：将下述练习：将下述LP问题化成规范形问题化成规范形二、线性规划的规范方式二、线性规划的规范方式令令x2 = x2 x2 ，且，且

18、x2，x2 0 x3 = -x3代入上式中，得代入上式中，得s.t.二、线性规划的规范方式二、线性规划的规范方式只需两个变量的线性规划问题只需两个变量的线性规划问题 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)x1x2D(0,6)C(4,6)B(8,3)A(8,0)z

19、 = 15z = 30z 法向法向z* = 42三、线性规划的几何解释三、线性规划的几何解释几点阐明几点阐明实践运用时还须留意以下几点实践运用时还须留意以下几点: :(1)(1)假设函数约束原型就是等式假设函数约束原型就是等式, ,那么其代表的区域仅那么其代表的区域仅为不断线为不断线, ,而且问而且问 题的整个可行域题的整个可行域R(R(假设存在的话假设存在的话) )也必然在此直线也必然在此直线上。上。(2)(2)在画目的函数等值线时只须画两条就能确定其法在画目的函数等值线时只须画两条就能确定其法线方向线方向, ,为此为此, , 只须赋给只须赋给z z 两个适当的值。两个适当的值。(3)(3)

20、在找出最优点后在找出最优点后, ,关于其坐标值有两种确定方法关于其坐标值有两种确定方法: : 在图上观测最优点坐标值在图上观测最优点坐标值 经过解方程组得出最优点坐标值经过解方程组得出最优点坐标值三、线性规划的几何解释三、线性规划的几何解释几种能够结果几种能够结果一、独一解一、独一解 如例如例1、例、例2都只需都只需一个一个最优点，属于独一解的最优点，属于独一解的情形。情形。s.t.max z = 3x1+4x2 x1 8 2x2 12 3x1 + 4x2 36 x1 ， x2 0 二、多重解二、多重解z = 12z* = 36线段线段BCBC上无穷多个上无穷多个点均为最优解。点均为最优解。O

21、(0,0)x1x2 D(0,6)C(4,6)B(8,3)A(8,0)三、线性规划的几何解释三、线性规划的几何解释x1x2z*三、无界解三、无界解3694812x1x2四、无可行解四、无可行解+三、线性规划的几何解释三、线性规划的几何解释相关定义相关定义定义定义2-1 可行域可行域在在n维空间中，满足条件维空间中，满足条件ai1x1+ai2x2+ain xn (= ) bi且且xj 0 的点集。的点集。O(0,0)x1x2 D(0,6)C(4,6)B(8,3)A(8,0)三、线性规划的几何解释三、线性规划的几何解释定义定义2-2 凸集凸集三、线性规划的几何解释三、线性规划的几何解释设设S是是n维

22、空间中的一个点集。假设对恣意维空间中的一个点集。假设对恣意n维向量维向量X1S，X2S，且，且X1X2，以及恣意实数，以及恣意实数 01，有，有X= X1+(1- )X2S那么称那么称S为为n维空间中的一个凸集维空间中的一个凸集Convex Set。点。点X称称为点为点X1和和X2的凸组合。的凸组合。凸集：凸集：非凸集：非凸集：定义定义2-3 凸集的极点凸集的极点三、线性规划的几何解释三、线性规划的几何解释设设S为一凸集，且为一凸集，且XS，假设，假设X不能用不同的两点不能用不同的两点X1S，X2S的线性组合表示为的线性组合表示为X= X1+(1- )X2 01那么称那么称X为为S的一个极点。

23、的一个极点。运用以上的定义，线性规划的可行域以及最优解有以下性质：运用以上的定义，线性规划的可行域以及最优解有以下性质：1假设线性规划的可行域非空，那么可行域必定为一凸假设线性规划的可行域非空，那么可行域必定为一凸集。集。2假设线性规划有最优解，那么最优解一定可以在凸集的假设线性规划有最优解，那么最优解一定可以在凸集的极点中找到。极点中找到。 这样，求线性规划最优解的问题，从在可行域内无限个可这样，求线性规划最优解的问题，从在可行域内无限个可行解中搜索的问题转化为在其可行域的有限个极点上搜索的问行解中搜索的问题转化为在其可行域的有限个极点上搜索的问题。题。基：设基：设A为线性规划模型约束条件系

24、数矩阵为线性规划模型约束条件系数矩阵m n，mn，而，而B为其为其mm子矩阵，假设子矩阵，假设|B|0，那么称，那么称B为该线性规划模型的一个基。为该线性规划模型的一个基。基变量：基中每个向量所对应的变量称为基变量。基变量：基中每个向量所对应的变量称为基变量。非基变量：模型中基变量之外的变量称为非基变量。非基变量：模型中基变量之外的变量称为非基变量。根本解基解：令模型中一切非基变量根本解基解：令模型中一切非基变量X非基非基=0后，由模后，由模型约束方程组型约束方程组 n aijxj =bi (i=1,2,m)得到的一组解。得到的一组解。 j=1根本可行解基可行解：在根本解中，同时又是可行解的解

25、称为根本根本可行解基可行解：在根本解中，同时又是可行解的解称为根本可行解。可行解。可行基：对应于根本可行解的基称为可行基。可行基：对应于根本可行解的基称为可行基。四、线性规划的基、根本可行解四、线性规划的基、根本可行解Max z=2x1+3x2 st. x1+x2 3 x1+2x2 4 x1,x2 0 Max z=2x1+3x2 +0 x3 +0 x4 st. x1+x2+x3=3 x1+2x2+x4=4 x1, x2, x3 , x4 0A=x1 x2 x3 x41 1 1 01 2 0 1可行解：可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T 等。等。设B= 1 0 0 1，令，那么| B |=10,令 x1=x2 =0，那么 x3 =3, x4=4，X=(0,0,3,4)T例：例：x3 x4基变量基变量令 B=1 1 1 0 x1 x3 ，那么令 x2=x4 =0，那么 x3 =-1, x1=4，