《整数第四章.doc》由会员分享，可在线阅读，更多相关《整数第四章.doc（48页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、整数规划1.1整数规划的定义在工程设计和企业管理中，常常会遇到要求决策变量取整数值的规划问题.安排生产时，投入的人力与机器数量必须是整数，生产的某些产品（如汽车、机床、船 舶 等）的 数 量 也 是 整 数.整 数 规 划 就 是 用 于 研 究、处 理 这一类问 题 的 数 学 规 划.如果在线 性 规 划 的 基 础 上，把 规 划 中 的 变 量 （ 部 分 或 全 部 ） 限 制 为 整 数 时，就称之为线性整数规划.大部分的整数规划都是线性的所以我们也称线性整数规划为整数规划.在许多情况下，我们都可以把规划问题的决策变量看成是连续的变量；但在某些情况下，规划问题的决策变量却被要求一定
2、是整数.例如，完成某项工作所需要的人数或设备台数，进入市场销售的商品件数，以及某一机械设备维修的次数等.当连续的决策变量变为离散变量时非线性优化问题通常会难解得多.但是应用软件就方便多了，本文给了Lindo在规划中的常用方法和程序.1.2 整数规划的分类1、纯整数规划：所有决策变量均要求为整数的整数规划2、混合整数规划：部分决策变量均要求为整数的整数规划3、纯01整数规划：所有决策变量均要求为01的整数规划4、混合01规划：部分决策变量均要求为01的整数规划整数规划与线性规划不同这处只在于增加了整数约束不考虑整数约束所得到的线性规划称为整数规划的线性松弛模型整数规划是指一类要求问题中的全部或一
3、部分变量为整数的数学规划。是近三十年来发展起来的、规划论的一个分支. 整数规划问题是要求决策变量取整数值的线性规划或非线性规划问题。一般认为非线性的整数规划可分成线性部分和整数部分，因此常常把整数规划作为线性规划的特殊部分。在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求解答必须是整数。例如，所求解是机器的台数，工作的人数或装货的车数等。为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称
4、为混合整数规划。整数规划的一种特殊情形是01规划，它的变数仅限于0或1。2 整数规划问题的理论基础在整数规划问题中，如果整数规划的目标函数和约束条件都是线性的，则称此问题为整数线性规划问题. 目前所流行的求解整数规划的方法，往往只适用于整数线性规划.本文我们主要讨论整数线性规划问题.整数线性规划的一般形式为 （2.1）整数规划求解方法总的思想是：松弛模型（2.1）中的约束条件（譬如去掉整数约束条件），使构成易于求解的新问题松弛问题（A），即（A） 如果问题（A）的最优解是原问题（2.1）的可行解，则就是原问题（2.1）的最优解；否则，在保证不改变松弛问题（A）的可行性的条件下，修正松弛问题（A
5、）的可行域（增加新的约束），变成新的问题（B），再求问题（B）的解，重复这一过程直到修正问题的最优解在原问题（2.1）的可行域内为止，即得到了原问题的最优解.2.3 0-1整数规划的数学模型如果整数规划中的所有决策变量仅限于取或两个值，则称此问题为0-1整数规划，简称0-1规划.其变量称为0-1变量，或二进制变量.相应的决策变量的取值约束变为或，等价于和，且为整数.线性规划的一般模型为 （2.2）2.3.1 0-1规划的求解方法1、 0-1规划的隐枚举法0-1整数规划模型的解法一般为显枚举法（穷举法）或隐枚举法.穷举法指的是对决策变量 的的每一个或值，均比较其目标函数值的大小，以从中求出最优解
6、这种方法一般适用于决策变量个数较小的情况，当较大时，由于个、的可能组合数为，故此时即便用计算机进行穷举来求最优解，也几乎是不可能的求解0-1整数规划问题的解法均是隐枚举法或称为部分枚举法隐枚举法是增加了过滤条件的一类穷举法2、 指派问题的匈牙利方法指派问题的模型：一般地，有项任务、个完成人，第人完成第项任务的代价为为了求得总代价最小的指派方案，引入型变量，并令 （2.3）这样，问题的数学模型可写成 （2.4）可见指派问题是型整数规划的特例匈牙利算法的基本步骤为：步骤1 对效益矩阵进行变换，使每行每列都出现0元素(1)从效益矩阵c中每一行减去该行的最小元素；(2)再在所得矩阵中每一列减去该列的最
7、小元素，所得矩阵记为D一(d.).步骤2将矩阵D中0元素置为1元素，非零元素置为0元素，记此矩阵为E步骤3确定独立1元素组(1)在矩阵E含有1元素的各行中选择1元素最少的行，比较该行中各1元素所在的列中1元素的个数，选择1元素的个数最少的一列的那个1元素；(2)将所选的1元素所在的行和列清0；(3)重复第2步和第3步，直到没有1元素为止，即得到一个独立1元素组步骤4 判断是否为最大独立1元素组(1)如果所得独立1元素组是原效益矩阵的最大独立1元素组(即1元素的个数等于矩阵的阶数)，则已得到最优解，停止计算(2)如果所得独立1元素组还不是原效益矩阵的最大独立1元素组，那么利用寻找可扩路的方法对其
8、进行扩张，进行下一步步骤5 利用寻找可扩路方法确定最大独立1元素组(1)做最少的直线覆盖矩阵D的所有0元素；(2)在没有被直线覆盖的部分找出最小元素，在没有被直线覆盖的各行减去此最小元素，在没被直线覆盖的各列加上此最小元素，得到一个新的矩阵，返回第2步 3 整数规划问题的LINGO求解方法LINGO可以用于求解非线性规划，也可以用于一些线性和非线性方程组的求解等，功能十分强大，是求解优化模型的最佳选择.目前，利用LINGO软件求解整数规划问题是一种比较有效的方法.3.1一般整数规划的解法一般的整数规划模型程序如下：MODEL:sets:num_i/1.m/:b;num_j/1.n/:x,c;l
9、ink(num_i,num_j):a;endsetsdata:b=b(1),b(2),.b(m);c=c(1),c(2),.c(n);a=a(1,1),a(1,2),.,a(1,n), a(2,1),a(2,2),.,a(2,n), . a(m,1),a(m,2),.,a(m,n);enddataOBJmax=sum(num_j(j):c(j)*x(j);for(num_i(i):sum(num_j(j):a(i,j)*x(j)=0;);for(num_j(j):GIN(x(j););END3.2一般0-1规划的解法针对一般的规划模型编写LINGO程序，在这里仍假设目标函数为最大化问题，约束条
10、件都为“小于等于”的情况具体程序如下：MODELsets:num_i/1.m/:b;num_j/1.n/:x,c; link(num_i,num_j):a;endsetsdata:b=b(1),b(2),.,b(m);c=c(1),c(2),.,c(n);a=a(1,1),a(1,2),.,a(1,n), a(2,1),a(2,2),.,a(2,n), . a(m,1),a(m,2),.,a(m,n);enddataOBJmax=sum(num_j(j):c(j)*x(j);for(num_i(i):sum(num_j(j):a(i,j)*x(j)=30000;x3b=0;x2a=0;x3a=
11、0;x4a=0;x5a=0;x1b=0;x2b=0;x3b=0;x4b=0;x5b=0;x1c=0;x2c=0;x3c=0;x4c=0;x5c=0;x1d=0;x2d=0;x3d=0;x4d=0;x5d=0;Variable Value Reduced CostX4A 22900.00 0.X3B 50000.00 0.X2C 40000.00 0.X5D 0. 0.X1A 62264.15 0.X1D 37735.85 0.X2A 0. 0.X2D 0. 0.E-01X3A 0. 0.X3D 21603.77 0.X4D 0. 0.E-01X5A 0. 0.X1B 0. 0.X2B 0. 0
12、.X4B 0. 0.X5B 0. 0.X1C 0. 0.X3C 0. 0.X4C 0. 0.X5C 0. 0.Row Slack or Surplus Dual Price1 80000.00 1.2 0. 1.3 0. 1.4 0. 1.5 0. 1.6 0. 1.7 0. -0.E+188 -20000.00 -0.E+109 -40000.00 -0.E+1010 -20000.00 0.E+1011 20000.00 0.12 0. 0.E-0113 62264.15 0.14 0. 0.15 0. 0.16 22900.00 0.17 0. 0.18 0. 0.19 0. 0.20
13、50000.00 0.21 0. 0.22 0. 0.23 0. 0.24 40000.00 0.25 0. 0.26 0. 0.27 0. 0.28 37735.85 0.29 0. 0.30 21603.77 0.31 0. 0.32 0. 0.4.2 0-1整数规划的实例分析例、消防站问题某城市的消防总站将全市划分为11个防火区，现有4个消防站，图4-11给出的是该城市各防火区域和防火站的示意图，其中1,2,3,4，表示消防站1，2，11表示防火区域，根据历史资料证实，各消防站可在事先规定允许的时间内对所负责的区域内的火灾予以扑灭，图中没有虚线连接的就表示不负责，现在总部提出：能否减少消
14、防站的数目，仍能保证负责各地区的防火任务？如果可以的话，应该关闭哪个？12123491011756483某城市的消防站总部将全市划分为11个防火区，现有四的。解：根据题意，用xi表示第i个消防站的关系的打开关闭情况X=1； 第i个消防站不关闭 0； 第i个消防站关闭用y代表第i个消防站到第j个防火区域的到达情况，0表示不可达，1表示可达，Y=1,1,1,1,0,1,1,1,0,0,0;1,1,0,1,0,0,0,1,1,0,0;0,0,0,1,1,1,0,0,0,0,1;0,0,0,0,0,1,1,1,1,1,1;则问题可归结为01整数规划模型。min z=sum x（i）;St ： x（i）
15、*y（i，j）=1；j=1,2,3.11 x（i）=1;);for(n_j(j):sum(n_i(i):x(i)=0;);end运行结果：Global optimal solution found. Objective value: 3. Extended solver steps: 0 Total solver iterations: 0Variable Value Reduced CostX( 1) 1. 1.X( 2) 0. 1.X( 3) 1. 1.X( 4) 1. 1.Y( 1, 1) 1. 0.Y( 1, 2) 1. 0.Y( 1, 3) 1. 0.Y( 1, 4) 1. 0.Y(
16、 1, 5) 0. 0.Y( 1, 6) 1. 0.Y( 1, 7) 1. 0.Y( 1, 8) 1. 0.Y( 1, 9) 0. 0.Y( 1, 10) 0. 0.Y( 1, 11) 0. 0.Y( 2, 1) 1. 0.Y( 2, 2) 1. 0.Y( 2, 3) 0. 0.Y( 2, 4) 1. 0.Y( 2, 5) 0. 0.Y( 2, 6) 0. 0.Y( 2, 7) 0. 0.Y( 2, 8) 1. 0.Y( 2, 9) 1. 0.Y( 2, 10) 0. 0.Y( 2, 11) 0. 0.Y( 3, 1) 0. 0.Y( 3, 2) 0. 0.Y( 3, 3) 0. 0.Y( 3
17、, 4) 1. 0.Y( 3, 5) 1. 0.Y( 3, 6) 1. 0.Y( 3, 7) 0. 0.Y( 3, 8) 0. 0.Y( 3, 9) 0. 0.Y( 3, 10) 0. 0.Y( 3, 11) 1. 0.Y( 4, 1) 0. 0.Y( 4, 2) 0. 0.Y( 4, 3) 0. 0.Y( 4, 4) 0. 0.Y( 4, 5) 0. 0.Y( 4, 6) 1. 0.Y( 4, 7) 1. 0.Y( 4, 8) 1. 0.Y( 4, 9) 1. 0.Y( 4, 10) 1. 0.Y( 4, 11) 1. 0.Row Slack or Surplus Dual PriceOBJ
18、 3. -1.2 0. 0.3 0. 0.4 0. 0.5 1. 0.6 0. 0.7 2. 0.8 1. 0.9 1. 0.10 0. 0.11 0. 0.12 1. 0.13 0. 0.14 0. 0.15 0. 0.16 0. 0.17 0. 0.18 0. 0.19 0. 0.20 0. 0.21 0. 0.22 0. 0.23 0. 0.24 1. 0.25 0. 0.26 1. 0.27 1. 0.结果如下： X= X=X=1，X=0；即应关闭2号消防站。农机购买计划题目:某农场要新买一批拖拉机以完成每年三季的工作量：春种330公顷，夏管130公顷，秋收470公顷。可供选择的拖拉机
19、型号、单台投资额及工作能力如下表所示。拖拉机型号单台投资（元）单台工作能力（公顷）春种夏管秋收A5000301741B4500291443C4400321642D5200311844问配购哪几种拖拉机各几台，才能完成上述每年工作量且使总投资最少？问题分析这个问题的目标是使农机的投资最小，要做的决策是农机购买的分配的问题，即A B C D型号农机各买多少 才能让农场的投资最少而不影响工作,按题目所给，将决策变量，目标函数和约束条件用数学符号及式子表示出来，就可以得到下面的模型。：决策变量要做的决策是四种农机分别购买的数量，这就是运筹学问题或系统中待确定的某些量，一般情况下，在实际问题中常常称作变
20、量（决策变量）。目标函数目标函数是参量为z，其z值越小,投资就越小。最优解最优解必须满足约束条件要求，并使目标函数达到最优值。将其带入目标函数得z= 49800,就是农机购买的投资最优值.建立数学模型:要使每年工作量且使总投资最少,我们先找出总投资条件,然后找出其最小值。总投资为，各季所用的第i种拖拉机的总的工作量要超过每季的工作量bi，有不等式各拖拉机的数量不能是负数，有则这一问题的数学模型为：设购置A,B,C,D型号的拖拉机分别为x1, x2,x3,x4,台，相应的数学模型为： s.t.实现：对于上述线性规划问题，用lindo进行求解运算，可以按照下述步骤进行：（1）.编辑程序文件，文件内
21、容如下：MIN 5000x1+4500x2+4400x3+5200x4ST30x1+29x2+32x3+31x4=33017x1+14x2+16x3+18x4=13041x1+43x2+42x3+44x4=470EndGIN 4输出：LP OPTIMUM FOUND AT STEP 2 OBJECTIVE VALUE = 49202.5312 OBJECTIVE FUNCTION VALUE 1) 49800.00 VARIABLE VALUE REDUCED COST X1 0. 5000. X2 6. 4500. X3 4. 4400. X4 1. 5200. ROW SLACK OR S
22、URPLUS DUAL PRICES 2) 3. 0. 3) 36. 0. 4) 0. 0. NO. ITERATIONS= 2RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 5000. INFINITY 706. X2 4500. 4. 512. X3 4400. 565. 4. X4 5200. INFINITY 593. RIGHTHAND SIDE RANGES ROW CURRENT
23、 ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 330. 28. 13. 3 130. 31. INFINITY 4 470. 19. 36.结果分析：“LP OPTIMUM FOUND AT STEP 2”表示LINDO在（用单纯形法）2次迭代或旋转后得到最优解。“OBJECTIVE FUNCTION VALUE 1) 49800.00”表示最优目标值为49800.00。“VALUE”给出最优解中各变量的值。 X1=0 X2=6 X3=4 X4=1 “REDUCED COST”表示其中的值随最优解中各变量变化而增加REDUCED COST中相应的变量
24、的值VARIABLE VALUE REDUCED COST X1 0. 5000. X2 6. 4500. X3 4. 4400. X4 1. 5200.即随着最优解值的变化一个单位最优值49800.00就增加一个相应的REDUCED COST中的值“SLACK OR SURPLUS”给出松弛变量的值。即将最优解中的值代入到约束方程中与原约束值相比较3. 36. 0.30*0+29*6+32*4+31*1=333-300=317x1+14x2+16x3+18x4=166-130=3641x1+43x2+42x3+44x4=470-470=0“DUAL PRICE”（对偶价格）列出最优单纯形表中
25、判别数所在行的松弛变量的系数，表示当对应约束有微小变动时，目标函数的变化率，输出结果中对应每一个约束有一个对偶价格:ROW SLACK OR SURPLUS DUAL PRICES 2) 3. 0. 3) 36. 0. 4) 0. 0. “RANGES IN WHICH THE BASIS IS UNCHANGED”给出灵敏度分析：如果做敏感性分析，则系统报告当目标函数的费用系数和约束右端项在什么范围变化（此时假定其他系数保持不变）时，最优基保持不变。报告中INFINITY表示正无穷。其中，“OBJ COEFFICIENT RANGES”为目标函数的系数可变范围；“RIGHTHAND SIDE
26、 RANGES”为边界约束的可变范围。最优基保持不变VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE(+) DECREASE(-) X1 5000. INFINITY 706. X2 4500. 4. 512. X3 4400. 565. 4. X4 5200. INFINITY 593.即:X1 5000-706.50005000+ INFINITY之间变化不影响最优解 X2 4500-512.545004500+4.之间变化不影响最优解 X3 4400-4.44004400+565.之间变化不影响最优解X4 5200-593.520052
27、00+ INFINITY之间变化不影响最优解约束右端项保持不变 ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 330. 28. 13. 3 130. 31. INFINITY 4 470. 19. 36.右端项330-13.330330+28.之间变化不影响其值右端项130- INFINITY130130+ 31.之间变化不影响其值右端项470-36.470470+ 19.之间变化不影响其值经以上分析可知，当x1=0,x2=6,x3=4,x4=1时，也就是A、B、C、D型拖拉机分别为0、6、4、1时取得最优解，所以完成每年工作量
28、且使总投资最少为49800.00元。钢管下料问题提出某钢管零售商从钢管厂进货，将钢管按照顾客要求的长度进行切割，称为下料。假定进货时得到的原料钢管长度都是19m。1）现有一客户需要50根长4m、20根长6m和15根长8m的钢管。应如何下料最节省？2）零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本。所以该零售商规定采用的不同切割模式不能超过3种。此外。该客户除需要1）中的3种钢管外，还要10根长5m的钢管。应如何下料最节省？问题分析：对于下料问题首先要确定采用哪些切割模式。所谓切割模式，是指按照顾客要求的长度在原料钢管上安排切割的一种组合。例如，我们可以将19
29、m的钢管切割成3根长4m的钢管，余料为7m；或者将长19m的钢管切割成长4m、6m和8m的钢管各1根，余料为1m。显然，可行的切割模式是很多的。其次，应当明确哪些切割模式是合理的。合理的切割模式通常还假设余料不应大于或等于客户需要钢管的最小尺寸。例如，可以将长19m的钢管切割成3根4m的钢管是可行的，但余料为7m，可进一步将7m的余料切割成4m钢管（余料为3m），或者将7m的余料切割成6m钢管（余料为1m）。经过简单的计算可知，问题1）的合理切割模式一共有7种，如表1所示：于是问题转化为在满足客户需要的条件下，按照哪几种合理的模式，每种模式切割多少根原料钢管最为节省。而所谓节省，可以有两种标准
30、，一是切割后剩余的总余料量最小，二是切割原料钢管的总根数最少。下面将对这两个目标分别讨论。问题1） 用xi表示按照表1第i种模式（i=1,2,7）切割的原料钢管的根数，若以切割后剩余的总余料量最小为目标，则按照表1最后一列可得minZ1 = 3x1+x2+3x3+3x4+x5+x6+3x7 若以切割原料钢管的总根数最少为目标，则有表1 钢管下料问题1）的合理切割模式模式4m钢管根数6m钢管根数8m钢管根数余料/m14003231013201341203511116030170022MinZ2 = x1+x2+x3+x4+x5+x6+x7约束条件为客户的需求，按照表1应有4x1+3x2+2x3+x4+x5 50x2+2x4+x5+3x6 20x3+x5+2x7 15最后，切割