运筹学基础-整数规划

《运筹学基础-整数规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章：整数规划与分配问题解决整数规划问题不能仅仅是在线性规划求解中，将解“四舍五入”就行了，因为化整后的解不见得是可行解；即便是可行解，也不一定是优解。注意：在前面讨论的线性规划问题中，有些最优解可能是分数或小数，但对于某些具体的问题，常有要求解答必须是整数的情形（称为整数解），解决这样的问题即为整数规划。§4.1整数规划一、整数规划问题的提出：例1：某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表：问两种货物各托运多少箱，可使利润为最大？建立线性规划模型为：maxZ=20x1+10x25x1

2、+4x2≤242x1+5x2≤13x1≥0,x2≥0利用单纯形法求得最优解为：x1＝4.8，x2＝0，maxZ＝96讨论：如何调整满足整数解（1）凑整：x1＝5，x2＝0，Z＝100但破坏了体积限制条件，因而不是可行解（2）舍小数：x1＝4，x2＝0，Z＝80但不是最优解，因x1＝4，x2＝1，Z＝90也是可行解C(4.8,0)maxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1≥0,x2≥0x2x111023234567++++++++++++B(4,1)x1＝4.8，x2＝0，maxZ＝9

3、6二、整数规划之分枝定解法问题A：maxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1≥0,x2≥0x1,x2整数问题B：maxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1≥0,x2≥0从问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数Z*的上界，记作，（如果是求最小值，即为下界）分枝定界法就是将B的可行域分成子区域的方法，逐步减小和增大，最终逼近Z*。写出整数规划问题A的伴随线性规划问题为B而A的任意可行解的目标函数值将是Z*的一个下界

4、，记作，（如果是求最小值，即为上界）≤Z*≤第一步：寻找替代问题并求解问题B：maxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1≥0,x2≥0利用单纯形法求得最优解为：x1＝4.8，x2＝0，Z＝96问题B1：maxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1≤4x1≥0,x2≥0问题B2：maxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1≥5x1≥0,x2≥0＝0≤Z*≤96＝利用单纯形法求得最优解为：x1＝4，x2＝0.02，Z＝80.16

5、无解；第二步：分枝与定界x2x111023234567++++++++++++＝0≤Z*≤96＝利用单纯形法求得最优解为：x1＝4，x2＝1，Z＝90问题B11：maxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1≤4x2≥1x1≥0,x2≥0问题B12：maxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1≤4x2≤0x1≥0,x2≥0利用单纯形法求得最优解为：x1＝4，x2＝0，Z＝80由此解x1＝4，x2＝0.02，Z＝80.16出发，继续就x2分枝第三步：剪枝（此题剪掉问

6、题B2）最后得最优解为：x1＝4，x2＝1，Z＝90x1x211023234567++++++++++++分枝为问题1、2后解可能出现的情况序号问题1问题2说明1无可行解无可行解整数规划无可行解2无可行解整数解此整数解即最优解3无可行解非整数解对问题2继续分枝4整数解整数解较优的一个为最优解5整数解，目标函数优于问题2非整数解问题1的解即最优解6整数解非整数解，目标函数优于问题1问题1停止分枝(剪枝)，其整数解为界，对问题2继续分枝情况2,4,5找到最优解情况3在缩减的域上继续分枝定界法情况6问题1的整数解作为界被保留，用于

7、以后与问题2的后续分枝所得到的整数解进行比较，结论如情况4情况1无可行解例2：问题A：maxZ=40x1+90x29x1+7x2≤567x1+20x2≤70x1≥0,x2≥0x1,x2整数利用单纯形法求解问题B得最优解为：x1＝4.81，x2＝1.82，Z＝356问题B2：maxZ=40x1+90x29x1+7x2≤567x1+20x2≤70x1≥5x1≥0,x2≥0＝0≤Z*≤356＝利用单纯形法求得最优解为：x1＝4，x2＝2.1，Z＝349利用单纯形法求得最优解为：x1＝5，x2＝1.57，Z＝341问题B：

8、maxZ=40x1+90x29x1+7x2≤567x1+20x2≤70x1≥0,x2≥0问题B1：maxZ=40x1+90x29x1+7x2≤567x1+20x2≤70x1≤4x1≥0,x2≥0＝0≤Z*≤349＝第一步：寻找替代问题并求解第二步：分枝与定界分枝定解法求解（续）