第1章 緒 論…………………………………………………………………………1 1.1 運(yùn)籌學(xué)發(fā)展概述…………………………………………………………………… 1 1.1.1 運(yùn)籌學(xué)發(fā)展簡(jiǎn)史………………………………………………………………… 1 1.1.2 運(yùn)籌學(xué)學(xué)科的發(fā)展……………………………………………………………… 2 1.1.3 中國(guó)運(yùn)籌學(xué)會(huì)(ORSC)簡(jiǎn)介………………………………………………… 2 1.1.4 現(xiàn)代運(yùn)籌學(xué)在我國(guó)的一些應(yīng)用………………………………………………… 4 1.1.5 運(yùn)籌學(xué)的性質(zhì)及特點(diǎn)…………………………………………………………… 5 1.2 運(yùn)籌學(xué)研究的內(nèi)容………………………………………………………………… 6 1.2.1 運(yùn)籌學(xué)的主要內(nèi)容……………………………………………………………… 6 1.2.2 運(yùn)籌學(xué)研究問(wèn)題的步驟………………………………………………………… 8 1.3 運(yùn)籌學(xué)應(yīng)用中應(yīng)注意的問(wèn)題…………………………………………………… 9 思考與練習(xí)………………………………………………………………………………… 9 第2章 線(xiàn)性規(guī)劃與單純形法……………………………………………………………… 10 2.1 線(xiàn)性規(guī)劃問(wèn)題的提出…………………………………………………………… 10 2.1.1 生產(chǎn)計(jì)劃問(wèn)題………………………………………………………………… 11 2.1.2 套裁問(wèn)題……………………………………………………………………… 12 2.1.3 人力資源安排問(wèn)題…………………………………………………………… 13 2.1.4 配料問(wèn)題……………………………………………………………………… 15 2.1.5 投資問(wèn)題……………………………………………………………………… 16 2.2 線(xiàn)性規(guī)劃的圖解法……………………………………………………………… 17 2.2.1 圖解法的基本步驟…………………………………………………………… 17 2.2.2 解的幾種可能結(jié)果…………………………………………………………… 18 2.3 線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)型……………………………………………………………… 19 2.3.1 線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式…………………………………………………… 19 2.3.2 非線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)化…………………………………………………… 20 2.4 線(xiàn)性規(guī)劃問(wèn)題的解……………………………………………………………… 21 2.4.1 線(xiàn)性規(guī)劃的解的相關(guān)概念……………………………………………………21 2.4.2 基本定理……………………………………………………………………… 24 2.5 線(xiàn)性規(guī)劃的單純形法…………………………………………………………… 24 2.5.1 單純形法迭代的基本思路…………………………………………………… 24 2.5.2 單純形表……………………………………………………………………… 27 2.5.3 單純形法計(jì)算步驟…………………………………………………………… 27 2.6 單純形法的進(jìn)一步討論………………………………………………………… 32 2.6.1 大M 法………………………………………………………………………… 32 2.6.2 兩階段法……………………………………………………………………… 34 2.6.3 單純形法計(jì)算中的幾個(gè)問(wèn)題………………………………………………… 36 思考與練習(xí)………………………………………………………………………………… 37 綜合訓(xùn)練…………………………………………………………………………………… 43 第3章 對(duì)偶問(wèn)題與靈敏度分析…………………………………………………………… 45 3.1 線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題…………………………………………………………… 45 3.1.1 對(duì)偶問(wèn)題的提出……………………………………………………………… 45 3.1.2 對(duì)稱(chēng)形式下對(duì)偶問(wèn)題的一般形式…………………………………………… 46 3.2 對(duì)偶問(wèn)題的基本性質(zhì)…………………………………………………………… 51 3.3 單純形法計(jì)算的矩陣描述……………………………………………………… 55 3.4 影子價(jià)格…………………………………………………………………………… 60 3.5 對(duì)偶單純形法……………………………………………………………………… 61 3.5.1 對(duì)偶單純形法的基本思路…………………………………………………… 61 3.5.2 對(duì)偶單純形法的計(jì)算步驟…………………………………………………… 61 3.6 靈敏度分析………………………………………………………………………… 64 3.6.1 分析cj的變化………………………………………………………………… 65 3.6.2 分析bi 的變化………………………………………………………………… 66 3.6.3 增加一個(gè)變量xj的分析……………………………………………………… 68 3.6.4 分析參數(shù)aij的變化…………………………………………………………… 69 3.6.5 增加一個(gè)約束條件的分析……………………………………………………71 3.7 參數(shù)線(xiàn)性規(guī)劃……………………………………………………………………… 73 思考與練習(xí)………………………………………………………………………………… 77 綜合訓(xùn)練…………………………………………………………………………………… 84 第4章 運(yùn)輸問(wèn)題……………………………………………………………………………… 88 4.1 運(yùn)輸問(wèn)題的數(shù)學(xué)模型…………………………………………………………… 88 4.2 表上作業(yè)法………………………………………………………………………… 90 4.2.1 表上作業(yè)法的步驟及解法…………………………………………………… 90 4.2.2 表上作業(yè)法的幾個(gè)問(wèn)題……………………………………………………… 94 4.3 產(chǎn)銷(xiāo)不平衡問(wèn)題………………………………………………………………… 95 4.3.1 產(chǎn)量大于銷(xiāo)量………………………………………………………………… 95 4.3.2 產(chǎn)量小于銷(xiāo)量………………………………………………………………… 96 4.4 運(yùn)輸問(wèn)題的應(yīng)用………………………………………………………………… 98 4.4.1 產(chǎn)銷(xiāo)不平衡問(wèn)題……………………………………………………………… 98 4.4.2 轉(zhuǎn)運(yùn)問(wèn)題……………………………………………………………………… 100 4.5 指派問(wèn)題………………………………………………………………………… 103 4.5.1 指派問(wèn)題的數(shù)學(xué)模型………………………………………………………… 103 4.5.2 匈牙利解法的原理…………………………………………………………… 105 4.5.3 一般的指派問(wèn)題……………………………………………………………… 111 思考與練習(xí)……………………………………………………………………………… 116 綜合訓(xùn)練………………………………………………………………………………… 121 第5章 整數(shù)規(guī)劃…………………………………………………………………………… 125 5.1 整數(shù)規(guī)劃的數(shù)學(xué)模型…………………………………………………………… 125 5.2 分枝定界法……………………………………………………………………… 127 5.3 割平面法………………………………………………………………………… 133 5.4 0-1整數(shù)規(guī)劃的應(yīng)用………………………………………………………… 137 5.4.1 場(chǎng)所選擇問(wèn)題………………………………………………………………… 137 5.4.2 投資問(wèn)題……………………………………………………………………… 138 5.4.3 背包問(wèn)題……………………………………………………………………… 139 5.4.4 固定費(fèi)用問(wèn)題………………………………………………………………… 139 5.4.5 指派問(wèn)題……………………………………………………………………… 140 5.4.6 分銷(xiāo)系統(tǒng)設(shè)計(jì)………………………………………………………………… 141 5.4.7 集合覆蓋和布點(diǎn)問(wèn)題………………………………………………………… 143 思考與練習(xí)……………………………………………………………………………… 144 綜合訓(xùn)練………………………………………………………………………………… 148 第6章 目標(biāo)規(guī)劃…………………………………………………………………………… 152 6.1 目標(biāo)規(guī)劃問(wèn)題的提出………………………………………………………………… 152 6.2 目標(biāo)規(guī)劃的圖解法…………………………………………………………………… 157 6.3 應(yīng)用舉例……………………………………………………………………………… 161 6.4 目標(biāo)規(guī)劃的單純形法………………………………………………………………… 164 思考與練習(xí)……………………………………………………………………………… 167 綜合訓(xùn)練………………………………………………………………………………… 171 第7章 圖論與網(wǎng)絡(luò)計(jì)劃技術(shù)…………………………………………………………… 175 7.1 圖的基本概念…………………………………………………………………… 175 7.1.1 圖的概念及相關(guān)術(shù)語(yǔ)………………………………………………………… 176 7.1.2 連通圖與支撐子圖…………………………………………………………… 179 7.2 樹(shù)…………………………………………………………………………………… 179 7.2.1 樹(shù)的概念……………………………………………………………………… 179 7.2.2 支撐樹(shù)………………………………………………………………………… 180 7.2.3 最小支撐樹(shù)…………………………………………………………………… 182 7.3 最短路問(wèn)題……………………………………………………………………… 184 7.3.1 最短路問(wèn)題的定義…………………………………………………………… 184 7.3.2 有向網(wǎng)絡(luò)的最短路算法———Dijkstra算法………………………………… 185 7.3.3 無(wú)向圖最短路的求法………………………………………………………… 187 7.4 網(wǎng)絡(luò)最大流……………………………………………………………………… 188 7.4.1 基本概念……………………………………………………………………… 188 7.4.2 Ford-Fulkerson標(biāo)號(hào)算法…………………………………………………… 190 7.4.3 截集與截量…………………………………………………………………… 193 7.5 網(wǎng)絡(luò)計(jì)劃技術(shù)…………………………………………………………………… 194 7.5.1 項(xiàng)目網(wǎng)絡(luò)圖的基本概念……………………………………………………… 195 7.5.2 繪制網(wǎng)絡(luò)圖的基本原則和步驟……………………………………………… 198 7.5.3 工序時(shí)間的估計(jì)……………………………………………………………… 198 7.5.4 網(wǎng)絡(luò)參數(shù)……………………………………………………………………… 199 7.5.5 項(xiàng)目完工的概率……………………………………………………………… 203 7.5.6 網(wǎng)絡(luò)的優(yōu)化…………………………………………………………………… 205 思考與練習(xí)……………………………………………………………………………… 206 綜合訓(xùn)練………………………………………………………………………………… 210 參考文獻(xiàn)……………………………………………………………………………………215