《商人过河案例建模》由会员分享,可在线阅读,更多相关《商人过河案例建模(2页珍藏版)》请在金锄头文库上搜索。
1、商人商人过过河河设有三名商人商人,各带一个随从,欲乘一小船渡河,小船只能容纳两人,须 由他们自己划行。随从们密约,在河河的任何一岸,一旦随从的人数比商人商人多, 就杀人越货。而如何乘船渡河的大权掌握在商人们的手中。商人们怎样才能安 全渡河呢?因这已经是一个相当清晰的理想化问题,所以直接讨论其模型描述以及模 型求解。这里将其描述为一个动态决策问题:记第k k次渡河前此岸的商人数为,随从数为, k=1,nk=1,n。将二维向量定义为状态,安全渡河条件下的状态集合称为允许状态集合, 记作S S, 。记第k k次渡船上的商人数为,随从数为, k=1,nk=1,n。将二维向量定义为决策。考虑小船载人数的
2、限制,应满足 ,而称 为允许决策集合。因为k k为奇数时,船从此岸驶向彼岸;k k为偶数时,船从彼岸驶回此岸,所以状态随决策的变化规律是(状态转移规律)。求决策,使状态按照状态转移规律,由初始状态经有限步n n到达状态。接下来讨论模型的求解,设是某个可行的渡河方案所 对应的状态序列,若存在某,且同为奇数或同为偶数,满足,则称所对应的渡河方案是可约的。这时也是某个可行的渡河方案所对应的状态序列。显然,一个 有效的渡河方案应当是不可约的。设渡河已进行到第k k步,为当前的状态,记, ,为保证构造的渡河方案不可约,则当前的决策除了应满足:1) ,且当k k为奇数时,当k k为偶数时,;还须满足:2)当k k为奇数时,;当k k为偶数时,。通过作图,可以得到两种不可约的渡河方案,如下图:思考题:思考题:(1)四名商人商人各带一名随从的情况(小船同前)。(2)n n名商人商人各带n n名随从的情况(小船同前)。