版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、本文主要研究?jī)纱箢?lèi)問(wèn)題:哈明距離下的逆優(yōu)化問(wèn)題和多物品的生產(chǎn)與分配問(wèn)題.對(duì)一個(gè)給定的(組合)優(yōu)化問(wèn)題,逆優(yōu)化問(wèn)題研究如何盡可能少地改變?cè)瓎?wèn)題中的權(quán)參數(shù),使得某些給定的解是問(wèn)題在新的權(quán)參數(shù)下的最優(yōu)解.由于該類(lèi)問(wèn)題不僅有很重要的理論研究?jī)r(jià)值,而且有很大的實(shí)際應(yīng)用價(jià)值,因此引起了許多學(xué)者的重視.許多文章研究了在l1,l∞和l2范數(shù)下的逆優(yōu)化問(wèn)題.盡管哈明距離下的逆優(yōu)化問(wèn)題在實(shí)際生活中有許多應(yīng)用,但很少有文章討論該類(lèi)問(wèn)題.本文我們研究哈明距離下
2、的逆優(yōu)化問(wèn)題. 由于物品的制造與分配問(wèn)題有很重要的理論研究與實(shí)際應(yīng)用價(jià)值,因此引起了許多學(xué)者的注意.該問(wèn)題可以描述為:有一些客戶,他們需要一定數(shù)量的產(chǎn)品,這些產(chǎn)品是通過(guò)一些工廠加工制造生產(chǎn)出來(lái)的,并通過(guò)一些分配中心運(yùn)送到每個(gè)客戶.如何安排原材料購(gòu)置、產(chǎn)品的生產(chǎn)與分配,使得總的費(fèi)用最小.本文我們也將研究多物品的制造與分配問(wèn)題. 在第二章,我們研究以下的求和型哈明距離下的賦權(quán)逆最小支撐樹(shù)問(wèn)題:對(duì)給定的一個(gè)連通無(wú)向圖G,每條邊
3、都有一個(gè)權(quán)和改造費(fèi)用.令T0為圖G的一個(gè)支撐樹(shù).如何改變圖的邊權(quán)向量使得T0為圖G在新的權(quán)向量下的一個(gè)最小支撐樹(shù),且在哈明距離下的總的改造費(fèi)用最小.我們討論了三種模型:無(wú)界情形,帶禁忌邊的無(wú)界情形和有界情形.應(yīng)用求二分圖的賦權(quán)頂點(diǎn)覆蓋方法以及求最小割的算法等求解所建立的數(shù)學(xué)模型,從而得出這三類(lèi)問(wèn)題都是強(qiáng)多項(xiàng)式時(shí)間可解的. 在第三章,我們研究如下的約束瓶頸型哈明距離下的逆最小支撐樹(shù)問(wèn)題:對(duì)給定的一個(gè)連通無(wú)向圖G,每條邊都有一個(gè)權(quán)和
4、改造費(fèi)用,T0為圖G的一個(gè)支撐樹(shù).如何改變圖的邊權(quán)向量使得:(1)T0為圖G在新的權(quán)向量下的一個(gè)最小支撐樹(shù),(2)在哈明距離下的總的改造費(fèi)用不超過(guò)給定的值,(3)改變的邊的改造費(fèi)用的最大值盡可能地小.我們討論了三種模型:無(wú)界情形,標(biāo)準(zhǔn)情形和約束情形.應(yīng)用二分圖的瓶頸型賦權(quán)頂點(diǎn)覆蓋方法及二分法等得出這三類(lèi)問(wèn)題都是強(qiáng)多項(xiàng)式時(shí)間可解的. 在第四章,我們首先討論了求和型哈明距離下的中心選址改造問(wèn)題,該問(wèn)題可以描述為:對(duì)給定的一個(gè)連通無(wú)向
5、圖G,每條邊都有一個(gè)長(zhǎng)度和改造費(fèi)用,如何改變圖的邊長(zhǎng)度向量使得在新的長(zhǎng)度向量下從給定的頂點(diǎn)s到網(wǎng)絡(luò)的其它頂點(diǎn)的距離不超過(guò)給定的上界,且在哈明距離下的總的改造費(fèi)用最小.我們利用把集覆蓋問(wèn)題的實(shí)例L-歸約到該問(wèn)題的實(shí)例,證明了對(duì)該問(wèn)題構(gòu)造一個(gè)近似性能比為O(log|V|)的近似算法是NP困難的.接著我們研究了如下的瓶頸型哈明距離下的中心選址改造問(wèn)題:如何改變圖的邊長(zhǎng)度向量使得在新的長(zhǎng)度向量下從給定的頂點(diǎn)s到網(wǎng)絡(luò)的其它頂點(diǎn)的距離不超過(guò)給定的上
6、界,且改變的邊的改造費(fèi)用的最大值盡可能地小.我們給出了該問(wèn)題的一個(gè)強(qiáng)多項(xiàng)式算法. 在第五章,我們研究了如下的求和型哈明距離下的最短路改造問(wèn)題:對(duì)給定的一個(gè)連通無(wú)向圖G,每條邊都有一個(gè)長(zhǎng)度和改造費(fèi)用,我們要求改變圖的邊長(zhǎng)度向量使得在新的長(zhǎng)度向量下從給定的頂點(diǎn)si到頂點(diǎn)ti(i=1,2,…,r)的距離不超過(guò)給定的上界di,且在哈明距離下的總的改造費(fèi)用最小.我們利用把3-SAT問(wèn)題的實(shí)例多項(xiàng)式時(shí)間歸約到該問(wèn)題的實(shí)例,證明了該問(wèn)題是強(qiáng)N
7、P困難的.對(duì)該問(wèn)題的一類(lèi)特殊問(wèn)題:鏈網(wǎng)絡(luò)下的單發(fā)點(diǎn)、單收點(diǎn)的求和型哈明距離下的最短路改造問(wèn)題,我們利用把背包問(wèn)題的實(shí)例多項(xiàng)式時(shí)間歸約到該問(wèn)題的實(shí)例,證明了該問(wèn)題是NP困難的.同時(shí)對(duì)該問(wèn)題給出了一個(gè)偽多項(xiàng)式時(shí)間的動(dòng)態(tài)規(guī)劃算法. 在第六章,我們研究了如下的多物品的生產(chǎn)與分配問(wèn)題:有多個(gè)客戶,他們需要不同的物品,這些物品是由工廠生產(chǎn)或通過(guò)物品供應(yīng)商直接提供并運(yùn)送到一些分配中心(DC),并統(tǒng)一由分配中心供給.如果某類(lèi)物品是由工廠生產(chǎn),則
8、該類(lèi)物品及某些物品是由原材料供應(yīng)商提供給該工廠的原材料按某種比例加工生產(chǎn)得到的.一個(gè)客戶由一個(gè)分配中心服務(wù).如何安排工廠的生產(chǎn),如何從物品(原材料)供應(yīng)商進(jìn)貨,哪些分配中心投入使用,如何決定分配中心服務(wù)客戶的方式以及如何安排運(yùn)貨等使得總的費(fèi)用最小.我們把該問(wèn)題轉(zhuǎn)化為混合整數(shù)規(guī)劃問(wèn)題,利用Benders分解方法給出了求解該問(wèn)題的算法.另外,我們還考慮了一類(lèi)廣義的多物品的生產(chǎn)與分配問(wèn)題. 在第七章,我們研究了如下的最小分配費(fèi)用流問(wèn)題
9、:有多個(gè)客戶,只有一個(gè)物品供應(yīng)商.每個(gè)客戶需要一定數(shù)量的物品,該物品是通過(guò)一些分配工廠或一些物品中間商提供給客戶.某客戶或中間商按一定的比例從某分配工廠得到的貨物.如何從物品供應(yīng)商處進(jìn)貨,如何安排運(yùn)貨等使得總的費(fèi)用(運(yùn)輸費(fèi)用,儲(chǔ)存費(fèi)用)最小.我們討論了該問(wèn)題的基本可行圖的性質(zhì)并給出了一個(gè)求解該問(wèn)題的原始基本可行解的算法.利用網(wǎng)絡(luò)單純型法,我們解決了該類(lèi)最小分配費(fèi)用流問(wèn)題.本章我們還研究了如何得到增廣網(wǎng)絡(luò)問(wèn)題的一個(gè)可行基. 最后,
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 賦權(quán)哈明距離下若干網(wǎng)絡(luò)逆問(wèn)題的研究.pdf
- 在l∞模和哈明距離下的樹(shù)上的逆1-中心問(wèn)題.pdf
- 在l∞模和哈明距離下的樹(shù)上的逆1中心問(wèn)題
- 多電網(wǎng)調(diào)峰負(fù)荷分配問(wèn)題的優(yōu)化算法研究.pdf
- 連續(xù)優(yōu)化逆問(wèn)題的理論與數(shù)值方法的研究.pdf
- 多ECAV協(xié)同干擾資源優(yōu)化分配問(wèn)題研究.pdf
- 不確定環(huán)境下的多周期采購(gòu)量分配問(wèn)題研究.pdf
- VMI模式下供應(yīng)商與制造商利益分配問(wèn)題.pdf
- 差異分批制造模式下的聯(lián)合調(diào)度問(wèn)題及優(yōu)化算法.pdf
- 安全投入的預(yù)測(cè)與優(yōu)化分配問(wèn)題的探討.pdf
- 云制造環(huán)境下虛擬制造單元調(diào)度優(yōu)化問(wèn)題研究.pdf
- 循環(huán)取料入庫(kù)道口分配問(wèn)題的建模與優(yōu)化.pdf
- 考慮價(jià)值因素的多物品多集散點(diǎn)車(chē)輛路徑問(wèn)題研究.pdf
- 多傳感器數(shù)據(jù)融合與線性逆問(wèn)題的多尺度求解方法.pdf
- 優(yōu)化算法在電磁逆散射問(wèn)題中的應(yīng)用.pdf
- 機(jī)場(chǎng)停機(jī)位分配優(yōu)化問(wèn)題的研究.pdf
- 供應(yīng)中斷風(fēng)險(xiǎn)下的訂單分配問(wèn)題研究--以E制造企業(yè)為例.pdf
- 多式聯(lián)運(yùn)網(wǎng)絡(luò)樞紐的定位-分配問(wèn)題.pdf
- 仿真優(yōu)化中資源分配問(wèn)題的研究.pdf
- 圖書(shū)購(gòu)置經(jīng)費(fèi)的優(yōu)化分配問(wèn)題的研究.pdf
評(píng)論
0/150
提交評(píng)論