第二章2_整数规划1.ppt

数学模型电子教案 重庆邮电大学 数理学院 虞继敏 第二章 规划论模型 第三节 非线性规划模型 5、计算结果 一、动态规划的基本思想 （二）、动态规划的基本思想 三、投资分配问题 四、背包问题 五、排序问题 k=5，出发点E1、E2、E3 u5(E1)=F1 E1 F1 G A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 6 8 3 5 3 3 8 4 2 2 1 2 3 3 3 5 5 2 6 6 4 3 u5(E2)=F2 E2 F2 G u5(E3)=F2 E3 F2 G k=6, F1 G f6(F1)=4 F2 G ,f6(F2)=3 k=4， f4(D1)=7 u4(D1)=E2 f4(D2)=6 u4(D2)=E2 f4(D3)=8 u4(D3)=E2 k=2, f2(B1)=13 u2(B1)=C2 f2(B2)=16 u2(B2)=C3 f3(C1)=13 u3(C1)=D1 f3(C2)=10 u3(C2)=D1 f3(C3)=9 u3(C3)=D1 f3(C4)=12 u3(C4)=D3 k=3, = min f1(A)= min d1(A,B1)+ f2(B1) d1(A,B2)+ f2(B2) 5+13 3+16 =18 k=1, u1(A)=B1 u2(B1)=C2 u3(C2)=D1 u4(D1)=E2 u1(A)=B1 u2(B1)=C2 u3(C2)=D1 u4(D1)=E2 u5(E1)=F1 E1 F1 G u5(E2)=F2 E2 F2 G u5(E3)=F2 E3 F2 G 7 5 9 u5(E2)=F2 u6(F2)=G 最优策略 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 3 6 8 5 3 3 8 4 2 2 2 1 3 3 3 5 2 5 6 6 4 3 求从A到E的最短路径 路线为A→B2→C1 →D1 →E ，最短路径为19 A B2 B1 B3 C1 C3 D1 D2 E C2 5 2 14 1 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 练习2： 1 现有数量为a（万元）的资金，计划分配给n 个工厂,用于扩大再生产。 假设：xi 为分配给第i 个工厂的资金数量（万元） ；gi(xi)为第i 个工厂得到资金后提供的利润值（万元）。 问题是如何确定各工厂的资金数，使得总的利润为最大。 据此，有下式： 令：fk(x) = 以数量为x 的资金分配给前k 个工厂，所得到的最大利润值。 用动态规划求解，就是求 fn(a) 的问题。 当 k=1 时， f1(x) = g1(x) （因为只给一个工厂） 当1＜k≤n 时，其递推关系如下： 设：y 为分给第k 个工厂的资金（其中 0≤y ≤ x ），此时还剩 x － y（万元）的资金需要分配给前 k-1 个工厂,如果采取最优策略，则得到的最大利润为fk－1(x－y) ,因此总的利润为： gk(y) ＋ fk－1(x－y) 如果a 是以万元为资金分配单位，则式中的y 只取非负整数0，1，2，…，x。上式可变为： 所以，根据动态规划的最优化原理，有下式： 例题： 设国家拨给60万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。 70 65 60 50 40 25 0 g4(x) 115 110 100 85 60 25 0 g3(x) 65 60 55 50 40 20 0 g2(x) 85 85 80 65 50 20 0 g1(x) 60 50 40 30 20 10 0 投资 利润 解：依据题意，是要求 f4(60) 。 1、写成标准形式： s.t. 2x1+3x2 6 s.t x1+4x2 5 x1,x2 0 例2 2、先建立M-文件 fun3.m: function f=fun3(x); f=-x(1)-2*x(2)+(1/2)*x(1