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