课程名称：《运筹学》第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个
内 容