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