哈明距離下的逆優(yōu)化問題及多物品的制造與分配問題.pdf

1、本文主要研究兩大類問題：哈明距離下的逆優(yōu)化問題和多物品的生產(chǎn)與分配問題.對(duì)一個(gè)給定的(組合)優(yōu)化問題，逆優(yōu)化問題研究如何盡可能少地改變?cè)瓎栴}中的權(quán)參數(shù)，使得某些給定的解是問題在新的權(quán)參數(shù)下的最優(yōu)解.由于該類問題不僅有很重要的理論研究價(jià)值，而且有很大的實(shí)際應(yīng)用價(jià)值，因此引起了許多學(xué)者的重視.許多文章研究了在l1，l∞和l2范數(shù)下的逆優(yōu)化問題.盡管哈明距離下的逆優(yōu)化問題在實(shí)際生活中有許多應(yīng)用，但很少有文章討論該類問題.本文我們研究哈明距離下

2、的逆優(yōu)化問題. 由于物品的制造與分配問題有很重要的理論研究與實(shí)際應(yīng)用價(jià)值，因此引起了許多學(xué)者的注意.該問題可以描述為：有一些客戶，他們需要一定數(shù)量的產(chǎn)品，這些產(chǎn)品是通過一些工廠加工制造生產(chǎn)出來的，并通過一些分配中心運(yùn)送到每個(gè)客戶.如何安排原材料購置、產(chǎn)品的生產(chǎn)與分配，使得總的費(fèi)用最小.本文我們也將研究多物品的制造與分配問題. 在第二章，我們研究以下的求和型哈明距離下的賦權(quán)逆最小支撐樹問題：對(duì)給定的一個(gè)連通無向圖G，每條邊

3、都有一個(gè)權(quán)和改造費(fèi)用.令T0為圖G的一個(gè)支撐樹.如何改變圖的邊權(quán)向量使得T0為圖G在新的權(quán)向量下的一個(gè)最小支撐樹，且在哈明距離下的總的改造費(fèi)用最小.我們討論了三種模型：無界情形，帶禁忌邊的無界情形和有界情形.應(yīng)用求二分圖的賦權(quán)頂點(diǎn)覆蓋方法以及求最小割的算法等求解所建立的數(shù)學(xué)模型，從而得出這三類問題都是強(qiáng)多項(xiàng)式時(shí)間可解的. 在第三章，我們研究如下的約束瓶頸型哈明距離下的逆最小支撐樹問題：對(duì)給定的一個(gè)連通無向圖G，每條邊都有一個(gè)權(quán)和

4、改造費(fèi)用，T0為圖G的一個(gè)支撐樹.如何改變圖的邊權(quán)向量使得：(1)T0為圖G在新的權(quán)向量下的一個(gè)最小支撐樹，(2)在哈明距離下的總的改造費(fèi)用不超過給定的值，(3)改變的邊的改造費(fèi)用的最大值盡可能地小.我們討論了三種模型：無界情形，標(biāo)準(zhǔn)情形和約束情形.應(yīng)用二分圖的瓶頸型賦權(quán)頂點(diǎn)覆蓋方法及二分法等得出這三類問題都是強(qiáng)多項(xiàng)式時(shí)間可解的. 在第四章，我們首先討論了求和型哈明距離下的中心選址改造問題，該問題可以描述為：對(duì)給定的一個(gè)連通無向

5、圖G，每條邊都有一個(gè)長度和改造費(fèi)用，如何改變圖的邊長度向量使得在新的長度向量下從給定的頂點(diǎn)s到網(wǎng)絡(luò)的其它頂點(diǎn)的距離不超過給定的上界，且在哈明距離下的總的改造費(fèi)用最小.我們利用把集覆蓋問題的實(shí)例L-歸約到該問題的實(shí)例，證明了對(duì)該問題構(gòu)造一個(gè)近似性能比為O(log｜V｜)的近似算法是NP困難的.接著我們研究了如下的瓶頸型哈明距離下的中心選址改造問題：如何改變圖的邊長度向量使得在新的長度向量下從給定的頂點(diǎn)s到網(wǎng)絡(luò)的其它頂點(diǎn)的距離不超過給定的上

6、界，且改變的邊的改造費(fèi)用的最大值盡可能地小.我們給出了該問題的一個(gè)強(qiáng)多項(xiàng)式算法. 在第五章，我們研究了如下的求和型哈明距離下的最短路改造問題：對(duì)給定的一個(gè)連通無向圖G，每條邊都有一個(gè)長度和改造費(fèi)用，我們要求改變圖的邊長度向量使得在新的長度向量下從給定的頂點(diǎn)si到頂點(diǎn)ti(i=1，2，…，r)的距離不超過給定的上界di，且在哈明距離下的總的改造費(fèi)用最小.我們利用把3-SAT問題的實(shí)例多項(xiàng)式時(shí)間歸約到該問題的實(shí)例，證明了該問題是強(qiáng)N

7、P困難的.對(duì)該問題的一類特殊問題：鏈網(wǎng)絡(luò)下的單發(fā)點(diǎn)、單收點(diǎn)的求和型哈明距離下的最短路改造問題，我們利用把背包問題的實(shí)例多項(xiàng)式時(shí)間歸約到該問題的實(shí)例，證明了該問題是NP困難的.同時(shí)對(duì)該問題給出了一個(gè)偽多項(xiàng)式時(shí)間的動(dòng)態(tài)規(guī)劃算法. 在第六章，我們研究了如下的多物品的生產(chǎn)與分配問題：有多個(gè)客戶，他們需要不同的物品，這些物品是由工廠生產(chǎn)或通過物品供應(yīng)商直接提供并運(yùn)送到一些分配中心(DC)，并統(tǒng)一由分配中心供給.如果某類物品是由工廠生產(chǎn)，則

8、該類物品及某些物品是由原材料供應(yīng)商提供給該工廠的原材料按某種比例加工生產(chǎn)得到的.一個(gè)客戶由一個(gè)分配中心服務(wù).如何安排工廠的生產(chǎn)，如何從物品(原材料)供應(yīng)商進(jìn)貨，哪些分配中心投入使用，如何決定分配中心服務(wù)客戶的方式以及如何安排運(yùn)貨等使得總的費(fèi)用最小.我們把該問題轉(zhuǎn)化為混合整數(shù)規(guī)劃問題，利用Benders分解方法給出了求解該問題的算法.另外，我們還考慮了一類廣義的多物品的生產(chǎn)與分配問題. 在第七章，我們研究了如下的最小分配費(fèi)用流問題

9、：有多個(gè)客戶，只有一個(gè)物品供應(yīng)商.每個(gè)客戶需要一定數(shù)量的物品，該物品是通過一些分配工廠或一些物品中間商提供給客戶.某客戶或中間商按一定的比例從某分配工廠得到的貨物.如何從物品供應(yīng)商處進(jìn)貨，如何安排運(yùn)貨等使得總的費(fèi)用(運(yùn)輸費(fèi)用，儲(chǔ)存費(fèi)用)最小.我們討論了該問題的基本可行圖的性質(zhì)并給出了一個(gè)求解該問題的原始基本可行解的算法.利用網(wǎng)絡(luò)單純型法，我們解決了該類最小分配費(fèi)用流問題.本章我們還研究了如何得到增廣網(wǎng)絡(luò)問題的一個(gè)可行基. 最后，