《運籌學原理與算法》(作者郭強、孫浩)與現行的其他運籌學教材相比，不涉及非線性規劃，但增加了網絡最優選址問題，擴充了網絡規劃和分配問題的內容。對一些經典運籌問題，補充了一些運籌理論，還補充了一些更加簡便、實用的運籌算法。《運籌學原理與算法》的另一個特點是，把運籌方法的程序設計納入教學內容中，詳細、完整、規范地給出了各種運籌方法的算法步驟。 《運籌學原理與算法》是針對應用數學專業本科生編寫的教材，也可作為經濟管理、系統工程、計算機工程等專業的本科生教材，還可供相關專業研究生及科技工作者參考。
運籌學是20世紀30年代逐步發展起來的一門新興學科，其涉及的內容具有共同的特征：在諸多因素制約下，為了實現既定的目標，如何通過數學方法作出最好的選擇。這樣的學科，無疑有著非常廣泛的應用背景和重要的應用價值。 《運籌學原理與算法》是編者在多年從事運籌學教學和研究的基礎上，結合運籌學的最新發展，編寫的面向應用數學專業的本科教材。 本書共13章，第1～10章由郭強編寫，第11～13章由孫浩編寫。
前言
第1章 線性規劃
1．1 線性規劃的模型及概念
一、線性規劃及其模型
二、線性規劃的幾何意義
1．2 單純形法
一、線性規劃的單純形表
二、可行基與基可行解的概念和性質
三、已知一個可行基的單純形法
1．3 對偶單純形法
一、正則基的概念和性質
二、已知一個正則基的對偶單純形法
習題1
第2章 線性規劃全過程算法
2．1 兩階段法
一、求可行基的方法
二、全過程算法一(兩階段法)
2．2 大M單純形法
一、基本原理
二、全過程算法二(大M單純形法)
2．3 大M對偶單純形法
一、基本原理
二、全過程算法三(大M對偶單純形法)
2．4亞基迭代算法
一、概念
二、全過程算法四(亞基迭代算法)
習題2
第3章 線性規劃的擴展問題
3．1 線性規劃的對偶理論
一、對偶線性規劃的概念
二、對偶線性規劃之間的關系
3．2 線性規劃的靈敏度問題
一、靈敏度的概念
二、目標函數中非最優基變量的系數□的靈敏度
三、目標函數中最優基變量的系數□的靈敏度
四、約束條件中常數項□的靈敏度
五、約束條件中非最優基變量的系數□的靈敏度
3．3 目標線性規劃
一、關于無最優解的多目標線性規劃
二、關于無可行解的線性規劃
習題3
第4章 整數線性規劃
4．1 整數線性規劃概念
4．2 一般整數線性規劃的解法
一、一般整數線性規劃與線性規劃的關系
二、分支定界法
三、割平面法
4．3 0-1整數規劃的解法
一、隱枚舉法
二、特殊0-1整數規劃的特殊解法
習題4
第5章 最小支撐樹和最優路徑問題
5．1 圖與網絡的概念
一、圖的概念
二、子圖的概念與幾種特殊子圖
5．2 最小支撐樹問題及其算法
一、破圈法
二、避圈法
三、生長樹法
5．3 最短路問題及其算法
一、最短路的概念
二、延伸路徑的方法與特點
三、無負權值最短路問題的Dijkstra算法
四、含負權值無回路最短路問題的強Dijkstra算法
五、最短路問題的Floyd算法
5．4 最長路徑問題及其算法
一、最長路的概念
二、最長路問題的仿強Dijkstra算法
三、最長路問題的仿Floyd算法
5．5 最大增流路徑問題
一、基本概念
二、最大增流路徑問題的仿Dijkstra算法
三、最大增流路徑問題的仿Floyd算法
習題5
第6章 網絡最優選址和網絡最優計劃問題
6．1 網絡最優選址問題
一、網絡最優選址的概念
二、單點最優選址問題的算法
三、多點最優選址問題的算法
四、半徑有界的最優選址問題的算法
6．2 網絡最優計劃問題
一、基本概念
二、網絡最優計劃問題的箭線圖
6．3 網絡最優計劃問題的算法
一、基于單箭線圖的網絡最優計劃問題的算法
二、基于復箭線圖的網絡最優計劃問題的算法
三、關鍵作業和關鍵路徑的概念與應用
習題6
第7章 最大流和最小費用流問題
7．1 最大流問題及其算法
一、有向網絡最大流問題及其數學模型
二、有向網絡的割與割量的概念與性質
三、有向網絡最大流的Ford—Fulkeen算法
四、無向網絡最大流算法
7．2 最小費用流問題及其算法
一、最小費用流的概念
二、調費圖與負回路的概念與性質
三、最小費用流問題的算法
習題7
第8章 運輸問題
8．1 運輸問題及其特征
一、運輸問題的數學模型
二、運輸問題的特征
8．2 運輸問題的解法一(表上回路法)
一、平衡運輸問題的基可行解獲取方法
二、平衡運輸問題的最優解獲取方法
三、不平衡運輸問題的解法
8．3 運輸問題的解法二(仿最小費用流算法)
一、運輸問題與最小費用流問題的關系
二、運輸問題的仿最小費用流算法
8．4 運輸問題的解法三(平衡負回路算法)
一、運輸問題的檢測矩陣與位置矩陣
二、運輸問題的平衡負回路算法
習題8
第9章 分配問題
9．1 分配問題及其特征
一、分配問題及其數學模型
二、幾種分配問題之間的關系
三、典則分配問題的性質
9．2 分配問題的解法一(匈牙利算法)
一、典則分配問題的解法
二、一般平衡分配問題的解法
三、不平衡分配問題的解法
9．3 分配問題的解法二(平衡負回路算法)
一、典則分配問題的平衡負回路算法
二、一般平衡分配問題的平衡負回路算法
習題9
第10章 動態規劃
10．1 階段性網絡上最優路徑的動態規劃算法
一、最優路徑的延伸算法的共同特點
二、階段性網絡上最優路徑的動態規劃算法
10．2 適合動態規劃的問題與最優性原理
一、動態規劃的概念
二、動態規劃在一些線性約束規劃上的應用
三、動態規劃在一些案例中的應用
習題10
第11章 存儲論
11．1 存儲論的基本概念
11．2 確定性存儲模型
一、不允許缺貨，即刻到貨模型
二、不允許缺貨，到貨需一定時間模型
三、允許缺貨，即刻到貨模型
四、允許缺貨，生產需一定時間
五、價格有折扣的存儲問題
11．3 隨機性存儲模型
一、需求是隨機離散的存儲模型
二、需求是連續型隨機變量的存儲模型
三、(s，S)型存儲策略
習題11
第12章 對策論
12．1 對策論概述
一、對策論的基本要素
二、對策的例子
12．2 矩陣對策中的策略
一、矩陣對策的最優純策略
二、矩陣對策的混合策略
12．3 矩陣對策的基本定理
一、基本定理
二、基本性質
12．4 矩陣對策的求解
一、圖解法
二、線性規劃法
三、方程組法
12．5 其他對策模型簡介
一、二人無限零和對策
二、二人無限非零和對策
三、合作對策
四、多人非合作對策
習題12
第13章 排隊論
13．1 隨機服務系統與過程
一、排隊系統的描述
二、排隊系統的符號表示
三、排隊系統的主要數量指標和記號
13．2 排隊系統的常用分布
一、指數分布
二、泊松分布
三、愛爾朗分布
13．3 單服務臺排隊模型
一、標準的M／M／1模型
二、系統容量有限的M／M／1／N／∞模型
三、顧客源有限的M／M／1／∞／m模型
13．4 多服務臺排隊模型
13．5 排隊系統的優化問題
一、M／M／1模型的最優平均服務率
二、M／M／c模型的最佳服務臺數
習題13
參考文獻
第1 章
線性規劃
線性規劃（linear programming）是運籌學中的一個重要分支，在現代工業、農業、商
業、交通運輸、國防軍事及經濟管理等諸多領域都有著廣泛、重要的應用．本章介紹的是
線性規劃的基本概念、性質及在可行基或正則基已知的前提下求解線性規劃的方法．
1.1 線性規劃的模型及概念
一、線性規劃及其模型
現實中有許多問題可以表示成，在滿足一組線性等式或線性不等式的條件下，尋求
一個能夠使某個線性函數的值最大（或最小）的一組變量的取值，這樣的問題稱為線性
規劃問題．其中，被要求值達到最大（或最小）的函數，稱為線性規劃的目標函數；要求變
量滿足的所有條件稱為線性規劃的約束條件．
例1.1.1 某廠生產產品A1 ，A2 ，… ，An 要用到原料B1 ，B2 ，… ，Bm.已知該廠每種
原料的擁有量、生產中每種單位產品要消耗的各種原料量，以及每種產品的單位價格，
見表1.1.1.
要研究的問題是：在現有條件下，要獲得最高產值，每種產品應各生產多少？
設xj 為產品A j 的生產量（ j ＝ 1 ，2 ，… ，n） ，則目標函數為總產值
c1 x1 + c2 x2 + … + cn x n
約束條件為原料Bi的擁有量對各種產品A j 的生產量x j 的限制
ai1 x1 + ai 2 x2 + … + ai n xn ≤ bi （ i ＝ 1 ，2 ，… ，m）
以及客觀條件xj ≥ 0（ j ＝ 1 ，2 ，… ，n）.因此，本題的數學模型為
max c1 x1 + c2 x2 + … + cn xn
s.t.
a1 1 x1 + a12 x2 + … + a1 n xn ≤ b1
a2 1 x1 + a22 x2 + … + a2 n xn ≤ b2
… …
am1 x1 + am2 x2 + … + amn xn ≤ bm
xj ≥ 0 （ j ＝ 1 ，2 ，… ，n）
其中max 是英文maximum 的縮寫，表示取最大；s.t.是英文subject to 的縮寫，表示受
約束于….
例1.1.2 從A1 ，A2 ，… ，An 礦石中均可提煉出B1 ，B2 ，… ，Bm 物質．已知每種礦石
中可以提煉的各種物質量、提煉單位礦石的費用，以及需要提取的各種物質量，見表
1.1.2.
要研究的問題是：要使總的提煉費用最少，這n 種礦石應各選用多少？
設xj 為礦石A j 的選用量（ j ＝ 1 ，2 ，… ，n） ，則目標函數為總提煉費用
c1 x1 + c2 x2 + … + cn x n
約束條件為物質Bi的需要量對各種礦石A j 的選用量x j 的最低要求
ai1 x1 + ai 2 x2 + … + ai n xn ≥ bi （ i ＝ 1 ，2 ，… ，m）
以及客觀條件xj ≥ 0（ j ＝ 1 ，2 ，… ，n）.因此，本題的數學模型為
min c1 x1 + c2 x2 + … + cn xn
s.t.
a11 x1 + a12 x2 + … + a1 n xn ≥ b1
a21 x1 + a22 x2 + … + a2 n xn ≥ b2
… …
am1 x1 + am2 x2 + … + amn xn ≥ bm
xj ≥ 0 （ j ＝ 1 ，2 ，… ，n）
其中min 是英文minmum 的縮寫，表示取最小；s.t.的含義同上．
例1.1.3 按照供需要求，要從發貨點A1 ，A2 ，… ，Am 處將貨物運往B1 ，B2 ，… ，Bn
各收貨點．已知各發貨點提供的貨物量、各收貨點的貨物需求量、從各發貨點到各收貨
點的單位貨物運費，見表1.1.3.
要研究的問題是：按照供需現狀，如何安排各發貨點到各收貨點的貨物量，才能使
總運費最少？
設xij 為A i 點運往B j 點的貨物量（ i ＝ 1 ，2 ，… ，m ；j ＝ 1 ，2 ，… ，n） ，則目標函數為總
運費Σ
m
i ＝ 1 Σ
n
j ＝ 1
cij x ij.但約束條件要分為以下三種情況：
（1） Σ
m
i ＝ 1
ai ＝ Σ
n
j ＝ 1
bj 時，約束條件是：Ai 點運出的貨物量應等于A i 點可提供的貨物
量，Bj 點收到的貨物量應等于B j 點的貨物需求量，即Σ
n
j ＝ 1
xij ＝ ai i ＝ 1 ，2 ，… ，m ；
Σ m
i ＝ 1
xij ＝ bj （ j ＝ 1 ，2 ，… ，n） ；以及客觀條件xij ≥ 0 i ＝ 1 ，2 ，… ，m ；j ＝ 1 ，2 ，… ，n.此
時，數學模型為
min Σ
m
i ＝ 1 Σ
n
j ＝ 1
cij x ij
s.t.
Σ n
j ＝ 1
xij ＝ ai （ i ＝ 1 ，2 ，… ，m）
Σ m
i ＝ 1
xij ＝ bj （ j ＝ 1 ，2 ，… ，n）
xij ≥ 0 （ i ＝ 1 ，2 ，… ，m ；j ＝ 1 ，2 ，… ，n）
（2） Σ
m
i ＝ 1
ai ≤ Σ
n
j ＝ 1
bj 時，約束條件是：Ai 點運出的貨物量應等于A i 點可提供的貨物
量，Bj 點收到的貨物量應不超過B j 點的貨物需求量，即Σ
n
j ＝ 1
xij ＝ ai i ＝ 1 ，2 ，… ，m ，
Σ m
i ＝ 1
xij ≤ bj （ j ＝ 1 ，2 ，… ，n） ；以及客觀條件xij ≥ 0 i ＝ 1 ，2 ，… ，m ；j ＝ 1 ，2 ，… ，n.此
時，數學模型為
min Σ
m
i ＝ 1 Σ
n
j ＝ 1
cij x ij
s.t.
Σ n
j ＝ 1
xij ＝ ai （ i ＝ 1 ，2 ，… ，m）
Σ m
i ＝ 1
xij ≤ bj （ j ＝ 1 ，2 ，… ，n）
xij ≥ 0 （ i ＝ 1 ，2 ，… ，m ；j ＝ 1 ，2 ，… ，n）
（3） Σ
m
i ＝ 1
ai ≥ Σ
n
j ＝ 1
bj 時，約束條件是：Ai 點運出的貨物量應不超過A i 點可提供的貨
物量，Bj 點收到的貨物量應等于B j 點的貨物需求量，即Σ
n
j ＝ 1
xij ≤ ai （ i ＝ 1 ，2 ，… ，m） ；
Σ m
i ＝ 1
xij ＝ bj （ j ＝ 1 ，2 ，… ，n） ；以及客觀條件xij ≥ 0（ i ＝ 1 ，2 ，… ，m ；j ＝ 1 ，2 ，… ，n）.此時，
數學模型為
min Σ
m
i ＝ 1 Σ
n
j ＝ 1
cij x ij
s.t.
Σ n
j ＝ 1
xij ≤ ai （ i ＝ 1 ，2 ，… ，m）
Σ m
i ＝ 1
xij ＝ bj （ j ＝ 1 ，2 ，… ，n）
xij ≥ 0 （ i ＝ 1 ，2 ，… ，m ；j ＝ 1 ，2 ，… ，n）
例1.1.4 某建筑工地因施工需要，要用12m 長的鋼筋，截取5.5m 、3.5m 、2.5m
長的鋼筋段各1600 、3500 、2800 根．試問：要使12m 長的鋼筋用量最少，應如何下料？
分析 按不同的下料方法可以獲得的不同結果，見表1.1.4.
設按第j 種方案用12m 的鋼筋xj 根（ j ＝ 1 ，2 ，… ，7） ，則目標函數為12m 長的鋼筋
總用量x1 + x2 + … + x7.約束條件為截出的5.5m 、3.5m 、2.5m 長的鋼筋數量應滿足的
需要量2 x1 + x2 + x3 ≥ 1600 ，x2 + 3 x4 + 2 x5 + x6 ≥ 3500 ，x2 + 2 x3 + 2 x5 + 3 x6 + 4 x7 ≥
2800 ，以及客觀條件xj ≥ 0（ j ＝ 1 ，2 ，… ，7）.因此，該問題的數學模型為
min x1 + x2 + … + x7
s.t.
2 x1 + x2 + x3 ≥ 1600
x2 + 3 x4 + 2 x5 + x6 ≥ 3500
x2 + 2 x3 + 2 x5 + 3 x6 + 4 x7 ≥ 2800
xj 為整數≥ 0 （ j ＝ 1 ，2 ，… ，7）
例1.1.5 在每項工作只能由一人承擔的要求下，安排m 個人去完成n 項工作．已
知第i 人完成第j 工作的用時為cij （ i ＝ 1 ，2 ，… ，m ；j ＝ 1 ，2 ，… ，n）.研究：如何進行工作
分配，才能使完成所有工作的總用時最少？
設xij ＝
1 ， 安排第i 人承擔第j 項工作，
0 ， 否則
（ i ＝ 1 ，2 ，… ，m ；j ＝ 1 ，2 ，… ，n） ，yi 為第i
人承擔的工作數（ i ＝ 1 ，2 ，… ，m） ，則目標函數為完成所有工作的總用時Σ
m
i ＝ 1 Σ
n
j ＝ 1
cij x ij.
約束條件是：每個人對各項工作是否承擔應當與其承擔的工作數相吻合，即Σ
n
j ＝ 1
xij ＝
yi （ i ＝ 1 ，2 ，… ，m） ；每項工作只能由一人承擔Σ
m
i ＝ 1
xij ＝ 1（ j ＝ 1 ，2 ，… ，n） ；所有工作都必
須完成，即Σ
m
i ＝ 1
yi ＝ n ；以及xij ∈ ｛0 ，1｝ （i ＝ 1 ，2 ，… ，m ；j ＝ 1 ，2 ，… ，n） 和yi ∈ ｛0 ，1 ，… ，n｝
（ i ＝ 1 ，2 ，… ，m）.因此，該問題的數學模型為
min Σ
m
i ＝ 1 Σ
n
j ＝ 1
cij x ij
s.t.
Σ n
j ＝ 1
xij ＝ yi （ i ＝ 1 ，2 ，… ，m）
Σ m
i ＝ 1
xij ＝ 1 （ j ＝ 1 ，2 ，… ，n）
Σ m
i ＝ 1
yi ＝ n
xij ∈ ｛0 ，1｝ ，yi ∈ ｛0 ，1 ，… ，n｝ （ i ＝ 1 ，2 ，… ，m ；j ＝ 1 ，2 ，… ，n）
以上5 個問題的數學模型，目標函數和約束條件都是線性的，變量都是非負的，因
此，都屬于線性規劃問題．一般線性規劃可分為以下三種形式：
（LP1）
min（或max） CT x
s.t.
A x ＝ b
x ≥ 0
（LP2）
min（或max） CT x
s.t.
A x ≤ b
x ≥ 0
（LP3）
min（或max） CT x
s.t.
A x ＝ b
Ax ≤ d
x ≥ 0
其中C ＝ （ c1 ，c2 ，… ，cn ）T ，x ＝ （ x1 ，x2 ，… ，xn ）T ，A ＝ （ aij ）m × n ，b ＝ （ b1 ，b2 ，… ，bm ）T ，A ＝
（ aij ）k × n ，d ＝ （ d1 ，d2 ，… ，dk ）T.
規定 （LP1）為線性規劃的標準形．（ LP2）和（ LP3）不是標準形，但都可以化成標
準形．
定義1.1.1 如果通過加（或減）非負變量把線性規劃的不等式約束變成等式約
束，則稱這樣的非負變量為該線性規劃的松弛變量．
例如，引入松弛變量xn + 1 ，xn + 2 ，… ，xn + m ≥ 0 ，可以把例1.1.1 中給出的非標準形線
性規劃轉化成標準形線性規劃：
max c1 x1 + c2 x2 + … + cn xn
s.t.
a11 x1 + a12 x2 + … + a1 n xn + xn + 1 ＝ b1
a21 x1 + a22 x2 + … + a2 n xn + xn + 2 ＝ b2
… …
am1 x1 + am2 x2 + … + amn x n + xn + m ＝ bm
xj ≥ 0 （ j ＝ 1 ，2 ，… ，n + m）
（1.1.1）
引入松弛變量xn + 1 ，xn + 2 ，… ，xn + m ≥ 0 ，可以把例1.1.2 給出的非標準形線性規劃
轉化成標準形線性規劃：
min c1 x1 + c2 x2 + … + cn xn
s.t.
a11 x1 + a12 x2 + … + a1 n xn - xn + 1 ＝ b1
a21 x1 + a22 x2 + … + a2 n xn - xn + 2 ＝ b2
… …
am1 x1 + am2 x2 + … + amn x n - xn + m ＝ bm
xj ≥ 0 （ j ＝ 1 ，2 ，… ，n + m）
（1.1.2）
不難理解，任何非標準形線性規劃都可以轉化成標準形線性規劃，因此，如何構建
標準形線性規劃問題的解法，是構建一般性線性規劃問題的解法的關鍵．
二、線性規劃的幾何意義
定義1.1.2 稱集合x A x ＝ b ，x ≥ 0 為線性規劃（ LP1）的可行域，該集合中的元
素稱為線性規劃（LP1）的可行解．
定義1.1.3 如果（LP1）的可行解能夠使（LP1）的目標函數達到目標要求，則該可
行解稱為（LP1）的最優解，對應的目標函數值稱為（LP1）的最優值．
線性規劃（LP2）和（LP3）的可行域、可行解、最優解及最優值的定義類似．
我們知道，二元一次方程ai1 x1 + ai2 x2 ＝ bi 在x1 Ox2 直角坐標系中，圖像是直線．三
元一次方程ai1 x1 + ai2 x2 + ai3 x3 ＝ bi在Ox1 x2 x3 直角坐標系中，圖像為平面．但是在n ＞
3 時，n 元一次方程ai1 x1 + ai2 x2 + … + ain xn ＝ bi的圖像是無法繪制的，為方便起見，稱n
元一次方程的圖像為超平面．因此，（LP1）的可行域是一系列超平面的公共點構成的集
合；（LP2）的可行域是一系列超平面圍成的集合．特別是在n ＝ 2 時，（ LP2）的可行域是
由若干條直線圍成的凸多邊形．在n ＝ 3 時，（ LP2）的可行域是由若個平面圍成的凸多
面體．
新書資訊