線性規(guī)劃

前言

　　電子計(jì)算機(jī)的出現(xiàn)是20世紀(jì)的大事，它改變了我們這個(gè)世界的面貌?？梢院敛豢鋸埖卣f(shuō)，它的影響遍及所有角落，幾乎無(wú)處不感覺(jué)到它的存在。數(shù)學(xué)更不例外。嚴(yán)格地說(shuō)，電子計(jì)算機(jī)本身就是近代數(shù)學(xué)的輝煌成就。將計(jì)算機(jī)與數(shù)學(xué)割裂開來(lái)，既不合理也不可能。組合學(xué)也就是在計(jì)算機(jī)科學(xué)蓬勃發(fā)展的刺激下而崛起的，從而成為近若干年來(lái)最活躍的數(shù)學(xué)分支。它研究的問(wèn)題有的可追溯到Euler和Hamiltan等18世紀(jì)的數(shù)學(xué)家，但它成為新的分支還是近若干年的事。它從與計(jì)算機(jī)科學(xué)相結(jié)合中獲得了廣闊的發(fā)展空間，從而也為計(jì)算機(jī)科學(xué)奠定了理論基礎(chǔ)?！　∈裁词怯?jì)算機(jī)科學(xué)呢？有的學(xué)者將它定義為研究算法的一門學(xué)科。研究算法無(wú)疑是計(jì)算機(jī)科學(xué)的重要領(lǐng)域，也是本叢書的核心內(nèi)容，貫穿始終。組合學(xué)家在20世紀(jì)70年代初建立的算法復(fù)雜性“NP理論”，至今仍然令無(wú)數(shù)計(jì)算機(jī)科學(xué)工作者與數(shù)學(xué)工作者為之折腰?！　∮?jì)算機(jī)科學(xué)里的組合學(xué)內(nèi)容十分廣泛。本叢書涉及組合分析、圖論、組合算法、近代密碼學(xué)、組合優(yōu)化、編碼理論及算法復(fù)雜性等7部分。　　組合分析是算法的理論基礎(chǔ)。組合分析之與組合算法猶如數(shù)學(xué)分析之與計(jì)算數(shù)學(xué)，眾所周知，前者是后者的理論根基?！　D論原本是組合數(shù)學(xué)這個(gè)“家族”的主要成員，只因它已成長(zhǎng)壯大，故自立門戶獨(dú)立出去?！　∷惴◤?fù)雜性的NP理論是近三十年的一大成就。研究表明對(duì)于一類叫做NPC類的困難問(wèn)題，至今都沒(méi)找到有效算法，但它們難度相當(dāng)，只要其中任何一個(gè)找到多項(xiàng)式解法，則全體都獲得解決；或證明它們根本不存在有效辦法。不論是前者還是后者都還看不見(jiàn)露到海平面上的桅桿塔，它吸引了眾多的有志之士。密碼學(xué)是其中十分引人人勝的分支。如若設(shè)計(jì)好的密碼，對(duì)它的破譯等價(jià)于某一NPC類困難問(wèn)題，無(wú)疑這樣的密碼將是牢不可破的?！　≡谟?jì)算機(jī)網(wǎng)絡(luò)深入普及的信息時(shí)代，信息本身就是時(shí)間，就是財(cái)富。信息的傳輸通過(guò)的是脆弱的公共信道，信息儲(chǔ)存于“不設(shè)防”的計(jì)算機(jī)系統(tǒng)中，如何保護(hù)信息的安全使之不被竊取及不至于被篡改或破壞，已成為當(dāng)今被普遍關(guān)注的重大問(wèn)題。密碼是有效而且可行的辦法。在計(jì)算機(jī)網(wǎng)絡(luò)的刺激下，近代密碼學(xué)便在算法復(fù)雜性理論的基礎(chǔ)上建立起來(lái)了。密碼作為一種技術(shù)，自從人類有了戰(zhàn)爭(zhēng)，不久便有了它。但作為一門學(xué)科則是近二十多年的事。甚至于它已成為其他學(xué)科的基礎(chǔ)。密碼也從此走出“軍營(yíng)”，進(jìn)入百姓家。

內(nèi)容概要

　　全書共9章，分單純形法和幾個(gè)專題兩部分?！　〉谝徊糠謫渭冃畏ǎ〝?shù)學(xué)模型、單純形法、改善的單純形法、單純形法的補(bǔ)充、對(duì)偶原理與對(duì)偶單純形共5章。第二部分幾個(gè)專題，包括運(yùn)輸問(wèn)題及其他、內(nèi)點(diǎn)法簡(jiǎn)介、目標(biāo)規(guī)劃、整數(shù)規(guī)劃共4章。　　第一部分是基本內(nèi)容；第二部分供各取所需選擇內(nèi)容，概括了線性規(guī)劃的各個(gè)方面，算例豐富是其特點(diǎn)。本書可作為計(jì)算機(jī)系、數(shù)學(xué)系、經(jīng)濟(jì)管理學(xué)院本科生及研究生的教材。

書籍目錄

第一部分 單純形法第1章 數(shù)學(xué)模型31.1 引言31.2 問(wèn)題的提出41.3 標(biāo)準(zhǔn)形式與矩陣表示81.4 幾何解釋9習(xí)題一12第2章 單純形法152.1 凸集152.1.1 凸集概念152.1.2 可行解域與極方向概念162.2 凸多面體172.3 松弛變量182.3.1 松弛變量概念182.3.2 松弛變量的幾何意義192.4 單純形法的理論基礎(chǔ)212.4.1 極值點(diǎn)的特性212.4.2 矩陣求逆222.4.3 可行解域無(wú)界的情況232.4.4 退化型舉例252.5 單純形法基礎(chǔ)262.5.1 基本公式262.5.2 退出基的確定與進(jìn)入基的選擇272.5.3 舉例292.6 單純形法（續(xù)）312.6.1 基本定理312.6.2 退化型概念322.6.3 單純形法步驟332.6.4 舉例342.7 單純形表格40習(xí)題二49第3章 改善的單純形法523.1 數(shù)學(xué)準(zhǔn)備523.2 改善的單純形法543.2.1 改善的單純形法的步驟543.2.2 舉例553.3 改善的單純形法表格603.3.1 表格的介紹603.3.2 復(fù)雜性分析63習(xí)題三64第4章 單純形法的補(bǔ)充664.1 二階段法664.2 大M法744.3 變量有上下界約束問(wèn)題794.3.1 下界不為零的情況794.3.2 有上界的約束794.4 退化情形874.4.1 退化形問(wèn)題874.4.2 出現(xiàn)循環(huán)舉例與防止循環(huán)的Bland準(zhǔn)則884.5 靈敏度分析904.5.1 C有變化914.5.2 右端項(xiàng)改變934.5.3 aij改變944.5.4 A的列向量改變954.5.5 A的行向量改變964.5.6 增加新變量984.5.7 增加新約束條件994.5.8 應(yīng)用舉例1014.5.9 參數(shù)規(guī)劃1024.6 分解原理1044.6.1 分解算法1054.6.2 說(shuō)明舉例1064.7 無(wú)界域問(wèn)題的分解算法1164.7.1 分解原理1164.7.2 說(shuō)明舉例116習(xí)題四121第5章 對(duì)偶原理與對(duì)偶單純形法1265.1 對(duì)偶問(wèn)題1265.1.1 對(duì)偶問(wèn)題定義1265.1.2 對(duì)偶問(wèn)題的意義1275.1.3 互為對(duì)偶1285.1.4 Ax=b的情形1295.1.5 其他類型1305.2 對(duì)偶性質(zhì)1325.2.1 弱對(duì)偶性質(zhì)1325.2.2 強(qiáng)對(duì)偶性質(zhì)1335.2.3 min問(wèn)題的對(duì)偶解法1335.3 影子價(jià)格1385.4 對(duì)偶單純形法1405.4.1 基本公式1405.4.2 對(duì)偶單純形法1415.4.3 舉例1425.5 原偶單純形法1465.5.1 問(wèn)題的引入1465.5.2 原偶單純形法之一1475.5.3 原偶單純形法之二..1 48習(xí)題五149第二部分 幾個(gè)專題*第6章 運(yùn)輸問(wèn)題及其他1556.1 運(yùn)輸問(wèn)題的數(shù)學(xué)模型1556.1.1 問(wèn)題的提出1556.1.2 運(yùn)輸問(wèn)題的特殊性1566.2 矩陣A的性質(zhì)1576.3 運(yùn)輸問(wèn)題的求解過(guò)程1586.3.1 求初始可行解的西北角法1586.3.2 最小元素法1606.3.3 圖上作業(yè)法1616.4 ci-zi的計(jì)算，進(jìn)入基的確定1626.5 退出基的確定1636.6 舉例1656.7 任務(wù)安排問(wèn)題1716.7.1 任務(wù)安排與運(yùn)輸問(wèn)題1716.7.2 求解舉例1726.8 任務(wù)安排的匈牙利算法1746.8.1 代價(jià)矩陣1746.8.2 Konig定理1766.8.3 標(biāo)志數(shù)法1766.8.4 匈牙利算法1796.8.5 匹配算法1836.9 任務(wù)安排的分支定界法1846.1 0一般的任務(wù)安排問(wèn)題1866.1 1運(yùn)輸網(wǎng)絡(luò)1896.1 1.1 網(wǎng)絡(luò)流1896.1 1.2 割切1906.1 1.3 Ford-Fulkerson定理1916.1 1.4 標(biāo)號(hào)法1936.1 1.5 Edmonds-Karp修正算法1946.1 1.6 Dinic算法196習(xí)題六198第7章 內(nèi)點(diǎn)法簡(jiǎn)介2007.1 Klee與Minty舉例2007.2 數(shù)學(xué)準(zhǔn)備2027.2.1 Lagrange乘數(shù)法2027.2.2 Kuhn-Tucker條件2037.2.3 垂直投影矩陣2047.2.4 最速下降法2057.2.5 牛頓法介紹2057.2.6 罰函數(shù)概念2067.2.7 中心路徑2077.3 路徑跟蹤法2077.3.1 原偶對(duì)稱型2077.3.2 KKT方程組及牛頓法2097.3.3 μ的確定，步長(zhǎng)的確定2107.3.4 初始值和結(jié)束準(zhǔn)則2117.3.5 算法步驟2117.3.6 收斂性的討論2127.3.7 KKT方程組的重要?dú)w約2147.4 梯度法與仿射變換215第8章 目標(biāo)規(guī)劃2188.1 問(wèn)題的提出2188.2 目標(biāo)規(guī)劃的幾何解釋2218.3 目標(biāo)規(guī)劃的單純形表格2268.4 目標(biāo)序列化方法2298.5 目標(biāo)規(guī)劃的靈敏度分析2348.6 應(yīng)用舉例245習(xí)題八248第9章 整數(shù)規(guī)劃2529.1 問(wèn)題的提出2529.2 整數(shù)規(guī)劃的幾何意義2569.3 0-1規(guī)劃和DFS搜索法2589.3.1 窮舉法2589.3.2 DFS搜索法2599.4 0-1規(guī)劃的DFS搜索法2629.4.1 搜索策略2629.4.2 舉例264*9.5 替代約束2679.5.1 Geoffrion替代約束2679.5.2 舉例2699.6 分支定界法2759.6.1 對(duì)稱型流動(dòng)推銷員問(wèn)題2759.6.2 非對(duì)稱型流動(dòng)推銷員問(wèn)題2769.7 整數(shù)規(guī)劃的分支定界解法2789.8 分支定界法在解混合規(guī)劃上的應(yīng)用2889.9 背包問(wèn)題的分支定界解法2929.10 整數(shù)規(guī)劃的割平面法2979.10.1 Gomory割平面方程2979.10.2 舉例2989.11 割平面的選擇3049.12　Martin割平面法3079.13 全整數(shù)割平面法3129.13.1 全整數(shù)單純形表格3129.13.2 舉例3149.14 混合規(guī)劃的割平面法319習(xí)題九321

圖書封面

評(píng)論、評(píng)分、閱讀與下載

---

    線性規(guī)劃 PDF格式下載

---