商人過(guò)河的數(shù)學(xué)模型及編程解決(已修改)
2025-06-19 17:34 本頁(yè)面
【正文】 摘要：M對(duì)商仆過(guò)河，一只船最多載N人，船上和岸上的仆人數(shù)都不能多于商人數(shù)，否則商人有危險(xiǎn)。安排合理的渡河方案，保證商人能安全渡河。（可利用向量，矩陣，圖解等方法）一． 問(wèn)題提出：有M對(duì)商仆乘船過(guò)河，一只船最多載N人，由商人和仆人自己劃船渡河，在河的任意一岸，一旦仆人數(shù)多于商人數(shù)，仆人就可將商人殺死，謀取利益，但是乘船渡河的主動(dòng)權(quán)掌握在商人們手中，商人們?nèi)绾伟才哦珊臃桨福拍馨踩珊?？二?假設(shè)：商人和仆人都會(huì)劃船，天氣很好，無(wú)大風(fēng)大浪，船的質(zhì)量很好，船槳足夠很多次的運(yùn)載商人和仆人。三． 參數(shù)：1． 設(shè)（x，y）是狀態(tài)向量，表示任一岸的商人和仆人數(shù)，并且x，y分別要大于等于0，小于等于M。2． 設(shè)（m，n）是運(yùn)載向量，表示運(yùn)載的商人數(shù)和仆人數(shù)，0=m=N，0=n=N，0=m+n=N。3． 設(shè)用s表示所有的可取狀態(tài)向量的集合。4． 設(shè)用d表示所有運(yùn)載向量的集合。5． 設(shè)用 表示從此岸到彼岸，作減；用 表示從彼岸到此岸，作加。Sk：表示第k步可取狀態(tài)向量（sk屬于s）；dk：表示第k步可取轉(zhuǎn)移向量（dk屬于d）；四． 問(wèn)題分析：商仆安全渡河問(wèn)題可以視為一個(gè)多步?jīng)Q策過(guò)程，多步?jīng)Q策是指決策過(guò)程難以一次完成，而是多步優(yōu)化，最后獲取一個(gè)全局最優(yōu)方案的決策方法。對(duì)于每一步，即船由此岸駛向彼岸，或者船由彼岸駛向此岸的決策，不僅會(huì)影響到該過(guò)程的效果，而且還會(huì)影響到下一步的初始狀態(tài)，從而對(duì)整個(gè)過(guò)程都會(huì)有影響。所以，在每一次過(guò)河時(shí)，就不能只從這一次過(guò)河本身考慮，還要把它看成是整個(gè)過(guò)河過(guò)程中的一個(gè)部分。在對(duì)船上的人員做決策時(shí)，要保證兩岸的商人數(shù)不能少于仆人數(shù)，用最少的步伐是人員全部過(guò)河。應(yīng)用狀態(tài)向量和運(yùn)載向量，找出狀態(tài)隨運(yùn)載變化的規(guī)律，此問(wèn)題就轉(zhuǎn)化為狀態(tài)在允許范圍內(nèi)（即安全渡河條件），確定每一次該如何過(guò)河，從而達(dá)到渡河的目標(biāo)?，F(xiàn)在我們都把它們數(shù)量化：即用數(shù)學(xué)語(yǔ)言來(lái)表示。 我們以3名商人為例設(shè)第k次渡河前此岸的商人數(shù)為xk，隨從數(shù)為yk，k=1，2，…，xk，yk =0，1，2，3，將二維向量Sk =（xk，yk）定義為狀態(tài)。安全渡河條件下的狀態(tài)集合稱(chēng)為允許狀態(tài)集合，記為S，則允許狀態(tài)集合為：S={（x，y）| x = 0或3，y = 0，1，2，3，x = y = 1，2} （1）又設(shè)第k次渡船上的商人數(shù)為uk，隨從數(shù)為vk，將二維向量dk=（uk+ vk）定義為決策。則允許決策集合為：D={（u，v）| u + v = 1，2} （2）因?yàn)閗為奇數(shù)時(shí)船從此岸駛向彼岸，k為偶數(shù)時(shí)船由彼岸駛向此岸，所以狀態(tài)Sk隨著決策dk變化的規(guī)律即狀態(tài)轉(zhuǎn)移規(guī)律是：Sk+1 = Sk +（ 1）k dk （3）這樣，制定安全渡河方案歸結(jié)為如下的多步?jīng)Q策問(wèn)題：求決策dk ∈ D（k = 1，2，…，n），使?fàn)顟B(tài)Sk ∈ S按照規(guī)律（3），由初始狀態(tài)S1=（3，3）經(jīng)有限步（設(shè)為n）到達(dá)
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1