大学数学实验 基本内容 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根