3.4指派问题(经典运筹学)

一、决策问题与0-1变量件事是否做第决策变量ixiix10做第i件事不做第i件事ni,,2,1n件事中必须做k件并只做k件事kxxxn21n件事中最多做k件事kxxxn21n件事中至少做k件事nxxx21k做第i件事的充要条件是做第j件事jixx做第i件事的充要条件是不做第j件事jixx1只在做了第i件事前提下才考虑是否做第j件事ijxx该公司只有600万资金可用于投资，由于技术上的原因，投资受到以下约束：1、在项目1、2和3中必须有一项被选中2、项目3和4只能选中一项3、项目5被选中的前提是项目1被选中;如何在满足上述条件下选择一个最好的投资方案，使投资收益最大例1（投资问题）华美公司有5个项目被列入投资计划，每个项目的投资额和期望的投资收益见下表：项目投资额（万元）投资收益（万元）121015023002103100604130805260180)5,,2,1ixi为决策变量（解：设ix10投资第i个项目不投资第i个项目Z表示投资效益投资项目模型：543211808060210150maxxxxxxZts.60026013010030021054321xxxxx1321xxx143xx15xx5,,2,11,0ixi例2（布点问题）某城市共有6个区，每个区都可以建消防站。市政府希望设置的消防站最少，但必须满足在城市任何地区发生火火警时，消防车要在15分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见右表。地区123456101016282720210024321710316240122721428321201525527172715014620102125140请为该市制定一个最节省的计划解：01ix在第i个地区建站Z表示全区消防站总数不在第i个地区建站i=1,2,…,6布点问题模型：654321minxxxxxxZ6,,2,11,0ixits.121xx1621xxx143xx1543xxx1652xxx最优解x2=1,x4=1最优值Z=2二、过滤隐枚举法（适合于变量个数较少的0-1规划）10,,64342422.253max3213221321321321或例：求xxxxxxxxxxxxxtsxxxZ（x1x2x3)Z值约束条件（1）（2）（3）（4）过滤条件（000）（001）（010）（100）（101）（110）（011）（111）√√√√0Z≥0枚举法：检验可行解：32次运算-25√√√√Z≥5318×366111321Zxxx最优值，，最优解：运算次数：21计算目标函数值：8次√√√√三、指派问题与匈牙利法设有n个工作，要由n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。12…j…n12…i…n指派问题模型：jiijijxcZmin1.21inijiixxxxtsi=1,2,…,n121njijjjxxxxj=1,2,…,nnjnixij,,2,1;,,2,11,0解：第i个人做第j人件事Z表示总费用i=1,2,…,n;j=1,2,…,n第i个人不做第j人件事01ijxnnnjnninijiinjnjcccccccccccccccc21212222211112111、指派问题的数学模型jiijijxcZminnnnnnnnnnnnnxcxcxcxcxcxcxcxcxc2211222222212111121211111.21inijiixxxxts121njijjjxxxxi=1,2,…,nj=1,2,…,n当n=4时，有16变量，8个约束方程111.21222221111211nnnjnnnjnjxxxxxxxxxxxxts11121222212112111nninnnninixxxxxxxxxxxx例：现有4份工作，4个人应聘，由于各人技术专长不同，他们承担各项工作所需费用如下表所示，且规定每人只能做一项工作，每一项工作只能由一人承担，试求使总费用最小的分派方案。工作人1234123435456768898101010911解：ijx10第i人做第j件事Z表示总费用i=1,2,3,4;j=1,2,3,4第i人不做第j件事141312115453maxxxxxZ242322218676xxxx3433323110898xxxx444342411191010xxxx1.14131211xxxxts124232221xxxx134333231xxxx144434241xxxx141312111xxxx142322212xxxx143332313xxxx144342414xxxxnjnixij,,2,1,,2,11,02、费用矩阵设有n个工作，要由n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。12…j…n12…i…nnnnjnninijiinjnjcccccccccccccccc2121222221111211nnnnnncccccccccC212222111211取cij表示第i个人做第j件事的费用费用矩阵例：现有4份工作，4个人应聘，由于个人的技术专长不同，他们承担各项工作所需费用如下表所示，且规定每人只能做一项工作，每一项工作只能由一个人承担，试求使总费用最小的分派方案。工作人1234123435456768898101010911费用矩阵11910101089886765453C0753193506650016532054321C设对应一个5个人5个工作的指派问题第2个人做第4个工作的费用5第4个人做第2个工作的费用0定理：在费用矩阵C=（cij）的任一行（列）中减去一个常数或加上一个常数不改变本问题的最优解。n个人n个工作的指派问题1nnnniniinnccccccccccccC21212222111211-bnnnniniinncccbcbcbcccccccC21212222111211iniicccb,,,min213、匈牙利法n个人n个工作的指派问题2Zminnnnnnnnnininiiiinnnnxcxcxcxcxcxcxcxcxcxcxcxc22112211222222212111121211111.21inijiixxxxts121njijjjxxxxnjnixij,,2,1;,,2,11,0i=1,2,…,nj=1,2,…,nZminnnnnnnnnininiiiinnnnxcxcxcxbcxbcxbcxcxcxcxcxcxc2211221122222221211112121111)()()(nnnniniinnccccccccccccC21212222111211nnnniniinncccbcbcbcccccccC212122221112111.21inijiixxxxts121njijjjxxxxnjnixij,,2,1;,,2,11,0i=1,2,…,nj=1,2,…,n-bZminnnnnnnnnininiiiinnnnxcxcxcxbcxbcxbcxcxcxcxcxcxc2211221122222221211112121111)()()()(212211221122222221211112121111iniinnnnnnnnininiiiinnnnxxxbxcxcxcxcxcxcxcxcxcxcxcxcbxcxcxcxcxcxcxcxcxcxcxcxcnnnnnnnnininiiiinnnn2211221122222221211112121111ZminZminnnnnnnnnininiiiinnnnxcxcxcxcxcxcxcxcxcxcxcxc2211221122222221211112121111bxcxcxcxcxcxcxcxcxcxcxcxcnnnnnnnnininiiiinnnn2211221122222221211112121111nnnniniinnccccccccccccC21212222111211nnnniniinncccbcbcbcccccccC21212222111211-b1.21inijiixxxxts121njijjjxxxxnjnixij,,2,1;,,2,11,0i=1,2,…,nj=1,2,…,n1.21inijiixxxxts121njijjjxxxxnjnixij,,2,1;,,2,11,0i=1,2,…,nj=1,2,…,nbZbZZminZmin的最优解是若ZXmin0的最优解也是，则ZXmin0的最优值是若ZZmin0的最优值是，则若ZbZmin0任务：对C的行和列减去某个常数，将C化的尽可能简单，简单到可一眼看出该问题的最优解nnnniniinnccccccccccccC21212222111211nnnniniinncccbcbcbcccccccC21212222111211-bbZbZ三、指派问题与匈牙利法12…j…n12…i…n指派问题模型：jiijijxcZmin1.21inijiixxxxtsi=1,2,…,n121njijjjxxxxj=1,2,…,nnjnixij,,2,1;,,2,11,0解：第i个人做第j人件事Z表示总费用i=1,2,…,n;j=1,2,…,n第i个人不做第j人件事01ijxnnnjnninijiinjnjcccccccccccccccc21212222211112111、指派问题的数学模型设有n个工作，要由n个人来承担，每个工作只能由一个人承担，且每个人只能承担一个工作。cij表示第i个人做第j件事的费用,求总费用最低的指派方案。2、费用矩阵设有n个工作，要由n个人来承