最小重量機(jī)器設(shè)計(jì)問(wèn)題工作分配問(wèn)題

《最小重量機(jī)器設(shè)計(jì)問(wèn)題工作分配問(wèn)題》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、一、算法實(shí)現(xiàn)題5-3最小重量機(jī)器設(shè)計(jì)問(wèn)題設(shè)某一機(jī)器由n個(gè)部件組成,每一種部件都可以從m個(gè)不同的供應(yīng)商處購(gòu)得。設(shè)w[i][j]是從供應(yīng)商j處購(gòu)得的部件i的重量，di][j]是相應(yīng)的價(jià)格，給出總價(jià)格不超過(guò)d的最小重量機(jī)器設(shè)計(jì)。1、解題說(shuō)明這是一個(gè)最優(yōu)規(guī)劃問(wèn)題，采用木章回溯法來(lái)求解。解空間是一個(gè)子集樹(shù)，因此通過(guò)遞歸函數(shù)對(duì)解空間進(jìn)行深度優(yōu)先搜索，只要在當(dāng)前結(jié)點(diǎn)，只要滿(mǎn)足限定條件和限界條件，則遞歸下一層，否則就嘗試下一個(gè)供應(yīng)商。Backtrack(1)實(shí)現(xiàn)對(duì)整個(gè)解空間的回溯搜索，Backtrack(i)搜索解空間中第i層子樹(shù)。類(lèi)

2、Machine的數(shù)據(jù)成員記錄界空間中結(jié)點(diǎn)信息。在算法Backtrack中，當(dāng)i〉n的時(shí)候，算法搜索至葉節(jié)點(diǎn)，得到一個(gè)新的可行解，與當(dāng)前最優(yōu)解進(jìn)行比較，并更新最優(yōu)值。當(dāng)i〈=n的時(shí)候，當(dāng)前擴(kuò)展結(jié)點(diǎn)是解空間屮的內(nèi)部結(jié)點(diǎn)。該結(jié)點(diǎn)有m個(gè)子節(jié)點(diǎn)。若滿(mǎn)足當(dāng)前總費(fèi)用小于最大總費(fèi)用，并且當(dāng)前總重量小于最小總重量，那么以深度優(yōu)先的方式遞歸地對(duì)可行子樹(shù)進(jìn)行搜索，或剪去不可行子樹(shù)。2、程序代碼#include#includeusingnamespacestd;classMachine{//機(jī)器類(lèi)publ

3、ic:MachineO{//構(gòu)造函數(shù)cw=cc=0;minw=1000;ifstreamin("i叩ut.txt");//從文件輸入in?n>>m?d;bestprovider=newint[m+l];//初始化最優(yōu)供應(yīng)商和供應(yīng)商數(shù)組provider=newint[ni+1];c=newdouble[n+l];//創(chuàng)建部件價(jià)格二維數(shù)組for(i=l;i〈=n;i++)c[i]=newdouble[m+l];for(i=l;i<=n;i++)//從文件瀆入價(jià)格for(intj=l;j<=m;j++)in〉〉c[i][j]

4、;//創(chuàng)逑部件東量二維數(shù)組w=newd()uble[n+l];for(i=l;i〈=n;i++)[i]=ncwdouble[m+l];for(i=l;i<=n;i++)//從文件讀入重量for(intj=l;j<=m;j++)in?w[i][j];voidBacktrack(inti){if(i〉n){//己得到一個(gè)可行解if(cw〈minw){//更新最小重量mimv-cw;for(intj=l;j<=m;j++)bestprovider[j]二provider[j];}return;for(intj=l;j<=m;

5、j++){provider[i]二j;//考慮第j個(gè)供應(yīng)商cc+=c[i][j];cw+=w[i][j];//滿(mǎn)足限定條件并且滿(mǎn)足限界條件，則遞歸下一層if(cc<=d&&cw

6、';cout<

7、ach.Output();return0;3、運(yùn)行截圖1）程序所在文件夾有input,txt,運(yùn)行完成后產(chǎn)生了output,txtDebugtjinputtxtoutput.txt最小重墾機(jī)器設(shè)計(jì)冋監(jiān)xpp最小重墾機(jī)器設(shè)計(jì)間g.dsp_最小雪墾機(jī)囂設(shè)計(jì)冋E.ncb_最小重墾機(jī)器設(shè)計(jì)間琵.opt_最小雪墾機(jī)囂設(shè)計(jì)冋E.plg2）輸入文件input,txt第一行分別是部件數(shù)量n，供應(yīng)商數(shù)量m，和最大費(fèi)用d;緊接著輸入一個(gè)n行m列的部件價(jià)格數(shù)組和一個(gè)n行m列的部件重量數(shù)組。邏input.txt?享本文件(F)顚(E)格式(0

8、3341233212221233212223)運(yùn)行程序后，打開(kāi)ouput.txt,輸出結(jié)果如下:output.txt-記事本文件(F)騎E)格式(O)查看(V)4131Dos界面運(yùn)行如下:<■懺:我的匚++職算法冊(cè)與分析5-31131Pressanykeytocontinue二、算法實(shí)現(xiàn)題5-13工作分配問(wèn)題設(shè)有n件工作分配給