非线性规划和动态规划

非线性规划问题v线性规划和整数规划它们的目标函数和约束条件都是自变量的线性函数，在实际中还有大量的问题，其目标函数或约束条件很难用线性函数来表示。如果目标函数或约束条件中含有非线性函数，则称这种规划问题为非线性规划问题。1二次规划模型二次规划模型问题1 容器设计问题某公司生产贮藏用容器，订货合同要求该公司制造一种敞口的长方体容器，容积为12立方米，该容器的底为正方形，容器总重量不超过68公斤。已知用作容器四壁的材料为每平方米10元，重3公斤；用作容器底的材料每平方米20元，重2公斤。试问制造该容器所需的最小费用是多少？2模型建立 设该容器的底边长和高分别为则问题的数学模型为则问题的数学模型为 3v在LINGO中求解：vmin=40*x1*x2+20*x12;vx12*x2=12;v12*x1*x2+2*x12=68;v得到x1=2.690416,x2=1.657839,min f=323.17784v用lingo求解：vmax=30*x1+450*x2;v0.5*x1+2*x2+0.25*x22=800;vgin(x1);vgin(x2);v得到x1=1495,x2=11,max f=49800 5v线性规划：lindo/lingov非线性规划：lingov二次规划：lingov整数规划：lindo/lingov0-1整数规划：lindo/lingo6第四节第四节 动态规划动态规划（Dynamic Programming)动动 态态 规规 划划 是是 1951年年 由由 美美 国国 数数 学学 家家 贝贝 尔尔 曼曼（Richard Bellman)提提出出，它它是是解解决决一一类类多多阶阶段段决决策策问问题题的的优优化化方方法法，也也是是考考察察问问题题的的一一种种途途径径，而而不不是是一一种种算算法法（如如LP单单纯纯形形法法）。因因此此它它不不象象LP那那样样有有一一个个标标准准的的数数学学表表达达式式和和明明确确定定义义的的一组规则，而必须对具体问题进行具体分析处理。一组规则，而必须对具体问题进行具体分析处理。动动态态规规划划方方法法是是现现代代企企业业管管理理中中的的一一种种重重要要决决策策方方法法。如如果果一一个个问问题题可可将将其其过过程程划划分分为为若若干干个个相相互互联联系系的的阶阶段段问问题题，且且它它的的每每一一阶阶段段都都需需进进行行决决策策，则则这这类类问问题题均均可可用用动动态态规规划划方法进行求解。方法进行求解。根根据据多多阶阶段段决决策策过过程程的的时时序序和和决决策策过过程程的的演演变变，动动态态规规划划方方法法有有以以下下四四种种类类型型：离离散散确确定定型型、离离散散随随机机型型、连连续续确确定定型和连续随机型型和连续随机型。7一一 动态规划的基本概念和最优化原理动态规划的基本概念和最优化原理1、引例（最短路问题）、引例（最短路问题）假如上图是一个线路网络，两点之间连线上的数字表示假如上图是一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），我们的问题是要将货物从两点间的距离（或费用），我们的问题是要将货物从A地运地运往往E地，中间通过地，中间通过B、C、D三个区域，在区域内有多条路径三个区域，在区域内有多条路径可走，现求一条由可走，现求一条由A到到E的线路，使总距离最短（或总费用的线路，使总距离最短（或总费用最小）。最小）。AB1B2B3C1C2C3D1D2E243746324265346333348 将将该该问问题题划划分分为为4个个阶阶段段的的决决策策问问题题，即即第第一一阶阶段段为为从从A到到Bj（j=1，2，3），有有三三种种决决策策方方案案可可供供选选择择；第第二二阶阶段段为为从从Bj到到Cj（j=1,2,3），也也有有三三种种方方案案可可供供选选择择；第第三三阶阶段段为为从从Cj到到Dj(j=1,2)，有有两两种种方方案案可可供供选选择择；第第四四阶阶段段为为从从Dj到到E，只只有有一一种种方方案案选选择择。如如果果用用完完全全枚枚举举法法，则则可可供供选选择择的的路路线线有有3321=18（条条），将将其其一一一一比比较较才才可可找找出出最短路线：最短路线：AB1C2D3E 其长度为其长度为12。显显然然，这这种种方方法法是是不不经经济济的的，特特别别是是当当阶阶段段数数很很多多，各各阶阶段段可可供供的的选选择择也也很很多多时时，这这种种解解法法甚甚至至在在计计算算机机上上完完成成也是不现实的。也是不现实的。由由于于我我们们考考虑虑的的是是从从全全局局上上解解决决求求A到到E的的最最短短路路问问题题，而而不不是是就就某某一一阶阶段段解解决决最最短短路路线线，因因此此可可考考虑虑从从最最后后一一阶阶段开始计算，由后向前逐步推至段开始计算，由后向前逐步推至A点：点：9第四阶段，由第四阶段，由D1到到E只有一条路线，其长度只有一条路线，其长度f4（D1）=3，同理同理f4（D2）=4。第三阶段，由第三阶段，由Cj到到Di分别均有两种选择，即分别均有两种选择，即，决策点为D1,决 策 点 为D1，决策点为D210第二阶段，由Bj到Cj分别均有三种选择，即：决策点为C2 决策点为C1或C2决策点为C2 11第一阶段，由A到B，有三种选择，即：决策点为B3 f1（A）=12说明从A到E的最短距离为12，最短路线的确定可按计算顺序反推而得。即AB3C2D2E 12