运筹学基础整数规划.ppt

关于运筹学基础整数规划第1页，共41页，星期日，2025年，2月5日*§4.1整数规划解决整数规划问题不能仅仅是在线性规划求解中，将解“四舍五入”就行了，因为化整后的解不见得是可行解；即便是可行解，也不一定是优解。注意：在前面讨论的线性规划问题中，有些最优解可能是分数或小数，但对于某些具体的问题，常有要求解答必须是整数的情形（称为整数解），解决这样的问题即为整数规划。一、整数规划问题的提出整数规划第2页，共41页，星期日，2025年，2月5日*【例1】某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表：问两种货物各托运多少箱，可使利润为最大？建立线性规划模型为：maxZ=20x1+10x25x1+4x2≤242x1+5x2≤13x1≥0,x2≥0利用单纯形法求得最优解为：x1＝4.8，x2＝0，maxZ＝96整数规划第3页，共41页，星期日，2025年，2月5日*讨论：如何调整满足整数解（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＝96非整数解整数规划第4页，共41页，星期日，2025年，2月5日*二、整数规划的求解方法1、分枝定解法2、割平面法3、利用EXCEL求解整数规划第5页，共41页，星期日，2025年，2月5日*1、整数规划之分枝定解法问题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*的一个下界，记作，（如果是求最小值，即为上界）≤Z*≤整数规划第6页，共41页，星期日，2025年，2月5日*第一步：寻找替代问题并求解问题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＝1，Z＝90无解；第二步：分枝与定界x2x111023234567++++++++++++最后得最优解为：x1＝4，x2＝1，Z＝90整数规划第7页，共41页，星期日，2025年，2月5日*【例2】问题A：maxZ=40x1+90x2