資源描述：
《貨郎擔問題課件.ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、貨郎擔問題小組成員：阿迪力劉帥馬曉貨郎擔問題貨郎擔問題一般提法為：一個貨郎從某城鎮(zhèn)出發(fā)，經(jīng)過若干個城鎮(zhèn)一次，且僅經(jīng)過一次，最后仍回到原出發(fā)的城鎮(zhèn)，問應如何選擇行走路線可使總行程最短，這是運籌學的一個著名的問題。實際中有很多問題可以歸結(jié)為這類問題。哈密爾頓回路：（環(huán)球旅行問題）即從一個結(jié)點出發(fā)，經(jīng)過所有結(jié)點回到出發(fā)點（結(jié)點不能重復經(jīng)過）。問題描述：設v1，v2，……..，vn是已知的n個城鎮(zhèn)，城鎮(zhèn)vi到城鎮(zhèn)vj的距離為dij，現(xiàn)求從v1出發(fā)，經(jīng)各城鎮(zhèn)一次且僅一次返回v1的最短路程。解決方案：1.窮舉法？2.最短路標號法？3.指派問題？4.整數(shù)規(guī)劃？5.動態(tài)規(guī)劃？建立動態(tài)規(guī)
2、劃模型：設S表示從v1到vi中間所可能經(jīng)過的城市集合，S實際上是包含除v1和vi兩個點之外的其余點的集合，但S中的點的個數(shù)要隨階段數(shù)改變。階段：S中的點的個數(shù)狀態(tài)變量（i，S）表示：從v1點出發(fā)，經(jīng)過S集合中所有點一次最后到達vi。最優(yōu)指標函數(shù)fk（i，S）為從v1出發(fā)，經(jīng)過S集合中所有點一次最后到達vi。決策變量Pk（i，S）表示：從v1經(jīng)k個中間城鎮(zhèn)的S集合到vi城鎮(zhèn)的最短路線上鄰接vi的前一個城鎮(zhèn)，則動態(tài)規(guī)劃的順序遞推關系為：fk（i，S）=min{fk-1（j，S、{j}+dji} j屬于Sf0（i，空集）=d1i（k=1，2，…,n-1,i=2,3,…n)例1
3、：已知4個城市間距離如下表，求從v1出發(fā)，經(jīng)其余城市一次且僅一次最后返回v1的最短路徑和距離。解：K=0由邊界條件知: f0(2,空集)=d12=6 f0(3,空集)=d13=7 f0(4,空集)=d14=9當k=1時: 從城市V1出發(fā),經(jīng)過1個城鎮(zhèn)到達Vi的最短距離為: f1(2,{3})=f0(3,空)+d32=7+8=15 f1(2,{4})=f0(4,空)+d42=9+8=14 f1(3,{2})=f0(2,空)+d23=6+9=15 f1(3,{4})=f0(4,空)+d43=9+5=14 f1(4,{2})=f0(2,空)+d24=6+7=13 f1(4,
4、{3})=f0(3,空)+d34=7+8=15當k=2時,從城市V1出發(fā),中間經(jīng)過2個城鎮(zhèn)到達Vi的最短距離.f2(2,{3,4})=min[f1(3,{4})+d32,f1(4,{3})+d42]=min[14+8,15+5]=20P2(2,{3,4})=4f2(3,{2,4})=min[14+9,13+5]=18P2(3,{2,4})=4f2(4,{2,3})=min[15+7,15+8]=22P2(4,{2,3})=2當k=3時: 從城市V1出發(fā),中間經(jīng)過3個城鎮(zhèn)最終回到Vi的最短距離.f3(1,{2,3,4})=min[f2(2,{3,4})+d21,f2(3,
5、{2,4})+d31,f2(4,{2,3})+d41]=min[20+8,18+5,22+6]=23P3(1,{2,3,4})=3逆推回去,貨郎的最短路線是1?2?4?3?1, 最短距離為23.貨郎擔問題當城市數(shù)目增加時,用動態(tài)規(guī)劃方法求解,無論是計算量還是存儲量都會大大增加,所以本方法只適用于n較小的情況.在很多貨郎擔問題中，經(jīng)常會看到dij不等于dji的情況。這是因為：1，各城市之間可能是復線2，兩地之間可能會使用不同的交通工具從而費用不同。實際中很多問題都可以歸結(jié)為貨郎擔這類問題. 如: 1,物資運輸路線中,汽車應該走怎樣的路線使路程最短; 2,工廠里在鋼板上要
6、挖一些小圓孔,自動焊接機的割咀應走怎樣的路線使路程最短; 3,城市里有一些地方鋪設管道時,管子應走怎樣 的路線才能使管子耗費最少,等等比如說，前面曾經(jīng)遇到的排序問題，以前我們是用0-1整數(shù)規(guī)劃來解決這類問題的。 在這里，我們同樣可以使用動態(tài)規(guī)劃的方法。而且相對簡單了很多。排序問題 一，問題的提出:設有n個工件要在機床A,B上加 工,每個工件都必須經(jīng)過先A后B的兩道加工工序, 以ai,bi分別表示工件i(1<=i<=n)在A,B上的加工 時間.問應如何在兩機床上安排工件加工的順序, 使在機床A上加工第一個工件開始到在機床B上 將最后一個工件加工完為止,所用的加工
7、時間最 少?二,模型及其解法min(ai,bj)<=min(aj,bi)這個條件就是工件i應該排在工件j之前,即對于從頭到尾的最優(yōu)排序而言,它的所有前后相鄰的兩個工件所組成的對都必須滿足以上不等式.根據(jù)這個條件,得到最優(yōu)排序的規(guī)則如下:(1)先工作的加工的加工時間的工時矩陣M=a1a2…..anb1b2…..bn設有5個工件需要在機床A,B上加工,加工的順序是先A后B,每個工件所需加工時間(單位:小時)如下表.問如何安排加工順序可使機床連續(xù)加工完所有的加工總時間最少?以一個例題來加以說明(2)在工時矩陣M中找到最小的元素(若最小的不止一
