§3 分派与装载
生活和工作中经常碰到任务分派问题，如由5个人承担5项任务，由于各人的专长不同，他们完成各项任务的时间（或代价）不同，那么派谁去完成哪项任务使总的效率最高呢？类似的问题很多。
例4 车间有n项加工任务，分派给n个工人完成，每人完成其中一项。已知每个人完成各项任务的时间（其中有若干人不能完成某几项任务），问如何进行任务分派，使所需总时间最少？
将工人编号为i?1,2,?,n，任务编号为j?1,2,?,n，第i人完成第j项任务的时间记为cij（若第i人不能完成任务j，则记cij?M，M是充分大的正数），任务分派用如下的0——1变量表述：
?1,若分派第i人完成任务j xij???0，否则问题的目标函数——总时间为 约束条件为
Z???cijxij （1）
i?1j?1nn?xj?1nnij?1,i?1,2,?,n （2）
?xi?1ij?1, j?1,2,?,n （3） i,j?1,2,?,n （4）
xij?0,1,其中（2）说明第i人只能完成一项任务，（3）说明任务j只能由一人完成。
这里决策变量xij只能取值0和1，称为0—1整数规划。满足（2）~（4）的可行解xij可表为矩阵形式，其中每一行和每一列都必须有且只能有一个1，其余元素均为0。
引入0—1变量解决任务分配问题还可以有其他方式，如
例5 工厂用k种不同工艺生产n种产品，每种产品的利润已知。在各种工艺条件下每种产品所消耗的资源（如原料）是确定的，并且工厂的总资源有一定的限制。问应选择哪种工艺，每种产品各生产多少，使总利润最高。
用A1,A2,?,Ak表示k种工艺，B1,B2,?,Bn表示n种产品。已知单件Bi的利润为
pi,(i?1,2,?,n)，设在工艺Aj,(j?1,2,?,k)下单件Bi的资源消耗为cij，资源限制为Qj。
显然，Bi的产量是决策变量，记为xi。目标函数——总利润为
Z??pixi （1）
i?1n在任一种工艺Aj,(j?1,2,?,k)下，资源限制都可以表为
?ci?1nijxi?Qj, j?1,2,?,k （2）
为确定工艺的选择，引入0-1变量
?0,选择工艺Aj yj???1,否则为了使（2）式k个条件中只有被选中的某一个起作用，（2）式代之以
?cxi?1niji?Qj?yjM, j?1,2,?,k （3）
?yj?1kj ?k?1 （4）
yj?0,1(j?1,2,?,k) （5） xi?0(i?1,2,?,n) （6）
其中M是一个充分大的正数。这样，y1,y2,?,yk中有k?1个取值1，这些yj对（3）是多余的，只有取值0的那个在（3）式中起作用，它就相应于被选中的工艺。于是问题归结为在条件（3）~（6）下求xi(i?1,2,?,n)和y1,y2,?,yk，使（1）的Z最大，这是混合0-1规划模型。
最优装载也是日常生活中经常碰到的问题，如空运若干种物资，每种物资的价值与装载上飞机的数量有关，而装载的总量受到飞机对重量、体积等条件的限制，问每种物资装载多少使空运的总价值最大。这类问题具有类似的模型，试看下例。
例6 要把7种规格的包装箱装到两辆铁路平板车上去，箱子宽、高相同，而厚度和重量不同，下表给出了它们的厚度、重量和数量。 c1 c2 52.0 3000 7 c3 61.3 1000 9 c4 72.0 500 6 c5 48.7 4000 6 c6 52.0 2000 4 c7 64.0 1000 8 厚度 t（厘米） 48.7 重量 w(千克) 2000 8 数量 n
每辆平板车有10.2米长的地方用于装箱（像面包片那样），载重40吨。由于货运限制，对c5，c6，c7三种包装箱的装载有如下特殊约束：它们所占的空间（厚度）不得超过302.7厘米。试把包装箱装到平板车上，使浪费的空间最小。
容易算出所有包装箱的厚度为27.495米，而两辆车共有20.4米长的地方，所以不可能全装上。记表中所给第i种箱子ci的厚度、重量和数量分别为ti，wi，ni(i?1,2,?,7)，问题的决策变量是装载到两辆车上的数量，记ci装到1，2辆车上的数量为xi1,xi2(i?1,2,?,7)。 问题要求使浪费空间最小，等价于装载所占的空间最大，故目标函数可表为
Z???tixij （1）
72i?1j?1约束条件包括 厚度约束
?txii?17ii?17ij?1020,j?1,2 （2）
重量约束
?wxij?40000, j?1,2 （3）
数量约束
?xj?17i2ij ?ni (i?1,2,?,7) （4）
特殊约束
?txi?5ij?302.7, j?1,2 （5）
自然约束 xi1,xi2(i?1,2,?,7)为非负整数 （6） 问题归结为在条件（线性规划模型。 2）~（6）下求xi1,xi2(i?1,2,?,7)，使（1）式给出的 Z最大，这是整数
数学建模案例分析--最优化方法建模3分派与装载
