《运筹学》课程授课教案（讲稿）第14讲 0-1型整数规划

课程名称：《运筹学》第14讲次授课题目0-1型整数规划本讲目的要求及重点难点：[目的要求］通过本讲课程的学习，掌握0-1变量的实际应用，并能够求解。[重点及难点]匈牙利法。内容[本讲课程的引入]今天我们开始学习一类特殊的整数问题，0-1型整数规划问题。[本讲课程的内容]1、0-1变量的概念0-1变量：一种逻辑变量，常用来表示系统处于某个特定状态，或者决策时是否取某个特定方案。【1当决策取方案P时x=0当决策不取方案P时2、0-1变量的实际应用（1）制定相互排斥的计划例1：投资场所的选定某公司拟在市东、西、南三区建立门市部，拟议中有7个位置A可供选择，规定：在东区，由A：A，A，三个点中至多选两个；在西区，由A4，A，两点中至少选择1个：在南区，由A，A，两点中至少选择1个。若选择A，点，估计设备投资为b，元，获利c，，但投资不能超过B元，如何投资获利最大？Max Z-Ecxi【1当A,点被选用时解：X(Ebx<≤B[0当A4,点未被选用时xi+x2+xg≤2x+xg≥1xg+x,≥1x=0或1(i=-1,2...n)

课程名称：《运筹学》 第 14 讲次 授课题目 0-1 型整数规划 本讲目的要求及重点难点： 目的要求] 通过本讲课程的学习，掌握 0-1 变量的实际应用，并能够求解。 [重点及难点] 匈牙利法。 内 容 [本讲课程的引入] 今天我们开始学习一类特殊的整数问题，0-1 型整数规划问题。 [本讲课程的内容] 1、0-1 变量的概念 0-1 变量：一种逻辑变量，常用来表示系统处于某个特定状态，或者决策时是否取某个特定 方案

内容（2）相互排斥的约束条件问题例：集装箱运货（用车运或用船运）重量车运体积船运体积利润甲57220435乙10托运限451324制两种货物各托运多少箱可以使利润最大？【1船运分析：0车运5x,+4x,≤245x,+4x,≤24+yM7x,+3x,≤457x)+3x2≤45+(1-y)M1船运解：xi，分别为甲乙两种货物的托运数量0车运Max Z=20x,+10x25x,+4x2≤24+yM7x,+3x,≤45+(1-p)M2x,+5x2≤13X，X2≥0，J=0或1为整数中（3）固定费用问题例：有三种资源被用于生产三种产品，资源量、产品单件可变费用售价、资源单耗量及组织三种产品生产的固定费用见下表。要求制定一个生产计划使总收益为最大。产品IIIII资源量资源A248500B234300c123100546单件可变费用100150200固定费用810单价12

内 容

内容解：设x，为生产第1种产品的产量，y为0-1变量MaxZ=4x,+5x,+6x3-100yr-150y2-200y32x,+4x2+8x,≤5002x,+3x,+4x,≤300x,+2x2+3x,≤100x,≤Miyix,≤M2J2x,≤Msys,≥0且为整数，j=1,2,3yF0或1，j=1,2,33、0-1型整数规划的解法隐枚举法隐枚举法：不同于穷举法，只检查变量取值组合的一部分就能找到问题的最优解。解题关键是寻找可行解，产生过滤条件。过滤条件：目标函数值优于计算过的可行解目标函数值。maxZ=3X,-2X,+5X,(X+2X2-X,≤2①X +4X,+X, ≤4 ②X+X≤3③4X,+, ≤6 ①约束条件过滤Z值XXX=0或1(X1/X2,X3)条件0??④(0,0,0)0Z>0JVVy5(0,0,1)Z≥51Y2(0,1,0)3(0,1,1)3(1,0,0)8(1,0,1)Z≥8(1,1,0)16(1,1,1)五、指派问题1、典型的指派问题某单位需完成n项任务，恰有n个人可以承担，由于每个人的专长不同，各人

内 容 3、0-1 型整数规划的解法 ——隐枚举法 隐枚举法：不同于穷举法，只检查变量取值组合的一部分就能找到问题的最优 解。解题关键是寻找可行解，产生过滤条件。 过滤条件：目标函数值优于计算过的可行解目标函数值。 五、指派问题 1、典型的指派问题 某单位需完成 n 项任务，恰有 n 个人可以承担，由于每个人的专长不同，各人

内容完成任务的效率不同，各人完成一项任务的同时，不能同时去做其它任务，如何分配任务会使所需的时间最小或成本最低。例：有一份中文说明书，需译成英、日、德、俄四种文字，分别记做E、J、G、R。现有甲、乙、丙、丁4人，他们将中文说明书翻译成不同语种的说明书所需的时间如下，问应指派何人去完成何种工作，使所需总时间最少？任务EGJR人员2甲151341041415乙91613丙147.811丁9指派问题的标准形式n个人，n件事，第i个人做第/件事的费用为cu确定人和事之间对应的指派方案，使完成n件事-的总费用最小。CiCin2.. Cin效率矩阵C21C22..C2nC-(Cg)nxn=或...............++系数矩阵Cul Cu .. Cnn1513241510414C-(cy)nxn1391416781192、标准指派问题的数学模型【1指派第i个人做第j件事xiF0不指派第i个人做第件事2min Z =H片x, =1 j-1,2..ni=1i-1,2..n解矩阵：满足约束条件的可行解也可以写成表格或矩阵的形式，称为解矩阵。0100各行各列的元0010例：X=(xg)4×4=素和都是10001000￥1

内 容 完成任务的效率不同，各人完成一项任务的同时，不能同时去做其它任务，如何分配任务 会使所需的时间最小或成本最低

内容3、匈牙利解法（1）关键性质：若从指派问题的系数矩阵(cr)axn的某行或某列各元素中分别减一个常数k，得到的新矩阵与原矩阵有相同的最优解。2415134151014C-(cy)nXn=9131416.78119J（2）基本思想：对同一项工作i来说，同时提高或降低每人相同的效率（常数k），不影响最优指派；同样，对同一个人i来说，完成各项工作的效率都提高或降低相同的效率（常数d)，也不影响最优指派，因此可得到新的系数矩阵(c)ax，个含有很多0元素的新系数矩阵，而最优解不变。min Z=自产2151341041415C=(Cg)nXn=9131416189:11（3）匈牙利法的步骤：第一步：使指派问题的系数矩阵经变换，在各行各列中都出现0元素。（1）从系数矩阵的每行元素减去该行的最小元素：（2）再从所得系数矩阵的每列元素中减去该列的最小元素。若某行（列)已有0元素，那就不必再减了。1321513401121310154146010119141613054781190214第二步：进行试指派，以寻求最优解。【若有n个，计算结束寻找独立0"元素若大于n个

内 容

内容(1）从只有一个0元素的行(列)开始，给这个0元素加圈，记作。这表示对这行所代表的人，只有一种任务可指派。然后划去所在列(行)的其他0元素，记作Φ。这表示这列所代表的任务已指派完，不必再考虑别人了。(2）给只有一个0元素列（行）的0元素加圈，记作：然后划去所在行的0元素，记作Φ。(3）反复进行(1)，(2)两步，直到所有0元素都被圈出和划掉为止。(4）若仍有没有划圈的0元素，且同行（列)的0元素至少有两个(表示对这个可以从两项任务中指派其一）。这可用不同的方案去试探。从剩有0元素最少的行（列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈（表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其他0元素。可反复进行，直到所有0元素都已圈出和划掉为止。(5）若元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到。若m<n，则转入下一步。1311C=(Cg)nXnO23Q&1可见m=n=4,所以得最优解为(0001)这表示：指定甲译出俄文0-1乙译出日文，丙译出英文(xg):0丁译出德文。0所需总时间最少00101513241415104C=(cg)nxn=13141698119J1Min Z=C31+C22+c43+C14=4+4+9+11=28例8求表所示效率矩阵的指派问题的最小解

内 容 (4) 若仍有没有划圈的 0 元素，且同行(列)的 0 元素至少有两个(表示对这个可以从 两项任务中指派其一)。这可用不同的方案去试探。从剩有 0 元素最少的行(列)开始，比较 这行各 0 元素所在列中 0 元素的数目，选择 0 元素少的那列的这个 0 元素加圈(表示选择性 多的要“礼让”选择性少的)。然后划掉同行同列的其他 0 元素。可反复进行，直到所有 0 元 素都已圈出和划掉为止。 (5) 若◎元素的数目 m 等于矩阵的阶数 n，那么这指派问题的最优解已得到。若 m＜n， 则转入下一步

容内任务DEABc人员甲779129Z89666丙71712149丁15146610成4107109解按上述第一步，将这系数矩阵进行变换1(12799750202896663000971712141015141069687-4101094再按上述步骤运算(522)0d23OΦd57102O98d45636d这里③的个数m=4，而n=5：所以解题没有完成这时应按以下步骤继续进行70202340001008350810011843605N04431V第三步：作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到最多的独立元素数。为此按以下步骤进行：（1）对没有的行打／号；(2）对已打／号的行中所有含Φ元素的列打／号；（3）再对打有√号的列中含元素的行打／号：

内 容 第三步：作最少的直线覆盖所有 0 元素，以确定该系数矩阵中能找到最多的独立元素 数。为此按以下步骤进行： (1) 对没有◎的行打√号； (2) 对已打√号的行中所有含Φ元素的列打√号； (3) 再对打有√号的列中含◎元素的行打√号；

内容(4）重复(2)，（3)直到得不出新的打号的行、列为止。(5）对没有打／号的行画一横线，有打／号的列画一纵线，这就得到覆盖所有0元素的最少直线数。令这直线数为l。若l<n，说明必须再变换当前的系数矩阵，才能找到n个独立的0元素，为此转第四步：若=n，而m<n，应回到第二步(4)，另行试探。注：m为的个数由此可见I=4<n。所以应继续对矩阵进行变换。转第四步。第四步：对②矩阵进行变换的目的是增加0元素。为此在没有被直线覆盖的部分中找出最小元素。然后在打√行各元素中都减去这最小元素，而在打√列的各元素都加上这最小元素，以保证原来0元素不变。这样得到新系数矩阵（它的最优解和原问题相同)。若得到n个独立的0元素，则已得最优解，否则回到第三步重复进行。0027七308008110-348d11

内 容 (4) 重复(2)，(3)直到得不出新的打√号的行、列为止。 (5) 对没有打√号的行画一横线，有打√号的列画一纵线，这就得到覆盖所有 0 元素 的最少直线数。 令这直线数为 l。若 l＜n，说明必须再变换当前的系数矩阵，才能找到 n 个独立的 0 元素，为此转第四步：若 l=n，而 m＜n，应回到第二步(4)，另行试探。 注：m 为◎的个数 由此可见 l=4＜n。所以应继续对矩阵进行变换。转第四步。 第四步：对②矩阵进行变换的目的是增加 0 元素。为此在没有被直线覆盖的部分中找 出最小元素。然后在打√行各元素中都减去这最小元素，而在打√列的各元素都加上这最 小元素，以保证原来 0 元素不变。这样得到新系数矩阵(它的最优解和原问题相同)。若得 到 n 个独立的 0 元素，则已得最优解，否则回到第三步重复进行

内容1000L已具有n个独立0元素。这就得到了00最优解，相应的解矩阵为000101000·由解矩阵得最优指派方案：0000甲-B，乙-D，丙-E，丁-C，戊-A本例还可以得到另一最优指派方案：甲-B，乙-C，丙E，丁-D，戊-A所需总时间为minz=324815512例：719171014C=(cy)nxn76912810671466610912解按上述第一步，将这系数矩阵进行变换。83110X11083U023103003210232408-0-003240-再按上述步骤运算Φ31183O1Φ2321O51o4Φ2340这里的个数m=4，而n=5；所以解题没有完成，这时应按以下步骤继续进行。第三步：作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到最多的独立元素数。为此按以下步骤进行：(1）对没有○的行打／号；

内 容 第三步：作最少的直线覆盖所有 0 元素，以确定该系数矩阵中能找到最多的独立元素 数。为此按以下步骤进行： (1) 对没有◎的行打√号；

内容(2）对已打／号的行中所有含Φ元素的列打／号；(3）再对打有／号的列中含元素的行打／号：(4)重复(2)，(3)直到得不出新的打√号的行、列为止。（5）对没有打／号的行画一横线，有打／号的列画一纵线，这就得到覆盖所有0元素的最少直线数。令这直线数为l。若1<n，说明必须再变换当前的系数矩阵，才能找到n个独立的0元素，为此转第四步：若1=n，而m<n，应回到第二步(4)，另行试探。由此可见=4<n。所以应继续对矩阵进行变换。转第四步。第四步：对②矩阵进行变换的目的是增加0元素。为此在没有被直线覆盖的部分中找出最小元素。然后在打√行各元素中都减去这最小元素，而在打√列的各元素都加上这最小元素，以保证原来0元素不变。这样得到新系数矩阵（它的最优解和原问题相同）。若得到n个独立的0元素，则已得最优解，否则回到第三步重复进行。0S

内 容 (2) 对已打√号的行中所有含Φ元素的列打√号； (3) 再对打有√号的列中含◎元素的行打√号； (4) 重复(2)，(3)直到得不出新的打√号的行、列为止。 (5) 对没有打√号的行画一横线，有打√号的列画一纵线，这就得到覆盖所有 0 元素 的最少直线数