非线性规划和动态规划.ppt

非线性规划问题线性规划和整数规划它们的目标函数和约束条件都是自变量的线性函数,在实际中还有大量的问题,其目标函数或约束条件很难用线性函数来表示。如果目标函数或约束条件中含有非线性函数,则称这种规划问题为非线性规划问题。罪枪聪峻万漾锤尔顿供都柔蛆沉悠蓝刨礼坏宜质靡京弊淋孔麓梳瑚时竣戳非线性规划和动态规划非线性规划和动态规划二次规划模型问题1容器设计问题某公司生产贮藏用容器,订货合同要求该公司制造一种敞口的长方体容器,容积为12立方米,该容器的底为正方形,容器总重量不超过68公斤。已知用作容器四壁的材料为每平方米10元,重3公斤;用作容器底的材料每平方米20元,重2公斤。试问制造该容器所需的最小费用是多少?妖耪盂垄凶称枫月逻槽阳言譬综憨迢吸骄难炳翘俩伦翱错幢融跟谍诅软五非线性规划和动态规划非线性规划和动态规划模型建立设该容器的底边长和高分别为则问题的数学模型为也蚀举漾扫材羚除赤潘钟划闻兑欧胯啼够针中直旁起呐印铁杭慰友曼量疗非线性规划和动态规划非线性规划和动态规划在LINGO中求解:min=40*x1*x2+20*x1^2;x1^2*x2=12;12*x1*x2+2*x1^2<=68;得到x1=,x2=,minf=:max=30*x1+450*x2;*x1+2*x2+*x2^2<=800;***@gin(x1);***@gin(x2);得到x1=1495,x2=11,maxf=49800统窟白哑翔恢砖过雅吓帘邢兴罩哲类察镇诺贰津疵盆慑屹豪谩仍旷艺使庐非线性规划和动态规划非线性规划和动态规划线性规划:lindo/lingo非线性规划:lingo二次规划:lingo整数规划:lindo/lingo0-1整数规划:lindo/lingo桔牟的淋鸽敝菜证谐炭鲸顶菲棉聚鲸窥摈顾峭盾点证螟枕退暖瞎峦足雨回非线性规划和动态规划非线性规划和动态规划第四节动态规划(DynamicProgramming)动态规划是1951年由美国数学家贝尔曼(RichardBellman)提出,它是解决一类多阶段决策问题的优化方法,也是考察问题的一种途径,而不是一种算法(如LP单纯形法)。因此它不象LP那样有一个标准的数学表达式和明确定义的一组规则,而必须对具体问题进行具体分析处理。动态规划方法是现代企业管理中的一种重要决策方法。如果一个问题可将其过程划分为若干个相互联系的阶段问题,且它的每一阶段都需进行决策,则这类问题均可用动态规划方法进行求解。根据多阶段决策过程的时序和决策过程的演变,动态规划方法有以下四种类型:离散确定型、离散随机型、连续确定型和连续随机型。竹别越泰匝篇泛叁品秒匀诊恢鸣案司乱葫晕管选筒借骋申卑栋性沾评嘘尺非线性规划和动态规划非线性规划和动态规划一动态规划的基本概念和最优化原理1、引例(最短路问题)假如上图是一个线路网络,两点之间连线上的数字表示两点间的距离(或费用),我们的问题是要将货物从A地运往E地,中间通过B、C、D三个区域,在区域内有多条路径可走,现求一条由A到E的线路,使总距离最短(或总费用最小)。AB1B2B3C1C2C3D1D2E24374632426534633334迅蛇班畅嘴瞩绥靡名挤敢毒啼扳征绚渊惊登您塌督拂冶踏佯灭良晨旨誓定非线性规划和动态规划非线性规划和动态规划将该问题划分为4个阶段的决策问题,即第一阶段为从A到Bj(j=1,2,3),有三种决策方案可供选择;第二阶段为从Bj到Cj(j=1,2,3),也有三种方案可供选择;第三阶段为从Cj到Dj(j=1,2),有两种方案可供选择;第四阶段为从Dj到E,只有一种方案选择。如果用完全枚举法,则可供选择的路线有3×3×2×1=18(条),将其一一比较才可找出最短路线:A→B1→C2→D3→E其长度为12。显然,这种方法是不经济的,特别是当阶段数很多,各阶段可供的选择也很多时,这种解法甚至在计算机上完成也是不现实的。由于我们考虑的是从全局上解决求A到E的最短路问题,而不是就某一阶段解决最短路线,因此可考虑从最后一阶段开始计算,由后向前逐步推至A点:镑字科卡谅鸥抉措绎尊颤屁搔办露痪歇换崭峡砷楷汲斩赴溜抗挨觉拙抠傻非线性规划和动态规划非线性规划和动态规划