整数规划与分配问题.docx

本文格式为Word版，下载可任意编辑整数规划与分配问题 99 第4章 整数规划与调配问题 §4．1 整数规划的数学模型及解的特点 1--1 整数规划数学模型的一般形式 要求一片面或全部决策变量务必取整数值的线性规划（Linear Programming，简记LP）问题称为整数规划（Integer Programming,简记IP）整数线性规划数学模型的一般形式为 max?或min?z??cjxjj?1n?n??aijxj???,??bi,i?1,?,m j?1??s..t?xj?0,j?1,?,n ?x,?,x中片面或全部取整数 n?1??根据对全体变量的要求不同，整数线性规划又分为以下几种类型： （1） 纯整数线性规划（Pure Integer Linear Programming）：指全部决策变量都务必取 整数值的整数线性规划有时也称为全整数规划 （2） 混合整数规划（Mixed Integer Linear Programming）：指决策变量中有一片面务必 取整数值，另一片面可以不取整数值的整数线性规划。

（3） 0-1型整数规划（Zero-one Integer Linear Programming）：指决策变量只能取值0 或1的整数线性规划 整数规划问题的L P松弛问题（Slack Problem）这个概念在求解IP时具有重要作用 定义1 不考虑变量的全体整数或0-1约束条件而得到的L P称为IP的L P松弛问题 换言之，不考虑变量为整数的约束条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题若松弛问题是一个线性规划，那么称该整数规划为整数线性规划（Integer Linear Programming） 1--2 整数规划的例子 在现实生活中，当决策变量代表产品的件数、个数、台数、箱数、艘数、辆数等时，往 100 第4章 整数规化与调配问题 往只能取整数值整数线性规划模型也有其广泛的应用领域，从以下几个例子中可以窥其一斑 例1 某厂在一个筹划期内拟生产甲、乙两种大型设备该厂有充分的生产才能来加工制造这两种设备的全部零件，所需原材料和能源也可得志供给，但A,B两种紧缺物资的供给受到严格限制，每台设备所需原材料如下表所示。

问该厂在本筹划期内应安置生产甲、乙设备各多少台，才能使利润达成最大？ 表4-1 原料/设备 A/吨 B/千克 每台单位利润/万元 甲 1 5 5 乙 1 9 6 可供资源数量 6 45 解 设x1，x2分别为该筹划期内生产甲、乙设备的台数，z为生产这两种设备可获得的总利润鲜明x1，x2都务必是非负整数，因此它是一个（纯）整数规划问题，其数学模型为 maxz?5x1?6x2?x1?x2?6?5x?9x?45 ?2s.t.?1?x1,x2?0??x1,x2为整数例2（投资决策模型）设有n个投资工程，其中第j个工程需要资金aj万元，将来可获利润cj万元若现有资金总额为b万元，那么理应选择哪些投资工程，才能获利最大？ ?1,对第j个工程投资； 解 设 xj???0，不然 这里j?1,?,n设z为可获得的总利润（万元），那么该问题的数学模型为 maxz??cjxjj?1n ?n ax?b??jjs.t.?j?1?x?0或1(j?1,?,n)?j 这是一个0-1型整数规划，由于全体的决策变量xj(j?1,?,n)只能取0或1值。

第4章 整数规划与调配问题 101 例2中的模型一般称为“0-1背包问题”，由于它最初来自描述一个旅行者在旅途中携带哪些物品的问题cj表示第j种物品的价值或效用，aj表示其重量，而b那么表示旅行者所能承受的最大负重假设允许所携带的同一种物品多于一件，那么只需把约束条件“xj?0或1”改换成“xj?0且为整数”即可这时该模型就是一个纯整数规划，同时也叫“一般背包问题”，它是整数规划一个重要的典型模型，由于大量实际问题都可归结为这类 模型，而且它的解法曾推动了一般整数规划解法的研究与进展 例3（物资调拨模型）某厂拟用a元资金生产m种设备A1,?,Am，其中设备Ai单位本金为pi(i?1,?,m)现有n个销售地点B1,?,Bn，其中Bj处可销售各种设备最多为 bj(j?1,?,n)台预计将一台设备Ai在Bj处销售可获利cij元，那么应如何调拨这些设备， 才能使预计总利润为最大？ 解 设yi为生产设备Ai的台数，xij是设备Ai调拨到Bj处销售的台数，z为预计能获得的总利润（元），那么该问题的数学模型为 maxz???ci?1j?1mnijxij?n??xij?yi(i?1,2,?,m)?j?1 ?m??xij?bj(j?1,2,?,n)?i?1s.t.?m??py?a?i?1ii??xij?0,yi?0??xij,yi均为整数例4（选址问题）某种商品有n个销售地，各销售地每月的需求量分别为bj(j?1,?,n)吨。

现拟在m个地点中选址建厂，用来生产这种产品以得志供给，且规定一个地址最多只能建一个工厂若选择第i个地址建厂，将来生产才能每月为ai吨，每月的生产本金为 di(i?1,?,m)元已知从第i个工厂至第j个销售地点的运价为cij元/吨，应如何选择厂 址和安置调运，可使总的费用最少？ 解 设每月从厂址i至销售地j的运量为xij吨，z为每月的总费用（元）， ?1,若在第i址建厂；yi?? 0，否那么 102 第4章 整数规化与调配问题 那么该问题的数学模型为 maxz???cijxij??diyii?1j?1i?1mnm?n??xij?aiyi(i?1,2,?,m) ?j?1?ms.t.??xij?bj(j?1,2,?,n)?i?1?xij?0,yi?0或1?? 1--3 整数规划解的特点 整数规划及其松弛问题，从解的特点上来说，二者之间既有紧密的联系，又有本质的识别 松弛问题作为一个线性规划问题，其可行解的集合是一个凸集，任意两个可行解的凸组合仍为可行解整数规划问题的可行解的集合是它的松弛问题可行解集合的一个子集，任意两个可行解的凸组合不确定得志整数约束条件，因而不确定仍为可行解，所以，前者最优解的目标函数值不会优于后者最优解的目标函数值。

在一般处境下，松弛问题的最优解不会刚好得志变量的整数约束条件，因而不是整数规划的可行解，自然就不是整数规划的最优解此时，若对松弛问题的这个最优解中不符合整数要求的分量简朴地取整，所得到的解不确定是整数规划问题的最优解，甚至也不确定是整数规划问题的可行解 例5 考虑下面的整数规划问题： maxz?x1?4x2??2x1?3x2?3 ?s.t.?x1?2x2?8?x,x?0且取整数?12 图4-1中四边形OBPC及其内部为松弛问题的可行域，其中那些整数格点为整数规划问题的可行解根据目标函数等值线的优化方向，从直观可知，P点（x1?是其松弛问题的最优解，其目标函数值z?1819,x2?）7794在P点邻近对x1和x2简朴取整，可得四点：7A1,A2,A3,A4其中，A1和A2为非可行解；A3和A4虽为整数可行解，但不是最优解本例 ? 整数规划的最优解为A点（x1?4,x2?2），其目标函数值z?12 第4章 整数规划与调配问题 103 图4-1 §4．2 解纯整数规划的割平面法 考虑纯整数规划问题 nmaxz??cjxj (4.2.1a)j=1?n??aijxj?bi i?1,2,?,m (4.2.1b) j?1??s..t?xj?0 j?1,2,?,n (4.2.1c)?x取整数 j?1,2,?,n (4.2.1d)?j??设其中aij(i=1,?,m)皆为整数（若不为整数时，可乘上一个倍?,m;j=1，?,n)和bi(i=1,数化为整数）。

纯整数规划的松弛问题由(4.2.1a),(4.2.1b)和(4.2.1c)构成，是一个线性规划问题，可以用单纯形法求解用割平面法（cutting plane approach）解整数规划时，若其松弛问题的最优解X不得志(4.2.1d)，那么从X的非整分量中选取一个，用以构造一个线性约束条件，将其参与原松弛问题中，形成一个新的线性规划，然后求解之若新的最优解X得志 ???(4.2.1d)，那么它就是整数规划的最优解；否那么，重复上述步骤，直到获得整数最优解为止 为最终获得整数最优解，每次增加的线性约束条件应当具备两个根本性质：其一是已获得的不符合整数要求的线性规划最优解不得志该线性约束条件，从而不成能在以后的解中再展现;其二是凡整数可行解均得志该线性约束条件,因而整数最优解始终被留存在每次形成的线性规划可行域中 整数规划的割平面法是Gomory在1958年提出来的，所以又称为Gomory割平面法该法的根本思想是在非整数解的松弛问题中逐次增加一个新约束（即割平面），它能割去原 — 8 —。