单纯形法的步骤ppt课件.ppt

《单纯形法的步骤ppt课件.ppt》由会员分享，可在线阅读，更多相关《单纯形法的步骤ppt课件.ppt（26页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能 数学既不严峻，也不遥远，她和数学既不严峻，也不遥远，她和几乎所有的人类活动有关，还让每个几乎所有的人类活动有关，还让每个对她感兴趣的人受益对她感兴趣的人受益。R.C.Buck 数学是理解世界及其发展的一把数学是理解世界及其发展的一把主要钥匙。主要钥匙。里约热内卢宣言上海交通大学数学科学学院上海交通大学数学科学学院数学实验数学实验为深入学习习近平新时代中国特色社会主义思想和党的十九

2、大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能合金工厂的生产规划合金工厂的生产规划为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能实际问题实际问题1 1为200kg、200kg和360kg.工厂生产每吨甲种合金 某合金工厂生产甲、乙两种合金，生产每吨甲种合金需用A元素20 kg、B元素40kg 和C元素90 kg

3、，而生产每吨乙种合金需用A元素100 kg、B元素80 kg和C元素60 kg.试问：应如何安排生产，才能获得最大利润？由于A、B、C三种元素都是原料市场上紧缺货品,工厂每月所能得到的这些元素的供应量分别利润为30万元，生产每吨乙种合金利润为40万元.为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能数学模型数学模型 设每月生产甲种合金 x1t，乙种合金 x2 t,x1,x2 满足约束条件线性规划问题求最优解利润为 u万元,那么

4、u=30 x1+40 x2 求何时有 max u=max(30 x1+40 x2)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能 二元一次方程 a1x1+a2x2=b 代表x1 x2平面图解法（回到问题图解法（回到问题1 1）a1x1+a2x2=ba1 x1+a2 x2 b则代表了以此直线为界的半平面而二元一次不等式a1x1+a2x2 b上的一条直线,为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新

5、时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能线性规划的容许集容许集 p Q R O S集.它是一个包含边界的凸多边形 OPQRSx1x2这问题中约束条件意味着五个半平面的交为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能x2 p Q R O S x1 30 x1+40 x2=u顶点时u再增将使直线离开容许集，则此临界状态直线所对应从图

6、看出最优解应为R点的增减，直线向右上或左下方平移.若直线经过容许集的某的u就是所求的最大值，此顶点的坐标就是问题的最优解将 u 视作参数，则30 x1+40 x2=u 代表一条直线，随着u 为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能 最优解在R点,由R是直线40 x1+80 x2=200与问题的解答问题的解答图解法的局限图解法的局限 画图并不方便，可以不画图而求出容许集所有直线90 x1+60 x2=360的交点,可得最优

7、解为x1=3.5,x2=0.75,此时有最大值为u=135.说明安排月生产甲、乙种合金分别为3.5 t、0.75t，才能获得最大利润135万元.较来求出最优解.但在约束条件多或多变量时，也的顶点，再将目标函数在这些顶点上的值加以比是难以做到的为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能单纯形法单纯形法的形式)若有最优解，其必定在容许集(在相应的 基本思路是：线性规划(通常是求最小值的几何空间中是一个凸多面体)的顶点达到，故从

8、某一个顶点出发，沿着凸多面体的棱向另一顶点迭代，使得目标函数的值下降,经过有限次迭代,将达到最优解点.为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能1.1.化标准型化标准型(1)把问题变为求在约束下的极小,(2)引进新变量,将约束中的不等式化为等式(除了变量xi非负)单纯形法的步骤单纯形法的步骤为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会

9、精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能 利用矩阵的初等变换来实现单纯形法x1x2x3 x4 x5 bi ix320100100 2002x44080010 200 2.5 x59060001 360630400000 从末一行非基变量取正系数最大者x2 为新基，由i=bi/(x2的各正系数)，最小者2，该行对应的x3 成 作初等变换主元变成1,这列其他系数变成0 选系数线性无关三个变量(x3,x4,x5)为基;用约束条件将目标函数写成仅含非基变量，列表末一行非基，交叉位的系数100 称主元主元;2.2.单纯形表单纯形表为深入学习习近平新时代中国特色社

10、会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能 这样得到的单纯形表(矩阵)为 x1x2 x3 x4 x5 bi i x2 1/51 1/100 0 0 2 10 x4240 -4/5 1 0 40 5/3 x5780 -3/5 0 1 240 120/39220 -2/3 0 0 -80是22，x1成新基;再看i=bi/(x1的正系数）其最小者5/3，所在行 再做初等变换主元变成1，这列其他系数变0 现在x2,x4,x5成为基,这次末一行正系数最大者对应 x

11、4成非基,24 成为主元主元为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能初等变换：先选末行初等变换：先选末行xi系数最大的列系数最大的列 算算(最小正最小正)定主元定主元为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能直至末行非基变量系数均负，对应表为x1x2

12、x3 x4 x5 bi i x2 01 0 3/160 -1/1203/4 x110 0 -1/80 1/60 7/2 x300 1 -13/8 1/2 5500 0 -3/8 -1/6 -135 这意味着目标函数显然在 x4=0,x5=0 时，v 最小，u 最大 单纯形法的计算是线性规划算法中极为重要为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能利用利用 Matlab linprog函数的一般语法：x,fval=linpro

13、g(f,A,b,Aeq,beq,lb,ub)其中：f为目标函数（注意是求极小值）A,b为A*x=b的不等式条件 Aeq,beq为Aeq*x=beq的等式条件 lb,ub为上下确界 x为最优解，fval为目标函数的值以上所有均以矩阵或向量形式表示为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能A=20 100;40 80;90 60;b=200,200,360;f=-30;-40;x,fval=linprog(f,A,b,0,0)

14、问题问题1 1的程序的程序Optimization terminated.x=3.5000 0.7500fval=-135.0000甲乙合金生产数目标函数的最小值为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能 MatlabMatlab不仅有处理线性规划的功能，而不仅有处理线性规划的功能，而且有处理非线性规划的功能（在工具箱且有处理非线性规划的功能（在工具箱optimization toolboxoptimization too

15、lbox）。关于线性规划的数学软件关于线性规划的数学软件 当当变变量量和和约约束束条条件件个个数数增增加加时时（数数百百甚甚至至数数千千个个是是“小小规规模模”的的，往往往往是是几几万万或或几几十万个），需要更有效的软件。十万个），需要更有效的软件。SoPlex,PCL SoPlex,PCL为免费软件为免费软件KarmarkerKarmarker算法（算法（BellBell实验室）实验室）收费收费为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小

16、学图书室育人功能某人有100万资金打算投资债券，现有三类债 实际问题实际问题 2 2投资决策投资决策券：债券A,一年期,年利率6%；债券B，二年期，年利率6.5%；债券C，三年期，年利率7.5%；债券A和B长期有售，但债券C隔年发售(现有售)且投资者对债券C每次投资不超过30万.问他应该 如何作连续投资使得在第五年末取得最大收益?为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能建立模型建立模型 设投资者在第i年投资于A、B、C债

17、券的数额依次 为xi1,xi2,xi3(万)，那么问题即求 约束条件：为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能改写目标利用利用MATLAB f=zeros(1,11);f(8,10,11)=-1.225;1.13;1.06;A=-1.06 0 0 1 1 0 0 0 0 0 0;0-1.13 0-1.06 0 1 1 1 0 0 0;0 0-1.225 0-1.13-1.06 0 0 1 1 0;0 0 0 0 0 0-

18、1.13 0-1.06 0 1;b=zeros(4,1);Aeq=1 1 1 0 0 0 0 0 0 0 0;beq=100;lb=zeros(11,1);ub=inf*ones(11,1);ub(3,8)=30;30;x,fval=linprog(f,A,b,Aeq,beq,lb,ub)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能Optimization terminated.x=15.1475 54.8525 30.00

19、00 0.0000 16.0563 14.4520 17.5314 30.0000 0.0000 70.2128 19.8104fval=-137.0895ABC第一年投资AB第二年投资ABC第三年投资 A B第四年投资 A 第五年投资最大收益(符号相反)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能要求整数条件的例子要求整数条件的例子某汽车厂生产小中大三类型的汽车，各类型每辆车对钢材、劳动时间的需求，利润及每月工厂钢材、劳动

20、时间的现有量如下表 小型小型 中型中型 大型大型现现有量有量钢钢材（吨）材（吨）1.5 3 51.5 3 5 600600劳动时间劳动时间（小（小时时）280 250 400280 250 400 60000 60000利利润润（万元）（万元）2 3 42 3 4试制定月生产计划，使工厂的利润最大.为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能模型与求解模型与求解用Matlab 求解可得到最优解问题 出现小数，显然不符合实际

21、在附近整数试探(注意符合条件)约束增加整数条件(整数规划，lingo)x1=64或65,x2=167或168为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能 数数学学规规划划是是运运筹筹学学和和管管理理科科学学中中应应用用极极广广泛泛的的分分支支，在在多多数数情情况况下下，数数学学规规划划的的使使用用如如此此成成功功以以致致它它超超出出运运筹筹学学的的范范畴畴，成成为为人们日常的规划工具人们日常的规划工具。关于数学规划关于数学规

22、划 数数学学规规划划包包括括线线性性规规划划，非非线线性性规规划划，整整数数规规划划，几几何何规规划划和和多多目目标标规规划划等等，每每个个规规划划包包含含无无数数的的实实例例，由由于于计计算算量量的的巨巨大大，算法问题是极为重要的。算法问题是极为重要的。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能实验任务实验任务本次任务选做教材中所附任务本次任务选做教材中所附任务必做题：必做题：1 1、4 4、5 5、7 7，其它可选做，其它可选做上海交通大学数学科学学院上海交通大学数学科学学院数学实验数学实验为深入学习习近平新时代中国特色社会主义思想和党的十九大精神为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神贯彻全国教育大会精神,充分发挥中小学图书室育人功能充分发挥中小学图书室育人功能谢谢各位！谢谢各位！