文档介绍：第四节 0-1型整数规划
例题:求解0-1整数规划
解法:穷举法(枚举法)、隐枚举法。(=8)
解题要点:
对于求max,变量摆放顺序按其在目标函数中值由小到大排列;
对于求min,则相反。
练习:
,(=6)
,(=3)
第五节指派问题
例题:某商业公司计划开为5家新商店。为了尽早建成营业,商业公司决定由5家建筑公司分别承建。已知建筑公司Ai(i=1,2,…,5)对新商店Bj(j=1,2,…,5)的建造费用的报价(万元)为cij(i,j=1,2,…,5),见下表。商业公司应当对5家建筑公司怎样分配建造任务,才能使总的建造费用最少?
,答案:34万元
解题要点:
在每行每列都减去该行和列的最小数,使得每行、每列都有0;
找√方法:无圈行→0列→圈行;
画线方法:无√行、有√列。
练习:求最小化指派问题。
,答案:32
,=48,,=21
上述解法叫匈牙利解法,1955年由库恩提出,此解法用到了匈牙利数学家康尼格的关于矩阵中独立零元素的定理。
即:从(cij)矩阵的每行(或列)减或加一个常数ui(或vj)构成新矩阵(cij*),cij*=cij±(ui+vj),对应(cij*)的(xij)最优解与原(cij)的最优解相同。
利用匈牙利法求解指派问题有以下条件:
⑴目标函数为求min;
⑵目标系数矩阵为方阵;
⑶目标系数矩阵(cij)≧0
具备上述条件的指派问题叫标准型指派问题,否则为非标准型指派问题。对于非标准型指派问题,一般转化为标准型求解。
转化方法如下:
⑴最大化指派问题。用矩阵中的最大元素减去矩阵中的每一个元素,就转化成了最小化指派问题。
⑵人数和事数不等的指派问题。添加虚拟的“人”或“事”,并令其在矩阵中的系数为0,就转化成了标准型指派问题。
⑶一人可做几件事的指派问题。将可做几件事的人化作相同的几个人来接受指派即可。
⑷某事一定不能由某人做的指派问题。可将相应的矩阵系数取足够大的数M。
例题:对上述例题,商业公司为了保证工程质量,决定舍弃A4和A5,而让技术力量较强的建筑公司A1、A2和A3来承建。并允许每家建筑承建一家或两家商店。求使总费用最少的指派方案。
(答案:35万元)
练习:求最小化指派问题
,