Question

【数学难题】你的数学很好吗？进来挑战你自己吧【数学高手进】

问题：
现在有三个水桶，编号分别为a,b,c。有三个人编号分别为m,n,k。
三个水桶一开始分别有高度为h_a,h_b和h_c的水。

现在让三个人往水桶里面注水。每一次，只能选择一个人往三个水桶里面注水。
如果选择让m来注水，可以分别使A,B,C三个水桶中水的高度分别增加H_ma,H_mb和H_mc。
同理，如果让n或者k来注水，可以使三个桶中的水增加H_na,H_nb,H_nc和H_ka,H_kb,H_kc。
以上所有参数都是已知，而且不变的。

问题就是，每一次应该如何选择让哪一个人来注水，才能用最少的次数，使三个水桶都被注满？
请讲出详细的算法，并说明为什么你的方案是最优的。

谢谢。

Answer 1

人：i=m,n,k; 桶 j=a,b,c 设桶的总高度为Hj，初始高度h_j,不同人注水一次的增加高度H_ij
正整数变量：注水次数 l ；
0，1变量：Xil 如果第 l 次注水选第 i 个人为1；否则0

数学模型：min l
约束：sum（（i ,l）, H_ij * Xil）>= Hj - h_j
l >0 取整数，Xil ：0，1变量

追问

非常感谢你的认真思考和恢复。对滴就是我要的答案。
不管你是否继续回答下面的附件问题，我都决定选你的答案了。
我还想问一下，如果改为水桶高度都是100cm。
如果选m注水，则有H_ma,H_mb和H_mc的概率使a,b,c水的高度上升1cm。选n,k同样也换成概率_na,H_nb,H_nc和H_ka,H_kb,H_kc使A,B,C高度上升1cm。
又应该怎样做呢？谢谢了

追答

这样的话，问题就是一个随机规划问题，模型要变成带概率和数学期望的形式，即随机规划问题的数学模型。（今天没时间做了，要出差。如果不急就等下周）

追问

好的 我等着你的回答。谢谢。

追答

1. 先修正一下上面的模型，加上每次只一个人去注水的限制条件。
约束： sum(i, Xil) =1,
2. 关于随机规划模型，目标函数应该为注水次数的数学期望最小，因此需要建立每个人注水增高概率和最小注水次数之间的一个函数关系，这个没想出来。第二个问题描述完整了吗？呵呵！感觉还缺东西。

追问

非常感谢你准时回来回答。
我的问题里面概率的分布很简单，比如m对a来注水，H_ma概率增加1，(1-H_ma)概率增加0。其他几个概率分布也类似。
其他没有任何信息了

追答

设Pij 为给定概率，设定一个置信水平apha，
min L
s.t. P(sum((i ,l), 1 * Xil）>= 100 - h_j)) = sum((i ,l), Pij * Xil）>= apha,
对于j＝1，2，3 ，l=1,...,L
sum(i, Xil) =1 对于l=1,...,L
L >0 取整数，Xil ：0，1变量
第一个约束的含义是L次注水后桶j满的概率要大于某个置信水平；第二个约束含义每次限定一个人注水，第三个约束变量约束。

追问

非常感谢。
我还有一个小疑问：
解上面的模型只是求出了一个在某个置信水平下的最小期望注水次数。对吧？
比如我们假设解出来的是L=120。
既然L=120只是一个期望，那么实际中可能大于120次。
实际操作中，我每次应该怎么去选择由谁来注水呢？

追答

上面的模型只能解决在设定置信水平上的一个最小注水次数。
求解模型，就可以得到每个 Xil 的值，如果对于某个l，某个 Xil 等于1，则意味着第l次注水，选择第 i 个人去注水。

追问

恩。我的意思是，假设解出来的是L=120。那么x1l,x2l,x3l都是一个只有120行（或者列）的向量。在前120次可以按照xil来注水。
但是实际中，可能是需要大于120次次能注满。那么超过120次以后应该怎么选择呢？

追答

如果按照一个设定的置信水平，求得最小次数L，按照此结果注水（实际操作），到L次仍旧未达到三个桶全满，之后如何操作，由前面的结果无法指导，但可以再解一次该模型，只不过3个桶里的初始水高为前一次经过L次注水后的高度，其他不变，仍旧可得到一个基于一定置信水平的注水方案和最小注水次数。如此迭代直到完成任务，三个桶满，将几次L相加即为注水次数。
还有一种方法，如果担心出现你所说的情况，可将置信水平设置得高一些，这样可保证L次完成注水任务。

Answer 2

解：设三只水桶都满时，m、n、k分别注水x、y、z次，设a高h1，b高h2，c高h3，则
xH_ma+yH_na+zH_ka≥h1-h_a
xH_mb+yH_nb+zH_kb≥h2-h_b
xH_mc+yH_nc+zH_kc≥h3-h_c
x、y、z≥0
要找N=x+y+z的最小值
这是一个最优化问题，同学可以参考《线性规划》或者《统筹学》。

Answer 3

A