单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第1章 线性规划的基本性质,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第1章 线性规划的,数学模型及相关概念,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,1,节,L,inear,P,rogramming,L,P,线性规划,的数学模型,第 1 节Linear Programming,1,第1,节,线性规划的,数学模型及相关概念,2,一、现实中的线性规划问题及数学模型,二、线性规划的标准形式,三、线性规划的几何解释,四、线性规划的基及基本可行解,第,1,节 线性规划的数学模型及相关概念,第1节 线性规划的数学模型及相关概念2一、现实中的线性规划问,2,3,一,现实中的,线性规划问题及模型,例,2-1,生产计划问题,某工厂拥有,A,、,B,、,C,三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如表,2-1,所示,，试,用线性规划制订使总利润最大的生产计划。,第1,节,线性规划的,数学模型及相关概念,产品甲 产品乙 产品丙 产品丁,1.5,1.0,1.5,2000,8000,5000,设备,A,设备,B,设备,C,单位产品消耗的机时数,产品,设备能力,（小时）,利润,（元,/,件）,5.24 7.30 8.34 4.18,1.0,5.0,3.0,2.4,1.0,3.5,1.0,3.5,1.0,3一 现实中的线性规划问题及模型例2-1 生产计划问题第,3,4,一,现实中的,线性规划问题及模型,z,x,1,x,2,x,3,x,4,决策变量,z,=5.24,x,1,+7.30,x,2,+8.34,x,3,+4.18,x,4,max,0,目标函数,1.5,x,1,+,1.0,x,2,+,2.4,x,3,+,1.0,x,4,2000 ,函数约束,非负性约束,s.t.,第1,节,线性规划的,数学模型及相关概念,1.0,x,1,+,5.0,x,2,+,1.0,x,3,+,3.5,x,4,8000 ,1.5,x,1,+,3.0,x,2,+,3.5,x,3,+,1.0,x,4,8000 ,x,1,，,x,2,，,x,3,，,x,4,0 ,产品甲 产品乙 产品丙 产品丁,1.5,1.0,1.5,2000,8000,5000,设备,A,设备,B,设备,C,单位产品消耗的机时数,产品,设备能力,（小时）,利润,（元,/,件）,5.24 7.30 8.34 4.18,1.0,5.0,3.0,2.4,1.0,3.5,1.0,3.5,1.0,4一 现实中的线性规划问题及模型z x1,4,5,一,现实中的,线性规划问题及模型,第1,节,线性规划的,数学模型及相关概念,求解这个线性规划，可以得到最优解为：,x,1,=294.12,（件）,x,2,=1500,（件）,x,3,=0,（件）,x,4,=58.82,（件）,最大利润为,z=12737.06,（元）,请注意最优解中利润率最高的产品丙在最优生产计划中不安排生产。说明按产品利润率大小为优先次序来安排生产计划的方法有很大局限性。尤其当产品品种很多，设备类型很多的情况下，用手工方法安排生产计划很难获得满意的结果。,5一 现实中的线性规划问题及模型第1节 线性规划的数学,5,6,一,现实中的,线性规划问题及模型,例,2-2,配料问题,某工厂要用四种合金,T,1,，,T,2,，,T,3,和,T,4,为原料，经熔炼成为一种新的不锈钢,G,。这四种原料含元素铬（,Cr,），锰（,Mn,）和镍（,Ni,）的含量（,%,），这四种原料的单价以及新的不锈钢材料,G,所要求的,Cr,，,Mn,和,Ni,的最低含量（,%,）如下表所示：,设熔炼时重量没有损耗，要熔炼成,100,公斤不锈钢,G,，应选用原料,T,1,，,T,2,，,T,3,和,T,4,各多少公斤，使成本最小。,第1,节,线性规划的,数学模型及相关概念,T,1,T,2,T,3,T,4,3.21,2.04,5.82,3.20,2.10,4.30,Cr,Mn,Ni,G,单价（元,/,公斤）,115 97 82 76,4.53,1.12,3.06,2.19,3.57,4.27,1.76,4.33,2.73,x,1,x,2,x,3,x,4,6一 现实中的线性规划问题及模型例2-2 配料问题第1节,6,7,第1,节,线性规划的,数学模型及相关概念,z,=115,x,1,+97,x,2,+82,x,3,+76,x,4,min,0.0321,x,1,+,0.0453,x,2,+,0.0219,x,3,+,0.0176,x,4,3.20,s.t.,x,1,，,x,2,，,x,3,，,x,4,0,0.0204,x,1,+,0.0112,x,2,+,0.0357,x,3,+,0.0433,x,4,2.10,0.0582,x,1,+,0.0306,x,2,+,0.0427,x,3,+,0.0273,x,4,4.30,x,1,+,x,2,+,x,3,+,x,4,=100,求解这个线性规划，可以得到最优解为：,x,1,=26.58 x,2,=31.57 x,3,=41.84 x,4,=0,最大利润为,z=9549.87,（元）,一,现实中的,线性规划问题及模型,7第1节 线性规划的数学模型及相关概念z=115x1,7,8,一,现实中的,线性规划问题及模型,例,2-3,背包问题,一只背包最大装载重量为,50,公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价值如下表所示：,要在背包中装入这三种物品各多少件，使背包中的物品价值最高,。,第1,节,线性规划的,数学模型及相关概念,物品,1,物品,2,物品,3,10,17,重量（公斤,/,件）价值（元,/,件）,41,72,20,35,x,1,x,2,x,3,8一 现实中的线性规划问题及模型例2-3 背包问题第1节,8,9,第1,节,线性规划的,数学模型及相关概念,z,=17,x,1,+72,x,2,+35,x,3,max,10,x,1,+,41,x,2,+,20,x,3,50,s.t.,x,1,，,x,2,，,x,3,0,且为整数,求解这个线性规划，可以得到最优解为：,x,1,=1 x,2,=0 x,3,=2,最,高价值,为,z=87,（元）,一,现实中的,线性规划问题及模型,9第1节 线性规划的数学模型及相关概念z=17x1+,9,10,一,现实中的,线性规划问题及模型,例,2-4,最小费用流问题,某公司下设两个分工厂，两个仓库及一个配送中心。其中,F,1,和,F,2,是两个工厂，,W,1,和,W,2,是两个仓库。,D,是一个分销中心。由工厂生产的产品经由图所示的运输网络运往仓库。每一条路线运输的单位成本在线段上给出，其中，,F,1,F,2,与,D,W,2,路线由于受到路线中的桥梁承重上限的要求，因此有最大运输量限制。其他路线有足够的运输能力来运输两个工厂生产的货物。需要制订的决策是关于每一条路线应该运输多少，目标是总体的运输成本最小化。,第1,节,线性规划的,数学模型及相关概念,10一 现实中的线性规划问题及模型例2-4 最小费用流问,10,11,一,现实中的,线性规划问题及模型,例,2-4,最小费用流问题,第1,节,线性规划的,数学模型及相关概念,900,元,/,单位,x,6,100,元,/,单位,x,7,最多,80,单位,x,4,x,5,x,2,x,3,x,1,300,元,/,单位,300,元,/,单位,F1,需求,30,单位,W1,生产,40,单位,F2,需求,60,单位,W2,200,元,/,单位,D,最多,10,单位,200,元,/,单位,400,元,/,单位,图,2-1,公司的配送网络,生产,50,单位,11一 现实中的线性规划问题及模型例2-4 最小费用流问,11,12,第1,节,线性规划的,数学模型及相关概念,z,=200,x,1,+400,x,2,+900,x,3,+300,x,4,+100,x,5,+3,x,6,+200,x,7,min,x,1,+,x,2,+,x,3,=,50,s.t.,x,1,，,，,x,7,0,-x,1,+,x,4,=40,-,x,2,-,x,4,+,x,5,=0,-,x,3,+,x,6,x,7,=-30,求解这个线性规划，可以得到最优解为：,（,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,，,x,7,）,=,（,0,，,40,，,10,，,40,，,80,，,0,，,20,）,z=49000,（元）,一,现实中的,线性规划问题及模型,-,x,5,-,x,6,+,x,7,=-60,x,1,10,，,x,5,80,12第1节 线性规划的数学模型及相关概念z=200 x1,12,13,线性规划的一般形式,一般,LP,模型的,三类参数,：,价值系数,c,j,，,消耗系数,a,ij,，,右端常数,b,i,.,LP,模型的,三要素,：,决策变量,，,目标函数,，,约束条件,.,s.t.,max(min),z=c,1,x,1,+,c,2,x,2,+,c,3,x,3,+,+,c,n,x,n,a,11,x,1,+,a,12,x,2,+,+,a,1n,x,n,(=),b,1,a,21,x,1,+,a,22,x,2,+,+,a,2n,x,n,(=),b,2,a,m1,x,1,+,a,m2,x,2,+,+,a,mn,x,n,(=),b,m,x,j,(,或,)0,或自由,j,=,1,2,n,第1,节,线性规划的,数学模型及相关概念,一,现实中的,线性规划问题及模型,13线性规划的一般形式 一般LP模型的三类参数：s.t.m,13,14,线性规划的向量和矩阵的表达形式,记向量和矩阵,第1,节,线性规划的,数学模型及相关概念,一,现实中的,线性规划问题及模型,则线性规划问题可以表示为：,max,（,min)z,=,CX,s.t.,AX,(=)b,X 0,14线性规划的向量和矩阵的表达形式记向量和矩阵第1节 线性规,14,15,二、线性规划的标准形式,称以下线性规划的形式为标准形式,max,z,=,c,1,x,1,+,c,2,x,2,+,c,3,x,3,+,+,c,n,x,n,s.t.,a,11,x,1,+,a,12,x,2,+,+,a,1n,x,n,=,b,1,(,0,),a,21,x,1,+,a,22,x,2,+,+,a,2n,x,n,=,b,2,(,0,),a,m1,x,1,+,a,m2,x,2,+,+,a,mn,x,n,=,b,m,(,0,),x,1,x,2,x,n,0,简记为：,max z,=,CX,s.t.,AX,=,b,X 0,(,M,1,):,(,M,2,):,第1,节,线性规划的,数学模型及相关概念,15二、线性规划的标准形式称以下线性规划的形式为标准形式ma,15,16,非标准形,LP,问题的标准化,一、极小化目标函数的问题,min z,=,CX,令,z,=,z,max z,=,CX,例,：,min z,=,3,x,1,2,x,2,max z,=,3,x,1,2,x,2,二、约束条件不是等式的问题,b,i,0,两边同时乘以,-,1,约束为形式 加上,松弛变量,约束为形式 减去,剩余变量,三、变量符号无限制或小于等于零的问题,若,x,k,为,自由变量,令,x,k,=,x,k,x,k,且,x,k,x,k,0,若,x,k,0,令,x,k,=,x,k,则,x,k,0,第1,节,线性规划的,数学模型及相关概念,二、线性规划的标准形式,x,z,z,z,min,z,=-z,z,max,x*,16非标准形LP问题的标准化第1节 线性规划的数学模型及相关,16,17,min z,=,2,x,1,3,x,2,x,3,x,1,x,2,2,x,