線性規(guī)劃問題的統(tǒng)一建模與快速算法

第1章線性規(guī)劃問題的數(shù)學(xué)模型

1.1線性規(guī)劃問題的提出

1.2線性規(guī)劃問題的標(biāo)準(zhǔn)形式與典則形式

1.3線性規(guī)劃問題的解

1.4線性規(guī)劃問題的對偶理論

第2章求解線性規(guī)劃問題的一般方法

2.1枚舉法

2.2兩個變量線性規(guī)劃問題的圖解法

2.3單純形法

2.4對偶單純形法

2.5有界變量的線性規(guī)劃問題求解方法

2.6其他方法

第3章定界對偶算法

3.1定界對偶算法的提出

3.2定界對偶算法的迭代方法描述

3.3定界對偶算法的正確性證明

3.4定界對偶算法求解示例

第4章特殊線性規(guī)劃問題的定界對偶算法

4.1運輸問題

4.2分派問題

4.3有向圖的最短路問題

4.4最大流問題

4.5最小費用流問題

4.6最小樹權(quán)下界問題

4.7博弈問題

4.8最大權(quán)匹配問題

4.9最大基數(shù)匹配問題

4.10計劃網(wǎng)絡(luò)圖的關(guān)鍵路線問題

4.11裝載問題

第5章定界對偶算法的靈敏度分析

5.1目標(biāo)函數(shù)中常數(shù)c發(fā)生變化

5.2變量的上、下界u，v發(fā)生變化

5.3增加新約束條件的分析

第6章經(jīng)典的線性規(guī)劃對偶問題

6.1原材料與產(chǎn)品的對偶

6.2運輸與販賣的對偶

6.3關(guān)鍵路徑與里程碑結(jié)點的對偶

6.4二人零和博弈的局中人策略的對偶

第7章整數(shù)規(guī)劃問題

7.1整數(shù)規(guī)劃問題的提出

7.2化為0—1型整數(shù)規(guī)劃求解

7.3割平面法

7.4分枝定界法

第8章多目標(biāo)規(guī)劃問題

8.1多目標(biāo)規(guī)劃問題的提出

8.2目標(biāo)規(guī)劃的圖解法

8.3目標(biāo)規(guī)劃的定界對偶算法求解示例

8.4多目標(biāo)規(guī)劃化為單目標(biāo)規(guī)劃求解

參考文獻

后記2100433B

《線性規(guī)劃問題的統(tǒng)一建模與快速算法》可作為運籌學(xué)、管理學(xué)、系統(tǒng)工程等專業(yè)的線性規(guī)劃課程研究生教材，也可供有關(guān)專業(yè)的院校教師、研究生和大學(xué)高年級學(xué)生以及從事經(jīng)濟管理研究的相關(guān)人員作為參考用書。

單純形算法利用多面體的頂點構(gòu)造一個可能的解，然后沿著多面體的邊走到目標(biāo)函數(shù)值更高的另一個頂點，直至到達最優(yōu)解為止。雖然這個算法在實際上很有效率，在小心處理可能出現(xiàn)的“循環(huán)”的情況下，可以保證找到最優(yōu)解，但它的最壞情況可以很壞：可以構(gòu)筑一個線性規(guī)劃問題，單純形算法需要問題大小的指數(shù)倍的運行時間才能將之解出。事實上，有一段時期內(nèi)人們曾不能確定線性規(guī)劃問題是NP完全問題還是可以在多項式時間里解出的問題。

第一個在最壞情況具有多項式時間復(fù)雜度的線性規(guī)劃算法在1979年由前蘇聯(lián)數(shù)學(xué)家Leonid Khachiyan提出。這個算法建基于非線性規(guī)劃中Naum Shor發(fā)明的橢球法 (ellip-soid method)，該法又是Arkadi Nemirovski（2003年馮?諾伊曼運籌學(xué)理論獎得主）和 D. Yudin的凸集最優(yōu)化橢球法的一般化。

理論上，“橢球法”在最惡劣的情況下所需要的計算量要比“單形法”增長的緩慢，有希望用之解決超大型線性規(guī)劃問題。但在實際應(yīng)用上，Khachiyan的算法令人失望：一般來說，單純形算法比它更有效率。它的重要性在于鼓勵了對內(nèi)點算法的研究。內(nèi)點算法是針對單形法的“邊界趨近”觀念而改采“內(nèi)部逼近”的路線，相對于只沿著可行域的邊沿進行移動的單純形算法，內(nèi)點算法能夠在可行域內(nèi)移動。

1984年，貝爾實驗室印度裔數(shù)學(xué)家卡馬卡（Narendra Karmarkar）提出了投影尺度法（又名Karmarkar's algorithm）。這是第一個在理論上和實際上都表現(xiàn)良好的算法：它的最壞情況僅為多項式時間，且在實際問題中它比單純形算法有顯著的效率提升。自此之后，很多內(nèi)點算法被提出來并進行分析。一個常見的內(nèi)點算法為Mehrotra predictor-corrector method。盡管在理論上對它所知甚少，在實際應(yīng)用中它卻表現(xiàn)出色。

單形法沿著邊界由一個頂點移動到“相鄰”的頂點，內(nèi)點算法每一步的移動考量較周詳，“跨過可行解集合的內(nèi)部”去逼近最佳解。當(dāng)今的觀點是：對于線性規(guī)劃的日常應(yīng)用問題而言，如果算法的實現(xiàn)良好，基于單純形法和內(nèi)點法的算法之間的效率沒有太大差別，只有在超大型線性規(guī)劃中，頂點幾成天文數(shù)字，內(nèi)點法有機會領(lǐng)先單形法。

線性規(guī)劃的求解程式在各種各樣的工業(yè)最優(yōu)化問題里被廣泛使用，例如運輸網(wǎng)絡(luò)的流量的最優(yōu)化問題，其中很多都可以不太困難地被轉(zhuǎn)換成線性規(guī)劃問題。

線性規(guī)劃理論中存在幾個尚未解決的問題，這些開放問題的答案將會是數(shù)學(xué)運算中的根本突破，并且很可能是我們解決大規(guī)模線性規(guī)劃問題的主要進展。

• LP存在強多項式時間算法嗎？

• LP存在多項式時間算法以得到一個嚴(yán)格互補解嗎"list-dot list-dot-paddingleft">

  LP在實數(shù)（單位成本）模型下存在多項式時間算法嗎"para" label-module="para">

  這些問題已經(jīng)由斯蒂芬·斯梅爾在二十一世紀(jì)十八個尚未解決的最偉大的問題中應(yīng)用。用斯梅爾的話來說，“第三個問題是線性規(guī)劃理論中最主要的尚未解決的問題”。然而，對于線性規(guī)劃問題存在弱多項式時間算法，比如橢球算法和內(nèi)點算法，尚未發(fā)現(xiàn)限制在約束條件個數(shù)和變量個數(shù)的強多項式時間算法，此算法的發(fā)展將會帶來理論上重大意義，或者是解決大規(guī)模線性規(guī)劃上的實際收益。

  線性規(guī)劃問題整數(shù)規(guī)劃

  要求所有的未知量都為整數(shù)的線性規(guī)劃問題叫做整數(shù)規(guī)劃（integer programming, IP）或整數(shù)線性規(guī)劃（integer linear programming, ILP）問題。相對于即使在最壞情況下也能有效率地解出的線性規(guī)劃問題，整數(shù)規(guī)劃問題的最壞情況是不確定的，在某些實際情況中（有約束變量的那些）為NP困難問題。

  0-1整數(shù)規(guī)劃是整數(shù)規(guī)劃的特殊情況，所有的變量都要是0或1（而非任意整數(shù)）。這類問題亦被分類為NP困難問題 。

  只要求當(dāng)中某幾個未知數(shù)為整數(shù)的線性規(guī)劃問題叫做混合整數(shù)規(guī)劃（mixed integer programming, MIP）問題。這類問題通常亦被分類為NP困難問題。

  存在著幾類IP和MIP的子問題，它們可以被有效率地解出，最值得注意的一類是具有完全單位模約束矩陣，和約束條件的右邊全為整數(shù)的一類。

  一個解決大型整數(shù)線性規(guī)劃問題的先進算法為delayed column generation。2100433B

《UML統(tǒng)一建模教程與實驗指導(dǎo)》是一本關(guān)于UML統(tǒng)一建模的實用教程，深入淺出、循序漸進地介紹了軟件建模的概念、規(guī)范和方法?！禪ML統(tǒng)一建模教程與實驗指導(dǎo)》共有3大部分，第一部分是理論篇，著重于介紹面向?qū)ο?、UML建模語言的一些基本理論，詳盡介紹了UML中類圖、對象圖、用例圖、包圖、序列圖、協(xié)作圖、活動圖、狀態(tài)圖、構(gòu)件圖和部署圖的概念；第二部分是繪圖篇，著重于介紹如何使用Rational Rose建模工具來創(chuàng)建理論篇中的各種視圖和圖；第三部分是實戰(zhàn)案例篇，通過一個綜合實例對使用Rational Rose進行UML建模的全過程進行了詳解的分析。此外，各章后配有適量的練習(xí)題和上機題，以加深讀者的理解。

設(shè)施選址問題是經(jīng)典的NP-難解問題之一，在運籌學(xué)、計算機科學(xué)和管理科學(xué)中有著廣泛的應(yīng)用。徐大川等編著的《設(shè)施選址問題的近似算法》介紹了設(shè)施選址問題及其變形的近似算法。主要內(nèi)容包括：無容量限制的設(shè)施選址問題的線性規(guī)劃舍入算法、無容量限制的設(shè)施選址問題的原始對偶算法、無容量限制的設(shè)施選址問題的局部搜索算法、有容量限制的設(shè)施選址問題、k層設(shè)施選址問題、凹設(shè)施選址問題、不確定設(shè)施選址問題、設(shè)施選址問題的其他變形等。

《設(shè)施選址問題的近似算法》可作為運籌學(xué)、計算機科學(xué)、管理科學(xué)和應(yīng)用數(shù)學(xué)專業(yè)的高年級本科生和研究生的教材和參考書，亦可供相關(guān)研究領(lǐng)域科研人員參考。