第4章整数规划

第4章整数规划判断:04100011用分枝定界法求解一个极大化的整数规划问题，任何一个可行解的目标函数值是该问题目标函数值的下界；04100021指派问题数学模型的形式同运输问题十分相似，故也可以用表上作用法求解；04100031效率矩阵的任一行（或列）减去（或加上）任一常数，指派问题最优解不会受到影响；04100041匈牙利法只能用于平衡分配问题；04100051对于极大化问题，匈牙利法不能直接求解。04100061整数规划问题解的目标函数值优于其相应的线性规划问题的解的目标函数。04100071用割平面法求解整数规划问题，构造的割平面有可能切去一些不属于最优解的整数解。04100081用分枝定界法求解一个极大化的整数规划问题时，当得到多于一个可行解时，通常可任取其中一个作为下界值，在进行比较剪枝。04100091分配问题的每个元素都加上同一个常数k，并不会影响最优分配方案。04100101分配问题的每个元素都乘上同一个常数k，并不会影响最优分配方案。04100111分配问题域运输问题的数学模型结构形式十分相似，故也可以用表上作业法求解。04100121隐枚举法也可以用来求解分配问题简答04200011试述分枝定界法求解问题的主要思想。04200021试述隐枚举法的步骤。04200031试讲述割平面方法的基本原理.04200041试例举三种应该剪枝的情况。计算题分枝定界法04301012用分枝定界法求解下列整数规划问题12maxZxx1212129511414123,xxxxxx0且为整数04301022用分枝定界法求解下列整数规划问题12max32Zxx121212231429,xxxxxx0且为整数04301032用分枝定界法求解下列整数规划问题12max2010Zxx1232312312324434323,,xxxxxxxxxxx－--0且为整数04301041用分枝定界法求解下列整数规划问题12max79Zxx121212136735,xxxxxxx－0，且为整数04301053用分枝定界法求解下列整数规划问题123max33Zxxx123231231231324432323,,,xxxxxxxxxxxxx－--0，且为整数04301062用分枝定界法解下列整数规划问题：1212121212232478188..3219,0MaxZxxxxxxstxxxx且为整数04301072用分枝定界法解下列整数规划问题1212121212250..6221,0MaxZxxxxxxstxxxx且为整数04301082用分枝定界法解下列整数规划问题12312121225231050..7228,0,MaxZxxxxxstxxxxx为整数04301092用分枝定界法解下列整数规划问题12312341234345272222..0,1,2,3,4,5,jMaxZxxxxxxxxxxxstxjxx为整数04301101用分枝定界法求解下列整数规划模型12max23zxx121257354936xxxx12,0xx且为整数04301111有如下整数规划问题12maxzxx12129511414123xxxx12,0xx且为整数试用分枝定界法求其最优解。要求画出分枝求解过程示意图。隐枚举法04302011用隐枚举法求下列0－1规划问题123max432Zxxx123123231235344331,,1xxxxxxxxxxx2+0或04302022用隐枚举法求下列0－1规划问题12345max56789Zxxxxx12345123451234512345223202,,,,1xxxxxxxxxxxxxxxxxxxx3-+2－－＋3＋+0或04302031用隐枚举法求下列0－1规划问题123max325Zxxx12312312231232244346,,1xxxxxxxxxxxxx+0或04302041用隐枚举法求下列0－1规划问题123max432Zxxx12312313123534431,,1xxxxxxxxxxx2+3＋0或04302052用隐枚举法求下列0－1规划问题123max325Zxxx1231231212322443,,1xxxxxxxxxxx+0或04302062用隐枚举法求下列0－1规划问题12345max32523Zxxxxx1234513451245123454473483,,,,1xxxxxxxxxxxxxxxxxx+311-6＋3-30或04302072用隐枚举法求下列0－1规划问题1234max4836Zxxxx1234123412343547116210,,,1xxxxxxxxxxxx+80或04302091用隐枚举法求下列0－1规划问题1234512345123452345571033542263220..221011,2,3,4,5)jMinZxxxxxxxxxxxxxxxstxxxxxj或（04302102用隐枚举法求下列0－1规划问题1234512345123452345571033542263220..221011,2,3,4,5)jMinZxxxxxxxxxxxxxxxstxxxxxj或（04302113用隐枚举法求下列0－1规划模型的解12345max32523zxxxxx13451234512457343832523116333xxxxxxxxxxxxx12345,,,,0xxxxx指派问题04303011用匈牙利法求解下述指派问题，已知效率矩阵分别如下：79101213121617151614151112151604303021用匈牙利法求解下述指派问题，已知效率矩阵分别如下：382103872976427584235910691004303032解下列系数矩阵的最小分派问题：842610955438926431039588504303042解下列系数矩阵的最小分派问题：3162294215411219395571401729504122223540384227331930291622372303050412004303051解下列系数矩阵的最小分派问题：1011428711101412569121413151110704303062解下列系数矩阵的最小分派问题：36267144385864375243576204303072已知下列五名运动员各种姿势的游泳成绩（各为50米）如下表所示，试问如何从中选拔一个参加200米混合泳的接力队，使预期比赛成绩为最好。单位：秒赵钱张王周仰泳蛙泳蝶泳自由泳37.743.433.329.232.933.128.526.433.842.238.929.637.034.730.428.535.441.833.631.104303083分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如下表所示。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。ABCDE甲乙丙丁253934242938274231262836422040233733324504303092某工厂有4个工人1234,,,AAAA分别均能操作1234,,,BBBB四台车床中的一台，每小时的产值如下表所示，求产值最大的分配方案。1B2B3B4B1A1098704303102某公司要把4个有关能源工程项目承包给4个互不相关的外商投标者，规定每个承包商只能且必须承包一个项目，试在总费用最少的条件下确定各个项目的承包者，总费用为多少？各承包商对工程的报价如下表所示。ABCD甲乙丙丁1519261918231721212216232418191704303112已知6个工厂担任4种任务的费用矩阵如下，问应该如何分配任务，使总费用最小？362671443858643752435762C04303123设6项任务由4个工厂担任，每个工厂可担任1至2件。已知各个工厂担任各项任务的费用矩阵如下，问应该如何分配任务，使总的费用最小？373655618427275346648732C04303132有5项设计任务可供选择。各项设计任务的预期完工时间分别为3，8，5，4，10天，设计报酬分别为7，17，11，9，21千元。设计任务只能一项一项的进行，总的期限使20天。选择任务时必须满足下面要求：（1）至少完成3项设计任务；（2）若选择任务1，必须同时选择任务2；（3）任务3和任务4不能同时选择；应当选择哪些设计任务，才能使总的设计报酬最大？04303142公司在各地有4项业务，选定了4位业务员去分别处理。由于业务能力、经验和其他情况的不同，4位业务员处理这4项业务的费用不同，费用估算见下表。应当怎样分派这4位业务员，才能使4项业务都能得到处理，同时总的业务费用又最少？2A34563A21124A435604303152需要分派5人去做5项工作，个人做各项工作的能力评分如下表所示。应如何分派，才能使总的得分最大？工作评分人员1B2B3B4B5B平车考克卷边绷缝打眼1A1.30.8001.02A01.21.31.303A1.0001.204A01.0500.21.45A1.00.90.601.104303163分配甲，乙，丙，丁去完成A,B,C,D，E五项任务。每个人完成各项任务的时间如下表所示。由于任务数多于人数，故考虑：（1）任务E必须完成，其他4项中可以任意选3项（2）其中有一个人完成两项，其他人每人完成一项。ABCDE甲2529314237乙3938262033丙3427284032丁2442362345试分别确定最优分配方案，使完成任务的总时间最少。04303171考虑问题123max201010zxxx业务费用业务员1234111008001000700260050030080034008001000900411001000500700约束条件123220415xxx123620420xxx123,,xxx是非负数把这个问题作为一个（连续的）线性规划来解，再说明应用简单的取整方法来得到一个可行整数解是不可能的。04303181（送货问题）考虑从一个中心仓库向m各不同销地送货的工作。在一次送货中每一个送货人至多可以合并运送r种定货。假定有n条可行的路线而每一条路线规定了运送货物的销地。再假定第j条路线的成本是jc。可能发生重复以致同一个销地有不止一个送货人到达。把这个问题表达成一个整数模型。04303192考虑问题12max2zxx约束条件：211324xx12,xx是非负的整数说明分数算法不能得到一个可行解，除非约束条件的系数和右边都是整数。并求最优解。04303202装载货船问题）假定装到货船上的货物有五种，各种货物的单位重量iW和单位体积iV以及他们相应的价值ir如下表所示货物iiWiVir15142887336642555744船的最大载重和体积分别是W＝112和V＝109。现在要确定怎样装运各种货物才可使装运的价值最大。把这个问题表示成整数规划模型再用分支定界法来解。043032