数学建模指派问题（课堂PPT）指派问题设有n项任务要分给n个人去完成,每人完成一项.由于每个人的专长不同,故完成不同任务所需的成本也不同.若第i个人完成第j项任务的成本为cij,则如何分配这些工作任务,使总成本为最小？这类问题称为指派问题，矩阵C=(cij)称为成本矩阵.设置变量:z………总成本数学模型:每项任务由一人完成每人只承担一项任务总成本最小解矩阵的特征全部元素仅取0或1每行有且仅有一个1每列有且仅有一个1性质从原成本矩阵C的任一行(列)中各元素加(减)一个常数,得到新的成本矩阵,则此两成本矩阵的指派问题的最优解是相同的.证明：设矩阵C...
指派问题设有n项任务要分给n个人去完成,每人完成一项.由于每个人的专长不同,故完成不同任务所需的成本也不同.若第i个人完成第j项任务的成本为cij,则如何分配这些工作任务,使总成本为最小？这类问题称为指派问题，矩阵C=(cij)称为成本矩阵.设置变量:z………总成本数学模型:每项任务由一人完成每人只承担一项任务总成本最小解矩阵的特征全部元素仅取0或1每行有且仅有一个1每列有且仅有一个1性质从原成本矩阵C的任一行(列)中各元素加(减)一个常数,得到新的成本矩阵,则此两成本矩阵的指派问题的最优解是相同的.证明：设矩阵C的第i行对应的常数为di，即f与z仅差一个常数,所以两目标在相同的约束条件下，最优解是相同的.求解的思想方法若利用以上性质，能把成本矩阵变换到存在n个独立的0元素(在不同行不同列),且保持每个Cij非负.这时让这n个0元素的位置对应的xij=1,其余位置的xij=0，就得最优解.因为它是目标值为0的可行解，且总有匈牙利数学家康尼格(D.Konig)的定理若在成本矩阵C中最多能找到k个独立0，则必可画k条直线把C的全部0覆盖.匈牙利法步骤(1)把成本矩阵的各行每一元素分别减去该行中的最小元素,再检查每列中是否都有0,若不是，则把没有0的列的每一元素分别减去该列中的最小元素.(2)如果能在矩阵中找到n个独立的0元素,就可以进行指派,即对应于这n个0元素的位置的xij=1,其余位置的xij=0.结束.(3)当独立的0个数km,则虚拟n-m个任务，相应Cij=0若n
本文档为【数学建模指派问题（课堂PPT）】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483