《运筹学教程》胡云权 第五版 运筹学 --1线性规划--图解法

,第一章线性规划,运筹学,规划论,图论,排队论,存储论,对策论,决策论,线性规划,非线性规划,整数规划,动态规划,目标规划,一般线性规划,特殊线性规划,运筹学的分支,运筹学解决问题的过程,1）提出问题：认清问题。2）寻求可行方案：建模、求解。3）确定评估目标及方案的标准或方法、途径。4）评估各个方案：解的检验、灵敏性分析等。5）选择最优方案：决策。6）方案实施：回到实践中。7）事后评估：考察问题是否得到完满解决。,内容提要,线性规划问题及其数学模型线性规划解的概念、图解法线性规划应用建模单纯形法原理和Excel求解,第一章线性规划,问题的提出如何合理地利用有限的人、财、物等资源，得到最好的经济效果?,线性规划问题及数学模型,例1.1：某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数见下表：问题：工厂应如何安排生产可获得最大的总利润？,目标函数maxz=1500 x1+2500 x2约束条件s.t.3x1+2x2652x1+x2403x275x1,x20,这是一个典型的利润最大化的生产计划问题。,营养配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？,各种食物的营养成分表,10,解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：minS=14x1+6x2+3x3+2x4s.t.1000 x1+800 x2+900 x3+200 x4300050 x1+60 x2+20 x3+10 x455400 x1+200 x2+300 x3+500 x4800 x1，x2，x3，x40,线性规划数学模型的构成三要素,决策变量表示某种重要的可变因素，变量的一组数据代表一个解决的方案或措施，用x1,x2,xn表示目标函数决策变量的函数，目标可以是最大化或最小化约束条件对决策变量取值的限制条件，由决策变量x1,x2,xn的不等式组或方程组构成,max(min)z=c1x1+c2x2+cnxn,Subjectto（s.t.）a11x1+a12x2+a1nxn(=,)b1a21x1+a22x2+a2nxn(=,)b2.am1x1+am2x2+amnxn(=,)bmx1,x2,xn0,线性规划的一般形式,线性规划的简化形式,向量形式C=(c1,c2,cn)价值向量,资源向量,变量xj对应的系数列向量,线性规划的向量形式,矩阵形式,约束条件系数矩阵,线性规划的矩阵形式,maxz=c1x1+c2x2+cnxn,s.t.a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx1,x2,xn0其中bi0，i=1,2,m,线性规划的标准形式,标准形式,标准形式：用向量和矩阵表述,目标最大化约束为等式决策变量均非负右端项非负对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式。,线性规划的标准形四个特点,1目标函数求极小时,MinZ=3x1+6x24x1+8x2=9x1,x20,4x1+8x2=9x1,x20,标准形式为:,MaxZ=-3x1-6x2,-k,k,Z,Z,Z=-Z,非标准形式化为标准形,2约束条件时,MaxZ=x1+2x22x1+2x2=80 x1+2x2=4x1,x20,标准形为,MaxZ=x1+2x22x1+2x280 x1+2x24x1,x20,x30,x40,8,2x1,2x2,x3,X3为松弛变量,经济意义是没有被充分利用的资源数,X4也为松弛变量,经济意义是没有被充分利用的资源数,+x3,+0 x3,+x4,+0 x4,3约束条件时,MaxZ=2x1+5x26x1+3x224x1,x20,标准形为,MaxZ=2x1+5x26x1+3x2=24x1,x20,x30,-x3,+0 x3,24,6x1,3x2,x3,X3是剩余变量,或负松弛变量,经济意义是超用的资源数,4变量取值无约束时,MaxZ=3x1+7x22x1+6x2=8x10,x2取值无约束,设x20,x20,令x2=x2-x2,则MaxZ=3x1+7x2-7x22x1+6x2-6x2=8x10,x20,x20,5右端项有负值的问题在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bi0，则把该等式约束两端同时乘以-1，得到：-ai1x1-ai2x2-ainxn=-bi。,6xj0问题：令xj=-xj即可。,例：将以下线性规划问题转化为标准形式minf=-3x1+5x2+8x3-7x4s.t.2x1-3x2+5x3+6x4284x1+2x2+3x3-9x4396x2+2x3+3x4-58x1,x30,x40,maxz=3x15x2+5x2”8x3-7x4s.t.2x13x2+3x2”+5x3-6x4+x5=284x1+2x2-2x2”+3x3+9x4-x6=39-6x2+6x2”-2x3+3x4-x7=58x1,x2,x2”,x3,x4,x5,x6,x70,minf=-3x1+5x2+8x3-7x4s.t.2x1-3x2+5x3+6x4284x1+2x2+3x3-9x4396x2+2x3+3x4-58x1,x30,x40（原问题）,(标准型),练习,将下列线性规划问题化为标准形:MinZ=x1+2x2+3x34x1+5x2+6x3=-78x1+9x2+10 x31112x1+13x2+14x315x10,x20,x3取值无约束,作业,教材P43习题1.21.101.13建模1.14建模（1）,2.线性规划的求解,(1)图解法只适用两个变量（2）单纯型法适用多个变量,线性规划的图解法,对于只有两个变量的线性规划问题，可以二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。,MaxZ=x1+2x22x1+2x280 x1+2x24x1,x20,o,x1,x2,1234,4321,2x1+2x2=8,2x2=4,Z=2,Z=6,最优解为:x1=2,x2=2,例1,MinZ=x1+2x2x1+x21x1-x20 x1,x20,o,x1,x2,12,21,x1+x2=1,x1-x2=0,Z=2,Z=1.5,最优解为:x1=0.5,x2=0.5,例2,LP问题解的四种情况唯一最优解,33,MaxZ=x1+2x22x1+2x280 x1+2x24x1,x20,o,x1,x2,1234,4321,2x1+2x2=8,2x2=4,Z=2,Z=6,最优解为:x1=2,x2=2,例1,MaxZ=2x1+2x22x1+2x280 x1+2x24x1,x20,o,x1,x2,1234,4321,2x1+2x2=8,2x2=4,最优解有:1x1=2,x2=22x1=4,x2=0,Z=4,LP问题解的四种情况无穷多最优解,MaxZ=x1+x2x12x1,x20,2,x1,x2,x1=2,LP问题解的四种情况无界解(有可行解,无最优解),2,x1,x2,MaxZ=2x1+3x2x1+x22x1+x24x1,x20,4,LP问题解的四种情况无可行解,x1+x22,