商人過河模型問題的求解

1、數(shù)學建模實驗課程考試試題-商人安全過河數(shù)學建模與求解一問題提出：4名商人帶4名隨從乘一條小船過河，小船每次自能承載至多兩人。隨從們密約, 在河的任一岸, 一旦隨從的人數(shù)比商人多, 就殺人越貨.乘船渡河的方案由商人決定，商人們如何才能安全渡河呢？二模型假設：商人和隨從都會劃船，天氣很好，無大風大浪，且船的質量很好，可以保證很多次安全的運載商人和隨從。三問題分析：商隨過河問題可以視為一個多步決策過程，通過多次優(yōu)化，最后獲取一個全局最優(yōu)的決策方案。對于每一步，即船由此岸駛向彼岸或由彼岸駛向此岸，都要對船上的人員作出決策，在保證兩岸的商人數(shù)不少于隨從數(shù)的前提下，在有限步內使全部人員過河。用狀態(tài)變量表示

2、某一岸的人員狀況，決策變量表示船上的人員狀況，可以找出狀態(tài)隨決策變化的規(guī)律，問題轉化為在狀態(tài)的允許變化范圍內(即安全渡河條件)，確定每一步的決策，達到安全渡河的目標。四模型構成：第k次渡河前此岸的商人數(shù)，第k次渡河前此岸的隨從數(shù), =0,1,2,3,4; k=1,2, =(, )過程的狀態(tài),S 允許狀態(tài)集合，S=(x , y)| x=0, y=0,1,2,3,4; x=4 ,y=0,1,2,3,4; x=y=1,2,3第k次渡船上的商人數(shù)第k次渡船上的隨從數(shù)=(, )決策，D=(u , v)| , =0,1,2 允許決策集合k=1,2, 因為k為奇數(shù)時船從此岸駛向彼岸，k為偶數(shù)時船從彼岸駛向此

3、岸，所以狀態(tài)隨決策的變化規(guī)律是=+狀態(tài)轉移律求D(k=1,2, n), 使S, 并按轉移律由=(4,4)到達狀態(tài)=(0,0)。五模型求解：1.圖解法：對于人數(shù)不多的情況，可以利用圖解法來求解。在xoy平面坐標系上畫出如圖所示的方格，方格點表示狀態(tài)s=(x,y)，允許狀態(tài)集合S是圓點標出的13個格子點，允許決策是沿方格線移動1格或2格，k為奇數(shù)時向左、下方移動，k為偶數(shù)時向右、上方移動。要確定一系列的使由=(4,4)經過那些圓點最終移動到原點(0,0)。由初始狀態(tài)(4,4)到原點(0,0)，無論怎樣走，都要經過(2,2)，但是無論怎樣變化人數(shù)，也只能到達此點后不能繼續(xù)走下去，只能循環(huán)走(由d7狀

4、態(tài)無法不重復循環(huán)地走下去)，達不到最終的目標(0,0)，因此該問題無解。 yd1 d7d6 d2 d2 d5 d4 4 3 d1 2 d3 1 0 1 2 3 4 x2. 窮舉法：根據(jù)分析可以通過編程上機求解，所用的c程序如下所示：#include <stdio.h>#define N 30int xN,yN,u6,v6,k;/* x,y：狀態(tài)值，分別表示此岸商人、隨從數(shù)*/*u,v：決策值，分別表示船上商人、隨從數(shù)*/* k：決策步數(shù)；k的奇偶性標志著船在河的此岸或彼岸 */next(int k,int i)/*計算下一狀態(tài)*/ if(k%2) /* k+1 為偶數(shù)，船從此岸到彼

5、岸 */ xk+1=xk-ui; yk+1=yk-vi; else /* k+1 為奇數(shù)，船從彼岸到此岸 */ xk+1=xk+ui; yk+1=yk+vi; return;allow(int p,int q)/* 判定狀態(tài)是否允許,是否重復 */ int ok,j; /* ok:標記狀態(tài)是否允許,是否重復；j:循環(huán)變量 */ if(p<0|p>x1|p!=0&&q>p|(x1-p)!=0&&(y1-q)>(x1-p)|q<0|q>y1) ok=0; /* 此時狀態(tài)不屬于允許集 */ else for(j=k-1;j>0

6、;j-=2) /* 是否重復與船在河的哪一岸有關 */ if(p=xj && q=yj ) ok=0; /* 此時狀態(tài)出現(xiàn)重復 */ break; if(j<=0) ok=1; /* 此時狀態(tài)屬于允許集，且不重復 */ return ok;void main() int i,j,mN,flag=1;/* m:采用的決策序號，flag:回溯標記 */ u1=2; v1=0; /* 給決策編號并賦值 */ u2=0; v2=2; u3=1; v3=0; u4=0; v4=1; u5=1; v5=1; k=1; /* 從初始狀態(tài)出發(fā) */ printf("請輸入商人和

7、隨從的初始狀態(tài):n商人數(shù)="); scanf("%d",&xk); printf("隨從數(shù)="); scanf("%d",&yk); while(flag) for(i=1;i<6;i+) /* 遍歷各種決策 */ next(k,i); /* 計算下一狀態(tài) */ if(allow(xk+1,yk+1) /* 若新狀態(tài)允許且不重復 */ mk=i; /* 記錄采用的決策序號 */ if(xk+1=0 && yk+1=0) /* 若到達目標狀態(tài),輸出結果 */ printf("初始值:商人%d隨從%dn",x1,y1); for(j=1;j<=k;j+) printf(" 第 %2d 次 %d %dn",j,xj+1,yj+1); flag=0; break; else /* 若未到達目標狀態(tài) */ k+; /* 生成下一步的步數(shù)值 */ break; /* 遍歷終止，進入下一步 */ else /* 若新狀態(tài)不允許或重復 */ while(i=5) /* 本步決策已經遍歷時 */ if(k=1) printf("本題無解!n"); flag=0; break; else /* 未到達初始狀態(tài) */ k