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

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

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

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

1.2線性規(guī)劃問題的標準形式與典則形式

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最小樹權下界問題

4.7博弈問題

4.8最大權匹配問題

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

4.10計劃網(wǎng)絡圖的關鍵路線問題

4.11裝載問題

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

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

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

5.3增加新約束條件的分析

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

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

6.2運輸與販賣的對偶

6.3關鍵路徑與里程碑結點的對偶

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

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

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

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

7.3割平面法

7.4分枝定界法

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

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

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

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

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

參考文獻

后記2100433B

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

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

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

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

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

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

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

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

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

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

  這些問題已經(jīng)由斯蒂芬·斯梅爾在二十一世紀十八個尚未解決的最偉大的問題中應用。用斯梅爾的話來說，“第三個問題是線性規(guī)劃理論中最主要的尚未解決的問題”。然而，對于線性規(guī)劃問題存在弱多項式時間算法，比如橢球算法和內點算法，尚未發(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困難問題 。

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

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

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

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

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

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