(5.3.6)-2.3指派问题数学建模

脚本——指派问题(ppt1,ppt2)同学，你好，今天我们来学习规划模型中的指派问题。(ppt3)我们先来看指派问题中的数学模型。(ppt4)（动画1）首先提出问题。（动画2）设有𝑛个人被分配去完成𝑛项工作，每人完成一项工作．因各人的专长不同，每个人去完成同一项工作所花费的时间也不相同．设𝑐_𝑖𝑗(𝑖,𝑗=1,2,…,𝑛)是第𝑖个人完成第𝑗项工作所花费的时间，现在应当如何分配他们的工作，才能使完成任务所花费的总时间最少。这就是指派问题或分派问题。其中称矩阵𝐶=(𝑐_𝑖𝑗)_(𝑛×𝑛)为指派问题的系数矩阵。(ppt5)（动画1）先来建立数学模型。（动画2）为建数学模型，我们引如变量𝑥_𝑖𝑗，若指派第𝑖人完成第𝑗项工作，则𝑥_𝑖𝑗=1，否则𝑥_𝑖𝑗=0，其中𝑖,𝑗=1,2,⋯,𝑛。于是指派问题的数学模型为。（动画3）目标函数为：minz=sigemai从1到n，sigemaj从1到n,c_ij*x_ij。其约束条件为x_ij，i从1到n求和等于1，这表示（动画4）一个人只能完成一件事。x_ij，j从1到n求和等于1，这表示（动画5）一件事只能被一个人完成。X_ij=0或者1。（动画6）上述模型中若将条件𝑥_𝑖𝑗=0或1改为𝑥_𝑖𝑗≥0，则模型就是一个特殊的运输问题：是𝑚=𝑛, 𝑎_𝑖=𝑏_𝑗=1的一个特殊运输问题。(ppt6)我们来看指派问题的匈牙利算法。(ppt7)（动画1）引入定理（动画2）定理1：将系数矩阵𝐶=(𝑐_𝑖𝑗)中的某一行（列）中的每一个元素都减去常数𝑎，得到一个新矩阵𝐵=(𝑏_𝑖𝑗)。若以𝐵=(𝑏_𝑖𝑗)为系数矩阵的指派问题的最优解为(𝑥

bar_𝑖𝑗)，则原指派问题的最优解也为(𝑥

bar_𝑖𝑗)，且对任意的可行解都有sigemai从1到n，sigemaj从1到n,c_ij*x_ij等于sigemai从1到n，sigemaj从1到n,b_ij*x_ij再加上a。（动画3）定理说明：我们做某一行（列）中的每一个元素都减去常数𝑎这种变换，不会改变最优解，只是目标函数改变了常数𝑎。(ppt8)（动画1）证明：设从𝐶=(𝑐_𝑖𝑗)的第𝑘行减去元素𝑎，得到当i不等于j时，𝑏_𝑖𝑗=𝑐_𝑖𝑗；当i=k时，𝑏_𝑖𝑗=𝑐_𝑖𝑗-a。由于对任意的可行解都有sigemaj从1到n，x_ij等于1，故有sigemai从1到n，sigemaj从1到n,b_ij*x_ij等于sigemai从1到n，j从1到n，𝑐_𝑖𝑗x_ij减去a。（动画2）由于(𝑥

̄_𝑖𝑗)是以(𝑏_𝑖𝑗)为系数矩阵的指派问题的最优解，所以对于任意的可行解都有sigemai从1到n，sigemaj从1到n,b_ij*x_ij大于等于sigemai从1到n，j从1到n，𝑐_𝑖𝑗*xbar_ij减去a。故有sigemai从1到n，sigemaj从1到n,c_ij*x_ij大于等于sigemai从1到n，sigemaj从1到n,c_ij*xbar_ij。从而(𝑥_𝑖𝑗)为原问题的最优解。(ppt9)（动画1）定理2：将系数矩阵𝐶=(𝑐_𝑖𝑗)的第𝑖行各元素减去常数𝑝_𝑖(𝑖=1,2,⋯,𝑛)，第𝑗列各元素减去常数𝑞_𝑗，得到一个新矩阵(𝑏_𝑖𝑗)，即𝑏_𝑖𝑗=𝑐_𝑖𝑗−𝑝_𝑖−𝑞_𝑗，若𝑏_𝑖𝑗≥0，且(𝑏_𝑖𝑗)中有𝑛个不同行不同列的零元素，即有(1,2,⋯,𝑛)的一个排列(𝑗_1𝑗_2⋯𝑗_𝑛)，使𝑏_(𝑗_1)=𝑏_(𝑗_2)=⋯𝑏_(𝑗_𝑛)=0。取矩阵(𝑥

bar_𝑖𝑗)，其中𝑥

bar_(1𝑗_1)=𝑥

bar_(2𝑗_2)=⋯𝑥

bar_(𝑛​𝑗_𝑛)=1，其余的𝑥

bar_𝑖𝑗=0，则(𝑥

bar_𝑖𝑗)就是以(𝑏_𝑖𝑗)为系数矩阵的指派问题的最优解，也是原指派问题的最优解。（ppt10）（动画1）证明：由已知条件可知sigemai从1到n，j从1到n，𝑏_𝑖𝑗*𝑥

bar_𝑖𝑗等于0。而对于任意的可行解(𝑥_𝑖𝑗)，由于𝑏_𝑖𝑗≥0，故sigemai从1到n，j从1到n，𝑏_𝑖𝑗𝑥_𝑖𝑗大于等于0，即大于等于sigemai从1到n，j从1到n，𝑏_𝑖𝑗*𝑥bar_𝑖𝑗。故(𝑥

̄_𝑖𝑗)为新指派问题的最优解，根据定理一，它也是原指派问题的最优解。(ppt11)（动画1）现在我们来讲解匈牙利算法。（动画2）第一步：变换系数矩阵，先将系数矩阵的每一行的所有元素都减去本行中的最小元素，然后将每一列的所有元素都减去本列中的最小元素。这样所得的变换矩阵的每一行每一列至少有一个“0”元素,而且没有负元素。(ppt12)（动画1）第二步：在变换后的系数矩阵中确定独立的“0”元素（即不同行不同列的“0”元素）。（动画2）若某行（或某列）只有一个“0”元素，则对此“0”元素画框。（动画3）把位于此“0”元素的同行同列的其他“0”元素划去。（动画4）若遇到所有的行列中的“0”元素都不只一个，我们任意选取一个“0”元素加框，同时划去其同行同列的其他“0”元素。（动画5）如此反复进行，直到所有的“0”元素被画上框，或者是被划去为止。（动画6）画上方框的“0”元素就是矩阵中独立的“0”元素。(ppt13)（动画1）如果独立的“0”元素有𝑛个，则令解矩阵中与独立“0”元素对应的位置上的变量取1，其他变量取0，此对应的指派方案总费用为0，从而一定是最优解。（动画2）如独立的“0”元素少于𝒏个，即至少有一行或者一列中没有画方框的“0”元素，采取如下的步骤进行变换：（动画3，4，5，6，7）看背板。(ppt14)（动画1）第三步，继续变换矩阵。找出未被直线覆盖的元素中的最小元素，令打横三角的行中的所有元素都减去这个最小元素，打正三角的列元素都加上这个最小元素。则原先选中的“0”元素不变，而未被直线覆盖的元素中至少有一个元素已经变为“0”元素，且新矩阵的指派问题与原指派问题有相同的最优解。（动画2）反复上面的步骤，直到找出n个独立的“0”元素为止。(ppt15)（动画1）我们来看一个例子。求设要给5个人分配5项工作，每个人做每件事情的费用如下面系数矩阵𝐶所示，要使得费用最小，求对应的指派问题的最优解。（动画2）：我们将第一行减去7，第二行减去6，第三行减去7，第四行减去6，第五行减去4，就得到新的矩阵。再按照上面的步骤，（动画3）先找到每一行的独立0元素，画上方框，把每一行每一列的重复的0元素打上叉。（动画4）在没有方框的行画上横三角。（动画5）给这一行0叉所在的列打上正三角。（动画6）再给这一列中有方框的0元素所在的行打上横三角。（动画7）最后划去没有打标记的行，和打了标记的列，如图所示。(ppt16)（动画1，2）则上面矩阵中的第一、二、四行和第一列被直线覆盖，未被直线覆盖的行列中的最小元素是2，故将第三、五行的元素减去2，第一列的元素加上2，这样就使得最后一行出现新的0元素，同时不会出现负数的元素，得到新的矩阵。（动画3）故得到相应的解为𝑥_12=1,𝑥_23=1,𝑥_31=1,𝑥_44=1,𝑥_55=1，其他的𝑥_𝑖𝑗=0。(ppt17)下面我们来介绍一般的指派问题。(ppt18)一般指派问题转化为标准指派问题的方法。（动画1）1.最大化指派问题：若目标函数是求最大不是求最小，设𝑀=𝑚𝑎𝑥{𝑐_𝑖𝑗}，令𝐶′=(𝑐_𝑖𝑗′)=(𝑀−𝑐_𝑖𝑗)，则以𝐶′=(𝑐_𝑖𝑗′)为系数矩阵的最小化指派问题就与原问题同解。（动画2）2.人与事的数目不等：若人多于事或者是事多于人,则添上相应数目的虚拟“事”或者是虚拟“人”，使得人与事的数目相等，不过人做虚拟的事或者是虚拟的人做事的费用都为0。（动画3）3.一个人可以做几件事：若一个人可以做几件事，则将该人化为相同的几个人，这几个人做事的费用也完全相同。（动画4）4.某事一定不能由某人来做：某事一定不能由某人来做，可取此人做该事时的费用是一个足够大的数。(ppt19)最后我们来看模型应用。(ppt20)（动画1）指派问题可以应用于很多最优安排问题上，如团体赛的安排，比如接力赛，有人擅长跑直线，有人擅长跑弯道，还有人擅长冲刺，因此这就需