运筹学概论 第5章 整数规划.pptVIP

第5章 整数规划 在求解线性规划问题时，得到的最优解可能是分数或小数，但许多实际问题要求得到的解为整数才行。这种要求线性规划有整数解的问题,称为整数规划(Integer Programming)或简称IP。 引例 某厂拟用火车装运甲、乙两种货物集装箱，每 箱的体积、重量、可获利润以及装运所受限制如下： 整数规划的数学模型 分类： 若要求所有 xj 的解为整数，称为纯整数规划 若要求部分 xj 的解为整数，称为混合整数规划 第二节 0-1 整数规划 0-1型整数规划是整数规划的一种特殊形式，它的变量xj仅取值0或1。这种只能取0或1的变量称为0-1变量或二进制变量。 下面通过一个例子说明一下： 建立模型如下所示： 课堂练习 某钻井队要从10个可供选择的井位中确定5个钻井探油，使总的钻探费用最少。若10个井位的代号为s1－s10，相应的钻探费用为c1－c10，并且井位选择应满足以下条件： 1) s1，s4，s5，s10井位中最多选择两个。 2) s2，s8，s9井位中最少选择一个 3) 如s3和s5都选择，则s8不选择 4) s6号和s7井位至少有一个不选择 建立该问题的数学模型。 * * * 第一节 整数规划的数学模型及解的特点 13 24 托运限制 10 5 4 乙 20 2 5 甲 利润(百元) 重量(百斤) 体积(米3) 货物集装箱 问两种货物各装运多少箱，可使获得利润最大？ 此例可解得x1=4.8,x2=0，凑整为x1=5,x2=0，这就破坏了条件(2)，因而不是可行解；如截断小数变为x1=4,x2=0，这当然满足所有约束条件，但不是最优解，因为对x1=4,x2=0有z＝80，而对x1=4,x2=1（也是可行解）有z＝90。因此要专门研究整数规划的解法。 设甲、乙两种货物装运箱数分别为x1和x2。显然，x1、x2 都要求为整数,于是可建立整数规划模型如下： Max z＝20x1+10x2 (1) 5x1+4x2≤24 (2) 2x1+5x2≤13 (3) x1,x2≥0 (4) x1,x2为整数 (5) 注意几点： 对应没有整数解要求的线性规划称之为松弛问题 整数规划的解是可数个的，最优解不一定发生在极点 整数规划的最优解不会优于其松弛问题的最优解 例:篮球队需要选择5名队员组成出场阵容参加比赛。8名队员的身高及擅长位置如下： 出场阵容应满足如下条件： （1）只能由一名中锋出场； （2）至少一名后卫； （3）如1号和4号均上场，则6号不出场； （4）2号和8号至少有一个不能出场。 问：应选择哪些队员出场，使队员平均身高最高。试建立数学模型。 后卫 后卫 后卫 前锋 前锋 前锋 中锋 中锋 位置 1.78 1.80 1.83 1.85 1.86 1.88 1.90 1.92 身高 8 7 6 5 4 3 2 1 队员 引入0-1变量xi（i=1,2,…,7）,令 1, 当第i个队员被选用, xi= 0, 当第i个队员没被选用。 （i=1,2,…,8) Max z= (c1x1+c2x2+…+c8x8）/5 x1+x2+…+x8=5 x1+x2=1 x6+x7+x7≥1 x2+x8 ≤ 1 xi=0或1, i=1,2,…,8 于是建立下列模型: x1+x4+x6 ≤ 2 第三节 指派问题 指派问题的标准形式及其数学模型 匈牙利解法求解指派问题 一般的指派问题 有n项任务，恰好n个人承担，第i 人完成第j 项任务的花费(时间或费用等)为cij，如何指派使总花费最省？ 一、指派问题的标准形式及其数学模型 指派问题的系数矩阵如下： Cij的含义可以不同，如费用、成本、时间等。 系数矩阵C中，第 i 行中各元素表示第 i 人做各事的费用；第j 列各元素表示第 j 事由各人做的费用。 为建立标准指派问题的数学模型，引入n×n个0—1变量： 指派问题的数学模型可写成如下页形式： 若派第i人做第j事 0 若不派第i人做第j事 （ij=1，2,…，n） 第j项工作由一个人做 第i人做一项工作 指派问题的每个可行解，可用矩阵表示如下： 矩阵X中，每行各元素中只有1个元素为1,其余各元素等0；每列各元素中也只有1个元素为1,其余各元素等0 。 指派问题有n！个可行解