大学数学实验 基本内容 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 =
(大学数学实验 资源分配问题 资源分配问题 用x表示将手中资源x分配给工厂k,k+1…,N时的 k-2Bf /(2)=ma [82 (u )+f,(x, )1= max [&, (u,)+/(r2-,) 最大利润,原问题即为计算f(M) 0)=maxg2(a2)+f2(0-2)=g2(0)+f(0)=0+0=0 f(x4)=max[8k(a4)+fk+(xk+)k=N,N-1,…,1, 0=m4g:{)+(-吗2月=mg:0+f(g20+(O fx+(x+)= max0+32+0=3 (2)=mayg:(a2)+f(2-)=mag:0)+f(28:0)+f(g2(2)+0 具体计算(例) M=4,N=3,边界条件∫(x小=f0)=0 f03)=muNg2{a2)+f(3-n2 axg2(0)+f(3g2(1)+f(2)g2(2)+f(g2(3)+f(0) k=3A:f(x)=maNg, (u,)+/(0)]=8,(x, 增函数) max0+7,2+55+35+0}=8 (4)=mNg)+4一月 f0)=8:(0=0f(1)=8(1)=3f3(2)=83(2)=5 =mg2(0)+f(4),g2()+f(3),g2(2)+f1(2)g2(3)+f(D),g2(4)+f(0) f(3)=g()=7,J(4)=85(4)=8 max0+82+75+5,6+38+0=10 大学学实编) 资源分配问题 klRt /(,)=max[g, (u, )+/2 (x2 )] max[g,(u,)+f2(x-1) 应用动态规划方法解整数规划 实例3:单产品、无能力限制的批量问题 m8(4)+f(4-4月 maxg(0)+f2(4),81(1)+f2(3),81(2)+f2(2g1(3)+f2(281(4)+f2(0 max80+10,4+8,6+5,7+3,7+0=12. min=∑(sy,+cx+h) 最优解n=12=24=1,最大利润为:=f1(4)=12 5.ln+x1-l1=d1,t=1,2,…,T, 推广:非线性整数规划问题,如 min==x2 +2x2+4x2 l。=0, x1,x2,x3∈z g(a2)=42-5B (学学奖 大学费学买验 假设费用均非负,则在景优解中4“420,即多24=3(千元=50千元),=1(千元千件 可以证明:一定存在满足条件1x=01≤t≤T)的 d1=2d2=3d3=2d4=4(千件) 最优解 具体计算过程如下 可以只考虑x∈d1,d+d1n,…,d+d1n+…+d} f=3+50*4+0+0=203 用表示当t时段初始库存为0时,从时段到T时段的 f=min{3+502+4)+1*4+0,3+50*2+0+11}=306 子问题的最优费用值 =min43+50(3+2+4)+1(2+4)+1*4+0,3+50(3+2)+1·2+11, 3+50*3+0+18}=458 f=min{3+502+3+2+4)+1(3+2+4)+1(2+4)+1*4+0 m,+c∑4+∑句+f可>0 3+2)+1(3+2)+1·2+11 +0(2+3)+1*3+18,3+50*2+0+26}=561 最优值(费用)为f X=(2,5,0,4)最优值为561(千元)
6 资源分配问题 用fk(xk) 表示将手中资源xk分配给工厂k,k+1,…, N 时的 最大利润，原问题即为计算 f1(M) M=4，N=3，边界条件 f4(x4) = f4(0) =0 ⎩ ⎨ ⎧ = = + = − + + + + ≤ ≤ ( ) 0. ( ) max [ ( ) ( )], , 1, ,1, 1 1 1 1 0 N N k k k k u x k k f x f x g u f x k N N k k L k=3时： （增函数） ( ) max[ ( ) (0)] ( ) 3 3 4 3 3 0 3 3 3 3 f x g u f g x u x = + = ≤ ≤ (0) (0) 0; f3 = g3 = (1) (1) 3; f3 = g3 = (2) (2) 5; f3 = g3 = (3) (3) 7; f3 = g3 = (4) (4) 8 f3 = g3 = 具体计算（例） k=2时： ( ) max [ ( ) ( )] max [ ( ) ( )] 2 2 3 2 2 0 2 2 3 3 0 2 2 2 2 2 2 f x g u f x g u f x u u x u x = + = + − ≤ ≤ ≤ ≤ (0) max[ ( ) (0 )] (0) (0) 0 0 0; 2 2 3 2 2 3 0 0 2 2 = + − = + = + = ≤ ≤ f g u f u g f u max{0 3,2 0} 3; (1) max[ ( ) (1 )] max{ (0) (1), (1) (0)} 2 2 3 2 2 3 2 3 0 1 2 2 = + + = = + − = + + ≤ ≤ f g u f u g f g f u max{0 5,2 3,5 0} 5; (2) max[ ( ) (2 )] max{ (0) (2), (1) (1), (2) (0)} 2 2 3 2 2 3 2 3 2 3 0 2 2 2 = + + + = = + − = + + + ≤ ≤ f g u f u g f g f g f u max{0 7,2 5,5 3,6 0} 8; max{ (0) (3), (1) (2), (2) (1), (3) (0)} (3) max[ ( ) (3 )] 2 3 2 3 2 3 2 3 2 2 3 2 0 3 2 2 = + + + + = = + + + + = + − ≤ ≤ g f g f g f g f f g u f u u max{0 8,2 7,5 5,6 3,8 0} 10; max{ (0) (4), (1) (3), (2) (2), (3) (1), (4) (0)} (4) max[ ( ) (4 )] 2 3 2 3 2 3 2 3 2 3 2 2 3 2 0 4 2 2 = + + + + + = = + + + + + = + − ≤ ≤ g f g f g f g f g f f g u f u u 资源分配问题 k=1时： ( ) max[ ( ) ( )] max[ ( ) ( )] 1 1 2 1 1 0 1 1 2 2 0 1 1 1 1 1 1 f x g u f x g u f x u u x u x = + = + − ≤ ≤ ≤ ≤ max{0 10,4 8,6 5,7 3,7 0} 12. max{ (0) (4), (1) (3), (2) (2), (3) (1), (4) (0)} (4) max[ ( ) (4 )] 1 2 1 2 1 2 1 2 1 2 1 1 2 1 0 4 1 1 = + + + + + = = + + + + + = + − ≤ ≤ g f g f g f g f g f f g u f u u 最优解 ,最大利润为 . 1, 2, 1 * 3 * 2 * u1 = u = u = (4) 12 1 * z = f = 推广：非线性整数规划问题，如： + ∈ + + = = + + − − − x x x Z st x x x z x x x x x x 1 2 3 1 2 3 1 2 3 2 3 2 2 2 1 , , . . 4 min 2 4 3 5 M=4, N=3 1 2 1 1 1 g (u ) = u − u 2 2 g2 (u2 ) = 2u2 −3u 3 2 g 3 (u3 ) = 4u3 − 5u 资源分配问题 应用动态规划方法解整数规划 , 0, 1,2, , . 0, 1,2, , , 0, 0, 1, 0, . . , 1,2, , , min ( ) 0 1 1 x I t T I t T x x y st I x I d t T z s y c x h I t t t t t t t t t t t t t t T t t L L L ≥ = = = ⎩ ⎨ ⎧ = > = + − = = = + + − = ∑ 实例3：单产品、无能力限制的批量问题 可以只考虑 可以证明：一定存在满足条件 的 最优解. 用ft 表示当t时段初始库存为0时，从t时段到T 时段的 子问题的最优费用值 最优值（费用）为 f1 . 假设费用均非负，则在最优解中 ，即 I 0 = IT = 0 ∑ ∑ = = = T t t T t xt d 1 1 0(1 ) It−1 xt = ≤ t ≤ T t { } dt dt dt dt dt dT x ∈ 0, , + +1,L, + +1 +L+ ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≤ ≤ ⎪ ⎩ ⎪ ⎨ ⎧ + + + > = = = ∑ ∑ ∑ − = + − = − = + ≤ ≤ + + + 1 . min [ ], 0, , 0. 0, 1 1 1 1 1 1 1 1 t T s c d d h f d f d f f t i t i j t i j i t t t i t T t t t T τ τ τ τ X=(2,5,0,4), 最优值为561（千元） T=4， （千元）， （千元）， （千元 st = 3 ct = 50 ht = 1 /千件） 2 (千件) d1 = d2 = 3 2 d3 = 4 d4 = 具体计算过程如下： f 5 = 0; f 4 = 3+50*4+0+0=203; f 3 = min{3+50(2+4)+1*4+0,3+50*2+0+11}=306; f 2 = min{3+50(3+2+4)+1(2+4)+1*4+0,3+50(3+2)+1*2+11, 3+50*3+0+18}=458; f 1 = min{3+50(2+3+2+4)+1(3+2+4)+1(2+4)+1*4+0, 3+50(2+3+2)+1(3+2)+1*2+11, 3+50(2+3)+1*3+18, 3+50*2+0+26} = 561
LIN0公司软件产品简要介绍 LIND0和LING软件能求解的优化模型 美国芝加哥 Chicago)大学的 Linus schrage教授于1980 年前后开发,后来成立 LINDO系统公司(L INDO 优化模型 SystemsInc),网址Ihttp://www.lindo.com 连续优化 整数规划(IP) LINGO: Linear INteractive General Optimizer LINDO API: LINDO Application Programming Interface (v2. 0) 线性规划二次规划非线性规划 What's BestI: (Spreadsheet e.g. EXCEL) NLP 演示(试用版、学生版、高级版、超级版、工业版 LINDO LINGO 扩展版.(求解问题规模和选件不同 例加工奶制品的生产计划 牛奶12小时13公斤A一获利24元公斤 4公斤A,→获利16元公斤 1桶 12小时132公 获利24元/公斤 牛奶 获利16元/公斤 每天50桶牛奶时间480小时至多加工100公斤A1 每天:50桶牛奶时间480小时至多加工100公斤A 决策变量x1桶牛奶生产A1x2桶牛奶生产A 目标函数获利24×3x1获利16×4x2 制订生产计划,使每天莪利最大 每天获利Max==72x1+64x2 35元可买到1桶牛奶,买吗?若买,每天最多买多少 线性 原料供应 x1+x2≤50 可聘用临时工人,付出的工资最多是每小时几元? 约束条件劳动时间12+8x25480模型 A1的获利增加到30元/公斤,应否改变生产计划? 加工能力 3x,≤100 (LP) 非负约束 x1,x220 (学学奖 大学费学买验 模型求解 x72x1+64x2 模型求解 reduced cost值表 OBJECTIVE FUNCTION VALUE OBJECTIVE FUNCTION VALUE 示当该非基变量 3360.000 2)xI+x2<50 3360.000 增加一个单位时 VARIABLE VALUE REDUCED COST 3)12x1+8x2<480 VARIABLE VALUE REDICED COST(其他非基变量 4)3xl<100 0.000000 保持不变)目标 0.000000 数减少的量(对 ROW SLACK OR SURPLUS DUAL PRICES ROW SLACK OR SURPLUS DUAL PRICES max型问题) DO RANGE 2)0.00000 ENSITIVITY 也可理解为 ANALYSIS? NO 为了使该非基变 000004 0.o00000 4000000 量变成基变量, NO. ITERATIONS= 目标函数中对应 20桶牛奶生产A1,30桶生产A2,利润360元。 系数应增加的量
7 LINDO 公司软件产品简要介绍 美国芝加哥(Chicago)大学的Linus Schrage教授于1980 年前后开发, 后来成立 LINDO系统公司（LINDO Systems Inc.）， 网址：http://www.lindo.com LINDO: Linear INteractive and Discrete Optimizer (V6.1) LINGO: Linear INteractive General Optimizer (V8.0) LINDO API: LINDO Application Programming Interface (V2.0) What’s Best!: (SpreadSheet e.g. EXCEL) (V7.0) 演示(试用)版、学生版、高级版、超级版、工业版、 扩展版… （求解问题规模和选件不同） LINDO和LINGO软件能求解的优化模型 LINDO LINGO 优化模型 线性规划 (LP) 非线性规划 (NLP) 二次规划 (QP) 连续优化 整数规划(IP) 例 加工奶制品的生产计划 1桶 牛奶 3公斤A1 12小时 8小时 4公斤A2 或 获利24元/公斤 获利16元/公斤 50桶牛奶 时间480小时 至多加工100公斤A1 制订生产计划，使每天获利最大 • 35元可买到1桶牛奶，买吗？若买，每天最多买多少? • 可聘用临时工人，付出的工资最多是每小时几元? • A1的获利增加到 30元/公斤，应否改变生产计划？ 每天： 1桶 牛奶 3公斤A1 12小时 8小时 4公斤A2 或 获利24元/公斤 获利16元/公斤 x1桶牛奶生产A1 x2桶牛奶生产A2 获利 24×3x1 获利 16×4 x2 原料供应 x1 + x2 ≤ 50 劳动时间 12 8 480 x1 + x2 ≤ 加工能力 3x1 ≤ 100 决策变量 目标函数 1 2 每天获利 Max z = 72x + 64x 约束条件 非负约束 x1 , x2 ≥ 0 线性 规划 模型 (LP) 时间480小时 至多加工100公斤A1 每天 50桶牛奶 模型求解 max 72x1+64x2 st 2）x1+x2<50 3）12x1+8x2<480 4）3x1<100 end OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2 DO RANGE (SENSITIVITY) ANALYSIS? No 20桶牛奶生产A1, 30桶生产A2，利润3360元。 Milk01.ltx 模型求解 reduced cost值表 示当该非基变量 增加一个单位时 （其他非基变量 保持不变）目标 函数减少的量(对 max型问题) OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2 也可理解为： 为了使该非基变 量变成基变量， 目标函数中对应 系数应增加的量
结果解释 结果解释 OBJECTIVE FUNCTION VALUE max 72x1-+6x2 最优解下“资源”增加1 1)3360.000 OBJECTIVE FUNCTION VALUE VARIABLE VAI REDUCED COST 2)x1+x2”(或“=”〔或“<”)功能相同 9.变量不能出现在一个约束条件的右端 变量与系数间可有空格甚至回车),但无运算符 10.表达式中不接受括号“()”和逗号“;”等任何符号,例 变量名以字母开头,不能超过8个字符 变量名不区分大小写(包括 LINDO中的关键字) 11.表达式应化简,如2X1+3X24X1应写成-2X1+3X2 5.目标函数所在行是第一行,第二行起为约束条件 12.缺省假定所有变量非负;可在模型的“END”语句 后用“ FREE name”将变量name的非负假定取消 6.行号(行名自动产生或人为定义。行名以“)”结束 13.可在“END”后用“SUB”或“SLB”设定变量上下界 行中注有“”符号的后面部分为注释。如 例如:“subx110”的作用等价于“x1<=10 8.在模型的任何地方都可以用“ TITLE”对模型命名 但用“SUB”和“SLB”表示的上下界约束不计入模型 的约束,也不能给出其松紧判断和敏感性分析。 (最多72个字符),如 14.“END”后对0-变量说明:INTn或 INT name TITLE This Model is only an Example 15.“END”后对整数变量说明;GINn或 gIN na
8 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 原料无剩余 时间无剩余 加工能力剩余40 max 72x1+64x2 st 2）x1+x2”（或“=”（或“<=”）功能相同 2. 变量与系数间可有空格(甚至回车), 但无运算符 3. 变量名以字母开头，不能超过8个字符 4. 变量名不区分大小写（包括LINDO中的关键字） 5. 目标函数所在行是第一行，第二行起为约束条件 6. 行号(行名)自动产生或人为定义。行名以“）”结束 7. 行中注有“!”符号的后面部分为注释。如: ! It’s Comment. 8. 在模型的任何地方都可以用“TITLE” 对模型命名 （最多72个字符），如： TITLE This Model is only an Example 9. 变量不能出现在一个约束条件的右端 10. 表达式中不接受括号“( )”和逗号“,”等任何符号, 例: 400(X1+X2)需写为400X1+400X2 11. 表达式应化简，如2X1+3X2- 4X1应写成 -2X1+3X2 12. 缺省假定所有变量非负；可在模型的“END”语句 后用“FREE name”将变量name的非负假定取消 13. 可在 “END”后用“SUB” 或“SLB” 设定变量上下界 例如： “sub x1 10”的作用等价于“x1<=10” 但用“SUB”和“SLB”表示的上下界约束不计入模型 的约束，也不能给出其松紧判断和敏感性分析。 14. “END”后对0-1变量说明：INT n 或 INT name 15. “END”后对整数变量说明：GIN n 或 GIN name 使用LINDO的一些注意事项
[注意]二次规划(QP)问题 实例2:钢管下料(问题1) LINDO可求解二次规划(QP)问题,但输入方式较 目标1(总余量)MZ1=3x1+x2+3x3+3x4+x5+x6+3 复杂,因为在 LINDO中不许出现非线性表达式 4x1+3x2+2x3+x4+x3≥50 民为、个度际约宽在实的对乘黄增加育关量的 x,+2x1+x4+3x≥20 阶最优条件,转化为互补问题 END”后面使用QCP命令指明实际约束开始的行号, x为整数 然后才能求解 建议总是用 LINGO解QP 最优解:x2=12,xs=15,其余为0; 最优值:27 注意对QP和P:敏感性分析意义不大 按模式2切割12根,按模式5切割15根,余料27米 实例2:钢管下料(问题1) LINGO软件简介 目标2(总根数)MmZ2=x+x2+x2+x+x3+x+x LⅠNGO模型的优点 最优解:x2=15, 4x1+3x2+2x3+x4+x5≥50 xs=5,x=5, 包含了 LINDO的全部功能,并能处理非线性优化 x2+2x4+x3+3x6220 其余为0; CUTOIb LTX 提供了灵活的编程语言(矩阵生成器 x3+x3+2x2≥15 最优值:25。 x为整数 LINGO模型的构成:4个段 按模式2切割15根, ·目标与约束段 按模 模式5切割5根 与目标1的结果“共切割27根 按模式7切劊根,余料27米”相比 ·集合段( SETS ENDSETS) 共25根,余料35米虽余料增加8米,但减少了2根 数据段( DATA ENDDATA) 当余料没有用处时,通常以总根数最少为目标 ·初始段( INIT ENDINIT) (学学奖 集合的类型 集合循环函数 tname [/member list/ 四个集合循环函数:FOR、SUM、MAX、MIN I: attribute list) @function( setname I( set index list)[ I condition): expression list): 派生集合基本集合 稀疏集合(密集合 2BENEFIT(LJ)MATCH(L,J/ 素列表法元素过滤法直接列举法)隐式列举法 objective! MAX=@SUM( PAIRS(L, J): BENEFIT( 1, D)* MATCH( L, D) ∑ MATCH(J,K)=1 (, AKPAlRC CITIES /AL, A2, A3, Bl, B2/ STUDENTS /IS8, 1, B2 AIRS STUDENT a FOR(STUDENTS( I) constraints ENDSETS aSUM( PAIRS( J, K)IJ#EQ# I #OR# K#EQ# 1: MATCH(J, K))=l)
9 [注意]二次规划(QP)问题 • LINDO可求解二次规划(QP)问题，但输入方式较 复杂，因为在LINDO中不许出现非线性表达式 – 需要为每一个实际约束增加一个对偶变量 （LAGRANGE乘子），在实际约束前增加有关变量的 一阶最优条件，转化为互补问题 – “END”后面使用QCP命令指明实际约束开始的行号， 然后才能求解 • 建议总是用LINGO解QP [注意]对QP和IP: 敏感性分析意义不大 目标1（总余量） 1 1 2 3 4 5 6 7 Min Z = 3x + x +3x +3x + x + x +3x 4x1 + 3x2 + 2x3 + x4 + x5 ≥ 50 2 3 20 x2 + x4 + x5 + x6 ≥ x3 + x5 + 2x7 ≥ 15 按模式2切割12根,按模式5切割15根，余料27米 最优解：x2=12, x5=15, 其余为0； 最优值：27 x CUT01a.LTX i 为整数 实例2：钢管下料(问题1) 当余料没有用处时，通常以总根数最少为目标 2 1 2 3 4 5 6 7 目标2（总根数） Min Z = x + x + x + x + x + x + x 最优解：x2=15, x5=5, x7=5, 其余为0； 最优值：25。 4x1 + 3x2 + 2x3 + x4 + x5 ≥ 50 2 3 20 x2 + x4 + x5 + x6 ≥ x3 + x5 + 2x7 ≥ 15 xi 为整数 按模式2切割15根， 按模式5切割5根， 按模式7切割5根， 共25根，余料35米 虽余料增加8米，但减少了2根 与目标1的结果“共切割27根， 余料27米” 相比: CUT01b.LTX 实例2：钢管下料(问题1) LINGO软件简介 • 目标与约束段 • 集合段（SETS ENDSETS） • 数据段（DATA ENDDATA） • 初始段（INIT ENDINIT） LINGO模型的构成：4个段 LINGO模型的优点 •包含了LINDO的全部功能，并能处理非线性优化 •提供了灵活的编程语言（矩阵生成器） 集合的类型 集合 派生集合 基本集合 稀疏集合 稠密集合 元素列表法 元素过滤法 直接列举法 隐式列举法 setname [/member_list/] [: attribute_list]; setname(parent_set_list) [/member_list/] [: attribute_list]; SETS: CITIES /A1,A2,A3,B1,B2/; ROADS(CITIES, CITIES)/ A1,B1 A1,B2 A2,B1 A3,B2/:D; ENDSETS SETS: STUDENTS /S1..S8/; PAIRS( STUDENTS, STUDENTS) | &2 #GT# &1: BENEFIT, MATCH; ENDSETS 集合循环函数 四个集合循环函数：FOR、SUM 、 MAX、MIN @function( setname [ ( set_index_list)[ | condition]] : expression_list); @FOR(STUDENTS( I): [constraints] @SUM( PAIRS( J, K) | J #EQ# I #OR# K #EQ# I: MATCH( J, K)) =1); Example: ∑I J ∈PAIRS BENEFIT I J MATCH I J ( , ) ( , )* ( , ) ( , ) 1 ( , ) ∑ = = = ∈ K I J I or J K PAIRS MATCH J K [objective] MAX = @SUM( PAIRS( I, J): BENEFIT( I, J) * MATCH( I, J));
实例2:钢管下料(问题2) 实例2铜管下料(问题2) 目标函数(总根数 增加约束,缩小可行域,便于求解 需求:4米50根,5米10每根原料钢管长19米 Min x,+x2+x 根,6米20根,8米15根「4×50+5×10+6×20+8×1 原料钢管总根数下界 1+122+1x325016≤41+5z1+6r1+8n1519 1x+2x2+23x3≥1016≤4+5+8n2≤19 特殊生产计划:对每根原料钢管 nx+nx,+n,x,> 2016≤4t;+52+6r3+83≤19 模式1:切割成4根4米钢管,需13根; 模式2:切割成1根5米和2根6米钢管,需1 (=1.35整数 模式3:切割成2根8米钢管,需8根 原料钢管总根数上界:3126≤x1+x2+x3≤31 模式排列顺序可任定 ≥x,≥ 实例2:钢管下料(问题2) 布置实验 演示cu 目的 able Value Reduced Cost模式1:每根原料钢管切割成3 2m根米和1根6米钢管,共10根 1)掌握用 LINDO/LINGO软件求解整数规划, 并对结果作初步分析; 38.000000 模式2:每根原料钢管切割成2 2)通过实例练习用整数规划求解实际问题 R130000000根4米、1根5米和根6米钢管 题00 共10根 内率课上布置,或参见网络学堂 模式3:每根原料钢管切割成2 .m.00原料铜管总根数为28根。 R432000000
10 50 r 11x1 +r 12x2 +r 13x3 ≥ r21 x1 + r22 x2 + r23 x3 ≥ 10 20 r31x1 + r32 x2 + r33 x3 ≥ r41 x1 + r42 x2 + r43 x3 ≥ 15 16≤ 4r11 +5r21 + 6r31 +8r41 ≤19 16≤ 4r 12 +5r22 +6r32 +8r42 ≤19 16 ≤ 4r13 + 5r23 + 6r33 +8r43 ≤19 目标函数（总根数） 1 2 3 Min x + x + x xi ,r1i , r2i , r3i , r4i (i=1,2,3)为整数 实例2：钢管下料(问题2) 增加约束，缩小可行域，便于求解 1 2 3 x ≥ x ≥ x 原料钢管总根数下界： 26 19 4 50 5 10 6 20 8 15 =⎥ ⎥ ⎤ ⎢ ⎢ ⎡ × + × + × + × 特殊生产计划：对每根原料钢管 模式1：切割成4根4米钢管，需13根； 模式2：切割成1根5米和2根6米钢管，需10根； 模式3：切割成2根8米钢管，需8根。 原料钢管总根数上界：31 26 ≤ x1 + x2 + x3 ≤ 31 模式排列顺序可任定 需求：4米50根，5米10 根，6米20根，8米15根 每根原料钢管长19米 实例2：钢管下料(问题2) Local optimal solution found at iteration: 12211 Objective value: 28.00000 Variable Value Reduced Cost X1 10.00000 0.000000 X2 10.00000 2.000000 X3 8.000000 1.000000 R11 3.000000 0.000000 R12 2.000000 0.000000 R13 0.000000 0.000000 R21 0.000000 0.000000 R22 1.000000 0.000000 R23 0.000000 0.000000 R31 1.000000 0.000000 R32 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.000000 R43 2.000000 0.000000 模式1：每根原料钢管切割成3 根4米和1根6米钢管，共10根； 模式2：每根原料钢管切割成2 根4米、1根5米和1根6米钢管， 共10根； 模式3：每根原料钢管切割成2 根8米钢管，共8根。 原料钢管总根数为28根。 演示cut02a.lg4； cut02b.lg4 实例2：钢管下料(问题2) 布置实验 目的 1)掌握用LINDO/LINGO软件求解整数规划， 并对结果作初步分析； 内容 课上布置，或参见网络学堂 2) 通过实例练习用整数规划求解实际问题
