0第04章整数规划.ppt

第四章 整数规划(IP) 整数规划的模型 分枝定界法 割平面法 0－1整数规划 指派问题 4.1 整数规划的模型 4.2 分枝定界法 2、例题 例2、用分枝定界法求解整数规划问题（单纯形法） 4.3 割平面法 4.4 0－1 整数规划 4.5 指派问题 例1： 其他整数规划问题 合理下料问题 建厂问题 机床分配问题 练习：用分枝定界法求解整数规划问题 （图解法） 练习1：用分枝定界法求解整数规划问题 （单纯形法） 练习3：求解指派问题 ◎ ◎ ◎ ? ? √ √ √ 独立零元素的个数m等于最少直线数l，即l＝m=3n=4； 第三步：作最少的直线覆盖所有0元素。 (1)对没有◎的行打√号； (2)对已打√号的行中所有含?元素的列打√号； (3)再对打有√号的列中含◎ 元素的行打√号； (4)重复(2),(3)直到得不出新的打√号的行、列为止； (5)对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有0元素的最少直线数 l 。l 应等于m，若不相等，说明试指派过程有误，回到第二步(4)，另行试指派；若 l＝m n，须再变换当前的系数矩阵，以找到n个独立的0元素，为此转第四步。 0 0 0 0 0 0 得到4个独立零元素， 所以最优解矩阵为：15. ◎ ◎ ◎ ? ? √-1 √-1 √+1 ◎ ◎ ◎ ? ? ◎ ◎ ◎ ? ? ◎ 练习 第四步，变换矩阵(bij)以增加0元素：没有被直线覆盖的所有元素中的最小元素为1，然后打√各行都减去1；打√各列都加上1，得如下矩阵，并转第二步进行试指派： 例1、合理下料问题 设用某型号的圆钢下零件A1, A2,…,Am 的毛坯。在一根圆钢上下料的方式有B1,B2, … Bn 种，每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量，如表所示。问怎样安排下料方式，使得即满足需要，所用的原材料又最少？ 零 件 毛坯数 零件 方 个数 式 零件 设：xj 表示用Bj (j=1.2…n) 种方式下料根数. 模型： 例2、（建厂问题）某公司计划在m个地点建厂，可供选择的地点有A1,A2…Am ，他们的生产能力分别是a1,a2,…am（假设生产同一产品）。第i个工厂的建设费用为fi (i=1.2…m),又有n个地点B1,B2, … Bn 需要销售这种产品，其销量分别为b1.b2…bn 。从工厂运往销地的单位运费为Cij。试决定应在哪些地方建厂，即满足各地需要，又使总建设费用和总运输费用最省？ 销量 建设 费用 生产 能力 单 销地 厂址 价 设： xij 表示从工厂运往销地的运量(i=1.2…m、j=1.2…n), 1 在Ai 建厂 又设 Yi＝ （i=1.2…m） 0 不在Ai 建厂 模型： 例3、机床分配问题 设有m台同类机床，要加工n种零件。已知各种零件的加工时间分别为a1,a2,…an ，问如何分配，使各机床的总加工任务相等，或者说尽可能平衡。 设： 1 分配第i台机床加工第j种零件； xij＝ （i=1.2…m,j=1.2…n） 0 相反。 于是，第i台机床加工各种零件的总时间为： 又由于一个零件只能在一台机床上加工，所以有 因此，求xij ，使得 （2）从(LP)的最优解中，任选一个不为整数的分量xr,,将最优单纯形表中该行的系数 和 分解为整数部分和小数部分之和，并以该行为源行，按下式作割平面方程： （3）将所得的割平面方程作为一个新的约束条件置于最优单纯形表中（同时增加一个单位列向量），用对偶单纯形法求出新的最优解，返回1。 的小数部分 的小数部分 例1：用割平面法求解整数规划问题 解：增加松弛变量x3和x4 ，得到(LP)的初始单纯形表和最优单纯形表： 0 1 0 x4 0 0 1 0 0 －Z 0 2 -3 0 x4 0 1 2 3 6 x3 0 x3 x2 x1 b XB CB 0 1 0 Cj -1/4 1/4 -1/6 x4 0 -1/4 0 0 -3/2 －Z 1/4 1 0 3/2 x2 1 1/6 0 1 1 x1 0 x3 x2 x1 b XB CB 0 1 0 Cj 此题的最优解为：X＊ (1 , 3/2) Z = 3/2 但不是整数最优解，引入割平面。以x2 为源行生成割平面。 此题的最优解为：X＊ (1 , 3/2) Z = 3/2