线性规划资源分配问题课件.ppt

,特殊类型的线性规划,资源分配问题,资源分配问题,资源分配问题又称为指派问题或分配问题，属于0-1规划。 如工程运输中各个运输任务的人力与物力分配问题；n个公司对n个工程项目的投标问题；公共交通客运公司与运营路线的分配问题等。,资源分配问题,例：有5个工人，要分配他们完成5项工作，每人做不同的工作所消耗的时间如下表所示。问应该分配哪个人去完成哪项工作，可使总的耗时最少？,资源分配问题,资源分配问题的特点是：每个人只能承担一项任务，而且每项任务只能由一个人完成。 设,则此分配问题的数学模型为：,资源分配问题,s.t.,资源分配问题,设,资源分配问题的一般数学模型为：,矩阵（cij）称为效率矩阵或费用矩阵,资源分配问题-匈牙利法,匈牙利法的基本思想： 等效变换效率矩阵，使变换后的效率矩阵有n个位于不同行不同列的0元素（独立的0元素），没有负元素，则分配问题的任意一个可行解矩阵（xij）一定是对应某变换后的效率矩阵中独立0元素对应的变量取值为1，其余变量取值为0。,资源分配问题-匈牙利法,例如： 原效率矩阵 变换后的效率矩阵,可行解矩阵,资源分配问题-匈牙利法,举例说明匈牙利法求解步骤：已知效率矩阵，求相应的解矩阵。,第1步：行简约化找出 各行的最小元素，各行并减去其最小元素，得到,资源分配问题-匈牙利法,第2步：列简约化找出 各列的最小元素，各列并减去其最小元素，得到与 相同的效率矩阵，仍记为,资源分配问题-匈牙利法,第3步：用最少的 条直线覆盖 中的0元素如果 ，则这时就可以得到最优解， 为的阶数。,在类元素中找出最小的元素 ，并且都减去 ；类元素保持不变；类元素都加上 。,资源分配问题-匈牙利法,第4步： 当 时，可以把简约化后矩阵的元素分为三类：没有被直线划到的元素被直线划过一次的元素被直线划过两次的元素,第5步：用最少的 条直线覆盖 中的0元素在 中可以找到5条直线覆盖全部0元素，第1、4、5列，第3、4行。 此时： 可以得到最优解。,资源分配问题-匈牙利法,资源分配问题-匈牙利法,第6步：确定不同行不同列的n个0元素首先将某行或某列是唯一的0元素划出，同时把这一行或列的其它0元素去掉，然后再划出某行或某列是唯一的0元素。,找出有唯一0元素的第5行，同时画去第4列的0元素。,资源分配问题-匈牙利法,第6步：确定不同行不同列的n个0元素首先将某行或某列是唯一的0元素划出，同时把这一行或列的其它0元素去掉，然后再划出某行或某列是唯一的0元素。,找出有唯一0元素的第3列，同时画去第4行的0元素。,资源分配问题-匈牙利法,第6步：确定不同行不同列的n个0元素首先将某行或某列是唯一的0元素划出，同时把这一行或列的其它0元素去掉，然后再划出某行或某列是唯一的0元素。,找出有唯一0元素的第2列，同时画去第3行的0元素。,资源分配问题-匈牙利法,第6步：确定不同行不同列的n个0元素首先将某行或某列是唯一的0元素划出，同时把这一行或列的其它0元素去掉，然后再划出某行或某列是唯一的0元素。,找出有唯一0元素的第2列，同时画去第3行的0元素。,资源分配问题-匈牙利法,第6步：确定不同行不同列的n个0元素首先将某行或某列是唯一的0元素划出，同时把这一行或列的其它0元素去掉，然后再划出某行或某列是唯一的0元素。,找出有唯一0元素的第1列，同时画去第1行的0元素。,资源分配问题-匈牙利法,第6步：确定不同行不同列的n个0元素首先将某行或某列是唯一的0元素划出，同时把这一行或列的其它0元素去掉，然后再划出某行或某列是唯一的0元素。,找出有唯一0元素的第2行。,资源分配问题-匈牙利法,第7步：确定最优解矩阵唯一0元素对应的变量为1，其余为0。,资源分配问题,特殊的指派问题：1）工人数 小于工作数 ：虚设 个工人，虚设工人不能创造价值，价值系数为0，目标函数不变。2）工人数 大于工作数 ：虚设 项工作，虚设工作的效率为0，目标函数不变。,资源分配问题,例：公交车交接班问题： 假设某公交公司在某一营运工作时段要安排n组司乘员与n辆各路在线公交车的司乘员进行交接班，设 为第i组司乘员去交接在线公交车j所需的时间。 并设： 则使交接班总时间最少的最优交接班方案的数学模型为：,资源分配问题,例：公交车交接班问题： 假设n=5，且已知预测的交接班时间矩阵,资源分配问题,第1步：行和列简约化,行简约化,列简约化,资源分配问题,第2步：画去0元素,资源分配问题,第3步：变换,资源分配问题,第4步：画去0元素,资源分配问题,第5步：找出独立的0元素,找出有唯一0元素的第5行，同时画去第1列的0元素。,资源分配问题,第5步：找出独立的0元素,找出有唯一0元素的第3行，同时画去第5列的0元素。,资源分配问题,第5步：找出独立的0元素,找出有唯一0元素的第2列，同时画去第1行的0元素。,资源分配问题,第5步：找出独立的0元素,找出有唯一0元素的第3列和第4列。,资源分配问题,第6步：最优解矩阵,资源分配问题,例:分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务。完成任务的时间如表所示。由于任务数多于人数，故考虑： (a)任务E必须完成，其他4项中可任选3项完成； (b)其中有一人完成两项，其他人每人完成一项。 试分别确定最优分配方案，使完成任务的总时间最少。,资源分配问题,(a)由于任务数多于人数，所以需要有一名假想的人，设为戊。因为工作E必须完成，故戊完成E的时间为M(M为非常大的数),其余的假想时间为0，建立的效率矩阵表如下：,X,资源分配问题,(a)由于任务数多于人数，所以需要有一名假想的人，设为戊。因为工作E必须完成，故戊完成E的时间为M(M为非常大的数),其余的假想时间为0，建立的效率矩阵表如下：,资源分配问题,建立的效率矩阵如下：,资源分配问题,行简约化：,资源分配问题,列简约化：,资源分配问题,调整：取,资源分配问题,调整：取,资源分配问题,得到最优矩阵：,资源分配问题,得到最优矩阵：,资源分配问题,得到最优矩阵：,资源分配问题,(b)由于所有任务都必须由甲、乙、丙、丁完成，所以假想的人的效率应该对每项工作而言，都是完成它的最好的人（戊一定要做一项工作），而不能假设为0值，所以构造的效率表如下：,资源分配问题,建立的效率矩阵如下：,克尼格定理： 如果从效率矩阵 的每一行元素中分别减去(或加上)一个常数k，从每一列中分别减去(或加上) 一个常数j，得到一个新的效率矩阵 ，则以 为效率矩阵的分配问题与以 为效率矩阵的分配问题具有相同的最优解。,分配问题,分配问题,行简约化,列简约化,分配问题,行简约化,列简约化,