线形规划是一种应用广泛的解优化问题的模型，一般使用单纯形法求解。单纯形法的理论和计算方法都比较繁琐，我们在这里只介绍其基本概念。

单纯形法的计算比较繁琐，虽然现在已有多种实用软件，使用起来仍不方便。因此，对于各种具体问题，又产生了一些较为简单的算法。例如，对运输模型，有表上作业法，图上作业法等。这里我们介绍指派问题的算法。

设有n项任务需要n个人去承担，每人只能承担一项任务。又设第 i个人完成第j项任务所需成本为 Cij，要决定如何指派任务使总成本为最低。这类问题称为指派问题。可以将它化为线形规划问题来解。但是由于问题的特殊性，可以有较为简单的解法。这种解法的根据是下列引理。

引理：若从系数矩阵（Cij）的某一行（或列）各元素中分别减去同一个数，得到新矩阵（bij），那么以（bij）为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。

` 利用这个引理，可使原系数矩阵变换为含有许多零元素而其他元素为正的矩阵而最优解不变。如果我们能在其中找到 n个位于不同行不同列的零元素，设它们位于（1,j2），（2,j2），...，（n,jn），那么指派第 i个人完成第 ji项任务，其成本为零，当然就得出最优解。