《科學版精品課程立體化教材·管理學系列》教材根據教育部“十二五”教材建設思路，會聚各學科優秀教師精心編寫而成。強調以創新型教學改革為先導，以科學性、先進性、適用性為指針，突出中國情景下人才培養特色，貫徹分層分類指導原則，理論功底與能力培養并重，努力構建一個包括教師手冊、習題集、試題庫、教學錄像、教學網站等的立體化教學資源系統。選用教師可通過以下地址與出版社聯系，以獲得相關支持。
《科學版精品課程立體化教材·管理學系列：運籌學（第2版）》重點介紹運籌學各主要分支的基本概念、基本理論和求解方法，包括線性規劃、對偶問題與靈敏度分析、運輸問題、目標規劃、圖論、動態規劃、排隊論、存儲論和決策論等具體內容。《科學版精品課程立體化教材·管理學系列：運籌學（第2版）》在內容上淡化較復雜的理論論述和證明，簡化繁瑣的人工計算，強調對實際問題建立模型并進行應用分析的能力訓練，各章都有詳細的案例，并且附有求解案例模型的Matlab程序代碼。
《科學版精品課程立體化教材·管理學系列：運籌學（第2版）》可作為大專院校、成人教育、函授學院專科生、本科生、研究生和MBA學生的教材和教學參考書，也可作為各類專業人員的自學參考書。
第二版前言
第一版前言
第1章線性規劃與單純形法
1.1線性規劃數學模型
1.2單純形法
1.3單純形法的進一步討論
1.4案例分析與Matlab求解
本章小結
名詞詞條
習題
第2章線性規劃的對偶理論和靈敏度分析
2.1單純形法的矩陣描述
2.2改進單純形法
2.3對偶問題的提出
2.4對偶問題的基本性質
2.5影子價格
2.6對偶單純形法
2.7靈敏度分析
2.8案例分析與Matlab求解
本章小結
名詞詞條
第3章運輸問題
3.1運輸問題的數學模型
3.2表上作業法
3.3產銷不平衡的運輸問題及其求解方法
3.4案例分析與Matlab求解
本章小結
名詞詞條
習題
第4章目標規劃
4.1目標規劃的數學模型
4.2目標規劃的圖解法
4.3案例分析與Matlab求解
本章小結
名詞詞條
習題
第5章整數規劃
5.1整數規劃數學模型
5.2分支定界法
5.3割平面法
5.40-1型整數規劃
……
第6章圖與網絡規劃
第7章動態規劃
第8章排隊論
第9章存儲論
第10章決策論
參考文獻
第1章
線性規劃與單純形法
學習目標
√了解線性規劃模型特征并能根據實際問題寫出線性規劃模型
√掌握線性規劃化標準型的方法
√掌握線性規劃的解的概念，并能夠用圖解法求解線性規劃問題
√熟練掌握線性規劃的單純形法
√利用Matlab求解線性規劃問題的最優解
引言
線性規劃是應用數學模型對所研究的問題進行表述。線性（linear）這個詞是指模型
中數學表達式的形式。規劃（programming）本質上是計劃的同義詞。因此，線性規劃是
用線性數學模型表示不同的生產活動、營銷活動、金融活動或其他活動的計劃。
單純形方法是美國數學家丹捷格（G.B.Dantzig）于1947年提出的一般線性規劃求
解方法，此后線性規劃在計算上趨向成熟，其應用也日趨廣泛和深入。
1.1線性規劃數學模型
1.1.1問題的提出
線性規劃應用的問題種類繁多，形式各異，主要分為四類線性規劃問題。前三類問題
分別是資源分配問題、成本效益問題以及網絡配送問題。例1.1、例1.2、例1.3討論了這
三類問題。這些線性規劃問題其共同特征是決策所基于的約束條件性質，三類線性規劃
問題約束分別是資源約束、收益約束、確定需求約束。更多的實際問題包含至少有兩種以
上的約束。這類問題不能絕對歸屬于這三類中的一類，于是把這第四類線性規劃的問題
稱為混合問題。
例1.1資源分配問題。
某工廠近期要安排生產甲、乙兩種產品，產品甲需要用原料A，產品乙需要用原料B，
由于兩種產品都在一個設備上生產，且設備使用時間有限，管理者必須合理安排兩種產
品的產量，使得在資源有限的條件下獲得最大的利潤。因此，這個問題的決策目標是收益
的最大化，研究者根據這個目標需要收集以下相關數據：
（1）工廠兩種原料存量以及可用設備工時數。
（2）甲、乙兩種產品的單位產品需要的原料和設備工時數。
（3）甲、乙兩種產品的單位產品利潤。
這些數據可以通過調研或估算得出，如表1.1所示。
為建立模型，引入變量如下：
x1＝產品甲的數量
x2＝產品乙的數量
Z＝利潤
由表1.1最后一行知
Z＝4x1+3x2
目標是如何確定x1和x2，使得利潤Z最大，同時需要滿足資源約束。
對于原料A和原料B，有
x1≤6，2x2≤8
對于設備工時，有
2x1+3x2≤18
此外，甲、乙兩種產品數量不可能是負值，因此，有如下對變量的非負約束：
x1≥0，x2≥0
于是，問題的數學模型現在可以用代數式表述如下：
maxZ＝4x1+3x2
滿足：
x1≤6（1.1）
2x2≤8（1.2）
2x1+3x2≤18（1.3）
x1，x2≥0（1.4）
實際上這是求一個線性函數在一組線性約束條件下的最大值問題，稱之為線性規劃
問題模型。在以上模型中，將x1、x2稱為決策變量，Z＝4x1+3x2為目標函數，式（1.1）～
式（1.3）為函數約束，式（1.4）為非負約束。
從以上過程我們可以歸納出根據實際問題建立線性規劃模型的步驟：
（1）根據管理層的要求確定決策目標和收集相關數據。
（2）確定要做出的決策，引入決策變量。
（3）確定對這些決策的約束條件和目標函數。
例1.2成本效益平衡問題。
某飼料公司希望用玉米、紅薯作原料配制一種混合飼料，各種原料包含的營養成分和
采購成本都不同，公司管理層希望能夠確定混合飼料中的各種原料數量，使得飼料能夠以
最低成本達到一定的營養要求。研究者根據這一目標收集到的有關數據如表1.2所示。
為建立線性規劃模型，我們引入變量如下：
x1＝混合飼料中的玉米數量；
x2＝混合飼料中紅薯的數量。
目標函數Z＝0.8x1+0.5x2，表示產量的成本函數，即如何確定x1、x2使得成本Z＝
0.8x1+0.5x2最低且滿足最低營養要求的約束，這些約束條件是
碳水化合物要求：8x1+4x2≥20。
蛋白質物要求：3x1+6x2≥18。
維生素物要求：x1+5x2≥16。
另外非負約束：x1≥0，x2≥0。
因此這個問題的線性規劃模型為
minZ＝0.8x1+0.5x2
s．t．
8x1+4x2≥20
3x1+6x2≥18
x1+5x2≥16
xi≥0，i＝1，2
其中，“s．t．”是“subjectto”的縮寫，意思是“受約束于……”。
例1.3物流網絡配送問題。
某物流公司需要將甲、乙、丙三個工廠生產的一種新產品送到A、B兩個倉庫，甲、乙
兩個工廠的產品可以通過鐵路運送到倉庫A，數量不限；丙工廠的產品可以通過鐵路運送
到倉庫B，同樣，產品數量不限。由于鐵路運輸成本較高，公司也可以考慮由獨立的卡車
來運輸，可將多達80單位的產品由甲、乙、丙三個工廠運到一個配送中心，再從配送中心
以最多90單位的載貨量運到各個倉庫。公司管理層希望以最小的成本運送所需的貨物。
為了建立該問題的數學模型，必須先了解這一網絡配送問題的活動和要求。該問題
涉及三個產品的生產和各線路的運輸量，由于產量給定，所以決策重點是運輸水平，即各
線路的運輸量。
首先，需要收集每條線路上的單位運輸成本和各工廠產品的產量以及各倉庫分配量
等數據，如表1.3所示。
為了更清楚地說明問題，我們用網絡圖來直觀表示該配送問題（圖1.1），其中，v1、
v2、v3分別表示甲、乙、丙三個工廠，節點v4表示配送中心，節點v5、v6表示兩個倉庫；每
一條箭線表示一條可能的運輸線路，并給出了相應的單位運輸成本，對運輸量有限制的路
線的最大運輸能力也同時給出。
我們要解決的是各條線路最大運輸量，引入變量xij表示由vi經過路線（vi，vj）運輸
到vj的產品數。問題的目標是總運輸成本最小化，總運輸成本可以表示為
總運輸成本＝7.5x15+3x14+8.2x25+3.5x24+2.3x45+3.4x34
+2.3x46+9.2x36
相應的約束條件包括對網絡中的每個節點vi（i＝1，2，…，6）的供求平衡約束。對生
產節點v1、v2、v3來說，由某一節點運出的產品數量等于其產量，即
x15+x14＝100
x25+x24＝80
x34+x36＝70
對配送中心v4運進的產品數量等于運出的產品數量，即
x14+x24+x34＝x45+x46
對倉庫v3、v5，運進的產品數量等于其需求量，即
x15+x25+x45＝120
x46+x36＝130
此外，對網絡中有運輸容量限制的路線的約束是：該路線上的運輸產品數量不超過該
線路的運輸能力，即
x14≤80，x24≤80，x34≤80，x45≤90，x46≤90
并且，所有xij≥0（非負約束）。因此，這個問題的線性規劃模型為
minZ＝7.5x15+3x14+8.2x25+3.5x24+2.3x45+3.4x34+2.3x46+9.2x36
s．t．
x15+x14＝100
x25+x24＝80
x34+x36＝70
x14+x24+x34＝x45+x46
x15+x25+x45＝120
x46+x36＝130
x14≤80，x24≤80，x34≤80，x45≤90，x46≤90
xij≥0
從以上的幾個例子可以看出，線性規劃問題有如下共同特征：
（1）每個問題都用一組決策變量，這組決策變量的值都代表一個具體方案。
（2）有一個衡量決策方案優劣的函數，它是決策變量的線性函數，稱為目標函數。按
問題不同，要求目標函數實現最大化或最小化。
（3）存在一些約束條件，這些約束條件包括：①函數約束；②決策變量的約束。
1.1.2線性規劃的標準型
根據1.1.1節分析，線性規劃的一般形式為
max（min）Z＝c1x1+c2x2+…+cnxn
s.t.
a11x1+a12x2+…+a1nxn≤＝，≥b1
a21x1+a22x2+…+a2nxn≤＝，≥b2
·
am1x1+am2x2+…+amnxn≤＝，≥bm
x1，x2，…，xn≥0
線性規劃問題有各種不同的形式。目標函數有的要求max，有的要求min；約束條件
可以是“≤”，也可以是“≥”形式的不等式，也可以是等式。決策變量一般是非負約束，
但也允許在（-∞，∞）范圍內取值，即無約束。將這種多形式的數學模型統一變換為標準
形式。這里規定的標準形式為：目標函數的要求是max，約束條件的要求是等式，決策變
量的要求是非負約束。在標準型式中規定各約束條件的右端項bi≥0，否則等式兩端乘以
“-1”。用向量和矩陣符號表述為
maxZ＝CX
s．t.Σ
n
j＝1
Pjxj＝b
xj≥0，j＝1，2，…，n
其中，C＝（c1，c2，…，cn）；
X＝
x1
x2
·
xn
；Pj＝
a1j
a2j
·
amj
；b＝
b1
b2
·
bm
向量Pj對應的決策變量是xj。
用矩陣描述時為
maxZ＝CX
AX＝b
X≥0
其中，A＝
a11a12…a1n
···
am1am2…amn
＝P1，P2，…，Pn；
0＝
0
0
·
0
；
A為約束條件的m×n維系數矩陣，其中，m，n＞0，m＜n；
b為資源向量；
C為價值向量；
X為決策變量向量。
下面討論化標準型的方法：
（1）若要求目標函數實現最小化，即minZ＝CX。這時只需將目標函數最小化變換
求目標函數最大化，即令Z′＝-Z，于是得到maxZ′＝-CX。這就同標準型的目標函數
的形式一致了。
（2）約束方程為不等式。這里有兩種情況：一種是約束方程為“≤”不等式，則可在
“≤”不等式的左端加入非負松弛變量xj，把原“≤”不等式變為等式；另一種是約束方程
為“≥”不等式，則可在“≥”不等式的左端減去一個非負剩余變量xk（也可稱松弛變量），
把不等式約束條件變為等式約束條件。
（3）若變量約束中：xi≤0，則令x′i＝-xi得到x′i≥0；若xj酬0，則令xj＝x′j-x″j，得
x′j，x″j≥0，用x′i、x′j、x″j分別代替xi、xj后得到線性規劃的變量約束均為非負約束。
（4）目標函數中加上0xi（松弛變量）。
下面舉例說明。
新書資訊