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