《数学建模指派问题精品文稿.ppt》由会员分享，可在线阅读，更多相关《数学建模指派问题精品文稿.ppt（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数学建模指派问题第1页，本讲稿共20页设置变量设置变量:z总成本 数学模型数学模型:每项任务由一人完成 每人只承担一项任务 总成本最小 第2页，本讲稿共20页解矩阵的特征解矩阵的特征全部元素仅取0或1每行有且仅有一个1每列有且仅有一个1第3页，本讲稿共20页性质 从原成本矩阵C的任一行(列)中各元素加(减)一个常数,得到新的成本矩阵,则此两成本矩阵的指派问题的最优解是相同的.证证明明：设矩阵C的第i行对应的常数为di，即f与z仅差一个常数,所以两目标在相同的约束条件下，最优解是相同的.第4页，本讲稿共20页求解的思想方法 若利用以上性质，能把成本矩阵变换到存在n个独立的0元素(在不同行不同列)
2、,且保持每个Cij非负.这时让这n个0元素的位置对应的xij=1,其余位置的xij=0，就得最优解.因为它是目标值为0的可行解，且总有 第5页，本讲稿共20页匈牙利数学家匈牙利数学家康尼格康尼格(D.Konig)的定理的定理若在成本矩阵C中最多能找到k个独立0，则必可画k条直线把C的全部0覆盖.第6页，本讲稿共20页匈牙利法匈牙利法步骤(1)把成本矩阵的各行每一元素分别减去该行中的最小元素,再检查每列中是否都有0,若不是，则把没有0的列的每一元素分别减去该列中的最小元素.(2)如果能在矩阵中找到n个独立的0元素,就可以进行指派,即对应于这n个0元素的位置的xij=1,其余位置的xij=0.结束
3、.第7页，本讲稿共20页(3)当独立的0个数km,则虚拟则虚拟n-m个任务，相应个任务，相应Cij=0若若nm,则虚拟则虚拟m-n个人，相应个人，相应Cij=0这样就化为人数与任务数相等的情况这样就化为人数与任务数相等的情况第13页，本讲稿共20页第14页，本讲稿共20页第15页，本讲稿共20页第16页，本讲稿共20页在在C中找出最多独立中找出最多独立0的步骤的步骤设Wi表示第i行0的数目,Lj表示第j列0的数目.1.统计Wi和Lj（i,j=1,2,n）.2.按W1，W2，,Wn,L1,L2,Ln顺序找出第一个最小正数，选中该行（列）首个0.3.删除该0所在的行与列,对应的Wi=0,Lj=0.4.重复步骤13，直到全部Wi=0为止.第17页，本讲稿共20页这样就找到4个独立0第18页，本讲稿共20页如果按自上而下从左到右顺序找这样只找到3个独立0第19页，本讲稿共20页画覆盖线的方法刚才每个独立0，都画了两条线，把覆盖0数目少的一条拿走，保留另一条.这样，4条线就覆盖了全部0第20页，本讲稿共20页