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

第5章 整数规划,在求解线性规划问题时，得到的最优解可能是分数或小数，但许多实际问题要求得到的解为整数才行。这种要求线性规划有整数解的问题,称为整数规划(Integer Programming)或简称IP。,第一节 整数规划的数学模型及解的特点,引例,某厂拟用火车装运甲、乙两种货物集装箱，每 箱的体积、重量、可获利润以及装运所受限制如下：,问两种货物各装运多少箱，可使获得利润最大？,此例可解得x1=4.8,x2=0，凑整为x1=5,x2=0，这就破坏了条件(2)，因而不是可行解；如截断小数变为x1=4,x2=0，这当然满足所有约束条件，但不是最优解，因为对x1=4,x2=0有z80，而对x1=4,x2=1（也是可行解）有z90。因此要专门研究整数规划的解法。,设甲、乙两种货物装运箱数分别为x1和x2。显然，x1、x2 都要求为整数,于是可建立整数规划模型如下： Max z20x1+10x2 (1) 5x1+4x224 (2) 2x1+5x213 (3) x1,x20 (4) x1,x2为整数 (5),整数规划的数学模型,分类： 若要求所有 xj 的解为整数，称为纯整数规划 若要求部分 xj 的解为整数，称为混合整数规划,注意几点： 对应没有整数解要求的线性规划称之为松弛问题 整数规划的解是可数个的，最优解不一定发生在极点 整数规划的最优解不会优于其松弛问题的最优解,第二节 0-1 整数规划,0-1型整数规划是整数规划的一种特殊形式，它的变量xj仅取值0或1。这种只能取0或1的变量称为0-1变量或二进制变量。 下面通过一个例子说明一下：,例:篮球队需要选择5名队员组成出场阵容参加比赛。8名队员的身高及擅长位置如下： 出场阵容应满足如下条件： （1）只能由一名中锋出场； （2）至少一名后卫； （3）如1号和4号均上场，则6号不出场； （4）2号和8号至少有一个不能出场。 问：应选择哪些队员出场，使队员平均身高最高。试建立数学模型。,建立模型如下所示：,Max z= (c1x1+c2x2+c8x8）/5,x1+x2+x8=5,x1+x2=1,x6+x7+x71,x2+x8 1,xi=0或1, i=1,2,8,于是建立下列模型:,x1+x4+x6 2,课堂练习,某钻井队要从10个可供选择的井位中确定5个钻井探油，使总的钻探费用最少。若10个井位的代号为s1s10，相应的钻探费用为c1c10，并且井位选择应满足以下条件： 1) s1，s4，s5，s10井位中最多选择两个。 2) s2，s8，s9井位中最少选择一个 3) 如s3和s5都选择，则s8不选择 4) s6号和s7井位至少有一个不选择 建立该问题的数学模型。,第三节 指派问题,指派问题的标准形式及其数学模型 匈牙利解法求解指派问题 一般的指派问题,有n项任务，恰好n个人承担，第i 人完成第j 项任务的花费(时间或费用等)为cij，如何指派使总花费最省？,一、指派问题的标准形式及其数学模型,指派问题的系数矩阵如下：,Cij的含义可以不同，如费用、成本、时间等。 系数矩阵C中，第 i 行中各元素表示第 i 人做各事的费用；第j 列各元素表示第 j 事由各人做的费用。,为建立标准指派问题的数学模型，引入nn个01变量：,指派问题的数学模型可写成如下页形式：,若派第i人做第j事 0 若不派第i人做第j事 （ij=1，2,，n）,第j项工作由一个人做,第i人做一项工作,指派问题的每个可行解，可用矩阵表示如下：,矩阵X中，每行各元素中只有1个元素为1,其余各元素等0；每列各元素中也只有1个元素为1,其余各元素等0 。 指派问题有n！个可行解。,例1 有一份中文说明书，需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种的说明书所需时间如下表。问应指派何人去完成何工作，使所需总时间最少？,指派问题的数学模型如下：,已知条件可用系数矩阵（效率矩阵）表示为：,其可行解也可用每行仅有一个1，每列也仅有一个1的矩阵表示，如：,匈牙利解法的关键是利用了指派问题最优解的如下性质： 若从指派问题的系数矩阵C的某行（或某列）各元素分别减去一个常数k，得到一个新的矩阵C，则以C和C 为系数矩阵的两个指派问题有相同的最优解。 （系数矩阵的变化并不影响数学模型的约束方程组，而只是目标函数值减少了常数k，所以最优解不变）,二、匈牙利法解题步骤,1955年，库恩利用匈牙利数学家康尼格的关于矩阵中独立零元素的定理，提出了解指派问题的一种算法，称为匈牙利解法。,-2 -4 -9 -7,若某行(列)已有0元素，那就不必再减了。例1的计算为：,1. 使系数矩阵各行、各列出现零元素 作法：系数矩阵各行元素减去所在行的最小元素，再从所得矩阵的各列减去所在列最小元素。(因一行中xij 取值一个1，其余为0，cij 同时减去一常数不影响xij取值)。,匈牙利法解题步骤如下：,-4 -2,这就保证每行每列至少有一个0元素，同时不出现负元素。,2. 试求最优解。如能找出n个位于不同行不同列的零元素，令对应的xij= 1，其余xij = 0，得最优解，结束；否则下一步。,例2求表中所示效率矩阵的指派问题的最小解。,经行运算即可得每行每列都有0元素的系数矩阵。,再按上述步骤运算，得到：,3. 作能覆盖所有0元素的最少直线数的直线集合 (1) 对没有 的行打 号； (2) 对已打 号的行中所有0元素的所在列打 号； (3) 再对打有 号的列中 0 元素的所在行打 号； (4)重复(2),(3)直到得不出新的打 号的行(列)为止； (5) 对没有打 号的行画一横线，对打 号的列画一 纵线，这就得到覆盖所有0元素的最少直线数,4.未被直线覆盖的最小元素为cij,在未被直线覆盖处减去cij,在直线交叉处加上cij。,Cij=2,解为,从系数矩阵C 中，找出最大元素m，用m减去矩阵C中所有元素得以系数矩阵B，则以B为系数矩阵的最小化指派问题和以C为系数矩阵的原最大化指派问题有相同最优解。,1.最大化指派问题,三、一般的指派问题,例4 有盈利矩阵C如下，求如何分配盈利最大。,解：1. 先找出最大元素m, 即m=16，减去C中所有元素得,2. 用求目标函数最小值的方法求解（略）,若人数少事件多，添上虚拟的人，费用系数值为 0。 若事件少人数多，添上虚拟的事件，费用系数值为 0。,2.人数和事件数不等的指派问题,将该人化作相同的几个人来接受指