運(yùn)籌學(xué)相關(guān)問題

運(yùn)籌學(xué)相關(guān)問題————————————————————————————————作者：————————————————————————————————日期：2一、某公司有6個(gè)零件加工廠，工廠之間的距離（對(duì)稱）以下表（公里）。現(xiàn)在要在6家工廠中選一個(gè)建裝置車間。加工廠123456零件重量10896861.520105——41.63035130.84012——1.35090.6600.71，若是組裝一個(gè)成品需要各個(gè)加工廠的零件重量分別為1.5,1.6,0.8，1.3，0.6,0.7噸，運(yùn)費(fèi)為3元·噸公里，那么怎樣選廠使得總運(yùn)費(fèi)最小？2，若是要從某一廠出發(fā)，把全部的道路巡邏一遍回到原處，應(yīng)該怎樣走使得總距離近來？3，若是要從某一廠出發(fā)，6個(gè)加工廠不重復(fù)的都巡邏一遍回到原處，怎樣走使得總距離最近？為何？我對(duì)這個(gè)題目的理解：第一問（運(yùn)輸問題）和第二問（中國郵遞員問題）都是會(huì)做的，運(yùn)算量也不是很大，重點(diǎn)是第三問應(yīng)該是顯然的TSP問題，就這個(gè)問題，我經(jīng)過查找資料知道了兩種方法：一種是動(dòng)向規(guī)劃的解法，但這種方法計(jì)算量特別大；另一種方法是分枝定界法，從一本運(yùn)籌學(xué)教材上找到的，馬上距離矩陣像匈牙利算法似地辦理，但是不是太理解。所以想問下老師（1）題目中說從某一廠出發(fā)，我以為可以任選一廠，求得的路線由于是循環(huán)的，所以結(jié)果應(yīng)該與選哪一廠沒關(guān)，想向老師求證一下（2）關(guān)于旅游商問題，不知道在老師知道的全部解法中，哪一種是最簡(jiǎn)略易于手算求解的？二、一條多品種流水線上要輪換生產(chǎn)n種不同樣零件，假設(shè)從生產(chǎn)零件i變換生產(chǎn)零件j所需要的設(shè)備調(diào)整時(shí)間為T，列出使總的設(shè)備調(diào)整時(shí)間最小的數(shù)學(xué)模型，以給出n個(gè)零件的生產(chǎn)序次。并就以下5個(gè)零件給出總調(diào)整時(shí)間最小的生產(chǎn)序次（要求說明所使用的方法獲得的生產(chǎn)序次是最優(yōu)的）。123451——3810727——61112368——544963——13511856——關(guān)于這個(gè)題目，我以為也是TSP問題吧，但問題在于這個(gè)矩陣是非對(duì)稱矩陣，所以想請(qǐng)問老師關(guān)于非對(duì)稱矩陣，求解方法可否會(huì)有變化？那一種方法可以通用？三、某科學(xué)試驗(yàn)可用1,2,3三套不同樣儀器中的任一套去完成，每做完一次試驗(yàn)后，若是下次仍用本來的儀器，則需要對(duì)該儀器進(jìn)行檢查整修而中止試驗(yàn)；假以下次換用別的一套儀器，則需要拆裝儀器，也要中止試驗(yàn)。假設(shè)一次試驗(yàn)時(shí)間比任何一套儀器的整修時(shí)間都長，所以一套儀器換下來隔一次再重新使用時(shí)，不會(huì)整修而影響試驗(yàn)。設(shè)i儀器換成j儀器所需中止試驗(yàn)的時(shí)間為t，以下表所示?，F(xiàn)要做4次試驗(yàn)，問應(yīng)怎樣安排使用儀器的序次，使總的中止試驗(yàn)的時(shí)間最??？Tj123110914i9121023/43658關(guān)于這個(gè)問題，我以為不是TSP問題，由于依據(jù)題目的說法，一套儀器是可以重復(fù)出現(xiàn)在4次試驗(yàn)中的，關(guān)于這個(gè)問題我的做法是用動(dòng)向規(guī)劃的方法，將每次試驗(yàn)儀器的編號(hào)作為狀態(tài)變量，不知道老師怎么看？由于動(dòng)向規(guī)劃的題目實(shí)在是變化多端，所以其實(shí)不確定？問題整理：一、相關(guān)真題1,2008年第五題，實(shí)質(zhì)是一TSP問題，即出名的旅游商問題（貨郎擔(dān)問題），關(guān)于這個(gè)問題誠然可以用動(dòng)向規(guī)劃解決，但是我試著手算了一下，完好算完最快也要分鐘，特別耗時(shí)，這在考場(chǎng)上現(xiàn)實(shí)嗎？我查察了大批的資料，認(rèn)識(shí)到這是一個(gè)NP難問題，也就是說沒有多項(xiàng)式算法，但是近似算法特別多，所以請(qǐng)問近似算法得出的結(jié)果可否正確呢？也許有沒有更好的簡(jiǎn)單易算的解法？求見教;關(guān)于這個(gè)問題的另一個(gè)想法是這是一個(gè)工件排序問題，也是特別典型的一類問題，并且在2011年的試題中也有出現(xiàn)，所以不知道解決這種問題有沒有一般的理論，可否介紹一些書本也許介紹一些理論，由于我自己找過，但是視線比較狹小，所以沒找到比較好的專著。2,2009年第四題的第4小問，出現(xiàn)了時(shí)間坐標(biāo)網(wǎng)絡(luò)圖這一觀點(diǎn)，但是課本上并無這一觀點(diǎn)，不單這樣，正如紅寶書中提到的2009年第七題的二人非零和博弈超綱，經(jīng)過研究真題，我發(fā)現(xiàn)每年都有不同樣程度的超綱內(nèi)容，對(duì)待這種超綱內(nèi)容應(yīng)該怎樣備考呢？3，2009年第六題紅寶書上寫著待寫，應(yīng)該是很難吧，下邊是我的理解，希望可以商議下：我對(duì)這個(gè)題目的理解：第一問是最短路問題，但是要求出每個(gè)點(diǎn)的最短路爾后再乘以重量，進(jìn)而比較各個(gè)點(diǎn)。第二問是中國郵遞員問題，有奇偶點(diǎn)作業(yè)法即可解決，運(yùn)算量也不是很大。第三問是顯然的TSP問題，可以用動(dòng)向規(guī)劃求解，如上所言，計(jì)算量特別大，但本題的特色矩陣是對(duì)稱的，不知道這一特色對(duì)解決本題有什么好的啟示，希望共同商議下。4,2010年第三題，拘束條件明確寫明是非負(fù)整數(shù)，也就是說這屬于失散型動(dòng)向規(guī)劃的求解，為何紅寶書中有連續(xù)型的方法求解？5,2010年第八題，紅寶書上把求解過程略了，應(yīng)該是求不出來吧，確立是一線性規(guī)劃問題嗎？剛開始我想的時(shí)候也以為是一線性規(guī)劃問題，但是列出模型此后發(fā)現(xiàn)求解特別復(fù)雜，加上廢弛變量共有22個(gè)，這在考場(chǎng)是不行能算出來的吧？是出題人根本就沒想讓我們做對(duì)呢？仍是可以轉(zhuǎn)變成其余問題，比方圖論等？從這個(gè)題目也可以看出歷年的真題的計(jì)算量都特別大，若是你是早年的考生，我想請(qǐng)問下考場(chǎng)上的時(shí)間是怎樣掌握的？可否是會(huì)做不完？并且運(yùn)籌素來重申的建立模型，為何南開這么重申計(jì)算呢？仍是說那些計(jì)