144
学类，计算机程序归属计算机类，但有些课程是跨类的，如运筹学可以归为运筹学类和数学类，数据结构归属于计算机类和数学类，管理统计归属数学类和运筹学类，计算机模拟归属计算机类和运筹学类，预测归属运筹学类和数学类．凡归属两类的课程选学后可认为两类中各学一门课．此外有些课程要求先学习先修课，如学计算机模拟或数据结构必须先修计算机程序，学管理统计须先修微积分，学预测必须先修管理统计．问一个硕士生最少应学几门，哪几门，才能满足上述要求？
解: 对微积分、运筹学、数据结构、管理统计、计算机模拟、计算机程序、预测7门课程分别编号为1、2、?、7. 设 xi??至此可得本题的数学模型如下：
?1,选学第i门课程7 i?1,,?0,不选学第i门课程minz?x1?x2?x3?x4?x5?x6?x7
?x1?x2?x3?x4?x7?2?x?x?x?x?2?2457?x3?x5?x6?2?s..t?.
x?x,x?x1465??x6?x3,x4?x7?7??xi?0或1,i?1,???,例7.9 集装箱装载问题 今有一集装箱，拟运装物品A1,A2,A3,A4,A5．A1、A3由于体积大，集装箱内只能装其中之一；A4、A5由于重量大也只能装一件；A1是食品不能与化工产品A4放在一起；A2与A5是配套产品，必须一起运输.A1的运费是1500元，A2的运费是2000元，A3的运费是1300元，A4的运费是2300元，A5的运费是2800元．问集装箱应如何装箱才能使运费收入最大？
解：设A1~A5是否装运的控制变量是x1～x5,xi=0,表示Ai不装，xi=1，表示Ai装箱运输．由此可知所述问题的数学模型
maxz?1.5x1?2x2?1.3x3?2.3x4?2.8x5
?x1?x3?1,?x?x?1,45??s..t?x2-x5?0,?x?x?1,?14??xi?0或1二者取一二者取一同时装箱或同时不装箱. 二者取一,但必装其一(i?1,...,5)例7.10 当决策变量是连续变量时的选择
145
Good Products公司的研究与发展部开发了三种可行的新产品．然而，为了使产品的生产线不至于过分多样化，管理层决定实施以下限制：
限制1 在三种新产品中，至多有两个被投入生产．每一种产品可能由两个工厂中的任何一个生产，出于管理的考虑，管理层实施了第二条限制：
限制2 两个工厂中，仅有一个能作为新产品的唯一生产者．
对于两个工厂来说，每种新产品的单位生产成本都是相同的．然而，由于两个工厂的生产设备不同，对每种产品的单位生产时间可能是不同的．数据在表7-4中给出，还有一些其他信息，包括在投产后每周每种新产品的预期销售数量．目标是选择新产品、工厂和生产新产品的生产率，以使总利润最大化．
表7-4:例7.9的数据（Good Products公司的问题）
工厂1 工厂2 单位利润/千美元 销售量/每周
单位产品的生产时间/小时 每周可用生产时间/小时 产品1 产品2 产品3 3 4 5 7 4 6 7 5 2 2 3 9 30 40 在某种程度上，这个问题类似一个标准的产品混合问题，实际上，如果我们去掉两个约
束条件并且满足表7-4列出的两个工厂（所以这两个工厂生产产品的工艺是不同的）生产每种新产品所用的时间，那么原问题就变成了此类问题．特别地，令x1、x2、x3分别代表新产品的生产率，那么模型变为
maxz?5x1?7x2?3x3?3x1?4x2?2x3?30?4x?6x?2x?4023?1?7 s.t.??x1.?x2?5??x3?9???x1?0,x2?0,x3?0对于实际问题，必然会给模型加入约束： 严格大于零的决策变量(x1,x2,x3)数必须?2
这个约束条件无法用一个线性或整数规划模型，所以关键问题是怎样把它转化成此类模
型，以便使用相应的算法求解总体模型．如果决策变量是0-1变量，那么约束条件就可以表达为x1?x2?x3?2．然而，我们需要一个更为复杂的模型，不仅涉及辅助0-1变量，还包含连续变量．第二个约束要求前两个约束条件3x1?4x2?2x3?30与4x1?6x2?2x3?40被下述约束条件代替：
3x1?4x2?2x3?30
146
或
4x1?6x2?2x3?40
至于哪个约束条件被保留，对应于选择哪个工厂来生产新产品，我们在前面的已讨论了怎样把或约束转化为一个线性或整数规划形式，我们再次用到一个辅助0-1变量．
使用辅助0-1变量建模
为了处理第一个要求，我们引入三个辅助0-1变量(y1,y2,y3)，它们的含义如下
??1,yj????0,如果xj?0被保留（生产成品j）如果xj?0被保留（不生产成品j）
j?1,2,3．为了把该含义融入模型中，我们把M（一个非常大的正数）加到约束条件当中
x1?My1x2?My2x3?My3y1?y2?y3?2yj是0-1变量,j?1,2,3或约束与非负约束使决策变量的可行域是有限的（每个xj?M）．因此，在每个约束条件而yj?0强迫xj?0（反过来，xj?0xj?Myj中，yj?1使xj能取到可行域中的任何值，
强迫yj?1，而xj?0是允许yj等于0或1）．结果，因为第四个约束条件令至多能有两个yj等于1，所以它等价于至多能有两种新产品被投入生产．
为了处理第二个要求，我们引入第二个辅助0-1变量y4，其含义如下
?1,y4???0,如果4x1?６x2?2x3?４0被保留（选择第二个工厂）
如果3x1?4x2?2x3?30被保留（选择第一个工厂）正如7.3节所论述的，通过加上如下约束条件来表达该含义，
3x1?4x2?2x3?30?My44x1?6x2?2x3?40?M(1?y4)y4是0-1变量．
结果，在我们把所有变量移到约束条件的左边后，完整的模型是：
maxz?5x1?7x2?3x3
147
x1?7??x2?5??x3?9?x1?My1?0??x2?My2?0?x3?My3?0?s..t?.y?y?y?2 123??3x1?4x2?2x3?My4?30??4x1?6x2?2x3?My4?40?M?且??x1?0,x2?0,x3?0?y是0-1变量,j?1,2,3,4j?现在这是一个MIP模型，三个变量xj不要求是整数，四个0-1变量，所以可以用MIP算法来求解这个模型．求得结果是（在用一个相当大的数替换M之后），最优解是y1?1，
1y2?0，y3?1，y4?1，x1?5，x2?0和x3?9；也就是，选择生产第一和第三个新
21产品，选择第二个工厂生产新产品，并且第一个产品的生产率是每周5个，第三个产品的生
2产率是每周9个．结果总利润是每周54500美元．
7.4 指派问题
在生产管理上，为了完成某项任务，总是希望把有关人员最合理地分派，以发挥其最大工作效率，创造最大的价值.
例7.11 设某单位有5个人，每个人都有能力去完场5项科研任务中的任一项，由于5个人的能力和经验不同，所需完成各项任务的时间如表7-5所示．问分配何人去完成何项任务使完成所有任务的总时间最少？
表7-5 各人完成各项任务时间表 项目 人员 甲 乙 丙 丁 戊 A 3 8 6 8 9 B 8 7 4 4 10 C 2 2 2 2 6 D 10 9 7 3 9 E 3 7 5 5 10 148
解 设决策变量xij表示第i个人去完成第j项任务，即
?1, 当第i个人去完成第j项任务时xij?? （1?i,j?5)
?0, 当第i个人不去完成第j项任务时每个人去完成一项任务的约束为
?x11?x12?x13?x14+x15=1?x?x?x?x+x=12122232425???x31?x32?x33?x34+x35=1 ?x?x?x?x+x=1?4142434445??x51?x52?x53?x54+x55=1每一项任务必有一个人去完成的约束为
?x11?x21?x31?x41+x51=1?x?x?x?x+x=11222324252???x13?x23?x33?x43+x53=1 ?x?x?x?x+x=1?1424344454??x15?x25?x35?x45+x55=1目标函数为完成任务的总时间最少：
minz?3x11?8x12?2x13?10x14?3x15?8x21?7x22?2x23?9x24?7x25?6x31?4x32?2x33?7x34?5x35?8x41?4x42?2x43?3x44?5x45 ?9x31?10x32?6x33?9x34?10x35记系数矩阵为
?38?87?C?(cij)??64??84??910210222697393?7??5? ?5?10??称为效益矩阵，或价值矩阵，cij表示第i个人去完成第j项任务时有关的效益（时间、费用、价值等）.故该问题为一个0-1规划模型：
minz???cijxij,
i?1j?155?5??xij?1(i?1,2,...,5),j?1??s..t?5
x?1(j?1,2,...,5),??ij?i?1??xij?0或1(i,j?1,2,...,5).