第5讲 整数规划nullnull 第三节
整数规划模型的解null例 整数规划模型且为整数是可行解，但非最优解，用穷举法也是不可取的。因有可行解：null一、分枝定界法设整数规划模型：（P）松弛问题：（P0）记可行域为S0 , 最优解为X0 ,最优目标值为z0 。nullnull剪完所有枝得：则最小上界对应的最优解为所求。null（1） 不可行，则剪枝；注：对于极大化问题，则是定下界，最大下界对应的整数解为所求。则归纳起来:null例 求解且为整数解松弛问题P0 可用
图解法目标函...
nullnull 第三节
整数规划模型的解null例 整数规划模型且为整数是可行解，但非最优解，用穷举法也是不可取的。因有可行解：null一、分枝定界法设整数规划模型：（P）松弛问题：（P0）记可行域为S0 , 最优解为X0 ,最优目标值为z0 。nullnull剪完所有枝得：则最小上界对应的最优解为所求。null（1） 不可行，则剪枝；注：对于极大化问题，则是定下界，最大下界对应的整数解为所求。则归纳起来:null例 求解且为整数解松弛问题P0 可用
图解法目标函数等值线nullnull分枝＃null二、0－1规划的解若对每一个变量取0、1进行分枝，计算量很大。如 的情形：n个变量的情形共有子问题个数：下面的方法可减少计算量。null1. 隐数法设模型为：• 若约束是“＝”，则可换为：上述假设之用处：null约定：表示原问题其余变量称为自由变量。＃null隐数法的基本思想：• 若该点可行，则为最优解；• 若不可行，则选分枝变量分枝（原则：其值升为“1”，其余仍取0，得一新解点“最接近可行”）• 若新解点可行，则剪枝，定界；•若新解点不可行，则与当前上界比较，确定剪枝或分枝。直到剪完所有的枝，最小上界对应的可行解为所求。用此思想初步计算 P.25 例1.21null例解因此它不是最优解。确定分枝变量：见图null对于P2 :所以该分枝。见图null一般编程步骤见P.25null部分枚举法思路：让 最小的 取1，其余取0，若是可行解，则为最优解；否则再让次小的 对应的变量升为1，直到可行为止。解因不可行，转入（3），若可行则为最优解。null仍不可行，转入（4）是一可行解，故得：#null2. 隐枚举法所以只需在满足过滤条件的解点中找最优者。解找到可行解点(1,0,0)，对应的 z =4, 得过滤条件：null逐点验证约束条件，对可行解，再比较目标值，最小者为所求。该过程可列表，见P.28.注：滤掉解点的多少与初始可行解有关。#null
本文档为【第5讲 整数规划】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483