基本模型 小型中型大型现有量 模型求解 第一种办法 设每月生产小、中、大型 铜材153 x,马,高为非负整数x,x2,x为非负实数 汽车的数量分别为x;x写消2 280250400 整数线性规划(LLP)日线性规划(LP) 决策变量 MATLAB 2,x2=167.74, Max ==2x,+3x,+4x 目标函数 LINDO/LINGO .1.5x1+3x2+5x3≤600 为了得到x,x2,x的整数解,在实数解附近试探 0x+250x2+400x3s60000约束条件 x1=65,x2=167,x 168,x=0 x1,x2,x3为非负整数 在满足约束条件前提下,计算并比较目标函数的大小 整数线性规划模型(ILP) 结果:x1=64,x2=168,x=0;z=632 模型求解 第二种办法 进一步研究的问题 ·若生产某类汽车,则至少生产80辆,求生产计划 利用直接求解整数线性规划的软件 Max ==2x+ 3x2+4x3 0,x2=0,x3≥80 (如: LINDO/LINGO) s1.15x+3x2+5x3≤600 x1=0,x2≥80,x3=0 280x1+250x2+400x1≤60000x=0.,x2≥80,x1280x 结果与上面相同 0或280x280 求解整数线性规划的复杂程度比线性规划大得多 方法1:分解为8个LP子模型x1≥80,x2≥80,x2=0 其中3个子模型应去掉,然后x≥80,x=0,x280 用普通软件能求解的整数线性规划的规模受到限制 逐一求解,比较目标函数值,x280x2280x≥80 再加上整数约束,得最优解 x=80,x2=150,x3=0,最优值=610 的法2引入0变量,化为整数规划y学 向4人口报 x=0或280日≤M1,280y1,M∈0BM为大的正 背景 世界人口增长概况 x2=0或280日x≤M2,x≥80,y2∈0B数,如100 x3=0或2809x≤My,x280y,y3∈{O1 年162518301930196019741987 人口(亿)5 方法3:化为非线性规划(NLP) x:=0或280日x(x1-80)20x20 中国人口增长概况 x2=0或≥80日x(x2-80)≥0x20 年1908 x3=0或280日x1(x-8020x20 人口(亿)3.0 NLP可用 LINGO, MATLAB求解,其结果常依赖 于初值的选择,且不能保证得到全局最优解 研究人口变化规律 控制人口过快增长4 2 1 3 2 4 3 Max z = x + x + x . . 1.5 3 5 600 s t x1 + x2 + x3 ≤ 280 250 400 60000 x1 + x2 + x3 ≤ x1, x2 , x3为非负整数 基本模型 小型 中型 大型 现有量 钢材 1.5 3 5 600 时间 280 250 400 60000 利润 2 3 4 整数线性规划模型（ILP） 设每月生产小、中、大型 汽车的数量分别为x1, x2, x3 决策变量 约束条件 目标函数 模型求解 第一种办法 x1, x2 , x3 为非负整数 整数线性规划（ILP） x1, x2 , x3 为非负实数 松弛 线性规划（LP） MATLAB LINDO/LINGO 为了得到 x1, x2, x3的整数解，在实数解附近试探： x1=64.52, x2=167.74, x3=0, z=632.26 x1=65, x2=167, x3=0; 在满足约束条件前提下，计算并比较目标函数的大小 x1=64，x2=168, x3=0; … 结果: x1=64, x2=168, x3=0; z=632 模型求解 第二种办法 利用直接求解整数线性规划的软件 （如：LINDO/LINGO） 求解整数线性规划的复杂程度比线性规划大得多 结果与上面相同 用普通软件能求解的整数线性规划的规模受到限制 进一步研究的问题 其中3个子模型应去掉，然后 逐一求解，比较目标函数值， 再加上整数约束，得最优解： 0, 0, 80 x1 = x2 = x3 ≥ x1 = 0, x2 ≥ 80, x3 = 0 x1 = 0, x2 ≥ 80, x3 ≥ 80 80, 0, 0 x1 ≥ x2 = x3 = x1 ≥ 80, x2 ≥ 80, x3 = 0 x1 ≥ 80, x2 = 0, x3 ≥ 80 x1 ≥ 80, x2 ≥ 80, x3 ≥ 80 x 1 , x 2 , x 3 = 0 方法1：分解为8个LP子模型 • 若生产某类汽车，则至少生产80辆，求生产计划。 1 2 3 Max z = 2x + 3x + 4x . . 1.5 3 5 600 s t x1 + x2 + x3 ≤ 280x1 + 250x2 + 400x3 ≤ 60000 x1,x2,, x3=0 或 ≥80 × × × x1=80，x2= 150，x3=0，最优值z=610 方法2：引入0-1变量，化为整数规划(LP) M为大的正 数，如1000 x1=0 或 ≥80 x2=0 或 ≥80 x3=0 或 ≥80 , 80 , {0,1} x1 ≤ My1 x1 ≥ y1 y1 ∈ , 80 , {0,1} x2 ≤ My2 x2 ≥ y2 y2 ∈ , 80 , {0,1} x3 ≤ My3 x3 ≥ y3 y3 ∈ NLP可用LINGO, MATLAB求解，其结果常依赖 于初值的选择，且不能保证得到全局最优解。 方法3：化为非线性规划（ NLP） x1=0 或 ≥80 ( 80) 0 0 x1 x1 − ≥ ，x1 ≥ x2=0 或 ≥80 x3=0 或 ≥80 ( 80) 0 0 x2 x2 − ≥ ，x2 ≥ x3(x3 −80) ≥ 0，x3 ≥ 0 例4 人口预报 背景 年 1625 1830 1930 1960 1974 1987 1999 人口(亿) 5 10 20 30 40 50 60 世界人口增长概况 中国人口增长概况 研究人口变化规律 控制人口过快增长 年 1908 1933 1953 1964 1982 1990 1995 2000 人口(亿) 3.0 4.7 6.0 7.2 10.3 11.3 12.0 13.0