《数学建模课件2124讲第23讲》由会员分享，可在线阅读，更多相关《数学建模课件2124讲第23讲（32页珍藏版）》请在金锄头文库上搜索。
1、数 学 建 模,第5章 数学规划模型,数学建模,线性规划模型,内容,1,非线性规划模型,2,多目标规划模型,4,整数规划模型,3,数学建模,整数规划模型,3,第23讲,数学建模,整数规划模型,在线性或非线性规划模型中，如果其部分或全部决策变量要求取整数时，就称该规划模型为整数规划模型。 整数规划模型：,整数线性或非线性规划模型 混合整数线性或非线性规划模型 0-1整数线性或非线性规划模型,例5.8（平板车装运） 有七种规格的包装箱要装到两节铁路平板车上去。包装箱的宽和高是一样的，但厚度及重量不同。 下表给出了每种包装箱的厚度、重量以及数量。 每节平板车有10.2米长的地方可用来装包装箱，载重4
2、0吨。 由于当地货运的限制，对于C5, C6, C7类包装箱的总数又一个特别的限制：这类箱子所占的空间（厚度）不能超过302.7厘米。 试把包装箱装到平板车上且使得浪费的空间最小。,数学建模,整数规划建模与求解,数学建模,表5.4包装箱规格等明细表,整数规划建模与求解,数学建模,决策变量及符号表示 xij 表示第j节车上装第 i 种包装箱的数量， i=1, 2, , 7, j=1,2； ni、wi、ti 表示第 i 种包装箱的件数、重量和厚度； dj、mj 表示第 j 节车的长度、载重量； s 为特殊限制，s=302.7。,整数规划建模与求解,数学建模,目标函数（装车的总厚度） 约束条件 各种
3、货物装箱总件数 每节车可装箱总长度 每节车可装的载重量 对于C5C7类包装箱的特殊限制 非负整数限制： 且为整数。,整数规划建模与求解,数学建模,规划模型,整数规划建模与求解,数学建模,模型求解 问题的最优解为： 第一节车装七种包装箱分别为4, 1, 9, 1, 2, 1, 0箱，装箱总长度1019.0cm； 第二节车装七种包装箱分别为4, 6, 0, 5, 1, 2, 0箱，装箱总长度1019.5cm。 两节车装箱总长度2039.4cm。 事实上本问题不是唯一最优解。,由LINGO软件求解,整数规划建模与求解,附3：LINGO程序： 1model: 2 sets: 3 type/17/: t
4、, w, n; 4 car/12/: d, W; 5 matrix(type, car): x; 6 endsets 7 8 max=sum(type(i): t(i)*(x(i,1)+x(i, 2); 9 for(type(i): x(i,1)+x(i,2)=n(i); 10 for(car(j): sum(type(i): t(i)*x(i,j)=d(j);,数学建模,整数规划建模与求解,数学建模,11 for(car(j): sum(type(i): w(i)*x(i,j)=m(j); 12 sum(type(i)i #GE# 5: t(i)* (x(i,1)+x(i, 2)=s; 13
5、 for(type(i): ginx(i,1); 14 for(type(i): ginx(i,2); 15 16 data 17 t=48.7, 52.0, 61.3, 72.0, 48.7, 52.0, 64.0; 18 w=2000, 3000, 1000, 500, 4000, 2000, 1000; 19 n=8, 7, 9, 6, 6, 4, 8; 20 d=1020,1020; 21 m=40000, 40000; 22 s=302.7; 23 enddata 24end,整数规划建模与求解,例5.9 汽车厂生产计划,小型 中型 大型 现有量 钢材（吨） 1.5 3 5 600
6、劳动时间（小时） 280 250 400 60000 利润 （万元） 2 3 4,一汽车厂生产小、中、大三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润以及每月工厂钢材、劳动时间的现有量如下表所示。,试制订月生产计划，使工厂的利润最大。,进一步讨论：由于各种条件限制,如果生产某一类型汽车,则至少要生产80辆，那么最优的生产计划应做何改变。,整数规划建模与求解,数学建模,决策变量：设每月生产小、中、大型汽车的数量为 x1，x2，x3 目标函数：目标是决策汽车产量使工厂的月利润最大 约束条件： 钢材的限制： （1） 劳动时间的限制： （2） 非负限制： （3）,整数规划建模与求解,数学
7、建模,规划模型 用LINGO软件编程求解 最优解为 最优值为 z=632。,问题的月生产计划为生产小型车64辆、中型车168辆，不生产大型车。,整数规划建模与求解,数学建模,进一步讨论 “如果生产某一类型汽车，则至少要生产80辆”，即 新模型,整数规划建模与求解,其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：,方法1：分解为8个LP子模型,x1=80，x2= 150，x3=0， z=610,整数规划建模与求解,方法2：引入0-1变量，化为整数规划,M为大的正数，可取1000,x1=0 或 80,用LINGO求解，得到与方法1得到同样的结果,整数规划建模与求解,方
8、法3：化为整数非线性规划,x1=0 或 80,用LINGO求解，结果与方法1和方法2相同,整数规划建模与求解,数学建模,例5.10（合理下料模型）,生产中通过切割、剪裁、冲压等手段，将原材料加工成所需大小。,按照工艺要求，确定下料方案，使所用材料最省，或利润最大。,整数规划建模与求解,数学建模,问题1.如何下料最节省 ?,问题2.客户增加需求：,节省的标准是什么？,由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过3种。如何下料最节省？,整数规划建模与求解,数学建模,按照客户需要在一根原料钢管上安排切割的一种组合。,切割模式,合理切割模式的余料应小于客户需要钢管的最小尺寸,钢
9、管下料,整数规划建模与求解,数学建模,为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？,合理切割模式,钢管下料问题1,整数规划建模与求解,数学建模,2. 所用原料钢管总根数最少,两种标准,1. 原料钢管剩余总余量最小,决策变量,目标1（总余量）,整数规划建模与求解,数学建模,约束,满足需求,按模式2切割12根,按模式5切割15根，余料27米,最优解：x2=12, x5=15, 其余为0； 最优值：27。,整数约束： xi 为整数,整数规划建模与求解,数学建模,目标2（总根数）,钢管下料问题1,约束条件不变,最优解：x2=15, x5=5, x7=5, 其余为0； 最优
10、值：25。,xi 为非负整数,按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米,与目标1的结果“共切割27根，余料27米”相比，虽余料增加8米，但减少了2根。 当余料没有用处时，通常以总根数最少为目标。,整数规划建模与求解,数学建模,钢管下料问题2,对大规模问题，用模型的约束条件界定合理模式,增加一种需求：5米10根；切割模式不超过3种。,现有4种需求：4米50根，5米10根，6米20根，8米15根，用枚举法确定合理切割模式，过于复杂。,决策变量,xi 按第i 种模式切割的原料钢管根数(i=1,2,3) r1i, r2i, r3i, r4i 第i 种切割模式下，每根
11、原料钢管生 产4米、5米、6米和8米长的钢管的数量,整数规划建模与求解,数学建模,目标函数（总根数） 约束条件 客户需求 模式合理 整数约束 xi ,r1i, r2i, r3i, r4i (i=1,2,3)为整数,整数规划建模与求解,数学建模,整数非线性规划模型 增加约束，缩小可行域，便于求解,整数规划建模与求解,数学建模,特殊生产计划：对每根原料钢管 模式1：切割成4根4米钢管，需13根； 模式2：切割成1根5米和2根6米钢管，需10根； 模式3：切割成2根8米钢管，需8根。,需求 4米50根，5米10根，6米20根，8米15根 原料钢管19米,原料钢管总根数下界,原料钢管总根数上界 13+10+8=31,整数规划建模与求解,数学建模,LINGO求解整数非线性规划模型 模式1：每根原料钢管切割成3根4米和1根6米钢管，共10根； 模式2：每根原料钢管切割成2根4米、1根5米和1根6米钢管，共10根； 模式3：每根原料钢管切割成2根8米钢管，共8根。 原料钢管总根数为28根。,整数规划建模与求解,
