整数规划__运筹学__胡运权__清华大学出版社.pptVIP

第五章 整数规划 线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有意义。 例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。 要求全部或部分决策变量的取值为整数的线性规划问题，称为整数线性规划，简称整数规划(Integer Programming)。 全部决策变量的取值都为整数，则称为全整数规划(All IP)； 仅要求部分决策变量的取值为整数，则称为混合整数规划(Mixed IP)； 要求决策变量只能取0或1值，则称为0-1规划(0-1 Programming)。 整数规划 Integer Programming（IP） 整数规划数学模型的一般形式 一、 整数规划的数学模型 为了满足整数要求，似乎可以把线性规划的小数最优解进行“舍入化整”以得到与最优解相近的整数解。 “舍入化整”一般是不可行的： 化整后的解有可能成为非可行解； 虽是可行解，却不是最优解。 例如 解：设x1为甲产品的台数，x2为乙产品的台数。 maxZ= 6x1 +5x2 2x1 + x2 ≤9 5x1 +7 x2 ≤35 x1, x2 ≥0 x1, x2取整数 不考虑整数约束则是一个LP问题,称为原整数规划的松弛问题。 不考虑整数约束的最优解：x1 *=28/9， x2 * =25/9，Z * =293/9 舍入化整 x1 =3， x2 =3，Z =33，不满足约束条件5x1 +7 x2 ≤35，非可行解； x1 =3， x2 =2，Z =28，满足约束条件，是可行解，但不是最优解； x1 =4， x2 =1，Z =29，满足约束条件，才是最优解。 步骤： 在线性规划的可行域内列出所有决策变量可能取的整数值， 求出这些变量所有可行的整数解， 比较它们相应的目标函数值，最优的目标函数值所对应的解就是整数规划的最优解。 实用性： 只有两个决策变量， 可行的整数解较少。 例：某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运受限制如下表所示。问两种货物各托运多少箱，可使获得利润为最大？ 【解】设甲、乙两种货物的托运箱数各为x1、x2箱，则 数学模型为： 如果不考虑x1、x2取整数的约束（称为其松弛问题），线性规划的可行域如图所示。不考虑整数约束的最优解：x1 *=4.8， x2 * =0，Z * =96 练习：试用图解法求下列问题的最优解和最优整数解 设备购置问题：某厂拟用M元资金购买m种设备，设备i 的单价为pi；现有n个地点可装置这些设备，第j 处最多可装置bj 台；设备i 装置在j 处可获利cij元。如何购置，总利润最大？ 假设：购买第i 种设备yi台数，将第i 种设备安装在第j 处的台数xij 该问题的数学模型 投资决策问题：某厂拟用b元资金投资n个项目，项目j 需资金aj元，可获利cj元。应选择那些项目，获利最大？ 假设：xj =1表示投资项目j ； xj =0表示不投资项目j 该问题的数学模型 工厂选址问题：某商品有n个销地，各销地的需求量为bj吨/天；现拟在m个地点中选址建生产厂，一个地方最多只能建一个工厂；若选i 地建厂，生产能力为ai吨/天，固定费用为di元/天；已知i 址至销地j 的运价为cij元/吨。如何选址和安排调运，总费用最小？ 假设：yi=1，选择第i 址建厂， yi=0，不选择第i 址建厂；从厂址i 至销地j 运量为xij 。 该问题的数学模型 二、割平面算法cutting plane approach 算法思想 割平面法求解整数规划问题时，若其松驰问题的最优解 X* 不满足整数要求时，则从 X* 的非整分量中选取一个，用以构造一个线性约束条件（Gomory 割平面），将其加入原松驰问题中，形成一个新的线性规划，然后求解之。其关键在于新增加的这个线性约束条件将切割掉部分非整数解，至少将当前松驰问题的非整数最优解切割掉了，而不会切割掉问题的任何整数解。 算法思想 由松弛问题的可行域向整数规划的可行域逼近 方法—利用超平面切除 要求整数解保留,松弛问题非整最优解被切割掉了 整数规划 Integer Programming（IP） 割平面法cutting plane approach 构造切割方程的步骤： 1、令 xi 是相应松驰问题的最优解中为非整数值的一个基变量，由单纯形表最终表得： xi + ∑aik xk = bi ……………（1 式） 其