第4章 整数规划判断:用分枝定界法求解一个极大化的整数规划问题，任何一个可行解的目标函数值是该问题目标函数值的下界；指派问题数学模型的形式同运输问题十分相似，故也可以用表上作用法求解；效率矩阵的任一行（或列）减去（或加上）任一常数，指派问题最优解不会受到影响； 匈牙利法只能用于平衡分配问题；对于极大化问题，匈牙利法不能直接求解。
整数规划问题解的目标函数值优于其相应的线性规划问题的解的目标函数。
用割平面法求解整数规划问题，构造的割平面有可能切去一些不属于最优解的整数解。
用分枝定界法求解一个极大化的整数规划问题时，当得到多于一个可行解时，通常可任取其中一个作为下界值，在进行比较剪枝。
分配问题的每个元素都加上同一个常数k ，并不会影响最优分配方案。
分配问题的每个元素都乘上同一个常数k ，并不会影响最优分配方案。
分配问题域运输问题的数学模型结构形式十分相似，故也可以用表上作业法求解。
隐枚举法也可以用来求解分配问题简答试述分枝定界法求解问题的主要思想。
试述隐枚举法的步骤。
试讲述割平面方法的基本原理. 试例举三种应该剪枝的情况。
计算题分枝定界法用分枝定界法求解下列整数规划问题12max Z x x =+1212129511414123,x x x x x x +≤-+≤≥0且为整数用分枝定界法求解下列整数规划问题12max 32Z x x =+121212231429,x x x x x x +≤+≤≥0且为整数用分枝定界法求解下列整数规划问题12max 2010Z x x =+1232312312324434323,,x x x x x x x x x x x ++≤≤+≤≥－--0且为整数用分枝定界法求解下列整数规划问题12max 79Z x x =+121212136735,x x x x x x x +≤+≤≥－0，且为整数用分枝定界法求解下列整数规划问题123max 33Z x x x =++123231231231324432323,,,x x x x x x x x x x x x x ++≤≤+≤≥－--0，且为整数用分枝定界法解下列整数规划问题：1212121212232478188..3219,0MaxZ x x x x x x s t x x x x =+-+≤⎧⎪+≤⎪⎨+≤⎪⎪≥⎩且为整数用分枝定界法解下列整数规划问题1212121212250..6221,0MaxZ x x x x x x s t x x x x =++≤⎧⎪-+≤⎪⎨+≤⎪⎪≥⎩且为整数用分枝定界法解下列整数规划问题12312121225231050..7228,0,MaxZ x x x x x s t x x x x x =-+-+≤⎧⎪-≤⎨⎪≥⎩为整数用分枝定界法解下列整数规划问题12312341234345272222..0,1,2,3,4,5,j MaxZ x x x x x x x x x x x s t x j x x =-+-⎧-+-+=⎪⎪⎪-++=⎨⎪≥=⎪⎪⎩为整数用分枝定界法求解下列整数规划模型12max 23z x x =+121257354936x x x x +≤+≤12,0x x ≥且为整数有如下整数规划问题12max z x x =+12129511414123x x x x +≤-+≤12,0x x ≥且为整数试用分枝定界法求其最优解。
要求画出分枝求解过程示意图。
隐枚举法用隐枚举法求下列0－1规划问题123max 432Z x x x =++123123231235344331,,1x x x x x x x x x x x -+≤+≥+≥=2+0或用隐枚举法求下列0－1规划问题12345max 56789Z x x x x x =++++12345123451234512345223202,,,,1x x x x x x x x x x x x x x x x x x x x -++-≥+-≥≥=3-+2－－＋3＋+0或用隐枚举法求下列0－1规划问题123max 325Z x x x =-+12312312231232244346,,1x x x x x x x x x x x x x +-≤+≤+≤+≤=+0或用隐枚举法求下列0－1规划问题123max 432Z x x x =++12312313123534431,,1x x x x x x x x x x x -+≤+≥≥=2+3＋0或用隐枚举法求下列0－1规划问题123max 325Z x x x =-+1231231212322443,,1x x x x x x x x x x x +-≤+≤+≤=+0或用隐枚举法求下列0－1规划问题12345max 32523Z x x x x x =+--+1234513451245123454473483,,,,1x x x x x x x x x x x x x x x x x x ++-+≤+-≤≥=+311-6＋3-30或用隐枚举法求下列0－1规划问题1234max 4836Z x x x x =+++1234123412343547116210,,,1x x x x x x x x x x x x +++≤++≤=+80或用隐枚举法求下列0－1规划问题1234512345123452345571033542263220..221011,2,3,4,5)j MinZ x x x x x x x x x x x x x x x s t x x x x x j =++++-++-≥⎧⎪-+--+≥⎪⎨-+-+≥⎪⎪==⎩或（用隐枚举法求下列0－1规划问题1234512345123452345571033542263220..221011,2,3,4,5)j MinZ x x x x x x x x x x x x x x x s t x x x x x j =++++-++-≥⎧⎪-+--+≥⎪⎨-+-+≥⎪⎪==⎩或（用隐枚举法求下列0－1规划模型的解12345max 32523z x x x x x =+--+13451234512457343832523116333x x x x x x x x x x x x x +-+≤+--+-+-≥ 12345,,,,0x x x x x ≥指派问题用匈牙利法求解下述指派问题，已知效率矩阵分别如下：791012131216171516141511121516⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦用匈牙利法求解下述指派问题，已知效率矩阵分别如下：3821038729764275842359106910⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦解下列系数矩阵的最小分派问题：8426109554389264310395885⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦解下列系数矩阵的最小分派问题：31622942154112193955714017295041222235403842273319302916223723030504120⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦解下列系数矩阵的最小分派问题：10114287111014125691214131511107⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦解下列系数矩阵的最小分派问题：362671443858643752435762⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦已知下列五名运动员各种姿势的游泳成绩（各为50米）如下表所示，试问如何从中选拔一个参加200米混合泳的接力队，使预期比赛成绩为最好。
单位：秒分配甲、乙、丙、丁四个人去完成五项任务。
每人完成各项任务时间如下表所 示。
由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。
试确定总花费时间为最少的指派方案。
某工厂有4个工人1234,,,A A A A 分别均能操作1234,,,B B B B 四台车床中的一台， 每小时的产值如下表所示，求产值最大的分配方案。
某公司要把4个有关能源工程项目承包给4个互不相关的外商投标者，规定每个承包商只能且必须承包一个项目，试在总费用最少的条件下确定各个项目的承包者，总费用为多已知6个工厂担任4种任务的费用矩阵如下，问应该如何分配任务，使总费用最小？362671443858643752435762C ⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦设6项任务由4个工厂担任，每个工厂可担任1至2件。
已知各个工厂担任各项任务的费用矩阵如下，问应该如何分配任务，使总的费用最小？373655618427275346648732C ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦有5项设计任务可供选择。
各项设计任务的预期完工时间分别为3，8，5，4，10天，设计报酬分别为7，17，11，9，21千元。
设计任务只能一项一项的进行，总的期限使20天。
选择任务时必须满足下面要求：（1） 至少完成3项设计任务；（2） 若选择任务1，必须同时选择任务2； （3） 任务3和任务4不能同时选择；应当选择哪些设计任务，才能使总的设计报酬最大？公司在各地有4项业务，选定了4位业务员去分别处理。
由于业务能力、经验和其他情况的不同，4位业务员处理这4项业务的费用不同，费用估算见下表。
应当怎样分派这4位业务员，才能使4项业务都能得到处理，同时总的业务费用又最少？需要分派5人去做5项工作，个人做各项工作的能力评分如下表所示。
应如何分派，才能使总的得分最大？分配甲，乙，丙，丁去完成A,B,C,D ，E 五项任务。
每个人完成各项任务的时间如下表所示。
由于任务数多于人数，故考虑：（1） 任务E 必须完成，其他4项中可以任意选3项 （试分别确定最优分配方案，使完成任务的总时间最少。
考虑问题123max 201010z x x x =++约束条件 123220415x x x ++≤ 123620420x x x ++= 123,,x x x 是非负数把这个问题作为一个（连续的）线性规划来解，再说明应用简单的取整方法来得到一个可行整数解是不可能的。
（送货问题）考虑从一个中心仓库向m 各不同销地送货的工作。
在一次送货中每一个送货人至多可以合并运送r 种定货。
假定有n 条可行的路线而每一条路线规定了运送货物的销地。
再假定第j 条路线的成本是j c 。
可能发生重复以致同一个销地有不止一个送货人到达。
把这个问题表达成一个整数模型。
考虑问题12max 2z x x =+ 约束条件： 211324x x +≤ 12,x x 是非负的整数说明分数算法不能得到一个可行解，除非约束条件的系数和右边都是整数。
并求最优解。
装载货船问题）假定装到货船上的货物有五种，各种货物的单位重量i W 和单位体积i V 以及他们相应的价值i r 如下表所示船的最大载重和体积分别是W ＝112和V ＝109。