《运筹学》课程教学资源（试卷习题）第6章 整数规划

第六章 整数规划

1 第六章 整数规划

引例：某厂利用集装箱托运甲、乙两种货物，每箱体积重量、可获利润及托运限制如下：利润体积重量甲52205乙4102413托运限制两种货物各托运多少箱使利润最大？MaxZ=20x, +10x25x1 +4x2≤242x +5x2≤13X1,X2≥0 X1,X2 为整数

引例：某厂利用集装箱托运甲、乙两种货物，每箱体 积重量 、可获利润及托运限制如下： 体积 重量 利润 甲 5 2 20 乙 4 5 10 托运限制 24 13 两种货物各托运多少箱使利润最大？ Max Z= 20x1 +10x2 5x1 +4x2≤24 2x1 +5x2≤13 x1 , x2≥0 x1 , x2 为整数

整数规划的数学模型1、整数规划问题(IP)整数规划问题：是指要求部分或全部决策变量的取值为整数的规划问题松弛问题：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题重点研究：喜整数线性规划问题

一、 整数规划的数学模型 1、整数规划问题 整数规划问题（IP）:是指要求部分或全部决策变 量的取值为整数的规划问题。 松弛问题：不考虑整数条件，由余下的目标函数 和约束条件构成的规划问题。 重点研究：整数线性规划问题

2、整数线性规划问的模型max(min) Z =c;x;j=1nZaijX, ≤(≥,=)b; i=1,2,..,mj=1x≥0x,中取部分或全部为整数j=1,2,.,n

2、整数线性规划问题的模型 j=1,2,.,n j n j Z c j x = = 1 max(min) 0 ( , ) 1     = = j i n j ij j x a x b i=1,2,.,m xj 中取部分或全部为整数

3、整数规划问题的类型：(1）纯整数规划问题minZ=X, +X2+x3+x$+xs+x6+x$+xgXi≥ 8X1 + X2 ≥ 8X1 + X2+ X3 ≥7Xi+X2+ X3 + X4 ≥1X2+ X3 + X4 + Xs≥2X3+ X4 + Xs +X ≥ 1X4 + Xs +X +X ≥5Xs+ X6 + X+Xg ≥ 10X6 + X +Xg ≥ 10X +Xg ≥ 6Xg≥ 6x;≥0(i=1,...,8)且为整数

3、整数规划问题的类型： (1) 纯整数规划问题 x1  8 x1 + x2  8 x1 + x2+ x3 7 x1+x2+ x3 + x4 1 x2+ x3 + x4 + x5 2 x3+ x4 + x5 +x6  1 x4 + x5 +x6 + x7  5 x5+ x6 + x7 +x8  10 x6 + x7 +x8  10 x7 +x8  6 x8  6 xi  0 (i =1,.,8)且为整数 minZ= x1 + x2 +x3+x4+x5+x6 +x7+x8