初等組合最優(yōu)化論（上冊）

(上冊)

前言摘要

上篇 基本理論

第1章 基本概念與初等方法 3

1.1 幾個(gè)組合**化問題 3

1.1.1 數(shù)的優(yōu)化問題 3

1.1.2 圖論型優(yōu)化問題 4

1.1.3 管理型優(yōu)化問題 6

1.2 組合**化的定義 6

1.2.1 定義 6 

1.2.2 論域、對象與提法 7

1.2.3 問題、實(shí)例與數(shù)字例 8

1.2.4 目標(biāo)函數(shù)與答案 9

1.2.5 算法與方法 10

1.3 正則實(shí)例 10 

1.3.1 定義 10

1.3.2 正則實(shí)例的一般表示形式 12 

1.4 特性集List PPP 13 

1.4.1 特性集的標(biāo)識符 13 

1.4.2 關(guān)于π(1)集的特性 13

1.4.3 關(guān)于π(2)集的特性 14

1.5 目標(biāo)函數(shù)與提法 14 

1.5.1 目標(biāo)函數(shù) 14

1.5.2 提法的分類 15

1.6 組合**化問題的代數(shù)分類 16 

1.7 兩個(gè)初等方法 18 

1.7.1 描述求解過程的幾種方法 18 

1.7.2 枚舉法 19

1.7.3 隱枚舉法 21

1.8 同解法 23

1.8.1 同解法概念 23

1.8.2 分支法 24

1.8.3 歸結(jié)法 25

1.9 連通性的判別子程序 26 

1.10 計(jì)算復(fù)雜性與多項(xiàng)式P 問題 28 

1.10.1 計(jì)算復(fù)雜性 28

1.10.2 多項(xiàng)式算法 30

1.11 幾點(diǎn)注記 30 

第2章 論域型與可行域型**化原理 33 

2.1 引言 33 

2.2 一般**化原理 35 

2.3 序集型優(yōu)化原理 36 

2.3.1 定理形式的原理 36 

2.3.2 公理形式的原理 37 

2.4 序集及其優(yōu)化原理 39

2.5 第1(論域型)**化原理 40 

2.5.1 原理的性質(zhì) 40

2.5.2 公理形式 41

2.6 基本性質(zhì) 42 

2.7 帶*與帶* 44

2.8 解帶*** 47

2.9 去劣法、擴(kuò)展法與遞推法 49 

2.10 生成法與分治法 51 

2.11 數(shù)字例及實(shí)例 53 

2.12 第2(可行域型)**化原理 55 

2.12.1 第2**化原理的公理形式 55

2.12.2 基本性質(zhì) 57

2.13 建立分支定界法的思路 57

2.14 求解實(shí)例的布局與要素 58

2.14.1 求解的布局 58

2.14.2 分支與賦序 59

2.14.3 松弛實(shí)例 60

2.15 分支定界法 62

2.15.1 基本分支定界法 62 

2.15.2 兩個(gè)分支定界法 62 

2.16 分支定界法的一般討論 64

2.17 關(guān)于原理的注記 65 

第3章 基本變換公式 67 

3.1 兩種描述可行集簇的方法 67

3.1.1 枚舉法 67

3.1.2 線性代數(shù)法 68

3.2 對可行集簇的幾點(diǎn)思考 71

3.2.1 可行域的幾種表示方法 71 

3.2.2 不同層次上的統(tǒng)一性 73 

3.2.3 對交錯路形式化的展望 75 

3.3 第三種描述方法——對稱差分解法 77 

3.3.1 兩個(gè)可行集的對稱差 77 

3.3.2 基本變換公式 78 

3.3.3 緊鄰可行集的圖形表示 79 

3.4 兩種基本圖形表示 79

3.5 可行集簇圖的基本性質(zhì) 81

3.5.1 簡單性與連通性 81 

3.5.2 均勻性 83

3.5.3 一致Hamilton性 84

3.5.4 拉格朗日有限增量公式 85 

3.6 值域的代數(shù)結(jié)構(gòu) 86 

3.6.1 極小準(zhǔn)域 86

3.6.2 極大準(zhǔn)域 88

3.6.3 強(qiáng)優(yōu)選準(zhǔn)域 89

3.7 獨(dú)立系統(tǒng)與擬陣 90 

3.7.1 基本概念 90

3.7.2 五個(gè)典型的擬陣 91 

3.7.3 K4的支撐樹簇圖 92 

3.8 擬陣的性質(zhì) 94 

3.9 幾何直觀的一點(diǎn)注記 97 

第4章 鄰域型與碎片型**化原理 99

4.1 求解連續(xù)型**化問題的微分法回顧 99

4.1.1 導(dǎo)數(shù)概念 99

4.1.2 幾點(diǎn)認(rèn)識 101 

4.2 緊鄰簇N(a)與改變度簇C(a)的分解 103 

4.3 第3(鄰域型)**化原理 104

4.3.1 原理的形式 104 

4.3.2 基本定理 106 

4.4 一般鄰點(diǎn)法 107

4.5 關(guān)于幾個(gè)子程序的事項(xiàng) 108

4.6 用鄰點(diǎn)法求解實(shí)例的基本方法 109

4.6.1 求解實(shí)例XYZ：S的方法 109

4.6.2 關(guān)于尋求初始可行解的Charnes子程序 112

4.7 求解提法1 的諸實(shí)例 114

4.7.1 求解實(shí)例XYZ-1：S的方法 114

4.7.2 求解實(shí)例XYZ-1j：S的方法 115

4.8 巡回商問題 116

4.8.1 巡回商問題的提出 116 

4.8.2 巡回商實(shí)例的近似算法 118 

4.9 第4(碎片型)**化原理 119

4.10 幾個(gè)具體對象的碎片型**化原理 120

4.10.1 路的優(yōu)化原理 120 

4.10.2 樹的優(yōu)化原理 121 

4.10.3 匹配優(yōu)化原理 121 

4.10.4 策略優(yōu)化原理 122 

第5章 極優(yōu)代數(shù)方法 124 

5.1 再論強(qiáng)優(yōu)選準(zhǔn)域 124 

5.1.1 問題的提出 124 

5.1.2 碎片值域的代數(shù)結(jié)構(gòu) 125 

5.1.3 碎片優(yōu)劣的比較 126 

5.1.4 強(qiáng)優(yōu)選性 127 

5.2 強(qiáng)優(yōu)選準(zhǔn)域的基本性質(zhì) 128

5.3 強(qiáng)優(yōu)選準(zhǔn)域的同構(gòu)性 130 

5.3.1 問題的提出 130 

5.3.2 同構(gòu)映射 130 

5.3.3 與極小準(zhǔn)域同構(gòu)的強(qiáng)優(yōu)選準(zhǔn)域 131

5.4 互為同構(gòu)的強(qiáng)優(yōu)選準(zhǔn)域 133

5.4.1 四個(gè)強(qiáng)優(yōu)選準(zhǔn)域 133 

5.4.2 同構(gòu)方法 135 

5.5 極優(yōu)代數(shù) 135 

5.6 應(yīng)用極優(yōu)代數(shù) 136 

5.6.1 引言 136

5.6.2 基本應(yīng)用模型 137 

5.6.3 例5.1過程的代數(shù)表示 139 

5.7 摹多項(xiàng)式及其應(yīng)用 139

5.7.1 摹多項(xiàng)式 139 

5.7.2 例5.2匹配優(yōu)化問題的數(shù)字例 140

5.7.3 例5.3溫課迎考問題的數(shù)字例 141

5.8 列車時(shí)刻表問題的數(shù)字例 143 

5.9 計(jì)數(shù)強(qiáng)優(yōu)選半環(huán) 145 

5.9.1 問題的提出 145 

5.9.2 計(jì)數(shù)強(qiáng)優(yōu)選半環(huán) 146 

5.10 一點(diǎn)注記 148 

第6章 組合**化問題的研究綱領(lǐng) 150 

6.1 基礎(chǔ)理論框架 150 

6.1.1 基本變換公式是一個(gè)核心概念 150

6.1.2 什么是基礎(chǔ)理論框架 152 

6.2 基本變換公式與某些數(shù)學(xué)分支的關(guān)系 153 

6.2.1 基本變換公式與導(dǎo)函數(shù)概念的同構(gòu)性 153 

6.2.2 離散型、連續(xù)型數(shù)學(xué)優(yōu)化問題的求解過程的并行性 154 

6.2.3 生物進(jìn)化論與求解優(yōu)化問題的同源性 155 

6.3 組合**化論的基本公理框架 157

6.4 拉卡托斯型的科學(xué)研究綱領(lǐng) 161 

6.4.1 學(xué)科發(fā)展的過程 161 

6.4.2 綱領(lǐng)的正文 162 

6.5 研究組合**化實(shí)例的綱領(lǐng) 163 

6.5.1 科學(xué)研究的綱領(lǐng) 163 

6.5.2 科學(xué)研究綱領(lǐng)的框圖 166 

6.6 對科學(xué)研究綱領(lǐng)的評價(jià) 166

6.7 兩點(diǎn)歷史資料 167 

6.7.1 克萊因傳略 167 

6.7.2 拉卡托斯傳略 168 

參考文獻(xiàn) 170 

(下冊)

中篇 代數(shù)對象型的優(yōu)化問題

第7章 集合型三個(gè)優(yōu)化問題

第8章 向量集型優(yōu)化問題

第9章 方陣集型全排列優(yōu)化問題

下篇 網(wǎng)絡(luò)對象型的優(yōu)化問題

第10章 樹的優(yōu)化問題

第11章 路的優(yōu)化問題

第12章 匹配優(yōu)化問題

全書結(jié)束語

參考文獻(xiàn)

名詞索引

附錄

附錄A 特性集

附錄B 方法與子程序集

附錄C 實(shí)例按提法分類

附錄D 問題按代數(shù)結(jié)構(gòu)分類1.6

附錄E 全書例題匯編