指派问题（经典运筹学）

3.40-1整数规划，1。决策问题和0-1变量，1，0，做第一项，不做第一项，做第K项，只做第N项中的第K项，最多做第N项中的第K项，至少做第N项中的第K项，做第一项的充要条件是做第J项，做第一项的充要条件是不做第J项，只考虑在做第一项的前提下是否做第J项，公司只有600万资金可供投资。由于技术原因，投资限制如下：1 .项目1、2和3中的一个项目必须选择2，项目3和4中只能选择一个项目3，项目5必须在选择项目1的前提下选择；如何在上述条件下选择最佳投资方案，使投资收益最大化？例1(投资问题)华美公司在投资计划中列出了5个项目。每个项目的投资金额和预期投资收益如下表所示：1，0。投资第一个项目，不要投资第一个项目。z代表投资收益。投资项目模式：例2(分配问题)一个城市有6个区，每个区都可以建消防站。市政府希望至少建立消防站，但必须满足当城市任何地方发生火灾时，消防车应在15分钟内到达现场的要求。根据现场测量，消防车在各区之间的行驶时间如右图所示。请为城市做一个最经济的规划，在I区建消防站，z代表整个区消防站的总数，不在I区建消防站，I=1，2，6，定位问题模型：最优解x2=1，x4=1，最优值z=2，2，过滤隐式枚举法，(适用于0-1少变量规划)，(000)，(001)，(010)，(100)，(101)，(110)，(011)，(111)， , 0，z 0，枚举法：测试可行解：32个运算，-2，5， , z 5，3，1，8，3，6，运算数：21，计算Cij代表第一个做第一件事的人的成本，寻找总成本最低的分配方案。分配问题模型：I=1，2，n，j=1，2，第一个人做第一件事，z代表总成本，I=1，2，n；J=1，2，第I个人不做第j件事。指派问题数学模型，I=1，2，n，j=1，2，当n=4时，有16个变量，8个约束方程，例如，有4个工作和4个候选人。由于每个人的技术专长不同，他们承担每个工作的费用，如下表所示，并规定每个人只能做一个工作，每个工作只能由一个人承担。试着找到使总成本最小化的分配方案。工作，人员，费用，1234，1234，3545，6768，89810，1010911，1，0，I做j的事情，z代表总成本，i=1，2，3，4；J=1，2，3，4，第一个人不做j，2，成本矩阵，有n个工作，由n个人承担，每个工作只能由一个人承担，每个人只能承担一个工作。Cij代表第一个做第一件事的人的成本，寻找总成本最低的分配方案。Cij代表我个人做成本矩阵的成本。例如，有4个工作和4个候选人。由于他们的技术专长不同，他们必须承担每个工作的费用，如下表所示，每个人只能做一个工作，每个工作只能由一个人承担。尝试找到一个最小化总成本的分配方案。例如，如果你不能找到解决问题的最佳方法，你就不能通过在成本矩阵C=(cij)的任何一行(列)中减去一个常数或增加一个常数来找到解决问题的最佳方法。n个人和n个工作的分配问题1，-b，3，匈牙利定律，n个人和n个工作的分配问题2，I=1，2，n，j=1，2，n，I=1，2，n，j=1，2，n，j=1，2，n，-b，b，I=1，2，n，j=1，2，n，j=1，2，n，任务：从C的行和列中减去一个常数，并使C尽可能简单，这样问题的最优解就可以一目了然，b，3.40-1整数规划，3，赋值问题和匈牙利方法，成本，12.j.n，12.i.指派问题模型：I=1，2，n，j=1，2，n，I人做J人的事情，z代表总成本，I=1，2，n；J=1，2，第一个人不做第二件事。1.指派问题的数学模型有n个工作由n个人承担，每个工作只能由一个人承担，每个人只能承担一个工作。Cij代表第一个做第一件事的人的成本，寻找总成本最低的分配方案。(2)成本矩阵，n个工作由n个人承担，每个工作只能由一个人承担，每个人只能承担一个工作。Cij代表第一个做第一件事的人的成本，寻找总成本最低的分配方案。成本，12.j.n，12.i.n，cij代表第一个做j事情的人的成本，成本矩阵，定理：从成本矩阵的任何一行(列)减去一个常数C=(cij)或增加一个常数不会改变问题的最优解。赋值问题的最优解：如果在C中不同的行和列中有n个零元素，那么让这些零元素对应的变量取1，其他变量取0，从而得到赋值问题的最优解，i=1，2，3，4，j=1，2，3，4，可行解，最优解，匈牙利方法的基本思想：从成本矩阵C的行和列中减去一个常数，C被转换成位于不同行和列中的n个零元素， 因此对应于这些零元素的变量取1，而其他变量取0，从而获得分配问题的最优解。 例如，有一本手册要分别翻译成英文、日文、德文和俄文，现在交给四个人，即A、B、C和D，来完成一本。由于个人专长不同，翻译成不同语言所需的时间(小时)如右侧表格所示。询问应该派谁去完成哪个任务，这样可以最大限度地减少总时间。工作，人，时间，英国，日本，德国和俄罗斯，甲方，乙方，丙方，丁方，215134，1041415，9141613，78119，和-2，4，9，7，和最佳计划：甲翻译俄语，乙翻译日语，丙翻译英语，丁翻译德语，总成本为28小时，和-4，2，2，4，9，7，4，2，如何得到最佳解决方案：从，然后在0所在的行和列中剪切掉剩余的0个元素，并使用该表示，依此类推。 如果可以获得n个0元素，那么最优解X0、示例：在成本矩阵的右表中找到分配问题的最优解、工作、人员、成本、ABCDE、a、b、c、d、e、127979、89666、717121412、15146610、410716、-7、-6、-4等对于n阶成本矩阵c，如果c在不同的行和列中有n个0元素，则最优解X0否则，调整C-2，2，2，2，最佳分配方案：A代表B，B代表C，C代表A，D代表D，E代表E？什么？当C在不同的行和列中没有N个零元素时调整C。第一步是使直线的最小集合能够覆盖所有的0个元素，1)在没有0的行上打勾，2)在没有0的行上打勾所有0个元素的列，3)在没有0的行上打勾所有0个元素的行，4)重复上述步骤直到找不到新的， 5)在没有的行上画水平线，在所有没有的列上画垂直线，得到覆盖所有0个元素的直线。步骤2:在没有被直线覆盖的元素中找出最小的元素，把这个元素加到标有的列上，从标有的行上减去这个元素。步骤3:在得到的矩阵上画0，如果可以得到n 0，则得到最优解，否则重复上述步骤，直到得到n 0。例如：寻找分配问题的最优解，其中成本矩阵如下表，工作，人员，成本，ABCDE，甲方，乙方，丙方，戊方，127979，89666，717121412，15146610，4107106，7，6，7，6，4，7，滴答，滴答，2，-2，-2，最优分配方案：甲做乙，乙做丙，丙做甲，丁步骤1:转换分配问题的成本矩阵，使其在每一行和每一列中出现0个元素：方法：首先从每一行中减去该行的最小元素，然后从每一列中减去该列的最小元素，步骤2:进行试分配(绘制)。 方法：从包含最少0个元素的行或列开始，圈出一个0元素，并用0来表示它。然后在0所在的行和列中分隔剩余的0个元素，用0表示它，依此类推。如果矩阵中零的个数等于n，则得到最优解。如果矩阵中的零的数量是n、工作、人员、费用，12.j.n，12.i.m，n 1n2.米，匈牙利方法是用来解决问题的。例如，有4个工作和6个候选人。由于个人的技术专长不同，每个工作所需的时间如下表所示，规定每个人只能做一项工作，每个工作只能由一个人承担。试着找到一个最小化总时间的分配方案。工作，人员，时间，1234，123456，5