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

第第 1 1 页页运筹学第1页2024/3/26 周二2024/3/26 周二上海财经大学运运筹筹学学规划论图论排队论存储论对策论决策论线性规划非线性规划整数规划动态规划目标规划一般线性规划特殊线性规划运筹学的分支运筹学的分支第第 2 2 页页运筹学第2页2024/3/26 周二2024/3/26 周二上海财经大学运筹学解决问题的过程运筹学解决问题的过程1）提出问题：认清问题。）提出问题：认清问题。2）寻求可行方案：建模、求解。）寻求可行方案：建模、求解。3）确定评估目标及方案的标准或方法、途径。）确定评估目标及方案的标准或方法、途径。4）评估各个方案：解的检验、灵敏性分析等。）评估各个方案：解的检验、灵敏性分析等。5）选择最优方案：决策。）选择最优方案：决策。6）方案实施：回到实践中。）方案实施：回到实践中。7）事后评估：考察问题是否得到完满解决。）事后评估：考察问题是否得到完满解决。第第 3 3 页页运筹学第3页2024/3/26 周二2024/3/26 周二上海财经大学 内容提要w线性规划问题及其数学模型w线性规划解的概念、图解法 w线性规划应用建模w单纯形法原理和Excel求解第一章第一章线性规划线性规划第第 4 4 页页运筹学第4页2024/3/26 周二2024/3/26 周二上海财经大学问题的提出问题的提出如何合理地利用有限的人、财、物如何合理地利用有限的人、财、物等资源，得到最好的经济效果等资源，得到最好的经济效果?线性规划问题及数学模型线性规划问题及数学模型第第 5 5 页页运筹学第5页2024/3/26 周二2024/3/26 周二上海财经大学 例例1.1：某某工工厂厂拥拥有有A、B、C三三种种类类型型的的设设备备，生生产产甲甲、乙乙两两种种产产品品。每每件件产产品品在在生生产产中中需需要要占占用用的的设设备备机机时时数数，每每件件产品可以获得的利润以及三种设备可利用的时数见下表：产品可以获得的利润以及三种设备可利用的时数见下表：问题：工厂应如何安排生产可获得最大的总利润？问题：工厂应如何安排生产可获得最大的总利润？产品甲产品乙设备能力（h）设备A3265设备B2140设备C0375利润（元/件）15002500第第 6 6 页页运筹学第6页2024/3/26 周二2024/3/26 周二上海财经大学目标函数目标函数maxz=1500 x1+2500 x2约束条件约束条件s.t.3x1+2x2652x1+x2403x275x1,x2 0 这是一个典型的利润最大化的生产计划问题。第第 7 7 页页运筹学第7页2024/3/26 周二2024/3/26 周二上海财经大学营养营养配餐问题配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？第第 8 8 页页运筹学第8页2024/3/26 周二2024/3/26 周二上海财经大学各种食物的营养成分表第第 9 9 页页运筹学第9页2024/3/26 周二2024/3/26 周二上海财经大学9解：设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第第 1010 页页运筹学第10页2024/3/26 周二2024/3/26 周二上海财经大学线性规划数学模型的构成三要素线性规划数学模型的构成三要素决策变量决策变量表示某种重要的可变因素，变量的一组数据代表一个解决表示某种重要的可变因素，变量的一组数据代表一个解决的方案或措施，用的方案或措施，用x1,x2,xn表示表示目标函数目标函数决策变量的函数，目标可以是最大化或最小化决策变量的函数，目标可以是最大化或最小化约束条件约束条件对决策变量取值的限制条件，由决策变量对决策变量取值的限制条件，由决策变量x1,x2,xn的的不等式组或方程组构成不等式组或方程组构成第第 1111 页页运筹学第11页2024/3/26 周二2024/3/26 周二上海财经大学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线性规划的一般形式 第第 1212 页页运筹学第12页2024/3/26 周二2024/3/26 周二上海财经大学线性规划的简化形式 第第 1313 页页运筹学第13页2024/3/26 周二2024/3/26 周二上海财经大学向量形式向量形式C=(c1,c2,cn)价值向量价值向量,资源向量变量xj对应的系数列向量线性规划的向量形式 第第 1414 页页运筹学第14页2024/3/26 周二2024/3/26 周二上海财经大学矩阵形式矩阵形式约束条件系数矩阵线性规划的矩阵形式 第第 1515 页页运筹学第15页2024/3/26 周二2024/3/26 周二上海财经大学maxz=c1x1+c2x2+cnxn s.t.a11x1+a12x2+a1n xn =b1a21x1+a22x2+a2n xn =b2 am1x1+am2x2+amn xn=bmx1,x2,xn0其中bi 0，i=1,2,m线性规划的标准形式第第 1616 页页运筹学第16页2024/3/26 周二2024/3/26 周二上海财经大学标准形式 第第 1717 页页运筹学第17页2024/3/26 周二2024/3/26 周二上海财经大学标准形式：用向量和矩阵表述 第第 1818 页页运筹学第18页2024/3/26 周二2024/3/26 周二上海财经大学目标最大化约束为等式决策变量均非负右端项非负 对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式。线性规划的标准形四个特点第第 1919 页页运筹学第19页2024/3/26 周二2024/3/26 周二上海财经大学1 1 目标函数求极小时目标函数求极小时MinZ=3x1+6x24x1+8x2=9x1,x204x1+8x2=9x1,x20标准形式为:MaxZ=-3x1-6x2-kkZZZ=-Z非标准形式化为标准形第第 2020 页页运筹学第20页2024/3/26 周二2024/3/26 周二上海财经大学2 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第第 2121 页页运筹学第21页2024/3/26 周二2024/3/26 周二上海财经大学 3 3 约束条件约束条件 时时MaxZ=2x1+5x26x1+3x224x1,x20标准形为MaxZ=2x1+5x26x1+3x2=24x1,x20 x30-x3+0 x3246x13x2x3X3是剩余变量,或负松弛变量,经济意义是超用的资源数第第 2222 页页运筹学第22页2024/3/26 周二2024/3/26 周二上海财经大学 4 4 变量取值无约束时变量取值无约束时MaxZ=3x1+7x22x1+6x2=8x10,x2取值无约束取值无约束设x2 0,x20,令x2=x2-x2,则MaxZ=3x1+7x2-7x22x1+6x2-6x2=8x10,x2 0,x2 0第第 2323 页页运筹学第23页2024/3/26 周二2024/3/26 周二上海财经大学5 右端项有负值的问题在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bi 0，则把该等式约束两端同时乘以-1，得到：-ai1 x1-ai2x2-ain xn=-bi。6 xj 0问题：令xj=-xj 即可。第第 2424 页页运筹学第24页2024/3/26 周二2024/3/26 周二上海财经大学例：将以下线性规划问题转化为标准形式 minf=-3x1+5x2+8x3-7x4s.t.2x1-3x2+5x3+6x4284x1+2x2+3x3-9x4396x2+2x3+3x4-58x1,x3 0,x40第第 2525 页页运筹学第25页2024/3/26 周二2024/3/26 周二上海财经大学 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-9x4396x2+2x3+3x4-58x1,x3 0,x40（原问题）(标准型)第第 2626 页页运筹学第26页2024/3/26 周二2024/3/26 周二上海财经大学练习练习将下列线性规划问题化为标准形:MinZ=x1+2x2+3x34x1+5x2+6x3=-78x1+9x2+10 x31112x1+13x2+14x315x10,x20,x3取值无约束第第 2727 页页运筹学第27页2024/3/26 周二2024/3/26 周二上海财经大学作业作业教材教材P43习题习题1.21.101.13建模建模1.14建模（建模（1）第第 2828 页页运筹学第28页2024/3/26 周二2024/3/26 周二上海财经大学 2.2.线性规划的求解线性规划的求解 (1)(1)图解法图解法只适用两个变量只适用两个变量（2 2）单纯型法）单纯型法适用多个变量适用多个变量第第 2929 页页运筹学第29页2024/3/26 周二2024/3/26 周二上海财经大学 线性规划的图解法线性规划的图解法 对对于于只只有有两两个个变变量量的的线线性性规规划划问问题题，可可以以二二维维直直角角坐坐标标平平面面上上作作图图表表示示线线性性规规划问题的有关概念，并求解划问题的有关概念，并求解。第第 3030 页页运筹学第30页2024/3/26 周二2024/3/26 周二上海财经大学MaxZ=x1+2x22x1+2x280 x1+2x24x1,x20ox1x2123443212x1+2x2=82x2=4Z=2Z=6最优解为:x1=2,x2=2例例1 1第第 3131 页页运筹学第31页2024/3/26 周二2024/3/26 周二上海财经大学MinZ=x1+2x2x1+x21x1-x20 x1,x20ox1x21221x1+x2=1x1-x2=0Z=2Z=1.5最优解为:x1=0.5,x2=0.5例例2 2第第 3232 页页运筹学第32页2024/3/26 周二2024/3/26 周二上海财经大学LP问题解的四种情况问题解的四种情况唯一最优解唯一最优解32MaxZ=x1+2x22x1+2x280 x1+2x24x1,x20ox1x2123443212x1+2x2=82x2=4Z=2Z=6最优解为:x1=2,x2=2例1第第 3333 页页运筹学第33页2024/3/26 周二2024/3/26 周二上海财经大学MaxZ=2x1+2x22x1+2x280 x1+2x24x1,x20ox1x2123443212x1+2x2=82x2=4最优解有:1x1=2,x2=22x1=4,x2=0Z=4LP问题解的四种情况问题解的四种情况无穷多最优解无穷多最优解第第 3434 页页运筹学第34页2024/3/26 周二2024/3/26 周二上海财经大学MaxZ=x1+x2x12x1,x202x1x2x1=2LPLPLPLP问题解的四种情况问题解的四种情况问题解的四种情况问题解的四种情况无界解无界解无界解无界解(有可行解有可行解有可行解有可行解,无最优解无最优解无最优解无最优解)第第 3535 页页运筹学第35页2024/3/26 周二2024/3/26 周二上海财经大学2x1x2MaxZ=2x1+3x2x1+x22x1+x24x1,x204LPLP问题解的四种问题解的四种情况情况 无可行解无可行解x1+x22x1+x24第第 3636 页页运筹学第36页2024/3/26 周二2024/3/26 周二上海财经大学重要概念重要概念MaxZ=x1+2x22x1+2x280 x1+2x24x1,x20(x1,x2)=(1,1)(x1,x2)=(2,2)(x1,x2)=(0,0)第第 3737 页页运筹学第37页2024/3/26 周二2024/3/26 周二上海财经大学图解法步骤图解法步骤：1 1、建立、建立直角坐标系直角坐标系2 2、图示、图示约束条件约束条件，找出找出可行域或判别是否存在可行域可行域或判别是否存在可行域3 3、图示、图示目标函数和寻找最优解目标函数和寻找最优解第第 3838 页页运筹学第38页2024/3/26 周二2024/3/26 周二上海财经大学作业作业教材教材P43习题习题1.1图解法求解图解法求解