3maxf(x)?x12x2x3S.t ?x1?x2?x3?6?(k?1,2,3)?xk?06. 带回收得资源分配问题
某厂新购某种新机床125台。据估计，该设备5年后将被其他心设备所
代替，此机床如在高负荷下工作，年损坏率为1/2，年利润为10万元，如在低负荷下工作，年损坏率为1/5，年利润为6万元。问应如何安排这些机床的生产，才能使5年内获得的利润最大？ 7. 用动态规划求解下面非线性规划问题
maxf(x)?x12x2S.tx?x2?221
8. 某公司将在一个竞争激烈的市场推出一种新产品。该公司已经决定分三个阶
段进行营销策略。第一阶段以低价向大家推销，以吸引初买者；第二阶段大举从事广告，以促使初买者以正常价格购买该产品，约于第二阶段末期另一公司将推出一种竞争性新产品，故在第三阶段从事加强性广告策略，以使购买者不转而购买竞争对手的产品。
该公司已经拨出四百万元的预算用于此项活动。现求如何在这三个阶段分配款项使该产品获得最大的市场占有率。令m表示第一阶段达成的最初市场占有率，f2、f3分别为第二、三阶段策略对市场占有率的影响，也即求得m f2f3最大。
1) 假定该款项以一百万元的整数倍用于每一阶段，【表2-3】表示各阶段的支出效果。
表2-3
支出额（百万元）01234
对市场占有率的影响mf2f3——0.20.3200.40.5300.50.6400.60.750————2) 假定在四百万元预算额度内各阶段支出额可以为任意实数，而在阶段k (k＝
1, 2, 3)支出xk百万元的支出效果为：
m?10x1?x12f2?0.4?0.1x2 f3?0.6?0.07x3
6
9. 用动态规划求解下面极大值问题。
2maxf(x)?x1x2x3S.t?2x1?3x2?x3?4
??xi?0(i?1,2,3)10. 用动态规划求解下面非线性规划问题。
3maxf(x)?36x1?36x2?9x12?6x13?3x2S.t?x1?x2?3??x1,x2?0
11. 某厂生产一种产品，以后四个月的订单如【表2-4】所示。合同规定在月底
前缴获，生产每批产品的固定成本为3千元，每批生长的产品件数不限。每件产品的可变成本为1千元，每批产品的最大生产能力是5件。产品每级每月的存储费为0.5千元。设1约初又库存产品1件，4月底不再留下产品。试求在满足需求的前提下，如何组织生产才能使总的成本费用最低。
表2-4 月 份 订货量bk（个） 1月 3 2月 3 3月 2 4月 4 12. 某公司有9个推销员在全国三个不同市场里推销货物，这三个市场里推销员
人数与收益的关系如下表，做出各市场推销人员数的分配方案，使总收益最大。
表2-5 推销员 市场 1 2 3 0 20 40 50 1 32 50 61 2 47 60 72 3 57 71 84 4 66 82 97 5 71 93 109 6 82 104 120 7 90 115 131 8 100 125 140 9 110 135 150 13. 设某工厂要在一台机器上生产两种产品，机器的总运转时间为5小时。生产
这两种产品的任何一件都需占用机器一小时。设两种产品的售价与产品产量成线性关系，分别为(12?x1)和(13?2x2)。这里x1和x2分别为两种产品的产量。假设两种产品的生产费用分别是4x1和3x2，问如何安排两种产品的生产量使该机器在5小时内获利最大。(要求用连续变量的动态规划方法求解)
7
第三章 匹配问题 判断题
1. 任务分配问题效率矩阵的每一个元素都乘上同一个常数k，将不影响最优分配方案。
( ) 2. 任务分配问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解。
( )
练习题
1. 用匈牙利算法求解下述任务分配问题。
?7?131) ??15??11
91216121016141512?17?? 15??16??1011428??711101412?? 3) ??5691214???131511107???3?8?2) ?6??8??9 ?8?0?4) ?3??4??9874210229739421063?7??5? ?5?10??4261?9554??8926?
?3103?5895??2. 有四个工人。要指派他们分别完成四项工作。每人做各项工作所消耗的时间
(h)如下表，问如何分派工作，使总的消耗时间最少？（以前的习题）
表3-1 工作 工人 甲 乙 丙 丁 A 3 3 1 4 B 3 2 5 6 C 5 5 1 4 D 3 2 6 10 3. 学生A，B，C，D的各门成绩如下表，现将此4名学生派去参加各门课的单项竞赛。据竞赛同时举行，每人只能参加一项。若以他们的成绩为选派依据，
8
应如何指派最有利？
表3-2
课程 学生 数学 物理 化学 外语 A B C D 89 87 95 75 92 88 90 78 68 65 85 89 81 78 72 96 4. 下表给出了使用各台设备完成各种工作的生产费用。试确定最优的指派方案，使总的生产费用最低。
表3-3
工作 设备 甲 乙 丙 丁 A B C D E 25 22 39 34 24 29 19 38 37 42 31 35 26 28 36 42 18 20 40 23 5. 某设备公司有三台设备可以租给A，B，C和D四项工程使用，各台设备用于各工程创造的利润如下表所示，问怎样分配设备才能使创造的总利润最大？
表3-4
工程 设备 M1 M2 M3 A 4 9 12 B 10 8 3 C 8 7 D 5 2 4 6. 已知下列五名运动员各种姿势的游泳成绩（各为50米）如下表所示，试问如何从中选拔一个参加200米混合泳的接力队，使预期比赛成绩为最好。
表3-5 仰泳 蛙泳 蝶泳 自由泳 赵 钱 孙 李 周 37.7 43.4 33.3 29.2 32.9 33.1 28.5 26.4 33.8 42.2 38.9 29.6 37.0 34.7 30.4 28.5 35.4 41.8 33.6 31.1 7. 现在有五项任务让甲、乙、丙、丁四个人去完成。其中一个人要完成两项任
9
务，每人完成各项任务的时间如下表所示。试确定总的花费时间为最少的分配方案。
表3-6 工作 工人 甲 乙 丙 丁 A 25 39 34 24 B 29 38 27 42 C 31 26 28 36 D 42 20 40 23 E 37 33 32 45 8. 从甲、乙、丙、丁、戊五个人中挑选四个人去完成四项工作。已知每人完成各项工作的时间如下表所示。规定每项工作只能有一个人去单独完成，每个人最多承担一项任务。又假定对甲必须保证分配一项任务，丁因为某种原因决定不同意承担第四项任务，在满足上述条件下，如何分配工作，使完成四项工作的总的花费时间为最少。
表3-7
工人 工作 甲 乙 丙 丁 戊 1 2 3 4 10 5 15 20 2 10 5 15 3 15 14 13 15 2 7 6 9 4 15 8 9. 6个人完成4项工作任务，由于个人的技术专长不同，他们完成4项工作任务所获得的收益如下表所示，且规定每人只能做一项工作，一项工作任务只需要1人操作，试求使总收益最大的指派方案？
表3-8
工人 工作 1 2 3 4 A 3 5 4 5 B 6 7 6 8 C 8 9 8 10 D 10 10 9 11 E 12 11 10 12 F 13 12 11 13 10. 有四项工作要交给甲、乙、丙、丁四个人去完成，以致每个人完成各项工作的时间如下表所示，问应该怎样指派才能使总的消耗时间为最少。
表3-9
工作 工人 甲
A 15 B 18 C 21 D 24 10