运筹学基础-整数规划(2).ppt

《运筹学基础-整数规划(2).ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、3、利用EXCEL求解整数规划1、根据线性规划模型建立计算模板maxZ=40x1+90x29x1+7x2≤567x1+20x2≤70x1≥0,x2≥0x1,x2整数整数规划1利用EXCEL求解整数规划的步骤利用“工具栏”之“规划求解”求解整数规划2利用EXCEL求解整数规划的步骤整数规划3利用EXCEL求解整数规划的步骤最优解为：x1=4,x2=2maxZ=340整数规划4【引例】背包问题一个旅行者的背包最多只能装16千克的物品。待装的有5件物品，其重量和价值见下表：物品编号12345合计重量（千克）34

2、34620价值（元）121291630他应在背包中携带哪几样物品可使携带的价值最大？试将该问题归结为数学问题。解：以x1,x2,x3,x4,x5表示旅行者携带的第1、2、…、5件物品的件数。各xi只能取1或者0：xi=1表示携带该件物品，xi=0表示不携带该件物品。问题归结为:maxZ=12x1+12x2+9x3+16x4+30x53x1+4x2+3x3+4x4+6x5≤16x1,x2,x3,x4,x5=0或1整数规划5§4.20－1规划此时决策变量只取0或1值。只取0或1值的变量称为0-1变量，决策变量为

3、0-1变量的线性规划称为0-1规划。0-1规划的求解方法：1、穷举法2、隐枚举法3、利用EXCEL的“规划求解”功能一、0-1规划的计算方法整数规划61、用计算机模拟穷举法0－1规划模型为：maxZ=3x1－2x2+5x3x1+2x2－x3≤2x1+4x2＋x3≤4x1+x2≤34x2+x3≤6x1,x2,x3=0或1列表进行枚举：（x1,x2,x3）=（0，0，0）（x1,x2,x3）=（1，0，0）（x1,x2,x3）=（0，1，0）（x1,x2,x3）=（0，0，1）（x1,x2,x3）=（1，1，

4、0）（x1,x2,x3）=（1，0，1）（x1,x2,x3）=（0，1，1）（x1,x2,x3）=（1，1，1）整数规划7列举法列表maxZ=3x1－2x2+5x3x1+2x2－x3≤2（1）x1+4x2＋x3≤4（2）x1+x2≤3（3）4x2+x3≤6（4）x1,x2,x3=0或1点条件满足条件是（＋）否（－）z值目标函数约束(1)约束(2)约束(3)约束(4)（0,0,0）00000＋8（0,0,1）31111＋（0,1,0）-22400＋（0,1,1）5-1111＋（1,0,0）13511－（1

5、,0,1）80222＋（1,1,0）31511－（1,1,1）62622－整数规划82、隐枚举法（略）基本思想：隐枚举法的本质是穷举法，但是应用隐枚举法可以更快地得到最优解。其实质是分枝定界法。但一般用是分枝定界法求解整数规划时，替代问题是放宽变量的整数约束。但用隐枚举法时，替代问题是在保持变量0-1的约束条件下先不考虑问题的主要约束。对一个有n个决策变量的0-1规划模型，其所要考虑的情况最多有2n种。如果变量不多，可以用隐枚举法来求解。整数规划9隐枚举法的步骤是：（1）化问题为0-1规划隐枚举法的标准形式：这

6、里要注意：标准形式的目标函数中各系数cj必须是非负数(不是非负数，令变量x’j=1-xj)；所求的问题必须是求最小值的形式；所有不等式约束都是≤形式。（2）在标准形式下，各0-1变量必优先考虑取0整数规划10（3）先看所有变量都取0时是否满足所有约束条件，如果满足，则已经得到最优解。如不满足，把问题分支成两个子问题。分支的方法是：指定一个变量，称为固定变量，其余变量称为自由变量。在两个子问题中，一个子问题中的固定变量取1，另一个子问题中的固定变量取0。每个自由变量都取0。检验由此得到的这组变量值是否满足所有约束

7、条件：如满足，则得到一个可行解，并得到0-1规划最优值的一个上界。如果某些约束条件未满足，则按照与分支定界法类似的方法再判断是否要继续分支及如何分支。如果需要继续分支，则再指定一个变量为固定变量，向下把子问题分成自由变量更少的子问题；直到不需分支时，即求得了最优解。整数规划11【例2】求解0-1规划最优解解：先将问题化为如下的标准问题minZ=4x1+3x2+2x32x1-5x2+3x3≤4(1)4x1+x2+3x3≥3(2)x2+x3≥1(3)x1,x2,x3=0或1minZ=4x1+3x2+2x32x1

8、－5x2+3x3≤4(1)－4x1－x2－3x3≤－3(2)－x2－x3≤－1(3)x1,x2,x3=0或1我们用图来说明解题的过程：整数规划12求解过程：下面各图中红字为固定变量。P0不满足条件(2)、(3)P2不满足条件(3)。进一步指定x2为固定变量，将P1分支为P3和P4,将P2分支为P5和P6,P6为可行解，停止分支。先将P3分支为P7和P8。P3和P5相当于P1和P2，