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

非线性规划问题

线性规划和整数规划它们的目标函数和约束条件都是自变量的线性函数，在实际中还有大量的问题，其目标函数或约束条件很难用线性函数来表示。如果目标函数或约束条件中含有非线性函数，则称这种规划问题为非线性规划问题。321

问题1容器设计问题某公司生产贮藏用容器，订货合同要求该公司制造一种敞口的长方体容器，容积为12立方米，该容器的底为正方形，容器总重量不超过68公斤。已知用作容器四壁的材料为每平方米10元，重3公斤；用作容器底的材料每平方米20元，重2公斤。试问制造该容器所需的最小费用是多少？

模型建立设该容器的底边长和高分别为01则问题的数学模型为02

在LINGO中求解：min=40*x1*x2+20*x1^2;x1^2*x2=12;12*x1*x2+2*x1^2=68;得到x1=2.690416,x2=1.657839,minf=323.1778

01用lingo求解：02max=30*x1+450*x2;035*x1+2*x2+0.25*x2^2=800;04@gin(x1);05@gin(x2);06得到x1=1495,x2=11,maxf=49800

线性规划：lindo/lingo非线性规划：lingo二次规划：lingo整数规划：lindo/lingo0-1整数规划：lindo/lingo

第四节动态规划

（DynamicProgramming)动态规划是1951年由美国数学家贝尔曼（RichardBellman)提出，它是解决一类多阶段决策问题的优化方法，也是考察问题的一种途径，而不是一种算法（如LP单纯形法）。因此它不象LP那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。动态规划方法是现代企业管理中的一种重要决策方法。如果一个问题可将其过程划分为若干个相互联系的阶段问题，且它的每一阶段都需进行决策，则这类问题均可用动态规划方法进行求解。根据多阶段决策过程的时序和决策过程的演变，动态规划方法有以下四种类型：离散确定型、离散随机型、连续确定型和连续随机型。010302

一动态规划的基本概念和最优化原理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点：

第四阶段，由D1到E只有一条路线，其长度f4（D1）=3，同理f4（D2）=4。第三阶段，由Cj到Di分别均有两种选择，即，决策点为D1,决策点为D1，决策点为D2

第二阶段，由Bj到Cj分别均有三种选择，即：决策点为C1或C2决策点为C2决策点为C2

决策点为B3f1（A）=12说明从A到E的最短距离为12，最短路线的确定可按计算顺序反推而得。即A→B3→C2→D2→E第一阶段，由A到B，有三种选择，即：