运输问题与指派问题

这是一个关于运输问题与指派问题的思维导图。运输问题与指派问题 运输问题(TransportationProblem)和指派问题(AssignmentProblem)属于线性规划问题，是线性规划的两类常见问题，并且这两类问题具有特殊的数学性质

运输问题与指派问题

• 运输问题及其数学模型
  • 运输问题是一种特殊的线性规划问题，又称康特洛维奇问题
  • 产销总量平衡
• 表上作业法
  • 表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质就是单纯形法
  • 运输问题的最优解也一定可以在基本可行解中找到
  • 约束方程组的增广矩阵的行是线性相关的，在m加n个约束方程式中任意m加n减一都是线性无关的，因此运输问题的每一组基应用m加n减一个基变量组成
  • m加n减一个变量构成基本可行解的充要条件是它不含闭回路
  • 确定初始基本可行解
    • 最小元素法
    • 差值法
    • 用最小元素法及差值法得到的是一组基本可行解，而画圈的地方正好是基变量
    • 任何运输问题都有最优解
  • 最优解的判别
    • 闭回路法
      • 从任一非基变量对应的空格出发，用水平或垂直线向前划，每碰到一画圈数字格字转90度后，继续前进，最后总能回到起始空格
    • 位势法
      • 求位势
      • 求各空格（非基变量）的检验数
      • 
  • 方案调整
    • 对已求得的基本可行解，存在有负的检验数，不是最优解
    • 在负的检验数中，一般取最小的（绝对值最大的）检验数所对应的非基变量作为换入变量
    • 在上述闭回路顶点以外的地方，Xij的值不变
    • 在上述闭回路的奇顶点上，Xij的值都加上调整量；在偶顶点上，Xij的值都减去调整量。
    • 在运输问题最优解表中，若非基变量的检验数为零时，说明该问题有无穷多个最优解，若以相应的空格为起点找闭回路，并在该闭回路中进行方案调整后，便可得到另一最优解。
• 特殊运输问题的解法
  • 产大于销
  • 销大于产
• 指派问题及其数学模型
  • 设有N个人需要分配他们去做N件工作，由于每个人的专长不同，个人做任一种工作的效率可能不同，因而创造的价值也不同，应如何安排才能使创造的总价值最大？
• 匈牙利算法
  • 对系数矩阵进行变换时，各行各列中都出现0元素
  • 试求最优解
    • 从行开始，遇到每行只有一个0元素的就用括号括上，然后画去所在列的其他0元素，遇到有两个及以上0元素的行先放下
    • 进行检验，给只有一个0元素的列的0元素，用括号括上，然后画去所在行的其他0元素
    • 反复进行前两步
    • 若仍有没有括上的0元素，且同行括号列的0元素至少有两个，这是可以从有0元素最少的行列开始开始比较这行列个0元素所在列行中的0元素的数目，选择0元素少的那列行的这个灵元素加括号，然后画掉同行同列的其他元素，反复进行，直到所有0元素都以括上和划掉为止
    • 若0元素的数目等于系数矩阵的阶数N，那这指派问题的最优解已得到，否则转入第3步

运输问题与指派问题

• 运输问题及其数学模型
  • 运输问题是一种特殊的线性规划问题，又称康特洛维奇问题
  • 产销总量平衡
• 表上作业法
  • 表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质就是单纯形法
  • 运输问题的最优解也一定可以在基本可行解中找到
  • 约束方程组的增广矩阵的行是线性相关的，在m加n个约束方程式中任意m加n减一都是线性无关的，因此运输问题的每一组基应用m加n减一个基变量组成
  • m加n减一个变量构成基本可行解的充要条件是它不含闭回路
  • 确定初始基本可行解
    • 最小元素法
    • 差值法
    • 用最小元素法及差值法得到的是一组基本可行解，而画圈的地方正好是基变量
    • 任何运输问题都有最优解
  • 最优解的判别
    • 闭回路法
      • 从任一非基变量对应的空格出发，用水平或垂直线向前划，每碰到一画圈数字格字转90度后，继续前进，最后总能回到起始空格
    • 位势法
      • 求位势
      • 求各空格（非基变量）的检验数
      • 
  • 方案调整
    • 对已求得的基本可行解，存在有负的检验数，不是最优解
    • 在负的检验数中，一般取最小的（绝对值最大的）检验数所对应的非基变量作为换入变量
    • 在上述闭回路顶点以外的地方，Xij的值不变
    • 在上述闭回路的奇顶点上，Xij的值都加上调整量；在偶顶点上，Xij的值都减去调整量。
    • 在运输问题最优解表中，若非基变量的检验数为零时，说明该问题有无穷多个最优解，若以相应的空格为起点找闭回路，并在该闭回路中进行方案调整后，便可得到另一最优解。
• 特殊运输问题的解法
  • 产大于销
  • 销大于产
• 指派问题及其数学模型
  • 设有N个人需要分配他们去做N件工作，由于每个人的专长不同，个人做任一种工作的效率可能不同，因而创造的价值也不同，应如何安排才能使创造的总价值最大？
• 匈牙利算法
  • 对系数矩阵进行变换时，各行各列中都出现0元素
  • 试求最优解
    • 从行开始，遇到每行只有一个0元素的就用括号括上，然后画去所在列的其他0元素，遇到有两个及以上0元素的行先放下
    • 进行检验，给只有一个0元素的列的0元素，用括号括上，然后画去所在行的其他0元素
    • 反复进行前两步
    • 若仍有没有括上的0元素，且同行括号列的0元素至少有两个，这是可以从有0元素最少的行列开始开始比较这行列个0元素所在列行中的0元素的数目，选择0元素少的那列行的这个灵元素加括号，然后画掉同行同列的其他元素，反复进行，直到所有0元素都以括上和划掉为止
    • 若0元素的数目等于系数矩阵的阶数N，那这指派问题的最优解已得到，否则转入第3步