管理运筹学021线性规划的数学模型及相关概念课件

第第 1 节节Linear ProgrammingL P线性规划线性规划的数学模型的数学模型第 1 节Linear Programming1第1节 线性规划的数学模型及相关概念2一、现实中的线性规划问题及数学模型一、现实中的线性规划问题及数学模型二、线性规划的标准形式二、线性规划的标准形式三、线性规划的几何解释三、线性规划的几何解释 四、线性规划的基及基本可行解四、线性规划的基及基本可行解第第1节节 线性规划的数学模型及相关概念线性规划的数学模型及相关概念第1节 线性规划的数学模型及相关概念2一、现实中的线性规划问23一一 现实中的现实中的线性规划问题及模型线性规划问题及模型例例2-12-1 生产计划问题生产计划问题某工厂拥有某工厂拥有A A、B B、C C三种类型的设备，生产甲、乙、丙、丁四三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如表可以获得的利润以及三种设备可利用的时数如表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.03一 现实中的线性规划问题及模型例2-1 生产计划问题第34一一 现实中的现实中的线性规划问题及模型线性规划问题及模型z z x1 x2 x3 x4 决策变量决策变量z z=5.24x1+7.30 x2+8.34x3+4.18x4maxmax0目标函数目标函数1.5x1+1.0 x2+2.4x3+1.0 x4 2000 函数约束函数约束非负性约束非负性约束s.t.s.t.第1节 线性规划的数学模型及相关概念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单位产品消耗单位产品消耗的机时数的机时数产品产品设备能力设备能力（小时）（小时）利润利润（元（元/件）件）5.24 7.30 8.34 4.181.05.03.02.41.03.51.03.51.04一 现实中的线性规划问题及模型z x1 45一一 现实中的现实中的线性规划问题及模型线性规划问题及模型第1节 线性规划的数学模型及相关概念求解求解这个个线性性规划，可以得到最划，可以得到最优解解为：x1=294.12（件）（件）x2=1500（件）（件）x3=0（件）（件）x4=58.82（件）（件）最大利最大利润为z=12737.06（元）（元）请注意最注意最优解中利解中利润率最高的率最高的产品丙在最品丙在最优生生产计划中不安排生划中不安排生产。说明按明按产品利品利润率大小率大小为优先次序先次序来安排生来安排生产计划的方法有很大局限性。尤其当划的方法有很大局限性。尤其当产品品品品种很多，种很多，设备类型很多的情况下，用手工方法安排生型很多的情况下，用手工方法安排生产计划很划很难获得得满意的意的结果。果。5一 现实中的线性规划问题及模型第1节 线性规划的数学56一一 现实中的现实中的线性规划问题及模型线性规划问题及模型例例2-22-2 配料问题配料问题某工厂要用四种合金某工厂要用四种合金T1，T2，T3和和T4为原料，经熔炼成为一种为原料，经熔炼成为一种新的不锈钢新的不锈钢G。这四种原料含元素铬（。这四种原料含元素铬（Cr），锰（），锰（Mn）和镍）和镍（Ni）的含量（）的含量（%），这四种原料的单价以及新的不锈钢材料），这四种原料的单价以及新的不锈钢材料G所要求的所要求的Cr，Mn和和Ni的最低含量（的最低含量（%）如下表所示：）如下表所示：设熔炼时重量没有损耗，要熔炼成设熔炼时重量没有损耗，要熔炼成100公斤不锈钢公斤不锈钢G，应选用，应选用原料原料T1，T2，T3和和T4各多少公斤，使成本最小。各多少公斤，使成本最小。第1节 线性规划的数学模型及相关概念T T1 1 T T2 2 T T3 3 T T4 43.212.045.823.20 2.10 4.30CrMnNiG G单价（元单价（元/公斤）公斤）115 97 82 764.531.123.06 2.193.574.271.764.332.73 x1 x2 x3 x4 6一 现实中的线性规划问题及模型例2-2 配料问题第1节67第1节 线性规划的数学模型及相关概念z z=115x1+97x2+82x3+76x4minmin0.0321x1+0.0453x2+0.0219x3+0.0176x4 3.20s.t.s.t.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 最大利最大利润为z=9549.87（元）（元）一一 现实中的现实中的线性规划问题及模型线性规划问题及模型7第1节 线性规划的数学模型及相关概念z=115x1 78一一 现实中的现实中的线性规划问题及模型线性规划问题及模型例例2-32-3 背包问题背包问题一只背包最大装载重量为一只背包最大装载重量为50公斤。现有三种物品，每种物品数公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价值如下表所示：量无限。每种物品每件的重量、价值如下表所示：要在背包中装入这三种物品各多少件，使背包中的物品价值最要在背包中装入这三种物品各多少件，使背包中的物品价值最高高。第1节 线性规划的数学模型及相关概念物品物品1 1 物品物品2 2 物品物品3 3 1017重量（公斤重量（公斤/件）件）价值（元价值（元/件）件）4172 2035 x1 x2 x38一 现实中的线性规划问题及模型例2-3 背包问题第1节89第1节 线性规划的数学模型及相关概念z z=17x1+72x2+35x3maxmax10 x1+41x2+20 x3 50s.t.s.t.x1 ，x2 ，x3 0 且为整数且为整数求解求解这个个线性性规划，可以得到最划，可以得到最优解解为：x1=1 x2=0 x3=2 最最高价高价值为 z=87（元）（元）一一 现实中的现实中的线性规划问题及模型线性规划问题及模型9第1节 线性规划的数学模型及相关概念z=17x1+910一一 现实中的现实中的线性规划问题及模型线性规划问题及模型例例2-4 2-4 最小费用流问题最小费用流问题 某公司下设两个分工厂，两个仓库及一个配送中心。其中某公司下设两个分工厂，两个仓库及一个配送中心。其中F1和和F2是两个工厂，是两个工厂，W1和和W2是两个仓库。是两个仓库。D是一个分销中心。是一个分销中心。由工厂生产的产品经由图所示的运输网络运往仓库。每一条路由工厂生产的产品经由图所示的运输网络运往仓库。每一条路线运输的单位成本在线段上给出，其中，线运输的单位成本在线段上给出，其中，F1F2与与DW2路线路线由于受到路线中的桥梁承重上限的要求，因此有最大运输量限由于受到路线中的桥梁承重上限的要求，因此有最大运输量限制。其他路线有足够的运输能力来运输两个工厂生产的货物。制。其他路线有足够的运输能力来运输两个工厂生产的货物。需要制订的决策是关于每一条路线应该运输多少，目标是总体需要制订的决策是关于每一条路线应该运输多少，目标是总体的运输成本最小化。的运输成本最小化。第1节 线性规划的数学模型及相关概念10一 现实中的线性规划问题及模型例2-4 最小费用流问1011一一 现实中的现实中的线性规划问题及模型线性规划问题及模型例例2-4 2-4 最小费用流问题最小费用流问题 第1节 线性规划的数学模型及相关概念900元元/单位单位x6100元元/单位单位x7最多最多80单位单位x4x5x2x3x1300元元/单位单位300元元/单位单位F1需求需求30单单位位W1生产生产40单位单位F2需求需求60单位单位W2200元元/单位单位D最多最多10单位单位200元元/单位单位400元元/单位单位图图2-1公司的配送网络公司的配送网络生产生产50单位单位11一 现实中的线性规划问题及模型例2-4 最小费用流问1112第1节 线性规划的数学模型及相关概念z z=200 x1+400 x2+900 x3+300 x4+100 x5+3x6+200 x7minminx1+x2+x3 =50s.t.s.t.x1 ，x7 0-x1 +x4 =40 -x2 -x4+x5 =0 -x3+x6 x7=-30求解求解这个个线性性规划，可以得到最划，可以得到最优解解为：（x1，x2，x3，x4，x5，x6，x7）=（0，40，10，40，80，0，20）z=49000（元）（元）一一 现实中的现实中的线性规划问题及模型线性规划问题及模型 -x5-x6+x7=-60 x1 10，x5 8012第1节 线性规划的数学模型及相关概念z=200 x11213线性规划的一般形式线性规划的一般形式 一般一般LP模型的模型的三类参数三类参数三类参数三类参数：价价价价值值系数系数系数系数c c j j，消耗系数消耗系数消耗系数消耗系数a a ij ij，右端常数右端常数右端常数右端常数b b i 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,或自由或自由,j=1,2,n 第1节 线性规划的数学模型及相关概念一一 现实中的现实中的线性规划问题及模型线性规划问题及模型13线性规划的一般形式 一般LP模型的三类参数：s.t.m1314线性规划的向量和矩阵的表达形式线性规划的向量和矩阵的表达形式记向量和矩阵记向量和矩阵第1节 线性规划的数学模型及相关概念一一 现实中的现实中的线性规划问题及模型线性规划问题及模型则线性规划问题可以表示为：则线性规划问题可以表示为：max（min)z=CX s.t.AX(=)b X 014线性规划的向量和矩阵的表达形式记向量和矩阵第1节 线性规1415二、线性规划的标准形式二、线性规划的标准形式称以下线性规划的形式为标准形式称以下线性规划的形式为标准形式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=CX s.t.AX=b X 0(M1):(M2):第1节 线性规划的数学模型及相关概念15二、线性规划的标准形式称以下线性规划的形式为标准形式ma1516非标准形非标准形LP问题的标准化问题的标准化 一、极小化目标函数的问题一、极小化目标函数的问题 min z=CX 令令 z=z max z=CX 例例：min z=3x1 2x2 max z=3x1 2x2 二、约束条件不是等式的问题二、约束条件不是等式的问题 bi0 两边同时乘以两边同时乘以 -1 约束为约束为形式形式 加上加上松弛变量松弛变量 约束为约束为形式形式 减去减去剩余变量剩余变量 三、变量符号无限制或小于等于零的问题三、变量符号无限制或小于等于零的问题 若若xk为为自由变量自由变量,令令 xk=xk xk且且 xk,xk 0 若若xk 0,令令 xk=xk,则则 xk 0 第1节 线性规划的数学模型及相关概念二、线性规划的标准形式二、线性规划的标准形式xzzzminz=-zz maxx*16非标准形LP问题的标准化第1节 线性规划的数学模型及相关1617min 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.第1节 线性规划的数学模型及相关概念例例例例2-5 2-5 2-5 2-5 将下述将下述LP问题化成标准形式问题化成标准形式解：令解：令z z=-z，x2=x2 x x2 2，x x3 3=-x3 max z=2 x1 3 x2-3x x2 2 x x3 3 x1 x2+x x2 2 2 x x3 3 +x4 =3 2x1+3x2 3x x2 2+x x3 3 x5=5 x1+x2 x x2 2 x x3 3 =4 x1,x2,x x2 2,x x3 3,x4,x5 0s.t.二、线性规划的标准形式二、线性规划的标准形式17min z=2x1 3 x2 x3s.t.第17第1章 线性规划的数学模型及相关概念18min 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问题化成标准形问题化成标准形二、线性规划的标准形式二、线性规划的标准形式第1章 线性规划的数学模型及相关概念18min z=x118第1章 线性规划的数学模型及相关概念19令令x2=x2 x x2 2，且，且 x2，x x2 2 0 x3=-x x3 3 代入上式中，得代入上式中，得 max z=x1 2 x2+2 x x2 2 3x x3 3 x1+2x2 2x x2 2+x x3 3+x4 =5 2x1+3x2 3x x2 2+x x3 3 x5 =6 x1+x2 x x2 2+x x3 3 +x6=2 x1,x2,x x2 2,x x3 3,x4,x5,x6 0s.t.二、线性规划的标准形式二、线性规划的标准形式第1章 线性规划的数学模型及相关概念19令x2=x2 19第1节 线性规划的基本性质20只有两个变量的线性规划问题只有两个变量的线性规划问题 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(4,6)B(8,3)A(8,0)z=15z=30z 法向法向z*=42边界方程边界方程边界方程边界方程三、线性规划的几何解释三、线性规划的几何解释第1节 线性规划的基本性质20只有两个变量的线性规划问题 X20第1节 线性规划的基本性质21几点说明几点说明实际运用时还须注意以下几点实际运用时还须注意以下几点:(1)(1)若函数约束原型就是等式若函数约束原型就是等式,则其代表的区域仅为一直线则其代表的区域仅为一直线,而且问而且问 题的整个可行域题的整个可行域R R(若存在的话若存在的话)也必然在此直线上。也必然在此直线上。(2)(2)在画目标函数等值线时只须画两条就能确定其法线方向在画目标函数等值线时只须画两条就能确定其法线方向,为此为此,只须赋给只须赋给z z 两个适当的值。两个适当的值。(3)(3)在找出最优点后在找出最优点后,关于其坐标值有两种确定方法关于其坐标值有两种确定方法:在图上观测最优点坐标值在图上观测最优点坐标值 通过解方程组得出最优点坐标值通过解方程组得出最优点坐标值三、线性规划的几何解释三、线性规划的几何解释第1节 线性规划的基本性质21几点说明三、线性规划的几何解释21第1节 线性规划的基本性质22几种可能结果几种可能结果一、唯一解一、唯一解 如例如例1 1、例、例2 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节 线性规划的基本性质22几种可能结果s.t.max z22第1节 线性规划的基本性质23x1x2z*三、无界解三、无界解3694812x1x2R R2 2R R1 1 R R2 2=四、无可行解四、无可行解+R R1 1三、线性规划的几何解释三、线性规划的几何解释第1节 线性规划的基本性质23x1x2z*三、无界解3623第1节 线性规划的基本性质24相关定义相关定义定义定义2-1 可行域可行域在在在在n n n n维空间中，满足条件维空间中，满足条件维空间中，满足条件维空间中，满足条件ai1x1+ai2x2+ain xn(=)bi且且且且xj 0 的点集。的点集。O(0,0)x1x2R D(0,6)C(4,6)B(8,3)A(8,0)三、线性规划的几何解释三、线性规划的几何解释第1节 线性规划的基本性质24相关定义O(0,0)x1x2R24第1节 线性规划的基本性质25定义定义2-2 凸集凸集三、线性规划的几何解释三、线性规划的几何解释设设S是是n维空间中的一个点集。若对任意维空间中的一个点集。若对任意n维向量维向量X1 S，X2 S，且，且X1 X2，以及任意实数，以及任意实数（01），有），有X=X1+(1-)X2 S则称则称S为为n维空间中的一个凸集（维空间中的一个凸集（Convex Set）。点）。点X称为称为点点X1和和X2的凸组合的凸组合。凸集：凸集：非凸集：非凸集：第1节 线性规划的基本性质25定义2-2 凸集三、线性规划的25第1节 线性规划的基本性质26定义定义2-3 凸集的极点凸集的极点三、线性规划的几何解释三、线性规划的几何解释设设S为一凸集，且为一凸集，且X S，若，若X不能用不同的两点不能用不同的两点X1 S，X2 S的线性组合表示为的线性组合表示为X=X1+(1-)X2 （01）则称则称X为为S的一个极点。的一个极点。运用以上的定义，线性规划的可行域以及最优解有以下性质：运用以上的定义，线性规划的可行域以及最优解有以下性质：（1）若线性规划的可行域非空，则可行域必定为一凸集。）若线性规划的可行域非空，则可行域必定为一凸集。（2）若线性规划有最优解，则最优解一定可以在凸集的极点中找到。）若线性规划有最优解，则最优解一定可以在凸集的极点中找到。这样，求线性规划最优解的问题，从在可行域内无限个可行解中搜索的这样，求线性规划最优解的问题，从在可行域内无限个可行解中搜索的问题转化为在其可行域的有限个极点上搜索的问题。问题转化为在其可行域的有限个极点上搜索的问题。第1节 线性规划的基本性质26定义2-3 凸集的极点三、线性2627第1节 线性规划的数学模型及相关概念基：基：设设A为线性规划模型约束条件系数矩阵（为线性规划模型约束条件系数矩阵（m n，mn），而），而B为为其其m m子矩阵，若子矩阵，若|B|0，则称，则称B为该线性规划模型的一个基。为该线性规划模型的一个基。基变量：基变量：基中每个向量所对应的变量称为基变量。基中每个向量所对应的变量称为基变量。非基变量：非基变量：模型中基变量之外的变量称为非基变量。模型中基变量之外的变量称为非基变量。基本解（基解）：基本解（基解）：令模型中所有非基变量令模型中所有非基变量X非基非基=0后，由模型后，由模型约束方程组约束方程组 n aijxj=bi(i=1,2,m)得到的一组解。得到的一组解。j=1基本可行解（基可行解）：基本可行解（基可行解）：在基本解中，同时又是可行解的解称为基本在基本解中，同时又是可行解的解称为基本可行解。可行解。可行基：可行基：对应于对应于基本可行解基本可行解的基称为可行基。的基称为可行基。四、线性规划的基、基本可行解四、线性规划的基、基本可行解27第1节 线性规划的数学模型及相关概念基：设A为线性规划模27-28-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，X=(4,0,-1,0)T|B|=-10,非基本可行解非基本可行解基本可行解基本可行解标准化第1节 线性规划的数学模型及相关概念四、线性规划的基、基本可行解四、线性规划的基、基本可行解-28-Max z=2x1+3x2 Max z=2x12829 定理定理2-1 线性规划的基本可行解就是可行域的极点。线性规划的基本可行解就是可行域的极点。第1节 线性规划的数学模型及相关概念四、线性规划的基、基本可行解四、线性规划的基、基本可行解Max z=2x1+3x2 s.t.x1+x2 3 x1+2x2 4 x1,x2 0 Max z=2x1+3x2+0 x3+0 x4 s.t.x1+x2 +x3 =3 x1+2x2 +x4=4 x1,x2,x3,x4 0例：例：标准化A矩矩阵包含以下六个包含以下六个22的子矩的子矩阵：B1=p1，p2 B2=p1，p3 B3=p1，p4B4=p2，p3 B5=p2，p4 B6=p3，p4其中所有的子矩其中所有的子矩阵行列式行列式值均不等于均不等于0，均，均为非奇异方非奇异方阵，因此，因此该问题共有共有6个基。个基。29 定理2-1 线性规划的基本可行解就是可行域的极点。第12930第1节 线性规划的数学模型及相关概念四、线性规划的基、基本可行解四、线性规划的基、基本可行解B6=1 0 0 1，则|B6|=10,x3 x4基变量基本可行解 对应O点令 x1=x2=0，则 x3=3,x4=4，X6=(0,0,3,4)T同理同理可以求得可以求得B1、B2、B3、B4、B5对应的基本解：对应的基本解：X1=(x1，x2，x3，x4)T=(2，1，0，0)T 对应对应B点点X2=(x1，x2，x3，x4)T=(4，0，-1，0)T对应对应E点点X3=(x1，x2，x3，x4)T=(3，0，0，1)T对应对应C点点X4=(x1，x2，x3，x4)T=(0，2，1，0)T对应对应A点点X5=(x1，x2，x3，x4)T=(0，3，0，-2)T对应对应D点点其中其中X1，X3，X4 是是基本可行解基本可行解。O(0,0)x1x2B(2,1,1)E(4,0)C(3,0)A(0,2,2)D(0,3)30第1节 线性规划的数学模型及相关概念四、线性规划的基、基30谢谢！谢谢！31