《管理运筹学-02-1线性规划的数学模型及相关概念课件》由会员分享，可在线阅读，更多相关《管理运筹学-02-1线性规划的数学模型及相关概念课件（31页珍藏版）》请在金锄头文库上搜索。
1、第第 1 节节Linear ProgrammingL P线性规划线性规划的数学模型的数学模型第1节 线性规划的数学模型及相关概念2一、一、现实中的线性规划问题及数学模型现实中的线性规划问题及数学模型二、线性规划的标准形式二、线性规划的标准形式三、线性规划的几何解释三、线性规划的几何解释 四、线性规划的基及基本可行解四、线性规划的基及基本可行解第第1节节 线性规划的数学模型及相关概念线性规划的数学模型及相关概念3一一 现实中的现实中的线性规划问题及模型线性规划问题及模型例例2-12-1 生产计划问题生产计划问题某工厂拥有某工厂拥有A A、B B、C C三种类型的设备，生产甲、乙、丙、丁四三种类型
2、的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如表可以获得的利润以及三种设备可利用的时数如表2-12-1所示所示，试，试用线性规划制订使总利润最大的生产计划。用线性规划制订使总利润最大的生产计划。第1节 线性规划的数学模型及相关概念产品甲产品甲 产品乙产品乙 产品丙产品丙 产品丁产品丁1.51.01.52000 8000 5000设备设备A 设备设备B 设备设备C单位产品消耗单位产品消耗的机时数的机时数产品产品设备能力设备能力（小时）（小时）利润利润（元（元/ /件）
3、件） 5.24 7.30 8.34 4.181.05.03.02.41.03.51.03.51.04一一 现实中的现实中的线性规划问题及模型线性规划问题及模型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
4、.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.05一一 现实中的现实中的线性规划问题及模型线性规划问题及模型第1节 线性规划的数学模型及相关概念求解这个线性规划，可以得到最优解为：求解这个线性规划，可以得到最优解为：x1=294.12（件）（件）
5、x2=1500 （件）（件） x3=0 （件）（件） x4=58.82 （件）（件） 最大利润为最大利润为z=12737.06（元）（元） 请注意最优解中利润率最高的产品丙在最优生产请注意最优解中利润率最高的产品丙在最优生产计划中不安排生产。说明按产品利润率大小为优先次计划中不安排生产。说明按产品利润率大小为优先次序来安排生产计划的方法有很大局限性。尤其当产品序来安排生产计划的方法有很大局限性。尤其当产品品种很多，设备类型很多的情况下，用手工方法安排品种很多，设备类型很多的情况下，用手工方法安排生产计划很难获得满意的结果。生产计划很难获得满意的结果。6一一 现实中的现实中的线性规划问题及模型线
6、性规划问题及模型例例2-22-2 配料问题配料问题某工厂要用四种合金某工厂要用四种合金T1，T2，T3和和T4为原料，经熔炼成为一种为原料，经熔炼成为一种新的不锈钢新的不锈钢G。这四种原料含元素铬（。这四种原料含元素铬（Cr），锰（），锰（Mn）和镍）和镍（Ni）的含量（）的含量（%），这四种原料的单价以及新的不锈钢材料），这四种原料的单价以及新的不锈钢材料G所要求的所要求的Cr，Mn和和Ni的最低含量（的最低含量（%）如下表所示：）如下表所示：设熔炼时重量没有损耗，要熔炼成设熔炼时重量没有损耗，要熔炼成100公斤不锈钢公斤不锈钢G，应选用，应选用原料原料T1，T2，T3和和T4各多少公斤，使
7、成本最小。各多少公斤，使成本最小。第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 7第1节 线性规划的数学模型及相关概念z z = 115x1 +97x2 +82x3 +76x4minmin0.0321x1 + 0.0453x2 + 0.0219x3 + 0.0176x4 3.20s.t.s.t.x1 ， x2 ， x3 ，
8、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（元）（元）一一 现实中的现实中的线性规划问题及模型线性规划问题及模型8一一 现实中的现实中的线性规划问题及模型线性规划问题及模型例例2-32-3 背包问题背包问题一只背包最大装载重量
9、为一只背包最大装载重量为50公斤。现有三种物品，每种物品数公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价值如下表所示：量无限。每种物品每件的重量、价值如下表所示： 要在背包中装入这三种物品各多少件，使背包中的物品价值最要在背包中装入这三种物品各多少件，使背包中的物品价值最高高。第1节 线性规划的数学模型及相关概念物品物品1 1 物品物品2 2 物品物品3 3 1017重量（公斤重量（公斤/件）件）价值（元价值（元 / 件）件）4172 2035 x1 x2 x39第1节 线性规划的数学模型及相关概念z z = 17x1 +72x2 +35x3maxmax10 x1 + 41x2
10、+ 20 x3 50s.t.s.t.x1 ， x2 ， x3 0 且为整数且为整数求解这个线性规划，可以得到最优解为：求解这个线性规划，可以得到最优解为： x1=1 x2=0 x3=2 最最高价值高价值为为 z= 87（元）（元）一一 现实中的现实中的线性规划问题及模型线性规划问题及模型10一一 现实中的现实中的线性规划问题及模型线性规划问题及模型例例2-4 2-4 最小费用流问题最小费用流问题 某公司下设两个分工厂，两个仓库及一个配送中心。其中某公司下设两个分工厂，两个仓库及一个配送中心。其中F1和和F2是两个工厂，是两个工厂，W1和和W2是两个仓库。是两个仓库。D是一个分销中心。是一个分销
11、中心。由工厂生产的产品经由图所示的运输网络运往仓库。每一条路由工厂生产的产品经由图所示的运输网络运往仓库。每一条路线运输的单位成本在线段上给出，其中，线运输的单位成本在线段上给出，其中，F1F2与与DW2路线路线由于受到路线中的桥梁承重上限的要求，因此有最大运输量限由于受到路线中的桥梁承重上限的要求，因此有最大运输量限制。其他路线有足够的运输能力来运输两个工厂生产的货物。制。其他路线有足够的运输能力来运输两个工厂生产的货物。需要制订的决策是关于每一条路线应该运输多少，目标是总体需要制订的决策是关于每一条路线应该运输多少，目标是总体的运输成本最小化。的运输成本最小化。第1节 线性规划的数学模型及
12、相关概念11一一 现实中的现实中的线性规划问题及模型线性规划问题及模型例例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单位单位12第1节 线性规划的数学模型及相关概念z z = 200 x1 +400 x2 +900 x3 +
13、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 8013线性规划的一般形式线性规划的一
14、般形式 一般一般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 (
15、= ) bm xj(或或) 0, , 或自由或自由, , j=1, ,2, , ,n 第1节 线性规划的数学模型及相关概念一一 现实中的现实中的线性规划问题及模型线性规划问题及模型14线性规划的向量和矩阵的表达形式线性规划的向量和矩阵的表达形式记向量和矩阵记向量和矩阵第1节 线性规划的数学模型及相关概念一一 现实中的现实中的线性规划问题及模型线性规划问题及模型则线性规划问题可以表示为：则线性规划问题可以表示为：max（min) z =CX s.t.AX (= ) b X 015二、线性规划的标准形式二、线性规划的标准形式称以下线性规划的形式为标准形式称以下线性规划的形式为标准形式max z=c
16、1x1+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节 线性规划的数学模型及相关概念16非标准形非标准形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 =
