《運籌學》教案

（本教案適用于20課時的班級）

第一章線性規劃與單純形法

1、教學計劃

第_J一次課2學時

緒論；第一章第節、第節、第節

授課章節123

授課方式口J理論課□討論課口實驗課口習題課□其他

了解線性規劃模型的背景、掌握建模方法以及線性規劃的標準形式。

課堂教學掌握兩個決策變量線性規劃問題可行域（凸集）、最優解的位置：了

目的及要求解無解（無界解、無可行解）、有解（唯一解、無窮多個解）的幾何

意義。

重點：線性規劃的數學模型及其標準形。在數學模型中，要求熟悉

矩陣形式；在標準形中，要求學生掌握非標準形式的幾種具體情形

課堂教學及其相應的標準化方法；如何用幾何的方法求兩個決策變量的線性

重點及難點規劃問題的最優解。

難點：線性規劃的基本概念，例如基、基變量、基解、基可行解和

可行基；多個最優解如何表示。

教學過程教學方法及手段

引言多媒體講解

運籌學模型，運籌學發展歷史與現狀，研究

方法；考核方法與教學大綱等。

實例講解

1.1線性規劃問題及其數學模型

線性規劃的數學模型：

變量的確定、約束條件與目標函數。

1.2線性規劃問題的標準形式

線性規劃的標準形式及非標準形式的標準

化處理。

教學過程1.3線性規劃問題的解

基、基變量、基解、基可行解和可行基。

1.4單純形法

單純形數表的構造，要注意代數形式和表格

形式的---對應性。

單純形法迭代過程：（1）換入基變量的確定；

（2）換出基變量的確定；（3）判定當前解已經

最優。

1.5單純形法的進一步討論及小結

人工變量法的思想，大M法和兩階段法的求

解思路和步驟。

單純形法小結

2、教案

1.1線性規劃問題及其數學模型

線性規劃模型的建立就是將現實問題用數學的語言表達出來。

例1：某工廠要安排生產I、II兩種產品，每單位產品生產所需的設備、材

料消耗及其利潤如下表所示。問應如何安排生產計劃使工廠獲利最多？

III

設備128臺時

原材料A4016kg

原材料B0412kg

單位產品的利潤（元）23

解：設生產產品I、II的數量分別為不和

首先，我們的目標是要獲得最大利潤，即

maxz=2陽+3x2

其次，該生產計劃受到一系列現實條件的約束，

設備臺時約束：生產所用的設備臺時不得超過所擁有的設備臺時，即

%1+2X2<8

原材料約束：生產所用的兩種原材料A、B不得超過所用有的原材料總數,

4%,<16

4X2<12

非負約束：生產的產品數必然為非負的,即

%i，x2>0

由此可得該問題的數學規劃模型：

maxz=2匹+3x2

匹+2X2<8

4玉<16

4X2<12

x],x2>0

總結:

線性規劃的一般建模步驟如下：

（1）確定決策變量

確定決策變量就是將問題中的未知量用變量來表示，如例1中的X和/。

確定決策變量是建立數學規劃模型的關鍵所在。

（2）確定目標函數

確定目標函數就是將問題所追求的目標用決策變量的函數表示出來。

（3）確定約束條件

將現實的約束用數學公式表示出來。

線性規劃數學模型的特點

（1）有一個追求的目標，該目標可表示為一組變量的線性函數，根據問題

的不同，追求的目標可以是最大化，也可以是最小化。

（2）問題中的約束條件表示現實的限制，可以用線性等式或不等式表示。

（3）問題用一組決策變量表示一種方案，一般說來，問題有多種不同的備

選方案，線性規劃模型正式要在這眾多的方案中找到最優的決策方案（使目標函

數最大或最小），從選擇方案的角度看，這是規劃問題，從目標函數最大或最小

的角度看，這是最優化問題。

1.2線性規劃問題的標準形式

根據問題的性質，線性規劃有多種形式，目標函數有要求最大化的，也有要

求最小化的；約束條件可以是“W”或“2”的不等式，也可以是“="；雖然決

策變量一般是非負的，但也可是無約束的，即，可以在（-8,+oo）取值。為了分析

問題的簡化，一般規定如下的標準形式：

maxz=CjX）+c2x2+

Q]]X]+al2X2+???,+Q]“X〃=瓦

+。22占+…,=b）

<

—+am2x2+...,+amnxn=bm

xi,x2,...,xn>0

非標準形式轉化為標準形式：

（1）若目標函數要求實現最小化minz,則可令z'=-z,可將原問題的目標

函數轉化為maxz'即可。

（2）若約束方程為“4”，則可在“4”的左邊加上非負的松弛變量；若約

束方程為“2”，則可在“2”的左邊減去非負的剩余變量。

(3)若存在取值無約束的變量.％,則可令％=七-匕，其中，x,,x；>0o

例：將如下問題轉化為標準形式：

minz=尤1+2X2

2范+3X2<6

Xj4-x>4

<2

xt-x2=3

X20,》2無約束

解：

首先，用七-乙替換/，其中，X3,X4>0；

其次，在第一個約束條件的左端加上非負的松弛變量恐；

再次，在第二個約束條件的左端減去非負的剩余變量超；

最后，令z'=-z,將求minz改為求maxz'。由此，可得標準形如下：

maxz'=-x,-2X3+2x4+Ox5+0x6

2X1+3X3-3X4+x5=6

x+x-x-x=4

<t}46

-x3+x4=3

XPX3,A:4,X5,X6>0

1.3線性規劃問題的解

首先，將線性問題的標準形式用矩陣和向量形式表示如下：

maxz=CX

AX=B

\X>0

其中，C=(cI5c2,...,c?)；X=區,》2,…,x")，，8=仇力2，...,"

a

°]2…\n

aa

A=“2122…2n

_am\am2…amn_

1、可行解和最優解

滿足約束條件的所有解x=a，…,乙)'成為線性規劃問題的可行解，其

中，使目標函數達到最大的可行解成為最優解。

2、基和基解

設A為約束方程組的〃維矩陣，其秩為〃?。設B為矩陣A中的mx〃邛介非

奇異子矩陣(忸上0),則稱8為線性規劃的一個基。

不妨設前〃?個變量的系數矩陣為線性規劃的一個基，則XR=區…

為對應于這個基的基變量。用高斯消去法可求得一個解

X=(X],X2，...,x.,0,...,0),

該解得非零分量的數目不大于方程個數機，稱X為基解。

3、基可行解

若基解X滿足非負約束，則稱其為基可行解。

4、可行基

對應于基可行解的基，成為可行基。

1.4單純形法

一、單純形表

考察一種最簡單的形式：目標函數最大化、所有約束條件均為“4”。利用

所有約束條件化為等號的方法,在每個約束條件的左端加一個松弛變量，并整理,

重新對變量及系數矩陣進行編號，得

Xl+&M+Mm+I+???+——=優

%2+。2,小+/,向+…+。2,/“=%

<......

X,”+65+內“+|+-+amnxn=bm

Xj>0,7=1,2...,/?

將其與目標函數的變換形式

—z+C[X]+c2x2+...,+cmxm+cm+lxm+l+...,+cnxn—0組成n+1個變量、”?+1個方程

的方程組。若將z看成不參與基變換的基變量，它與玉,々,…,x,“的系數構成一個

基，利用初等變換將。,。2,…,c,"變為零，則可得

-z項xx4+1-X”b

2-,n

010...0ain仇

001...0a2,m+\?,a2nb2

b

a,n

000...1,nn

100...0C〃J+1-e,

Z=1i=\i=\

據此，可設計如下的數表

C

J%,。+1%

qn

CBXBb4+】x.

1…0…a

GXi仇a\,m+\

0…0a

c2x2b22,m+\…的“%

??????.................???????????????

01

c,"x,“b,?

0…***"i

CJ~ZJ

c,“+i-

r=lz=i

X8列表示基變量，在這里為花,々,…,X,“；

CB列為基變量用，z，…,X,“對應的價值系數；

匕列為約束方程的右端項；

C,行為所有變量的價值系數；

。，列的數字是在確定換入變量后，按。規則計算后填入；

最后一行為各變量的檢驗數，尤其要注意的是非基變量的檢驗數。

例，求解

maxz=2匹+3x2

x1+2X2<8

4x)<16

4X2<12

Xj,x2>0

首先將其轉換為標準形式,

maxz=2/+3x2+Ox3+0x4+Ox5

Xj+2X2+x3=8

+X4=16

*

4X2+x5=12

.西，工2，%3，》4，》5>0

構造初始單純形表如下：

J23000

仇

gXBh*2￡X5

0當8121004

0X41640010-

0X5120⑷0013

CJ-ZJ23000

由上表可得初始基可行解

X(°)=(0,0,8,16,12)7

由于占和X2的檢驗數大于零，表明上述解不是最優解，由于X2的檢驗數更

大，所以，先以它為換入變量。根據。規則，可確定/為換出變量，計算得新表

如下：

Cj23000

仇

X

CBXBbx2X3X45

0X32[1]010-1/22

0X416400104

3X2301001/4-

CJ-ZJ2000-3/4

可得新解X(D=(0,3,2,16,0)。目標函數取值Z=9。

七的檢驗數為2,換入。根據。規則，可確定專為換出變量，計算得新表如

下:

CJ23000

2

XBb芯尤3X

CB45

2*21010-1/2-

0800-41[2]4

3X2301001/412

Cj-Zj00-201/4

得新解乂⑵二(2,3,08,0)7目標函數取值z=13O

%的檢驗數為1/4,換入。根據e規則,可確定與為換出變量，計算得：

Cj23000

仇

CBXBb芯尤34X5

2XI41001/40

0X5400-21/21

3x22011/2-1/80

Cj-Zj00-3/2-1/80

得角星X⑶=(4,2,00,4)"目標函數取值w:=14。由于所有的檢驗都小于零,

達到最優。

PS：如果目標函數是求最小化，貝IJ,檢驗數的最優準則為檢驗數大于零。

1.5單純形法的進一步討論及小結

一、人工變量法

如果初始約束條件不全是小于等于號，則不能直接得到初始基（單位基）和

初始基可行解，此時必須要構造人工變量。

在迭代結束后，如果最后基變量中不再含有非零的人工變量，表示原問題有

解；反之，則表示無可行解。

例：

minz=-3%]+x2+x3

X]-2X24-x3<11

—4尤]++2/23

<

-2x）4-x3=1

,x2,x3>0

在第一個約束條件中加入松弛變量X4;在第二個約束條件中加入剩余變量

Z和人工變量4；在第三個約束條件中加入人工變量與0

（1）大M法：

在一個線性規劃問題的約束條件中加入人工變量后，要求人工變量對目標函

數值不產生影響，可假定人工變量在目標函數中的系數為（-M）（M為很大的正

數），這樣在目標函數要實現最大化時，必須將人工變量從基變量中換出，否則

目標函數不會實現最大化。

對上例求解，加入人工變量后，規劃問題變成

minz=-3X]+x2+x3+0x4+Ox5+Mx6+Mx-,

X]-2X2+七+x=11

-4X]+x+2X-x+x=3

<2356

-2x,+x3+x7=1

x],x2,x3,x4,x5,x6,x1>0

然后，利用單純形法求解，詳見P33。

（2）兩階段法

第一階段：不考慮原問題是否有基可行解；給原線性規劃問題加上人工變量

后，構造僅含人工變量的目標函數和要求實現最小化；然后用單純形法求解，若

得到該規劃的最優解為零，說明原問題存在基可行解，否則原問題無可行解，停

止計算。

第二階段：將第一階段的最重計算表出去人工變量，換回原目標函數的系數

作為第二階段計算的初始表，利用單純形法求解。

前一個例子的兩階段法求解如下：

構造出第一階段的數學模型如下：

minz=4+與

X]-2X2+七+x=11

—4X]+X2+—%+4—3

*

—2Xj+X3+匕=1

Xj,X2,X3,X4,X5,X6,X7>0

Cj0000011a

CBXBbx2當x4X54X]

0Z111-21100011

13-4120-1103/2

1X71-20[1]00011

CJ-ZJ6-1-30100

J0000011

a

CBXBb占X2￡X4X5X7

0乙103-20100-1-

1410[1]00-11-21

01-2010001-

CJ-ZJ0-100100

Cj0000011

CBXBb占x2x3X4X5x7

0123001-22-5—

0x210100-11-21

0x31-2010001—

00000

cj-zJ11

得最優解X=(0,1,1,12,0,0,0)，0由于人工變量43=0,說明

X=(0,1,1,12,0)T是原問題的基可行解，可進行第二階段運算0利用單純形法，從

下表開始：

J-31100e；

CBXBb修X2X4X5

0福12[3]001-2-

1X210100-11

1七1-20100-

Cj-ZJ-10001

CJ-31100

CBXBbX|X2X3X4X5

-3為41001/3-2/3-

1/10100-11

1與90012/3-4/3-

Cj-Zj0001/31/3

二、解的退化

所有的檢驗數均40

1、基變量中有非零的人工變量，無可行解；

2、某非基變量的檢驗數為零，有無窮多解；

對于任一檢驗數＞0,若對應的系數向量號=0,則有無界解。

單純形法小結

>0不需處理

變量XL。令x'j=-Xj；Xj>0

Xj無約束令Xj=X：-X：,Xj,x：>0

bNO不需處理

約束條件

b<0約束條件兩端同乘7

<加松弛變量與

=加入工變量龍山

減剩余變量,加人工變量

>

%

maxz

minz

目標函數

加入變量的系松弛變量/0

數人工變量%-M

第三章運輸問題

1、教學計劃

第2次課2學時

第三章

授課章節

授課方式□V理論課口討論課口實驗課口習題課□其他

掌握運輸問題的模型特點；熟悉表上作業法的基本步驟如初始調運方

課堂教學

案的確定，非基變量檢驗數的確定方法，當前解是否最優解的判斷，

目的及要求

閉回路調整方法；非平衡運輸問題的求解。

重點：初始調運方案的確定，非基變量檢驗數的確定，判斷當前解

課堂教學

是否最優解，閉回路調整方法，非平衡運輸問題的求解方法。

重點及難點

難點：初始基可彳丁解日勺確定、判斷，非平衡問題日勺不解思路。

教學過程教學方法及手段

多媒體講解

3.1運輸問題的提出及其模型特征

運輸問題的提出背景及其模型特征

3.2運輸問題的求解：表上作業法實例講解

教學過程表上作業法的思路和步驟如初始基可行解

的確定（最小元素法和伏格爾法），最優解的判

斷方法，閉回路調整方法。

3.3產銷不平衡的運輸問題

將不平衡問題轉化為平衡問題。

2、教案

3.1運輸問題的提出及其模型特征

1、背景

大規模的物資調運，將物資從生產地點運往消費地點，要求在現有的交通網

絡下，制定出總費用最小的運輸方案。

2、模型特征

12…〃產量

1C[[G2C]“

c

22Q2

:?

2c〃

加

肖

A量

-

t

2

"

ZX

J=1

川

zA?1

X-jJ-1,2

f="l

12

zX=Q=1

/=l

X>o

一

mX"個變量，機+〃個約束方程，但由于總產量等于總銷量的關系存在，所

以，獨立的約束方程為m+〃-1,因此，其可行解中的基變量個數必然是

系數矩陣：變量局的系數向量舄除第，個分量和第優+j個為1外其余為零。

3.2運輸問題的求解：表上作業法

表上作業法實際上是單純形法在求解運輸問題時的一個簡化，主要步驟：

（1）找出初始基可行解：最小元素法和伏格爾（Vogel）法

最小元素法：優先滿足運價最小的供銷關系

例：

\銷地產量（噸）

B,B2B3B4

產地\

A,3113107

A219284

A3741059

銷量（噸）3656

肖地產量（噸）

B,B2B3B4

產地

A,3113107

Ai9284

(1)

(3)

A3741059

銷量（噸）3656

肖地產量（噸）

B,B2BaB4

產地

A,3113107

A984

2?d)②

(3)(1)

741059

A3

銷量（噸）3656

、銷地產量（噸）

B,B2B3B,

產士廣、

A,311107

(4)

A?984

-(t>?

(3)(i)

A3741059

銷量（噸）3656

\銷地B,產量（噸）

B2B3B4

產地\

*

A,311107

③

(4)

42984

-?②

(3)(1)

A371059

@

(6)

銷量（噸）3656

\銷地B,產量（噸）

B2B3B4

產地\

\

A,3fl107

(3)

(4)

A?984

-e②

（3）(1)

A37109

3（5）

(6)(3)

銷量（噸）3656

\銷地B.產量（噸）

B2B3B4

產地

A.437

A2314

A3639

銷量（噸）3656

伏格爾法：優先滿足最小運價與次小運價差值最大的行、列中的最小運價所對應

的供銷關系。

\銷地

B,B2B3B4行差

產地、

A,3113100

A?19281

A37④1051

列差2513

（2）求各非基變量（空格）的檢驗數。

閉回路法：首先找到與空格對應的閉回路，規則是從要檢驗空格出發用水平或垂

直線向前滑，碰到數字格轉90度（也可不轉，空格處絕不轉），最后回到出發空

格形成閉回路。然后，在該空格處試著增加1單位運量，并保持平衡，在閉回路

作相應的調整，調整后回路的總運費相對于調整前的變動量就是該空格的檢驗數

B2B3B4產量（噸）

43

1③

3

銷量（噸）3656

銷地產量（噸）

B,B2B3B4

產地

A、7

A?34

Aa⑤69

銷量（噸）3656

如空格A3B1的檢驗數:7*1-5*1+10*1-3*1+2*1-1*1=10

空格AzB,的檢驗數:8*1-2*1+3*1-10*1=-1

位勢法:

構造位勢（/,（/=1,2…m）和V.（；=1,2…〃）；由基變量的檢驗數C?-（6+匕）=0,

可得g=6+匕；任取U4=l,2…〃2）、匕（j=1,2…〃）其中之一為零,可求得其

他U,（i=l,2…⑼、匕（）=1,2…〃）；最后，由。廠“+匕）可求得個非基變量（空

格）的檢驗數。

BiB2B3B4

1131010

(-8+10)-(10-1)

A219-(9-1)28-(9+0)9

A37-(-8+5)410-(-7+5)55

V,-80

（3）若存在檢驗數為負的空格，用閉回路法進行調整，檢驗數最小的空格優先

調整。調整時，以相應的空格位調入格（以它對應的非基變量為換入變量），以

相應的閉回路進行調整，調入量為閉回路中數字格中所能調出量的最小者。

\銷地產量（噸）

B,B2B3B4

產地、

A,437

A2314

A3639

銷量（噸）3656

三、運輸問題的特殊情況：

1、多重解

當非基變量的檢驗數為零時，會出現多重解。

2、退化

①當在某空格處填入數值時，恰好該處供應量等于需求量，在此填入相應的數值

時須同時劃去一行一列，此時，必須在劃去的該行、該列的任意空格處添一個零。

②閉回路調整時，如出現兩個或兩個以上調出格的數值相等，此時只能選擇其中

一個作為調出格，另一個格中必須填零。

3.3產銷不平衡的運輸問題

相對于標準形式的運輸問題，產銷不平衡問題的求解關鍵在于將其轉化為標

準形式的運輸問題，即產銷平衡問題。

如果是產量大于銷量，則可增加一個虛擬銷地，任何運往虛擬銷地的產量等

同于就地儲存，因此，所有產地運往虛擬銷地的運費為0。

如果是銷量大于產量，則可增加一個虛擬產地，由虛擬產地運往各銷地的運

量實際上就是供給的缺口，表示現實中沒有實際的供給，因此，由虛擬產地運往

各銷地的運費為0o

產銷不平衡問題轉化為產銷平衡問題之后，利用表上作業法進行求解的思路

和步驟和前一節的內容完全相同。

\銷地B,B2B3B4B5產量（噸）

產地\

A.31131007

42192804

Aa7410509

銷量（噸）36533

如果存在某些特定的約束，如某地存在一個最低的需求，則應注意該部分不

能由虛擬產地供給，即，虛擬產地運往該地的單位運輸費用應用是一個很大的正

數M。

、\辱求地區1234產量

化肥廠

A1613221750

B1413191560

C192023M50

D50

最低需求3070010

最局需求50703060

求地區1，1”234'4”產量

化肥廠

A16161322171750

B14141319151560

C19192023MM