二維裝箱問題的非線性優(yōu)化方法.pdf

1、本文從一個(gè)新的視角來(lái)研究一類二維裝箱問題-2SP(two-dimensionalstrippackingproblem)，旨在給出各種2SP問題的非線性優(yōu)化模型并設(shè)計(jì)求解方法.本文的最優(yōu)化模型的最優(yōu)性條件依據(jù)擬可微分析和變分分析建立，計(jì)算方法采用非線性Lagrange方法. 主要結(jié)果可概括如下： 1.第2章，對(duì)d(d是正整數(shù))維空間的裝箱問題進(jìn)行了討論.首先給出了d維空間一般形狀物品裝箱問題的數(shù)學(xué)模型，然后具體到d-維的

2、矩形體和球體的特殊情形.給出了矩形體圖元裝箱問題的一個(gè)不可微優(yōu)化模型，該模型是一擬可微優(yōu)化模型，用擬可微優(yōu)化的理論建立了該模型的一階最優(yōu)性條件.然后將其轉(zhuǎn)化為一個(gè)光滑的優(yōu)化模型，用變分分析中的最優(yōu)性理論建立了該光滑模型的最優(yōu)性必要條件.對(duì)球體圖元的裝箱問題直接給出光滑的優(yōu)化模型，依據(jù)變分分析的最優(yōu)性理論建立了最優(yōu)性必要條件. 2.第3章，主要研究各種二維裝箱問題(2SP)的非線性優(yōu)化模型.首先用兩種不同的方式為圖元為矩形的2SP

3、問題建立了數(shù)學(xué)模型.前一種方式基于兩個(gè)矩形位置關(guān)系的數(shù)學(xué)表述，給出了一個(gè)光滑優(yōu)化模型，依據(jù)非線性規(guī)劃的最優(yōu)性理論建立了該優(yōu)化問題的最優(yōu)性必要條件.后一種方式直接從兩個(gè)矩形不相交的條件出發(fā)給出了一個(gè)不可微模型并用擬可微理論建立了最優(yōu)性條件.然后，將不可微模型轉(zhuǎn)化為一個(gè)非線性規(guī)劃模型，用變分分析的最優(yōu)性理論建立了最優(yōu)性必要條件.將光滑模型與非線性規(guī)劃模型進(jìn)行了比較，后者優(yōu)于前者.此外，還分別對(duì)圓形、三角形、多邊形這些特殊形狀圖元的裝箱問題進(jìn)

4、行了研究.以凸集分離定理為基礎(chǔ)，依據(jù)多邊形的幾何特性給出了三角形和多邊形圖元裝箱問題的不可微模型，并用擬可微理論為這些模型建立了一階最優(yōu)性條件. 3.第4章，考慮的是求解二維裝箱問題的非線性優(yōu)化模型的數(shù)值算法.首先針對(duì)只含有不等式約束的非線性規(guī)劃問題提出了一個(gè)修正Lagrange函數(shù)，分析了該函數(shù)具有很好的性質(zhì).基于該修正Lagrange函數(shù)給出了一個(gè)對(duì)偶算法，即非線性Lagrange算法.對(duì)這一算法給出了精細(xì)的收斂性結(jié)果，證明

5、了存在罰參數(shù)的一個(gè)閾值，當(dāng)罰參數(shù)小于這個(gè)閾值時(shí)，算法收斂.此外，對(duì)修正Lagrange函數(shù)的Hesse陣的條件數(shù)進(jìn)行了估計(jì)，結(jié)果表明在實(shí)際計(jì)算時(shí)，罰參數(shù)不能取的太小.最后，將所提出的非線性Lagrange算法和經(jīng)典的增廣Lagrange算法分別用于求解圓形圖元和矩形圖元的二維裝箱問題并就幾個(gè)例題給出計(jì)算結(jié)果. 4.第5章，將二維裝箱問題的研究結(jié)果應(yīng)用于集裝箱碼頭關(guān)于貨船的泊位分配問題.將泊位分配問題描述為一個(gè)帶約束的二維裝箱問題