《商人过河案例建模》由会员分享，可在线阅读，更多相关《商人过河案例建模（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名随从的情况（小船同前）。
