例4生产与库存问题(续)补充:动态规划 网络流中需求节点的流入和流出量导致这个模型成为一个转运模型(网络最 优化问题中的最小费用流问题) 我们通过建立一个流图来代表这个问题。首先根据4个季节建立4个产量节点 和4个需求节点。每个产量节点由一个流出弧连接对应的需求节点。弧的流量 代表了这时期所生产的毛毯。相对于每个需求节点,一个流出弧代表了库存 的数量,即供给下季度需求节点的数量。下图显示了这个网络模型。 决策变量:(图中弧的流量) 4个季度的生产量x(i=1,2,3,4), 生产节点 需求节点 前3个季度库存量R(i=1,2,3) 600G季度产量) 2 目标:MinC=2x+5x2+3x3+3x4+ →(1季度需求)400 0.25 0.25(R1+R2+R3) 300(季度产量)5Q季度需求 约束条件: 500 生产能力:x≤600,x2≤300, 0.25 x3≤500,x4≤400 500(3季度产量) 季度需求) 400第一季度需求:x1-R1=400 0.25 第二季度需求:x2+R1-R2=500 400(4季度产量) 1季度需求400 第三季度需求:x3+R2-R3=400 第四季度需求:x4+R3=400 非负:x;≥0|=1,2,3,4,R1≥0(=1,2,3) RuC Information School, Ye Xiang, 2007补充：动态规划 RUC Information School，Ye Xiang，2007 例4 生产与库存问题(续) • 网络流中需求节点的流入和流出量导致这个模型成为一个转运模型（网络最 优化问题中的最小费用流问题） • 我们通过建立一个流图来代表这个问题。首先根据4个季节建立4个产量节点 和4个需求节点。每个产量节点由一个流出弧连接对应的需求节点。弧的流量 代表了这时期所生产的毛毯。相对于每个需求节点，一个流出弧代表了库存 的数量，即供给下季度需求节点的数量。下图显示了这个网络模型。 1季度产量 3季度产量 2季度产量 4季度产量 生产节点 1季度需求 3季度需求 2季度需求 4季度需求 需求节点 600 300 500 400 400 500 400 400 2 5 3 3 0.25 0.25 0.25 决策变量：（图中弧的流量） 4个季度的生产量xi (i=1,2,3,4)， 前3个季度库存量Ri (i=1,2,3) 目标：Min C=2x1+5x2+3x3＋3x4＋ 0.25(R1+R2+R3 ) 约束条件： 生产能力： x1 600， x2300， x3 500， x4 400 第一季度需求： x1 － R1 ＝400 第二季度需求：x2 ＋R1 － R2 ＝500 第三季度需求：x3 ＋R2 － R3 ＝400 第四季度需求：x4 ＋R3 ＝400 非负： xi 0(i=1,2,3,4), Ri  0(i=1,2,3)