线性规划整数规划教学PPT.ppt

第四讲 整数规划,在求解线性规划问题时，得到的最优解可能是分数或小数，但许多实际问题要求得到的解为整数才行。这种要求线性规划有整数解的问题,称为整数规划(integer programming)或简称ip。,第一节 整数规划的数学模型及解的特点,整数规划的数学模型,第二节 0-1 整数规划,0-1型整数规划是整数规划的一种特殊形式，它的变量xj仅取值0或1。这种只能取0或1的变量称为0-1变量或二进制变量。 下面通过过以下几个例子说明一下：,篮球队要选择5名队员组成上场阵容，8名队员的身高及擅长位置见下表：,上场阵容应满足以下条件： (1)只能有一名中锋上场 (2)至少有一名后卫 (3)如一号和4号均上场，则6号不出场 (4)2号和8号至少有一个不出场 问应如何选择5名上场队员，才能使出场队员平均身高最高，试建立其模型。,1,2,8,9,10,7,3,4,6,5,11,1,2,3,4,监视摄像头安装,2,1,3,10,4,5,6,7,9,8,12,11,13,二.解01规划的过滤隐枚举法 01规划若有n个变量，则产生2n个可能的组合，当n较大则完全枚举不可能。 最优解为目标函数值最大的可行解。 可行解为满足所有约束条件的解。,1.找出任意一可行解，目标函数值为z0；,2. 原问题求最大值时，则增加一个过滤条件,3. 列出所有可能解，对每个可能解先检验式（*），若满足再检验其它约束，若不满足式（*），则过滤掉，若所有约束都满足，求出目标值，判断此时目标函数值是否大于过滤条件，若是，用当前的目标函数值代替过滤条件值，否则过滤条件不变。,4. 目标函数值最大（最小）的解就是最优解。,（*）,第三节 指派问题,指派问题的标准形式及其数学模型 匈牙利解法求解指派问题 一般的指派问题,有n项任务，恰好n个人承担，第i 人完成第j 项任务的花费(时间或费用等)为cij，如何指派使总花费最省？,一、指派问题的标准形式及其数学模型,100自由泳 皮特-范登霍根邦德 荷兰 47.84 2000年9月19日 100米仰泳 兰尼-克雷泽尔伯格 美国 53.60 1999年8月24日 100蛙泳 北岛康介 日本 59.78 2003年7月21日 100蝶泳 伊安-克罗克尔 美国 50.98 2003年7月26日 100米自由泳 50.51沈坚强上 海1989年全国游泳冠军赛 100米仰泳 55.11欧阳鲲鹏上 海2002年国家游泳队测验赛 100米蛙泳 1:01.66曾启亮广 东第8届全运会 100米蝶泳 53.20蒋丞稷上 海第26届奥运会,指派问题的系数矩阵如下：,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！个可行解。,匈牙利解法的关键是利用了指派问题最优解的如下性质： 若从指派问题的系数矩阵c的某行（或某列）各元素分别减去一个常数k，得到一个新的矩阵c，则以c和c 为系数矩阵的两个指派问题有相同的最优解。,二、匈牙利法解题步骤,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。 若事件少人数多，添上