需求的差，即bn?1??ai??bj,单位运费cin?1?0(i?1,2,?,m)；这样原问题就
i?1j?1mn转化成供销平衡模型的运输问题了.另一种情况可类似虚设一个供给地.
容易理解，这里虚设了一个运费等于零的销地Bn+1,因为运费为零物资是运不走的.所以本质上多余的物资，仍留在产地.
另外运输问题也可以由计算机求解，在第十三章中介绍了一种用计算机求解运输问题的方法．
第二节 0—1 规 划 问 题
人们在探讨线性规划问题时，常常会有实际问题要求全部或部分决策变量必须为非负整数. 例如决策变量表示人数、车辆数、机床数等，这样的线性规划问题，称为整数规划（integer programming）. 解决的方法常有分支定界法和割平面法．鉴于本书篇幅所限，不作介绍，有兴趣的读者可参阅有关文献. 但作为整数规划中的一个特殊情况——0-1规划和指派问题，因为有特殊解法，下面作简要介绍．同样整数规划的计算机求解也是很成功的，见第十三章.
一、0—1规划的概念
整数规划中若有变量的取值被限制为0或1的，称此变量为0-1变量. 在讨论线性规划问题时，如果研究的对象具有互相对立的两种可能情况，那么引入0-1变量，将有助于问题的解决．对于全部变量都是0-1变量的线性规划问题，就称为0-1规划问题. 0-1规划是特殊的整数规划，自然可以用分支定界法或割平面法求解，这里从略.
我们建立下述实例的数学模型，并给出0-1规划问题的标准型.
例3-2 在暑假期间，某同学准备徒步回家探亲．他把要带的物品装进包后，觉得还能多放5个单位重量的东西． 为此，他列出了拟放物品的清单，见表3-11． 他认为：应使所增加的物品总价值为最大．基于以上的考虑，他到底还要带哪些
东西呢？ 表3-11 物品重量、价值表
- 11 -
?0,不带j号物品解 设：xj??
?1,带j号物品y为所增加的物品总价值，于是该问 题的数学模型为
MaxY?6x1?3xx?2?35x4编号 名称 重量 价
值
1 书籍 5 6 2 诱饵 2 3 3 电筒 1 1 4 食物 3 5
?3x?5 ??5x1?2x2?x34s.t?.?1,2,3,4)??xj?0,1.j(一般地，称下面形式的数学模型为0-1规划的标准型
MaxY??cjxjj?1n ?nax?b(i?1,2,,?,m)i??ijjs.t.?j?1?x?0,1.(j?1,2,?,n)?j如果0-1规划模型不是标准型，总可以通过适当的变换，使其化为标准型.
二、0—1规划的解法
从理论上讲，求解0-1规划问题，有比单纯形法更简单的方法——枚举法，即检查变量取值为0或1的每一个组合是否满足所有约束条件，再比较目标函数值，以求得最优解，对于n个变量就需要检查2n个取值组合．当n＞10时，即使经历漫长的计算过程找到了最优解，也会由于时过境迁而失去应用价值．现介绍隐枚举法（implicit enumeration）求解0-1规划问题，它只须检查(x1,x2,?,xn)取值的一部分，即可找到最优解．
以例3-2说明求解步骤．
首先，采取试探法找出它的一个可行解：(x1,x2,x3,x4)=（1，0，0，0）． 随后算出相应的目标函数值：y = 6．这是一个求y的最大值问题，当然可以认为ymax?6．因此就有：6x1?3x2?x3?5x4?6． 将这个不等式加到约束条件中． 这个新的约束条件具有滤掉非最优解的功能，所以称为过滤条件(filtering constraint)．我们把这个过滤条件和原有的约束条件5x1?2x2?x3?3x4?5依次记作(0)和(1)，而把它们左边的取值分别写成(0)?和(1)?．由于该问题有4个决策变
- 12 -
量，所以(x1,x2,x3,x4)共有2种不同的取值．据此，我们列出表3—12．其中：
4
(x1,x2,x3,x4)是2种取值，(0)?和(1)?是将(x1,x2,x3,x4)取值代入后的计算结
4
果．继而考查它们是否满足(0)和(1)：当不满足某个约束条件时，同行以下的各项就不再考虑，这表明(x1,x2,x3,x4)不是可行解；当满足全部约束条件时，这表明(x1,x2,x3,x4)是可行解， 然后求出这些可行解对应的目标函数的最大值：
ymax?max?6,8??8．
表3-12 隐枚举法计算表
(x1,x2,x3,x4)
(0, 0, 0, 0) (0, 0, 0, 1) (0, 0, 1, 0) (0, 0, 1, 1) (0, 1, 0, 0) (0, 1, 0, 1) (0, 1, 1, 0) (0, 1, 1, 1) (1, 0, 0, 0) (1, 0, 0, 1) (1, 0, 1, 0) (1, 0, 1, 1) (1, 1, 0, 0) (1, 1, 0, 1) (1, 1, 1, 0) (1, 1, 1, 1)
(0)′ 0 5 1 6 3 8 4 9 6 11 7 12 9 14 10 15
（1）′ 4 5 6 8 9 7 10 8 11
是（√）否 （×）可行解？ × × × √ × √ × × × × × × × ×
y
6 8
于是,该问题的最优值ymax =8．从而最优解(x1,x2,x3,x4)=（0，1，0，1）．这表明，该同学还要带诱饵和食物．
从提高隐枚举法的效率着想，当求解最大（小）化0-1规划时，若遇到y值大（小）于（0）式的右边，应随即让（0）式的右边改取这个y值．求解0-1规划，不要墨守成规，应视具体情况选择适当的解法，以期收到事半功倍的效果．
例3-3 求下面0-1规划的解.
- 13 -
MaxY?3x1?2x2?5x3?x1?2x2?x3?2 (1)? (2)?x1?4x2?x3?4 ?s.t.?x1?x2?3 (3)?4x2?x3?6 (4)???xj?0或1.(j?1,2,3,)解 首先用试探的方法找一个可行解(x1,x2,x3)?(100)，它满足约束条件（1）到（4），且对应的目标函数值y=3．于是过滤条件为：
3x1?2x2?5x3?3(0)
用全部枚举法，3个变量共有23=8个解，原来4个约束条件共需32次运算，现在用隐枚举法，将5个约束条件按（0）~（4）顺序排好（见表3-13），对每个解依次代入约束条件左侧，求出数值，看是否适合不等式条件，如某一条件不适合，同行以下各条件可不必再检查，因而就减少了运算次数. 本例实际只作18次运算．最优解(x1,x2,x3)?(101),maxy?8．
表3-13 隐枚举法计算表
满足√
否则× × √ × × × √ × ×
(x1,x2,x3)
(0, 0, 0) (0, 0, 1) (0, 1, 0) (0, 1, 1) (1, 0, 0) (1, 0, 1) (1, 1, 0) (1, 1, 1)
(0) 0 5 -2 3 3 8 1 6
（1） -1 0
（2） 1 2
（3） 0 1
（4） 1 1
y 5 8
第三节 指 派 问 题
指派问题（assignment problem）也称为分配问题，是0-1规划的特殊情况，对人员和设备的科学管理具有重要的意义．
一、指派问题的概念
指派问题就是人员和设备的任务安排问题．设某部门需完成n项任务，恰好
- 14 -
有n个人可以承担这些任务，每人分别完成其中一项．因工作性质和个人专长的差异，每个人完成各个任务的时间或收益不同．于是便提出这样的问题：指派哪个人完成哪项任务，可使他们完成n项任务的总时间最短或总收益最大？
凡是能同这个典型事例比照的问题，诸如：有n项加工任务，如何指定n台机器分别来完成，可使它们总的加工时间最短？有n条航线，怎样分配n艘船舶各自去航行，能让它们总的经济效益最大？等等，统称为典型的指派问题．
例3-4 某医院的四名化验员（甲、乙、丙、丁）完成四项化验任务（A、B、C、D）所消耗的时间见表3-14. 问哪个化验员担当哪项化验任务，可使所需总时间最少？ 表3-14 化验工作所需时间（min）
分析：为了方便叙述和建立数学模型. 设： i =1，2，3，4分别表示化验员
甲，乙，丙，丁；
j =1, 2, 3, 4分别表示A，B，
甲
乙 丙 丁
A 2 10 9 7
B 15 4 14 8
C 13 8 16 15
D 4 15 13 9
C，D四项化验任务；
bij 表示第i名化验员完成第j项任务所需要的时间； ?1,表示第i名化验员担任第j项化验任务, xij???0,表示第i名化验员不担任第j项化验任务,四名化验员所消耗的总时间为y，于是数学模型为
15 13 4 ??? ??4415??10 4 8 MinY???bijxij 其中： ?bij???? 9 14 16 13i?1j?1??? 7 8 15 9????4??xij?1,?i?1?4s.t.??xij?1,?j?1?x?0或 1 ?ij??j?1, 2, 3, 4??i?1, 2, 3, 4? ?i, j?1, 2, 3, 4?
由于目标函数是求y的最小值，所以本例也称为最小化指派问题. 一般地，最小化指派问题的数学模型是:
- 15 -