运筹学教程胡云权 第五运筹学 线性规划图解法.pptx

《运筹学教程胡云权 第五运筹学 线性规划图解法.pptx》由会员分享，可在线阅读，更多相关《运筹学教程胡云权 第五运筹学 线性规划图解法.pptx（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学解决问题的过程1）提出问题：认清问题。2）寻求可行方案：建模、求解。3）确定评估目标及方案的标准或方法、途径。4）评估各个方案：解的检验、灵敏性分析等。5）选择最优方案：决策。6）方案实施：回到实践中。7）事后评估：考察问题是否得到完满解决。第1页/共38页 内容提要w线性规划问题及其数学模型w线性规划解的概念、图解法 w线性规划应用建模w单纯形法原理和Excel求解第一章 线性规划第2页/共38页问题的提出如何合理地利用有限的人、财、物等资源，得到最好的经济效果?线性规划问题及数学模型第3页/共38页 例1.1：某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需

2、要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数见下表：问题：工厂应如何安排生产可获得最大的总利润？产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）15002500第4页/共38页目标函数maxz=1500 x1+2500 x2约束条件s.t.3x1+2x2652x1+x2403x275x1,x2 0 这是一个典型的利润最大化的生产计划问题。第5页/共38页营养配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才

3、能在满足营养的前提下使购买食品的费用最小？第6页/共38页各种食物的营养成分表第7页/共38页8解：设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第8页/共38页线性规划数学模型的构成三要素决策变量表示某种重要的可变因素，变量的一组数据代表一个解决的方案或措施，用x1,x2,xn表示目标函数决策变量的函数，目标可以是最大化或最小化约束

4、条件对决策变量取值的限制条件，由决策变量 x1,x2,xn 的不等式组或方程组构成第9页/共38页max(min)z=c1x1+c2x2+cnxn Subjectto（s.t.）a11 x1+a12 x2+a1n xn (=,)b1a21 x1+a22 x2+a2n xn (=,)b2.am1 x1+am2x2+amn xn(=,)bm x1,x2,xn0线性规划的一般形式 第10页/共38页线性规划的简化形式 第11页/共38页向量形式C=(c1,c2,cn)价值向量,资源向量变量xj对应的系数列向量线性规划的向量形式 第12页/共38页矩阵形式约束条件系数矩阵线性规划的矩阵形式 第13页/

5、共38页maxz=c1x1+c2x2+cnxn s.t.a11x1+a12x2+a1n xn =b1a21x1+a22x2+a2n xn =b2am1x1+am2x2+amn xn=bmx1,x2,xn0其中bi0，i=1,2,m线性规划的标准形式第14页/共38页标准形式 第15页/共38页标准形式：用向量和矩阵表述 第16页/共38页目标最大化约束为等式决策变量均非负右端项非负 对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式。线性规划的标准形四个特点第17页/共38页1 目标函数求极小时MinZ=3x1+6x24x1+8x2=9x1,x204x1+8x2=9x

6、1,x20标准形式为:MaxZ=-3x1-6x2-kkZZZ=-Z非标准形式化为标准形第18页/共38页2 约束条件 时MaxZ=x1+2x22x1+2x2=80 x1+2x2=4x1,x20标准形为MaxZ=x1+2x22x1+2x280 x1+2x24x1,x20 x30 x4082x12x2x3X3为松弛变量,经济意义是没有被充分利用的资源数X4也为松弛变量,经济意义是没有被充分利用的资源数+x3+0 x3+x4+0 x4第19页/共38页 3 3 约束条件约束条件 时时Max Z=2x1+5x26x1+3x2 24x1,x2 0标准形为MaxZ=2x1+5x26x1+3x2=24x1,

7、x20 x30-x3+0 x3246x13x2x3X3是剩余变量,或负松弛变量,经济意义是超用的资源数第20页/共38页 4 变量取值无约束时Max Z=3x1+7x22x1+6x2=8x1 0,x2取值无约束设x2 0,x20,令x2=x2-x2,则MaxZ=3x1+7x2-7x22x1+6x2-6x2=8x10,x2 0,x2 0第21页/共38页5 右端项有负值的问题在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bi 0，则把该等式约束两端同时乘以-1，得到：-ai1 x1-ai2x2-ain xn=-bi。6 xj 0问题：令xj=-xj 即可。第22页/共3

8、8页例：将以下线性规划问题转化为标准形式 minf=-3x1+5x2+8x3-7x4s.t.2x1-3x2+5x3+6x4284x1+2x2+3x3-9x4396x2+2x3+3x4-58x1,x3 0,x40第23页/共38页 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,x70minf=-3x1+5x2+8x3-7x4s.t.2x1-3x2+5x3+6x4284x1+2x2+3x3-9x439

9、6x2+2x3+3x4-58x1,x3 0,x40（原问题）(标准型)第24页/共38页练习将下列线性规划问题化为标准形:MinZ=x1+2x2+3x34x1+5x2+6x3=-78x1+9x2+10 x31112x1+13x2+14x315x10,x20,x3取值无约束第25页/共38页作业教材P43 习题1.21.101.13建模1.14建模（1）第26页/共38页 2.线性规划的求解 (1)图解法只适用两个变量（2）单纯型法适用多个变量第27页/共38页 线性规划的图解法 对于只有两个变量的线性规划问题，可以二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。第28页/共38页Ma

10、xZ=x1+2x22x1+2x280 x1+2x24x1,x20ox1x2123443212x1+2x2=82x2=4Z=2Z=6最优解为:x1=2,x2=2例1第29页/共38页Min Z=x1+2x2x1+x2 1x1-x2 0 x1,x2 0ox1x21221x1+x2=1x1-x2=0Z=2Z=1.5最优解为:x1=0.5,x2=0.5例2第30页/共38页 LP问题解的四种情况 唯一最优解31MaxZ=x1+2x22x1+2x280 x1+2x24x1,x20ox1x2123443212x1+2x2=82x2=4Z=2Z=6最优解为:x1=2,x2=2例1第31页/共38页MaxZ=

11、2x1+2x22x1+2x280 x1+2x24x1,x20ox1x2123443212x1+2x2=82x2=4最优解有:1x1=2,x2=22x1=4,x2=0Z=4LP问题解的四种情况 无穷多最优解第32页/共38页MaxZ=x1+x2x12x1,x202x1x2x1=2LPLPLPLP问题解的四种情况问题解的四种情况问题解的四种情况问题解的四种情况无界解无界解(有可行解有可行解,无最优解无最优解)第33页/共38页2x1x2MaxZ=2x1+3x2x1+x22x1+x24x1,x204LPLP问题解的四种问题解的四种情况情况 无可行解无可行解x1+x22x1+x24第34页/共38页重要概念MaxZ=x1+2x22x1+2x280 x1+2x24x1,x20(x1,x2)=(1,1)(x1,x2)=(2,2)(x1,x2)=(0,0)第35页/共38页图解法步骤：1、建立直角坐标系2、图示约束条件，找出可行域或判别是否存在可行域3、图示目标函数和寻找最优解第36页/共38页作业教材P43 习题1.1 图解法求解第37页/共38页感谢您的观看！第38页/共38页