數(shù)學(xué)建模 信息創(chuàng)新121-劉聰

1、數(shù)學(xué)建模數(shù)學(xué)建模信息創(chuàng)新信息創(chuàng)新121121班1818劉聰劉聰0606黃超黃超電話：電話：1884087235518840872355最優(yōu)解，可以通過枚舉法，但由于數(shù)據(jù)量過大，顯然枚舉法行不通。經(jīng)過分析，決定采用貪婪法來獲得次優(yōu)解，即以自頂向下的方式進(jìn)行，以迭代的方式做出相應(yīng)的貪心選擇，每作一次貪心選擇就將所求問題簡(jiǎn)化為規(guī)模更小的子問題。我們選擇貪婪算法的原因，是因?yàn)榇藛栴}滿足貪婪算法能夠獲得最優(yōu)解的兩個(gè)條件：一、貪婪選擇性質(zhì)，所求問題

2、的整體最優(yōu)解可以通過一系列局部最優(yōu)解的選擇，即貪心選擇來達(dá)到，從一點(diǎn)開始，每一次尋找距離此點(diǎn)最近的點(diǎn)，將兩點(diǎn)連線，再以第二個(gè)點(diǎn)為基準(zhǔn)，按這種思想尋找下一個(gè)點(diǎn)，依次將所有連起來，因?yàn)槊恳淮味际侨∽疃叹嚯x，因而所有點(diǎn)的連線也是最短的。二、最優(yōu)子結(jié)構(gòu)性質(zhì)，本題中每一點(diǎn)尋找與之距離最近的點(diǎn)都會(huì)受到上一個(gè)點(diǎn)的影響，因?yàn)橹挥写_定了上一級(jí)的點(diǎn)，才可能確定下一個(gè)點(diǎn)。另外，由于八種刀具轉(zhuǎn)換時(shí)候即可以順時(shí)針旋轉(zhuǎn)，也可以逆時(shí)針旋轉(zhuǎn)，因此在刀具轉(zhuǎn)換過程中，要選

3、擇正確的旋轉(zhuǎn)方向，以減少加工成本。同時(shí)，由于刀具在行進(jìn)過程中，可以同時(shí)進(jìn)行刀具，但相應(yīng)費(fèi)用不減。因此，為了提高生產(chǎn)效率，我們選擇刀具一邊行進(jìn)，一邊進(jìn)行刀具轉(zhuǎn)換，如果行進(jìn)過程的時(shí)間小于刀具轉(zhuǎn)換所需時(shí)間，則當(dāng)打孔機(jī)達(dá)到目標(biāo)點(diǎn)的時(shí)候繼續(xù)進(jìn)行刀具轉(zhuǎn)換。問題二:本問題中，打孔機(jī)在作業(yè)的時(shí)候，既要保證行進(jìn)時(shí)間最短和作業(yè)成本最少，又要保證在過孔加工的任何時(shí)刻保持兩鉆頭不小于3cm。尋找一條最短路徑相對(duì)容易些，但是要想時(shí)刻保證兩鉆頭的距離不小于3cm則

4、相對(duì)困難。為了保證打孔路線最優(yōu)，經(jīng)過研究，我們決定同樣采用貪婪法解決雙鉆頭打孔問題。同時(shí)，我們采用動(dòng)態(tài)監(jiān)測(cè)的方法，每隔一段時(shí)間（即鉆頭每行進(jìn)1mm所對(duì)應(yīng)的時(shí)間）檢測(cè)每一個(gè)鉆頭在尋找下一個(gè)目標(biāo)點(diǎn)的過程中與另外一個(gè)鉆頭的距離，以近似地滿足兩鉆頭合作間距。另外，為了避免兩鉆頭相撞，我們假設(shè)兩鉆頭同時(shí)尋找下一個(gè)目標(biāo)點(diǎn)，即如果一個(gè)鉆頭先完成當(dāng)前的作業(yè)，也必須等待另一個(gè)鉆頭完成作業(yè)后，才能夠共同尋找各自的下一個(gè)目標(biāo)點(diǎn)。當(dāng)我們計(jì)算出兩鉆頭作業(yè)時(shí)的最優(yōu)