網(wǎng)絡(luò)優(yōu)化

前言

　　最優(yōu)化是人們在工程技術(shù)、科學(xué)研究和經(jīng)濟管理等諸多領(lǐng)域中經(jīng)常遇到的問題.結(jié)構(gòu)設(shè)計要在滿足強度要求等條件下使所用材料的總重量最輕；資源分配要使各用戶利用有限資源產(chǎn)生的總效益最大；安排運輸方案要在滿足物質(zhì)需求和裝載條件下使運輸費用最低；編制生產(chǎn)計劃要按照產(chǎn)品工藝流程和顧客需求，盡量降低人力、設(shè)備、原材料等成本使總利潤最高.可以預(yù)測，隨著科學(xué)技術(shù)尤其是計算機技術(shù)的不斷發(fā)展，以及數(shù)學(xué)理論與方法向各學(xué)科和各應(yīng)用領(lǐng)域更廣泛、更深入的滲透，在21世紀這個信息時代，最優(yōu)化理論和技術(shù)必將在社會的諸多方面起著越來越大的作用.　　解決實際生活中優(yōu)化問題的手段大致有以下幾種：一是靠經(jīng)驗的積累，憑主觀作出判斷；二是做試驗選方案，比優(yōu)劣定決策；三是建立數(shù)學(xué)模型，求解最優(yōu)策略.雖然由于建模時要作適當(dāng)?shù)暮喕?，可能使結(jié)果不一定非常完善，但是它基于客觀數(shù)據(jù)，求解問題簡便、經(jīng)濟，而且規(guī)?？梢院艽螅▽頃絹碓酱螅?人們還可以吸收從經(jīng)驗得到的規(guī)則，用實驗不斷校正建立的模型.隨著數(shù)學(xué)方法和計算機技術(shù)的進步，用建模和數(shù)值模擬解決優(yōu)化問題這一手段，將會越來越顯示出它的效能和威力.顯然，在決策定量化、科學(xué)化的呼聲日益高漲的今天，數(shù)學(xué)建模方法的推廣應(yīng)用是符合時代潮流和形勢發(fā)展需要的.　　.　　最優(yōu)化理論、模型與方法所包含的內(nèi)容很多，國內(nèi)已出版了不少教材和專著介紹其各個分支.但是，一方面，近年來發(fā)展起來的、有著廣泛應(yīng)用背景的規(guī)劃模型（如隨機規(guī)劃、模糊規(guī)劃等），以及一些已經(jīng)為許多人采用、受到廣泛關(guān)注的優(yōu)化算法（如模擬退火算法、遺傳算法等）還缺乏詳細和系統(tǒng)的介紹；另一方面，一些偏重優(yōu)化理論和方法的教材，其要求難以與工科學(xué)生的數(shù)學(xué)知識銜接，也缺少對于應(yīng)用來說十分重要的建模過程和軟件介紹，而一些比較通俗的運籌學(xué)教材，則在加強理論基礎(chǔ)，適應(yīng)學(xué)生將來從事科研工作需要上考慮較少.這套教材試圖彌補以上兩方面的缺陷，力求體現(xiàn)下述特點：　　1.內(nèi)容既包含傳統(tǒng)的線性規(guī)劃與非線性規(guī)劃等部分，又納入有廣泛應(yīng)用前景的隨機規(guī)劃和模糊規(guī)劃；在傳統(tǒng)內(nèi)容中，既注重典型的數(shù)學(xué)思想和方法的系統(tǒng)敘述，又引入豐富的建模實例.　　2.數(shù)學(xué)基礎(chǔ)既與工科學(xué)生所學(xué)知識銜接，又考慮到研究生閱讀文獻、從事科研工作的需要，適當(dāng)提高理論基礎(chǔ)的起點.　　3.對一般教材介紹的諸多算法進行精選，配合介紹一些應(yīng)用軟件，并引入近年來迅速發(fā)展的若干新算法.

內(nèi)容概要

本書系統(tǒng)介紹了網(wǎng)絡(luò)優(yōu)化的基本模型和基本算法，包括構(gòu)造這些算法的基本思想以及相應(yīng)算法在計算機上的一些具體實現(xiàn)技巧和復(fù)雜性分析。　　全書由7章組成： 第1章為概論，第2章介紹關(guān)于算法的一些基本知識，第3章到第7章分別討論樹的問題、最短路問題、最大流問題、最小費用流問題和匹配問題.每章還安排了一些練習(xí)題?！　”緯勺鳛閿?shù)學(xué)、應(yīng)用數(shù)學(xué)、運籌學(xué)、管理科學(xué)、系統(tǒng)科學(xué)、信息科學(xué)、計算機科學(xué)與工程等專業(yè)的高年級大學(xué)生和研究生教材，也可供其他相關(guān)專業(yè)的學(xué)者和技術(shù)人員參考。

書籍目錄

序言前言第1章 概論　1.1 網(wǎng)絡(luò)優(yōu)化問題的例子　1.2 圖與網(wǎng)絡(luò)　1.3 圖與網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)　1.4 計算復(fù)雜性的概念　練習(xí)題第2章 算法基礎(chǔ)　2.1 NP，NPC和NP-hard概念　2.2 算法設(shè)計與分析　2.3 小結(jié)　練習(xí)題第3章 最小樹與最小樹形圖　3.1 樹的基本概念　3.2 最小樹算法　3.3 最小樹形圖　3.4 最大分枝　練習(xí)題第4章 最短路問題　4.1 最短路問題的數(shù)學(xué)描述　4.2 無圈網(wǎng)絡(luò)與正費用網(wǎng)絡(luò)：標號設(shè)定算法　4.3 一般費用網(wǎng)絡(luò)：標號修正算法　練習(xí)題第5章 最大流問題　5.1 最大流問題的數(shù)學(xué)描述　5.2 增廣路算法　5.3 最短增廣路算法　5.4 一般的預(yù)流推進算法　5.5 最高標號預(yù)流推進算法　5.6 單位容量網(wǎng)絡(luò)上的最大流算法　練習(xí)題第6章 最小費用流問題　6.1 最小費用流問題的數(shù)學(xué)描述　6.2 消圈算法與最小費用路算法　6.3 原始-對偶算法　6.4 瑕疵算法　6.5 松弛算法　6.6 網(wǎng)絡(luò)單純形算法　練習(xí)題第7章 匹配問題　7.1 匹配問題的數(shù)學(xué)描述　7.2 二部基數(shù)匹配問題　7.3 非二部基數(shù)匹配問題　7.4 二部賦權(quán)匹配問題　7.5 非二部賦權(quán)匹配問題　練習(xí)題索引及英文關(guān)鍵詞參考文獻

章節(jié)摘錄

　　第1章　概論　　我們生活在一個網(wǎng)絡(luò)社會中。從某種意義上說，現(xiàn)代社會是一個由計算機信息網(wǎng)絡(luò)、電話通信網(wǎng)絡(luò)、運輸服務(wù)網(wǎng)絡(luò)、能源和物質(zhì)分派網(wǎng)絡(luò)等各種網(wǎng)絡(luò)所組成的復(fù)雜的網(wǎng)絡(luò)系統(tǒng)。網(wǎng)絡(luò)優(yōu)化就是研究如何有效地計劃、管理和控制這個網(wǎng)絡(luò)系統(tǒng)，使之發(fā)揮最大的社會和經(jīng)濟效益?！　【W(wǎng)絡(luò)優(yōu)化是運籌學(xué)（Operations Research）中的一個經(jīng)典和重要的分支，所研究的問題涉及經(jīng)濟管理、工業(yè)工程、交通運輸、計算機科學(xué)與信息技術(shù)、通訊與網(wǎng)絡(luò)技術(shù)等諸多領(lǐng)域。本書中將要討論的最短路問題、最大流問題、最小費用流問題和匹配問題等都是網(wǎng)絡(luò)優(yōu)化的基本問題。　　本章主要介紹網(wǎng)絡(luò)優(yōu)化問題的一些實際例子以及圖與網(wǎng)絡(luò)的基本概念，初步介紹計算復(fù)雜性理論，為后續(xù)章節(jié)的學(xué)習(xí)奠定基礎(chǔ)。　　1.1　網(wǎng)絡(luò)優(yōu)化問題的例子　　我們首先通過一些例子來了解網(wǎng)絡(luò)優(yōu)化問題?！　±?.1　公路連接問題　　某地區(qū)有若干個主要城市，現(xiàn)準備修建高速公路把這些城市連接起來，使得從其中任何一個城市都可以經(jīng)高速公路直接或間接到達另一個城市。假定已經(jīng)知道了任意兩個城市之間修建高速公路的成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最??？

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    網(wǎng)絡(luò)優(yōu)化 PDF格式下載

---