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

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

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

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

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

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

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

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

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

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