大学数学实验 基本内容 1.实例及其数学模型 Experiments in Mathematics 2.基本原理与解法 分枝定界法 实验9整数规划( Integer programming) 动态规划法 3.LIND0/LINc0软件的使用 半大歇教科系 实例1:选课问题 决策变量:x1(=1选修课程,=不选修课程 校规:学生每学期选修的总学分不能少于20,任选课 学分不能少于总学分的16,也不能超过总学分数的1/3 标函数:选修课程之和 限选课课号1234|5678 约東条件:选修课程i时必须选修课程j:x2x 分 Mi∑x yl,y2分别表示选修的限选课、任 同时选惨要求 选课的学分数,y表示总学分数 任选课课号91011121314151617s st.y1=5x+5x2+4x+4x4+3x+3x+3x2+2x 学分3332|221111 同时选修要求864576 规划=3+3x0+3x1+2x2+2x+2x++耳+x+x (种特y=+马+2 ≥20y≤6y2,y≥3y 本学期必修课只有一门(2学分);限选课有8门,任 殊整数 选课有10门,最少应该选几门课? 规划)x≥和x2不2,2耳1,石2耳 n=5x+52+4x1+4x4+3x+3x+3+2学 实例2:钢管下料 y2=3x+3x0+3x1+2x2+2x1+2x14+x1+x16+x17+x18 乃+y2 20,y≤6y2, 客户需求几 原料钢管:每根19米 x4≥x1, 8米 1P松弛问题流示 Course.LTX 线性规划(LP)最优解:(其他x为0) 问题1如何下料最节省?节省的标准是什么? x1=x2=x4=x11=1,x3=0.0833,x6=x10=0.111l 问题2.客户增加需求: 5米10 四會五入,选4门课程1/2/4/11,共19个学分,太少; 向上取整,选7门加3/6/10),共27个学分,太多? 由于采用不同切割模式太多,会增加生产和管理成 整数规划一般不能通过解LP松弛问题得到最优解 本,规定切割模式不能超过种。如何下料最节省?
1 大学数学实验 Experiments in Mathematics 实验9 整数规划 (Integer Programming) 清华大学数学科学系 基本内容 2. 基本原理与解法 3. LINDO / LINGO软件的使用 1. 实例及其数学模型 • 分枝定界法 • 动态规划法 实例1：选课问题 校规：学生每学期选修的总学分不能少于20，任选课 学分不能少于总学分的1/6，也不能超过总学分数的1/3 同时选修要求 8 6 4 5 7 6 学分 3 3 3 2 2 2 1 1 1 1 任选课课号 9 10 11 12 13 14 15 16 17 18 同时选修要求 1 2 学分 5 5 4 4 3 3 3 2 限选课课号 1 2 3 4 5 6 7 8 本学期必修课只有一门（2学分）；限选课有8门，任 选课有10门 ，最少应该选几门课？ {0,1} , , , , , , 2, 20, 6 , 3 3 3 3 2 2 2 . . 5 5 4 4 3 3 3 2 4 11 5 12 7 13 6 14 1 5 2 7 8 9 6 10 1 2 2 2 2 9 10 11 12 13 14 15 16 17 18 1 1 2 3 4 5 6 7 8 18 1 ∈ ≥ ≥ ≥ ≥ ≥ ≥ ≥ ≥ = + + ≥ ≤ ≥ = + + + + + + + + + = + + + + + + + ∑= i i i x x x x x x x x x x x x x x x x x y y y y y y y y y x x x x x x x x x x st y x x x x x x x x Min x 决策变量：xi （=1选修课程i，=0不选修课程i） 目标函数：选修课程之和 约束条件：选修课程 i 时必须选修课程 j ： xj ≥xi 0-1规划 (一种特 殊整数 规划) y1，y2 分别表示选修的限选课、任 选课的学分数，y 表示总学分数 线性规划（LP）最优解： （其他 xi 为0） x1 = x2 = x4 = x11 =1，x3 = 0.0833， x6 = x10 = 0.1111 {0,1} , , , , , , 2, 20, 6 , 3 3 3 3 2 2 2 5 5 4 4 3 3 3 2 4 11 5 12 7 13 6 14 1 5 2 7 8 9 6 10 1 2 2 2 2 9 10 11 12 13 14 15 16 17 18 1 1 2 3 4 5 6 7 8 ∈ ≥ ≥ ≥ ≥ ≥ ≥ ≥ ≥ = + + ≥ ≤ ≥ = + + + + + + + + + = + + + + + + + i x x x x x x x x x x x x x x x x x y y y y y y y y y x x x x x x x x x x y x x x x x x x x 0 ≤ xi ≤ 1 LP松弛问题 • 四舍五入，选4门课程 1/2/4/11，共19个学分, 太少； • 向上取整，选7门(加 3/6/10)，共27个学分，太多？ 整数规划一般不能通过解LP松弛问题得到最优解 演示： Course.LTX 问题1. 如何下料最节省 ? 实例2：钢管下料 问题2. 客户增加需求： 原料钢管:每根19米 4米50根 6米20根 8米15根 客户需求 节省的标准是什么？ 由于采用不同切割模式太多，会增加生产和管理成 本，规定切割模式不能超过3种。如何下料最节省？ 5米10根
X学酸学笑验 钢管下料 切割模式 钢管下料问题1合理切割模式 按照客户需要在一根原料钢管上安排切割的一种组合。 模式4米钢管根数6米钢管根数8米钢管根数余料米) 4米1根6米1根 8米1根 余料1米 米1根6米1根 6米根 余料3米 为满足客户需要,按照哪些种合理模式,每种模式 米1根 8米1根 余料3米 切割多少根原料钢管,最为节省 两种1.原料钢管剩余总余量最小 合理切割模式的余料应小于客户需要钢管的最小尺寸 标准2.所用原料钢管总根数最少 决策变量 x-按第i种模式切割的原料钢管根数(1,2,7 钢管下料问题1 目标1(总余量)Mm石=3x+x2+3x+3x1+x+x6+3x 当余料没有用处时,通常以总根数最少为目标 模式4米根数6米根数8米根数余料 目标2(总根数)Mi22=x1+x2+x3+x4+x5+x6+x 约束条件不变 x3+x3+2x2≥15 需求 为整数 约束 4x1+3x2+2x3+x4+x3≥50 满足需求+2x+x+3x≥20 数约束 以上两个模型均是一般整数线性规划 +x+2x≥15 为整数 (学学奖 钢管下料问题2 钢管下料问题2 增加一种需求:5米10根;切割模式不超过3种。 目标函数(总根数)inx1+x2+x3 现有4种需求:4米50根,5米10根,6米20根,8米 约束条件 15根,用枚举法确定合理切割模式,过于复杂。 满足需求 模式合理;每根 对大规模问题,用模型的约束条件界定合理模式 式x1+F2x2+Fx3≥50 余料不超过3米 F21x+2x2+F2x321016≤4r1+51+6r1+81≤19 决策变量 r3x1+r2x2+3x3≥2016≤412+52+6y2+82≤19 x-按第种模式切割的原料钢管根数(=1,23) r41x1+F2x2+r43x321516≤4r13+53+63+843≤19 r1pr2pr4-第i种切割模式下,每根原料钢管 整数约束:x,1pr2F4(=12,3)为整数 生产4米、5米、6米和8米长的钢管的数量 整数非线性规划
2 按照客户需要在一根原料钢管上安排切割的一种组合。 切割模式 4米1根 6米1根 8米1根 余料1米 4米1根 6米1根 6米1根 余料3米 合理切割模式的余料应小于客户需要钢管的最小尺寸 8米1根 8米1根 余料3米 钢管下料 为满足客户需要，按照哪些种合理模式，每种模式 切割多少根原料钢管，最为节省？ 合理切割模式 2. 所用原料钢管总根数最少 模式 4米钢管根数 6米钢管根数 8米钢管根数 余料(米) 1 4 0 0 3 2 3 1 0 1 3 2 0 1 3 4 1 2 0 3 5 1 1 1 1 6 0 3 0 1 7 0 0 2 3 钢管下料问题1 两种 标准 1. 原料钢管剩余总余量最小 xi ~按第i 种模式切割的原料钢管根数(i=1,2,…7) 约束 满足需求 决策变量 目标1（总余量） 1 1 2 3 4 5 6 7 Min Z = 3x + x +3x +3x + x + x +3x 4 3 2 50 x1 + x2 + x3 + x4 + x5 ≥ 2 3 20 x2 + x4 + x5 + x6 ≥ 2 15 x3 + x5 + x7 ≥ 模式 4米根数 6米根数 8米根数 余料 1 4 0 0 3 2 3 1 0 1 3 2 0 1 3 4 1 2 0 3 5 1 1 1 1 6 0 3 0 1 7 0 0 2 3 需求 50 20 15 整数约束： xi 为整数 以上两个模型均是一般整数线性规划 2 1 2 3 4 5 6 7 目标2（总根数） Min Z = x + x + x + x + x + x + x 钢管下料问题1 约束条件不变 4x1 + 3x2 + 2x3 + x4 + x5 ≥ 50 2 3 20 x2 + x4 + x5 + x6 ≥ x3 + x5 + 2x7 ≥ 15 xi 为整数 当余料没有用处时，通常以总根数最少为目标 钢管下料问题2 对大规模问题，用模型的约束条件界定合理模式 增加一种需求：5米10根；切割模式不超过3种。 现有4种需求：4米50根，5米10根，6米20根，8米 15根，用枚举法确定合理切割模式，过于复杂。 决策变量 xi ~按第i 种模式切割的原料钢管根数(i=1,2,3) r1i , r2i , r3i , r4i ~ 第i 种切割模式下，每根原料钢管 生产4米、5米、6米和8米长的钢管的数量 满足需求 50 r 11x1 +r 12x2 +r 13x3 ≥ 10 r21 x1 + r22 x2 + r23 x3 ≥ 20 r31x1 + r32 x2 + r33 x3 ≥ r41 x1 + r42 x2 + r43 x3 ≥ 15 模式合理：每根 余料不超过3米 16 4 5 6 8 19 ≤ r11 + r21 + r31 + r41 ≤ 16≤ 4r 12 +5r22 +6r32 +8r42 ≤19 16 ≤ 4r13 + 5r23 + 6r33 +8r43 ≤19 整数非线性规划 钢管下料问题2 目标函数（总根数） 1 2 3 Min x + x + x 约束条件 整数约束： xi ,r1i , r2i , r3i , r4i (i=1,2,3)为整数
实例3:饮料的生产批量问题 生产批量问题的一般提法 饮料厂使用同一条生产线轮流生产多种饮料。 c;时段生产费用(元/件);假设初始库存为 若某周开工生产某种饮料,需支出生产准备费3千元 h一时段(末)库存费(元/件);制订生产计划,满 某种饮料4周的需求量 s1时段生产准备费G元);足需求并使T个时 周次箭求量千箱 生产成本(可变成本) d时段t市场需求(件); 段的总费用最小 50元箱(50千元千箱) 决策变量 标mn==∑(sy+cx+h 存贮费 x-时段生产量; 每周每千箱饮料1千元 时段(末)库存量;约来11+x-1=d x>0, y2=1~时段开工生产 安排生产计划,满足每周的需求,使4周总费用最小。 y-10,x=0 (;=0~不开工)。 大学学实编) 生产批量问题的一般提法 网 整数规划问题一般形式 min f(x) mn二= s.h2(x)=0,i=1,…,m +x-l=d 分类 8,(x)≤0,j=1,…, 1,x>0, M是一个充分大的正数 y=0,1 (这里可取M=11) 整数线性规划(LP)目标和约束均为线性函数 l=lr=0.x,1≥0 整数非线性规划INLP目标或约束中存在非线性函数 混合非线性0-1规划? 混合线性0-1规划 纯(全整数规划(PP)决策变量均为整数 混合整数规划(MIP)决策变量有整数,也有实数 0-1规划决策变量只取0或1 (学学奖 整数规划问题对应的松弛问题 整数规划问题对应的松弛问题 取消整数规划中决策变量为整数的限制〔松弛),对 应的连续优化问题称为原问题的松弛问题 对松弛问题的最优解(分量)舍入为整数,得到的往 往不是原整数规划问题的最优解(甚至不是可行解) 整数规划问题 最优解 松弛 非最优解 最 整数 目标函数下降方向 松弛问题 优 →非整教舍入一→整数 原问题 下界(对Min问题) IP可行解对应于整点A(2,2)和B(1,1),而最优解为A点 松弛 上界(对Ma问题) 但IP松弛的最优解为c(35,2.5)
3 实例3： 饮料的生产批量问题 • 安排生产计划, 满足每周的需求, 使4周总费用最小。 生产成本（可变成本）: 50元/箱 (50千元/千箱) 存 贮 费: 每周每千箱饮料1千元 饮料厂使用同一条生产线轮流生产多种饮料。 若某周开工生产某种饮料, 需支出生产准备费3千元。 某种饮料4周的需求量 周次 需求量(千箱) 1 2 2 3 3 2 4 4 合计 11 生产批量问题的一般提法 ct ~时段t 生产费用(元/件)； ht ~时段t (末)库存费(元/件)； st ~时段t 生产准备费(元)； dt ~时段t 市场需求(件)； 假设初始库存为0 制订生产计划, 满 足需求,并使T个时 段的总费用最小。 t t t t I + x − I = d −1 min ( ) 1 t t t t t T t t z =∑ s y + c x + h I = 0, , 0 I0 = IT = xt It ≥ ⎩ ⎨ ⎧ = > = 0, 0, 1, 0, t t t x x y 决策变量 xt ~时段t 生产量； It ~时段t (末)库存量； yt =1 ~时段t 开工生产 (yt =0 ~不开工)。 目标 约束 混合线性0-1规划 0,1. 0 = − ≤ t t t y x My 生产批量问题的一般提法 t t t t I + x − I = d −1 0, , 0 I0 = IT = xt It ≥ ⎩ ⎨ ⎧ = > = 0, 0, 1, 0, t t t x x y min ( ) 1 t t t t t T t t z =∑ s y + c x + h I = M是一个充分大的正数 （这里可取M= 11） 混合非线性0-1规划？ 整数规划问题一般形式 g x j l s t h x i m f x j i x Z n ( ) 0, 1,..., . . ( ) 0, 1,..., min ( ) ≤ = = = ∈ • 整数线性规划(ILP) 目标和约束均为线性函数 • 整数非线性规划(INLP) 目标或约束中存在非线性函数 • 纯(全)整数规划(PIP) 决策变量均为整数 • 混合整数规划(MIP) 决策变量有整数，也有实数 • 0-1规划 决策变量只取0或1 分 类 取消整数规划中决策变量为整数的限制（松弛），对 应的连续优化问题称为原问题的松弛问题 整数规划问题对应的松弛问题 松弛问题 松 弛 整数规划问题 最优解 最 优 解 整数 非整数 舍入 整数 下界（对Min问题） 上界（对Max问题） 非最优解 原问题 松弛 对松弛问题的最优解（分量）舍入为整数，得到的往 往不是原整数规划问题的最优解（甚至不是可行解） IP可行解对应于整点A(2,2)和B(1,1),而最优解为A点. 但LP松弛的最优解为C(3.5,2.5) 目标函数下降方向 x1 x2 C A B O 整数规划问题对应的松弛问题
max ==5x +8x, 整数规划的分枝定界法 s.x1+x2≤6 BB: Branch and Bound 5x1+9x2≤45 基本思想:隐式地枚举一切可行解(“分而治之”) x1,x20且为整数 所谓分枝,就是逐次对解空间〔可行域)进行划分;而 去掉整数限制后,可行域为点(0,0),(6,0),(0,5), 所谓定界,是指对于每个分枝(或称子域),要计算原 P(225375)国成的4边形 问题的最优解的下界(对极小化问题).这些下界用来 在求解过程中判定是否需要对目前的分枝进一步划分 LP最优解PP的含入解最靠近P的可行解P最优解 也就是尽可能去掉一些明显的非最优点,避免完全枚举 (225,3.75)(2,4) z=4125 对于极小化问题,在子域上解LP,其最优值是IP限定 从LP最优解经过简单的“移动不一定得到P最优解 在该子域时的下界;IP任意可行点的函数值是IP的上界 线性 IP min 2=cx 分枝定界算法-例mn:=x-为 s.Ax=b,x≥0(P0) s1.2x1-x2≥ 2x1+x2≤ 线性规划松弛定界A∈Zmx,m≤n (P0 该问题的P松弛解为x=(,), x2≥ 若在某一时刻,得到一个全整数解的费用为乙m,则乙m 不是整数解最优值为。=4 为原问题的一个上界 QP1):(P0)加上x22 否则得该分枝的一个下界,继续分枝 为:少 dr= b 不是整数解最优值为=3.5 P3):(P1)加上x222 P)x2:1P2)x1 P4):(P1)加上x2≤1 x∈Z (学学奖 P0=(,3),z4 分枝定界算法QMin问题 x=(2引),z=7/2 STEP.令 actives{0(原问题:U-; currentbest=0. P1 STEPI如果 activeset=2,则已经得到原问题的最优解,结束;否 则从活跃分枝点集合 activeset中选择一个分枝点k;将k从 去掉继续STEP2 =-13/4 STEP生成k的各分枝产12…,n4及其对应的下界z 无可行解 STEP3对分枝12…,n4:如果分枝i得到的是全整数解且 x°=(21)y EU则令U=且 currentbest响如果分枝i得到的不是全整数 无可行解 解且x<U则把i加入 actveset中 STEP4.转STEP1
4 , 0 且为整数 5 9 45 . . 6 max 5 8 1 2 1 2 1 2 1 2 ≥ + ≤ + ≤ = + x x x x st x x z x x ． ． ． ． ． ． ．． ． ． ． ． ． ． ． ． ． ． ． x1 x2 0 oP 6 9 Zmax 5 6 去掉整数限制后，可行域为点（0,0), (6,0), (0,5), P (2.25,3.75) 围成的4边形 LP 最优解P P 的舍入解 最靠近P 的可行解 IP 最优解 （2.25，3.75） （2，4） （2，3） （0，5） z=41.25 不可行 z=34 z=40 从LP最优解经过简单的 “移动”不一定得到IP最优解 基本思想：隐式地枚举一切可行解（“分而治之”） 所谓分枝，就是逐次对解空间（可行域）进行划分；而 所谓定界，是指对于每个分枝（或称子域），要计算原 问题的最优解的下界（对极小化问题）. 这些下界用来 在求解过程中判定是否需要对目前的分枝进一步划分， 也就是尽可能去掉一些明显的非最优点，避免完全枚举. 整数规划的分枝定界法 （BB: Branch and Bound） 对于极小化问题，在子域上解LP，其最优值是IP限定 在该子域时的下界；IP任意可行点的函数值是IP的上界 线性规划松弛定界 若在某一时刻，得到一个全整数解的费用为zm，则zm 为原问题的一个上界; 否则得该分枝的一个下界，继续分枝． （P1） ⎣ ⎦ n i i T x Z x x x st Ax b c x ∈ ≥ + ≥ = 1 0 . . min 0 （P2） ⎣ ⎦ n i i T x Z x x x st Ax b c x ∈ ≤ ≥ = 0 0 . . min A Z m n s t Ax b x P z c x m n T ∈ ≤ = ≥ = × , . . , 0 ( 0) 线性IP min 分枝定界算法 – 例 （P0） + ∈ ≥ + ≤ − ≥ = − − x x Z x x x st x x z x x 1 2 2 1 2 2 11 1 2 2 1 1 2 1 2 , 2 . . 2 min 该问题的LP松弛解为 , 不是整数解,最优值为z0=-4. (P1): (P0)加上 ; (P2): (P0)加上 . T x ( , )2 5 2 0 3 = 2 x1 ≥ 1 x1 ≤ 问题(P1)的LP松弛解为 , 不是整数解,最优值为z1=-3.5 (P3): (P1)加上 ; (P4): (P1)加上 . T x (2, )2 1 3 = x2 ≥ 2 1 x2 ≤ P0 P1 P2 x1 ≥ 2 1 x1 ≤ P3 P4 2 x2 ≥ x2 ≤ 1 P5 P6 3 x1 ≥ x1≤2 T , x x (2,1) * 6 = = 6 3 * z =z =− 无可行解 P0 P1 P2 P3 P4 2 x1≥ x1 ≤1 2 x2 ≥ x2 ≤1 T x ( , )2 5 2 0 3 = , z0=-4 T x (2, )2 1 3 = , z1=-7/2 T x ( ,1) 4 4 9 = z0=-13/4 T x (2,1) 6 = z0=-3 无可行解 T x (1, ) 2 2 3 = z2=-2.5 > z6 分枝定界算法(Min问题) STEP4. 转STEP1. STEP0. 令activeset={0}(原问题);U = ∞；currentbest=0. STEP1. 如果 activeset=∅, 则已经得到原问题的最优解, 结束; 否 则从活跃分枝点集合 activeset 中选择一个分枝点 k ；将 k 从 activeset中去掉, 继续STEP2. STEP2. 生成 k 的各分枝 i=1,2,…,nk 及其对应的下界zi . STEP3.对分枝 i=1,2,…,nk : 如果分枝 i 得到的是全整数解且 zi <U, 则令 U=zi 且 currentbest=i；如果分枝 i 得到的不是全整数 解且zi <U, 则把 i 加入activeset中
整数规划的动态规划法 最优化原理 例:最短路问题求各点到T的最短路 “全过程的最优策略具有这样的性质:不管该最优 策略上某状态以前的状态和决策如何,对该状态而 言,余下的诸决策必定构成最优子策略.”即:最优策 略的任一后部子策略都是最优的 这只是最优性定理的一个推论,即最优策略的必 要条件 L()=min(cn+L()节点到节点r的最短路长 最优子结构〔 Optimal Substructure) An optimal solution to the problem contains within it L(T)=0 递推计算 optimal solutions to subproblems. 建立动态规划模型的基本过程 动态规划基本方程 逆序递推41 1)正确划分阶段,选择阶段变量k (2)对每个阶段,正确选择状态变量x选择状态变 x世xx 量时应当注意两点:一是要能够正确描述受控过程的 演变特性,二是要满足无后效性 f(x1)f2(x2) f(x1) fa(r,) (3)对每个阶段,正确选择决策变量k f(x)表示第k阶段初始状态为x时 (4)列出相邻阶段的状态转移方程:xk+=T(x,uA) k后部子过程阶段kk+1,,n)的最优准则函数 (5)列出按阶段可分的准则函数vm J(x2=mirv(e, 4)+H(xe+) Lm(xn)=0(边界条件)x41=7(x2L4) 假设问题的目标是极小化 (学学奖 (学学 应用动态规划方法的几个例子 少共有M个工厂,可以把问题分解为N个阶段: 资源分配问题:某公司现有M台设备准备分配给该公 司所属的N家工厂.当分配台u设备给工厂A时,工厂k 当阶段kN时,把手中设备分配给工厂N; 利用这些设备为公司创造的利润(假设非负)为gA(u) 当阶段k=N-1时,把手中设备分配给工厂N1; 如何分配设备资源,使得公司总利润最大? 依次类推; 当阶段k=1时,把手中设备分配给工厂 max:=∑8(4) 状态变量x-第阶段初分配者手中拥有的设备台数 由题意可知x=M,xN=0 决策变量a:第A阶段分配给工厂k的设备台数0≤叫≤x ∈z 状态转移方程 可能是非线性整数规划,甚至gA(u4)没有显式表达式 阶段的准则函数为"(x1,41)=8(a4)
5 整数规划的动态规划法 例：最短路问题 求各点到T的最短路 5 6 7 7 4 9 6 8 6 5 8 3 3 6 C1 B1 C2 B2 A1 A2 A3 T S 6 ( ) 节点i到节点T 的最短路长 ( ) 0 ( ) min ( ) ( , ) = = + ∈ L T L i c L j ij i j A 递推计算 “全过程的最优策略具有这样的性质：不管该最优 策略上某状态以前的状态和决策如何，对该状态而 言，余下的诸决策必定构成最优子策略. ”即：最优策 略的任一后部子策略都是最优的. 这只是最优性定理的一个推论，即最优策略的必 要条件. 最优化原理 最优子结构（Optimal Substructure）: An optimal solution to the problem contains within it optimal solutions to subproblems. （1） 正确划分阶段，选择阶段变量k. （2） 对每个阶段，正确选择状态变量xk. 选择状态变 量时应当注意两点：一是要能够正确描述受控过程的 演变特性，二是要满足无后效性. （3） 对每个阶段，正确选择决策变量uk . （4） 列出相邻阶段的状态转移方程： xk+1= Tk(xk, uk). （5） 列出按阶段可分的准则函数V1,n . 假设问题的目标是极小化 建立动态规划模型的基本过程 逆序递推 k=1 k=2 k k=n 1 x 2 x 3 x k+1 x n+1 x k x n x ( ) 1 1 f x 1 u 2 u k u n u ( ) 2 2 f x ( ) k k f x ( ) n n f x ⎩ ⎨ ⎧ = = + + + + + ∈ ( ) 0 (边界条件） ( ) min[ ( , ) ( )] 1 1 1 1 n n k k k k k u U k k f x f x v x u f x k k ( , ) k 1 k k uk x =T x + fk(xk)表示第 k 阶段初始状态为xk时， k后部子过程(阶段k,k+1,…,n)的最优准则函数 动态规划基本方程 资源分配问题： 某公司现有M台设备准备分配给该公 司所属的N家工厂. 当分配台uk设备给工厂k时，工厂k 利用这些设备为公司创造的利润（假设非负）为gk(uk). 如何分配设备资源，使得公司总利润最大？ 可能是非线性整数规划, 甚至gk(uk)没有显式表达式 应用动态规划方法的几个例子 + = = ∈ = = ∑ ∑ u Z st u M z g u k k N k k N k k 1 1 . . max ( ) ( ) k k g u k u 工厂k 设备数 1 2 3 0 1 2 3 4 0 4 6 7 7 0 2 5 6 8 0 3 5 7 8 状态变量xk - 第k阶段初分配者手中拥有的设备台数. 由题意可知 x0 = M， xN+1 = 0 阶段的准则函数为 共有N个工厂，可以把问题分解为N个阶段： 当阶段k=N时，把手中设备分配给工厂N； 当阶段k=N-1时，把手中设备分配给工厂N-1； 依次类推； 当阶段k=1时，把手中设备分配给工厂1. 决策变量uk：第k阶段分配给工厂k的设备台数 k k 0 ≤ u ≤ x 状态转移方程 k k u k x +1 = x − ( , ) ( ) k k uk gk uk v x =