運籌學相關問題

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