统筹规划问题

统筹规划问题

先列约束,画表或流程图;按“时间最短、费用最低、效率最高”三目标,优先安排瓶颈资源,用贪心或枚举比对方案;运输问题比较吨千米数,生产问题算边际贡献,30秒得最优解。


一、知识点梳理


1.核心题型与原则

统筹问题研究人力、物力的优化配置,目标为时间最少、费用最省、效率最高。核心原则包括:

- 并行处理:能同时进行的任务尽量并行;
- 短时优先:耗时短的任务优先处理,减少等待时间;
- 轻往重靠:货物集中时,轻量端向重量端移动。

2.高频题型与公式

(1) 空瓶换酒问题

核心公式

$z = x + \left\lfloor \frac{x}{y/n - 1} \right\rfloor $

推导依据:$y $空瓶换$n $瓶饮料 →$y-n $ 空瓶换 $n $份纯饮料。

示例:12空瓶换1瓶水 ⇒ $11 $ 空瓶换$1 $份纯水


(2) 人员分配问题

设 $X$ 个工厂、 $Y $辆车:

- $X > Y $

最少人数 = 需求最多的 $Y$ 个工厂人数之和;

- $X \leq Y $

最少人数 = 所有工厂需求人数之和。


(3) 货物集中问题

操作步骤

① 按位置排列货物点;

② 比较任意点两侧总重量;

③ 轻侧货物向重侧移动。


(4) 排队打水问题

$n$ 人打水时间分别为$t_1, t_2, \dots, t_n $(升序排列),总等待时间最小值为:

$\sum_{i=1}^{n} t_i \times (n-i+1) $

原则:打水时间短者优先。



二、历年真题解析


真题1:时间统筹(2023联考)

题干:烧水壶(1分钟)、烧水(15分钟)、洗茶壶(1分钟)、洗茶杯(1分钟)、拿茶叶(2分钟)。求最快沏茶时间。

解析:烧水同时可完成洗茶壶、洗茶杯、拿茶叶。

$\text{总耗时} = \max(\text{烧水时间}, \text{其他任务时间}) + \text{烧水壶时间} = 15 + 1 = 16 \text{分钟} $


真题2:空瓶换酒(2020甘肃)

题干:12空瓶换1瓶水,现有101空瓶,求最多喝多少瓶水。

解析

$z = 101 + \left\lfloor \frac{101}{12-1} \right\rfloor = 101 + \left\lfloor \frac{101}{11} \right\rfloor = 101 + 9 = 110 \text{瓶} $

关键:11 空瓶换 1份纯水(不含瓶)。


真题3:货物集中(2017国考)

题干:5个仓库依次排列,1号存10吨、2号存20吨、5号存40吨。每吨每公里运费0.5元,集中到一仓库求最小运费。

解析:五号仓库货物最重(),向五号集中。运费计算:

$\text{运费} = 0.5 \times (10 \times 400 + 20 \times 300) = 0.5 \times (4000 + 6000) = 5000 \text{元} $

原则非闭合路径遵循“轻往重靠”。

$40 \text{吨} > 10+20=30 \text{吨} $


真题4:人员分配(2015安徽)

题干:5工厂需装卸工(7、9、4、10、6人),3辆车。求最少装卸工数。

解析:$X=5 > Y=3 $,取需求最多的3个工厂(10、9、7)之和:

$\text{最少人数} = 10 + 9 + 7 = 26 \text{人} $


真题5:排队打水(2023吉林)

题干:5人打水需时1、2、3、4、5分钟,1个水龙头。求最小总等待时间。

解析:按升序排列(1、2、3、4、5),总等待时间:

$ \begin{aligned} \text{总时间} &= \sum_{i=1}^{5} t_i \times (6-i) \\ &= 1 \times 5 + 2 \times 4 + 3 \times 3 + 4 \times 2 + 5 \times 1 \\ &= 5 + 8 + 9 + 8 + 5 = 35 \text{分钟} \end{aligned} $

原则短时优先减少群体等待。



三、技巧总结

1. 通用原则

时间统筹:并行任务、短时优先;
货物集中:轻往重靠;
效率分配:高效优先。

2. 公式应用

空瓶换酒严格验证公式(如例题2);
人员分配注意 $X$ 与 $Y$ 大小关系。

3. 易错点

货物集中时距离影响运费计算(如例题3中的距离倍数);
排队取水中“等待时间”需累加前面所有人耗时。