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

,第 1 节,Linear Programming,L P,线性规划,的数学模型,第1节 线性规划的数学模型及相关概念,2,一、现实中的线性规划问题及数学模型二、线性规划的标准形式三、线性规划的几何解释 四、线性规划的基及基本可行解,第1节 线性规划的数学模型及相关概念,3,一 现实中的线性规划问题及模型,例2-1 生产计划问题某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如表2-1所示，试用线性规划制订使总利润最大的生产计划。,第1节 线性规划的数学模型及相关概念,1.05.03.0,2.41.03.5,1.03.51.0,4,一 现实中的线性规划问题及模型,z,x1 x2 x3 x4,决策变量,z=5.24x1+7.30 x2+8.34x3+4.18x4,max,0,目标函数,1.5x1+1.0 x2+2.4x3+1.0 x4 2000,函数约束,非负性约束,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.05.03.0,2.41.03.5,1.03.51.0,5,一 现实中的线性规划问题及模型,第1节 线性规划的数学模型及相关概念,求解这个线性规划，可以得到最优解为：x1=294.12（件）x2=1500（件）x3=0（件）x4=58.82（件）最大利润为z=12737.06（元）请注意最优解中利润率最高的产品丙在最优生产计划中不安排生产。说明按产品利润率大小为优先次序来安排生产计划的方法有很大局限性。尤其当产品品种很多，设备类型很多的情况下，用手工方法安排生产计划很难获得满意的结果。,6,一 现实中的线性规划问题及模型,例2-2 配料问题某工厂要用四种合金T1，T2，T3和T4为原料，经熔炼成为一种新的不锈钢G。这四种原料含元素铬（Cr），锰（Mn）和镍（Ni）的含量（%），这四种原料的单价以及新的不锈钢材料G所要求的Cr，Mn和Ni的最低含量（%）如下表所示：设熔炼时重量没有损耗，要熔炼成100公斤不锈钢G，应选用原料T1，T2，T3和T4各多少公斤，使成本最小。,第1节 线性规划的数学模型及相关概念,4.531.123.06,2.193.574.27,1.764.332.73,x1 x2 x3 x4,7,第1节 线性规划的数学模型及相关概念,z=115x1+97x2+82x3+76x4,min,0.0321x1+0.0453x2+0.0219x3+0.0176x4 3.20,s.t.,x1，x2，x3，x4 0,0.0204x1+0.0112x2+0.0357x3+0.0433x4 2.10,0.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-3 背包问题一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价值如下表所示：要在背包中装入这三种物品各多少件，使背包中的物品价值最高。,第1节 线性规划的数学模型及相关概念,4172,2035,x1 x2 x3,9,第1节 线性规划的数学模型及相关概念,z=17x1+72x2+35x3,max,10 x1+41x2+20 x3 50,s.t.,x1，x2，x3 0 且为整数,求解这个线性规划，可以得到最优解为：x1=1 x2=0 x3=2 最高价值为 z=87（元）,一 现实中的线性规划问题及模型,10,一 现实中的线性规划问题及模型,例2-4 最小费用流问题 某公司下设两个分工厂，两个仓库及一个配送中心。其中F1和F2是两个工厂，W1和W2是两个仓库。D是一个分销中心。由工厂生产的产品经由图所示的运输网络运往仓库。每一条路线运输的单位成本在线段上给出，其中，F1F2与DW2路线由于受到路线中的桥梁承重上限的要求，因此有最大运输量限制。其他路线有足够的运输能力来运输两个工厂生产的货物。需要制订的决策是关于每一条路线应该运输多少，目标是总体的运输成本最小化。,第1节 线性规划的数学模型及相关概念,11,一 现实中的线性规划问题及模型,例2-4 最小费用流问题,第1节 线性规划的数学模型及相关概念,生产50单位,12,第1节 线性规划的数学模型及相关概念,z=200 x1+400 x2+900 x3+300 x4+100 x5+3x6+200 x7,min,x1+x2+x3=50,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 80,13,线性规划的一般形式,一般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,或自由,j=1,2,n,第1节 线性规划的数学模型及相关概念,一 现实中的线性规划问题及模型,14,线性规划的向量和矩阵的表达形式,记向量和矩阵,第1节 线性规划的数学模型及相关概念,一 现实中的线性规划问题及模型,则线性规划问题可以表示为：,max（min)z=CX,s.t.,AX(=)b,X 0,15,二、线性规划的标准形式,称以下线性规划的形式为标准形式,max z=c1x1+c2x2+c3x3+cnxn,s.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=xk,则 xk 0,第1节 线性规划的数学模型及相关概念,二、线性规划的标准形式,x,z,z,zmin,z=-z,z max,x*,17,第1节 线性规划的数学模型及相关概念,例2-5 将下述LP问题化成标准形式,解：令z=-z，x2=x2 x2，x3=-x3,max z=2 x1 3 x2-3x2 x3 x1 x2+x2 2 x3+x4=3 2x1+3x2 3x2+x3 x5=5 x1+x2 x2 x3=4 x1,x2,x2,x3,x4,x5 0,s.t.,二、线性规划的标准形式,第1章 线性规划的数学模型及相关概念,18,解:,max z=x1 2x2 3x3,s.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章 线性规划的数学模型及相关概念,19,令,x2=x2 x2，且 x2，x2 0,x3=-x3,代入上式中，得,二、线性规划的标准形式,第1节 线性规划的基本性质,20,只有两个变量的线性规划问题,X*=(4,6)T,z*=42,1画出可行域图形 2画出目标函数的 等值线及其法线 3确定最优点,x1=8,A(8,0),2x2=12,D(0,6),3x1+4x2=36,z=15,z=30,z 法向,z*=42,边界方程,三、线性规划的几何解释,第1节 线性规划的基本性质,21,几点说明实际运用时还须注意以下几点:(1)若函数约束原型就是等式,则其代表的区域仅为一直线,而且问 题的整个可行域R(若存在的话)也必然在此直线上。(2)在画目标函数等值线时只须画两条就能确定其法线方向,为此,只须赋给z 两个适当的值。(3)在找出最优点后,关于其坐标值有两种确定方法:在图上观测最优点坐标值 通过解方程组得出最优点坐标值,三、线性规划的几何解释,第1节 线性规划的基本性质,22,几种可能结果一、唯一解 如例1、例2都只有一个最优点，属于唯一解的情形。,二、多重解,z=12,z*=36,线段BC上无穷多个点均为最优解。,三、线性规划的几何解释,第1节 线性规划的基本性质,23,x1,x2,z*,三、无界解,R2,R1R2=,四、无可行解,+,R1,三、线性规划的几何解释,第1节 线性规划的基本性质,24,相关定义定义2-1 可行域在n维空间中，满足条件ai1x1+ai2x2+ain xn(=)bi且xj 0 的点集。,三、线性规划的几何解释,第1节 线性规划的基本性质,25,定义2-2 凸集,三、线性规划的几何解释,设S是n维空间中的一个点集。若对任意n维向量X1S，X2S，且X1X2，以及任意实数（01），有X=X1+(1-)X2S则称S为n维空间中的一个凸集（Convex Set）。点X称为点X1和X2的凸组合。,凸集：,非凸集：,第1节 线性规划的基本性质,26,定义2-3 凸集的极点,三、线性规划的几何解释,设S为一凸集，且XS，若X不能用不同的两点X1S，X2S的线性组合表示为X=X1+(1-)X2（01）则称X为S的一个极点。,运用以上的定义，线性规划的可行域以及最优解有以下性质：（1）若线性规划的可行域非空，则可行域必定为一凸集。（2）若线性规划有最优解，则最优解一定可以在凸集的极点中找到。这样，求线性规划最优解的问题，从在可行域内无限个可行解中搜索的问题转化为在其可行域的有限个极点上搜索的问题。,27,第1节 线性规划的数学模型及相关概念,基：设A为线性规划模型约束条件系数矩阵（m n，mn），而B为其mm子矩阵，若|B|0，则称B为该线性规划模型的一个基。,基变量：基中每个向量所对应的变量称为基变量。,非基变量：模型中基变量之外的变量称为非基变量。,基本解（基解）：令模型中所有非基变量X非基=0后，由模型约束方程组 n aijxj=bi(i=1,2,m)得到的一组解。j=1,基本可行解（基可行解）：在基本解中，同时又是可行解的解称为基本可行解。,可行基：对应于基本可行解的基称为可行基。,四、线性规划的基、基本可行解,-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 0,A=,x1 x2 x3 x4,1 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节 线性规划的数学模型及相关概念,四、线性规划的基、基本可行解,29,定理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个基。,30,第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 是基本可行解。,B(2,1),E(4,0),C(3,0),A(0,2),D(0,3),