学而思讲义第13讲---统筹与最优化(竞赛班程度)

《学而思讲义第13讲---统筹与最优化(竞赛班程度)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第十三讲·统筹与最优化本讲围绕尽可能在节省人力物力时间的前提下，在允许的范围内获得最好的效益这个中心，出现了以下几类题型：过河（桥）问题：解题思路1、选择时间最少的两个过河，到达对岸后，选择时间最少的一个返回；2、选择时间最多的两个过河，到达对岸后，选择时间最少的一个返回；3、……反复上边1、2步骤，直至全部过河为止。如：骑牛赶牛题；夜里打灯过桥题。排队等待题：解题思路1、将所用时间从小到大排出一列；2、按照分配对象个数分出组数；3、从左到右，从上到下地将时间分配到各组。例：水龙头打水题（水龙头的个数决定组数）；机器加工零件（机器数决定组数）；维修队维修电

2、器（维修队个数决定组数）集合点选址：解题思路1、如果线上有奇数(2n+1)个点，集合点位于第n个点；2、如果线上有偶数(2n)个点，集合点位于第n个点到第n+1个点之间的线段上均可。例：街道上选公交站；1993个少先队员选集合点。仓库选址：原则：“小往大靠，支往干靠”。解题思路1、先观察图形，选定最大点出发，考虑它与另一边的大小。如果大，仓库选在此。如果小，它往另一边的最近点靠。2、重复上一步，比较被靠上点的数与其另一边的大小。如果大，仓库选在此。如果小，它往另一边最近点靠。3、重复上一步，直至确定仓库选址。例：仓库选址、小学选址、糖厂选址、麦场选址……调

3、运货物问题：[例]：北京、洛阳分别有11台和5台完全相同的机器，准备调运给杭州7台、西安9台，每台机器的运费如下表，如何调运才能使总费用最省？杭州西安运到站费发站北京600500洛阳800600法一：设从北京发杭州x个机器，则北京发西安11-x个机器，从洛阳发杭州7-x个机器，从洛阳发西安x-2个机器，依题意得：总费用=600xxx+50011()−+8007(−+)600(x−2)=−9900100x当x最大为7时候，总费用最少，为9200元。法二：观察表格，发现从北京调往杭州比从洛阳调往杭州每台节约200元，而从北京调往西安比从杭州调往西安每台节约10

4、0元，200>100。可见从北京调往杭州更划算。所以从北京往杭州调7台，从北京往西安调4台；从洛阳往西安调5台。总费用最省，为9200元。（法二虽然更简单，但务必要掌握法一）[竞赛班]A、B两个粮店分别有70吨和60吨大米，甲、乙、丙三个居民点分别需要30吨、40吨和50吨大米。从A、B两粮店每运1吨大米到三个居民点的费用如下，如何调运才能最省钱？甲乙丙运到站费发站A273B3105【分析】方法如上题法二，观察图形：3-2=1，10-7=3，5-3=2.其中第二列差最大。因此A粮店的大米应尽力可能多的供应给乙，即A供应给乙40吨。同理，第三列的差比第一列的

5、差大，A店余下的30吨给了丙。丙还差20吨，从B粮店调20吨。于是B粮店余下40吨。从这40吨当中调出30吨给甲。此时运费最少。为：303407303205×+×+×+×=560元。调运方案如下：甲乙丙运到站费发站A04030B30020物资流向图：原则——避免对流例：勘探队调整人数题劳力组合之效率比问题：多种劳力（或者机械）干两种配套活的一般分工原则：设甲生产A产品与生产B产a1a2a1a2品的数量比为，乙生产A产品与B产品的数量比为；如果＞，则甲b1b2b1b2擅长生产A产品，乙擅长生产B产品。在分工合作时，就让甲多用A,乙多做B，此时最有效率。