《運籌學(xué)》教案

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

第一章線性規(guī)劃與單純形法

1、教學(xué)計劃

第_J一次課2學(xué)時

緒論；第一章第節(jié)、第節(jié)、第節(jié)

授課章節(jié)123

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

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

課堂教學(xué)掌握兩個決策變量線性規(guī)劃問題可行域（凸集）、最優(yōu)解的位置：了

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

意義。

重點：線性規(guī)劃的數(shù)學(xué)模型及其標準形。在數(shù)學(xué)模型中，要求熟悉

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

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

重點及難點規(guī)劃問題的最優(yōu)解。

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

可行基；多個最優(yōu)解如何表示。

教學(xué)過程教學(xué)方法及手段

引言多媒體講解

運籌學(xué)模型，運籌學(xué)發(fā)展歷史與現(xiàn)狀，研究

方法；考核方法與教學(xué)大綱等。

實例講解

1.1線性規(guī)劃問題及其數(shù)學(xué)模型

線性規(guī)劃的數(shù)學(xué)模型：

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

1.2線性規(guī)劃問題的標準形式

線性規(guī)劃的標準形式及非標準形式的標準

化處理。

教學(xué)過程1.3線性規(guī)劃問題的解

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

1.4單純形法

單純形數(shù)表的構(gòu)造，要注意代數(shù)形式和表格

形式的---對應(yīng)性。

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

（2）換出基變量的確定；（3）判定當(dāng)前解已經(jīng)

最優(yōu)。

1.5單純形法的進一步討論及小結(jié)

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

解思路和步驟。

單純形法小結(jié)

2、教案

1.1線性規(guī)劃問題及其數(shù)學(xué)模型

線性規(guī)劃模型的建立就是將現(xiàn)實問題用數(shù)學(xué)的語言表達出來。

例1：某工廠要安排生產(chǎn)I、II兩種產(chǎn)品，每單位產(chǎn)品生產(chǎn)所需的設(shè)備、材

料消耗及其利潤如下表所示。問應(yīng)如何安排生產(chǎn)計劃使工廠獲利最多？

III

設(shè)備128臺時

原材料A4016kg

原材料B0412kg

單位產(chǎn)品的利潤（元）23

解：設(shè)生產(chǎn)產(chǎn)品I、II的數(shù)量分別為不和

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

maxz=2陽+3x2

其次，該生產(chǎn)計劃受到一系列現(xiàn)實條件的約束，

設(shè)備臺時約束：生產(chǎn)所用的設(shè)備臺時不得超過所擁有的設(shè)備臺時，即

%1+2X2<8

原材料約束：生產(chǎn)所用的兩種原材料A、B不得超過所用有的原材料總數(shù),

4%,<16

4X2<12

非負約束：生產(chǎn)的產(chǎn)品數(shù)必然為非負的,即

%i，x2>0

由此可得該問題的數(shù)學(xué)規(guī)劃模型：

maxz=2匹+3x2

匹+2X2<8

4玉<16

4X2<12

x],x2>0

總結(jié):

線性規(guī)劃的一般建模步驟如下：

（1）確定決策變量

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

確定決策變量是建立數(shù)學(xué)規(guī)劃模型的關(guān)鍵所在。

（2）確定目標函數(shù)

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

（3）確定約束條件

將現(xiàn)實的約束用數(shù)學(xué)公式表示出來。

線性規(guī)劃數(shù)學(xué)模型的特點

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

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

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

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

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

數(shù)最大或最?。?，從選擇方案的角度看，這是規(guī)劃問題，從目標函數(shù)最大或最小

的角度看，這是最優(yōu)化問題。

1.2線性規(guī)劃問題的標準形式

根據(jù)問題的性質(zhì)，線性規(guī)劃有多種形式，目標函數(shù)有要求最大化的，也有要

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

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

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

maxz=CjX）+c2x2+

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

+。22占+…,=b）

<

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

xi,x2,...,xn>0

非標準形式轉(zhuǎn)化為標準形式：

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

函數(shù)轉(zhuǎn)化為maxz'即可。

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

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

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

例：將如下問題轉(zhuǎn)化為標準形式：

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線性規(guī)劃問題的解

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

maxz=CX

AX=B

\X>0

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

a

°]2…\n

aa

A=“2122…2n

_am\am2…amn_

1、可行解和最優(yōu)解

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

中，使目標函數(shù)達到最大的可行解成為最優(yōu)解。

2、基和基解

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

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

不妨設(shè)前〃?個變量的系數(shù)矩陣為線性規(guī)劃的一個基，則XR=區(qū)…

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

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

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

3、基可行解

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

4、可行基

對應(yīng)于基可行解的基，成為可行基。

1.4單純形法

一、單純形表

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

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

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

Xl+&M+Mm+I+???+——=優(yōu)

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

<......

X,”+65+內(nèi)“+|+-+amnxn=bm

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

將其與目標函數(shù)的變換形式

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

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

基，利用初等變換將。,。2,…,c,"變?yōu)榱悖瑒t可得

-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=\

據(jù)此，可設(shè)計如下的數(shù)表

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,“對應(yīng)的價值系數(shù)；

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

C,行為所有變量的價值系數(shù)；

。，列的數(shù)字是在確定換入變量后，按。規(guī)則計算后填入；

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

例，求解

maxz=2匹+3x2

x1+2X2<8

4x)<16

4X2<12

Xj,x2>0

首先將其轉(zhuǎn)換為標準形式,

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

Xj+2X2+x3=8

+X4=16

*

4X2+x5=12

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

構(gòu)造初始單純形表如下：

J23000

仇

gXBh*2￡X5

0當(dāng)8121004

0X41640010-

0X5120⑷0013

CJ-ZJ23000

由上表可得初始基可行解

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

由于占和X2的檢驗數(shù)大于零，表明上述解不是最優(yōu)解，由于X2的檢驗數(shù)更

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

如下：

Cj23000

仇

X

CBXBbx2X3X45

0X32[1]010-1/22

0X416400104

3X2301001/4-

CJ-ZJ2000-3/4

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

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

下:

CJ23000

2

XBb芯尤3X

CB45

2*21010-1/2-

0800-41[2]4

3X2301001/412

Cj-Zj00-201/4

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

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

Cj23000

仇

CBXBb芯尤34X5

2XI41001/40

0X5400-21/21

3x22011/2-1/80

Cj-Zj00-3/2-1/80

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

達到最優(yōu)。

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

1.5單純形法的進一步討論及小結(jié)

一、人工變量法

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

初始基可行解，此時必須要構(gòu)造人工變量。

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

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

例：

minz=-3%]+x2+x3

X]-2X24-x3<11

—4尤]++2/23

<

-2x）4-x3=1

,x2,x3>0

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

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

（1）大M法：

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

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

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

目標函數(shù)不會實現(xiàn)最大化。

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

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）兩階段法

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

后，構(gòu)造僅含人工變量的目標函數(shù)和要求實現(xiàn)最小化；然后用單純形法求解，若

得到該規(guī)劃的最優(yōu)解為零，說明原問題存在基可行解，否則原問題無可行解，停

止計算。

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

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

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

構(gòu)造出第一階段的數(shù)學(xué)模型如下：

minz=4+與

X]-2X2+七+x=11

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

*

—2Xj+X3+匕=1

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

Cj0000011a

CBXBbx2當(dāng)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

得最優(yōu)解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

二、解的退化

所有的檢驗數(shù)均40

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

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

對于任一檢驗數(shù)＞0,若對應(yīng)的系數(shù)向量號=0,則有無界解。

單純形法小結(jié)

>0不需處理

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

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

bNO不需處理

約束條件

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

<加松弛變量與

=加入工變量龍山

減剩余變量,加人工變量

>

%

maxz

minz

目標函數(shù)

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

數(shù)人工變量%-M

第三章運輸問題

1、教學(xué)計劃

第2次課2學(xué)時

第三章

授課章節(jié)

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

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

課堂教學(xué)

案的確定，非基變量檢驗數(shù)的確定方法，當(dāng)前解是否最優(yōu)解的判斷，

目的及要求

閉回路調(diào)整方法；非平衡運輸問題的求解。

重點：初始調(diào)運方案的確定，非基變量檢驗數(shù)的確定，判斷當(dāng)前解

課堂教學(xué)

是否最優(yōu)解，閉回路調(diào)整方法，非平衡運輸問題的求解方法。

重點及難點

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

教學(xué)過程教學(xué)方法及手段

多媒體講解

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

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

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

教學(xué)過程表上作業(yè)法的思路和步驟如初始基可行解

的確定（最小元素法和伏格爾法），最優(yōu)解的判

斷方法，閉回路調(diào)整方法。

3.3產(chǎn)銷不平衡的運輸問題

將不平衡問題轉(zhuǎn)化為平衡問題。

2、教案

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

1、背景

大規(guī)模的物資調(diào)運，將物資從生產(chǎn)地點運往消費地點，要求在現(xiàn)有的交通網(wǎng)

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

2、模型特征

12…〃產(chǎn)量

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"個變量，機+〃個約束方程，但由于總產(chǎn)量等于總銷量的關(guān)系存在，所

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

系數(shù)矩陣：變量局的系數(shù)向量舄除第，個分量和第優(yōu)+j個為1外其余為零。

3.2運輸問題的求解：表上作業(yè)法

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

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

最小元素法：優(yōu)先滿足運價最小的供銷關(guān)系

例：

\銷地產(chǎn)量（噸）

B,B2B3B4

產(chǎn)地\

A,3113107

A219284

A3741059

銷量（噸）3656

肖地產(chǎn)量（噸）

B,B2B3B4

產(chǎn)地

A,3113107

Ai9284

(1)

(3)

A3741059

銷量（噸）3656

肖地產(chǎn)量（噸）

B,B2BaB4

產(chǎn)地

A,3113107

A984

2?d)②

(3)(1)

741059

A3

銷量（噸）3656

、銷地產(chǎn)量（噸）

B,B2B3B,

產(chǎn)士廣、

A,311107

(4)

A?984

-(t>?

(3)(i)

A3741059

銷量（噸）3656

\銷地B,產(chǎn)量（噸）

B2B3B4

產(chǎn)地\

*

A,311107

③

(4)

42984

-?②

(3)(1)

A371059

@

(6)

銷量（噸）3656

\銷地B,產(chǎn)量（噸）

B2B3B4

產(chǎn)地\

\

A,3fl107

(3)

(4)

A?984

-e②

（3）(1)

A37109

3（5）

(6)(3)

銷量（噸）3656

\銷地B.產(chǎn)量（噸）

B2B3B4

產(chǎn)地

A.437

A2314

A3639

銷量（噸）3656

伏格爾法：優(yōu)先滿足最小運價與次小運價差值最大的行、列中的最小運價所對應(yīng)

的供銷關(guān)系。

\銷地

B,B2B3B4行差

產(chǎn)地、

A,3113100

A?19281

A37④1051

列差2513

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

閉回路法：首先找到與空格對應(yīng)的閉回路，規(guī)則是從要檢驗空格出發(fā)用水平或垂

直線向前滑，碰到數(shù)字格轉(zhuǎn)90度（也可不轉(zhuǎn)，空格處絕不轉(zhuǎn)），最后回到出發(fā)空

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

作相應(yīng)的調(diào)整，調(diào)整后回路的總運費相對于調(diào)整前的變動量就是該空格的檢驗數(shù)

B2B3B4產(chǎn)量（噸）

43

1③

3

銷量（噸）3656

銷地產(chǎn)量（噸）

B,B2B3B4

產(chǎn)地

A、7

A?34

Aa⑤69

銷量（噸）3656

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

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

位勢法:

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

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

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

格）的檢驗數(shù)。

BiB2B3B4

1131010

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

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

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

V,-80

（3）若存在檢驗數(shù)為負的空格，用閉回路法進行調(diào)整，檢驗數(shù)最小的空格優(yōu)先

調(diào)整。調(diào)整時，以相應(yīng)的空格位調(diào)入格（以它對應(yīng)的非基變量為換入變量），以

相應(yīng)的閉回路進行調(diào)整，調(diào)入量為閉回路中數(shù)字格中所能調(diào)出量的最小者。

\銷地產(chǎn)量（噸）

B,B2B3B4

產(chǎn)地、

A,437

A2314

A3639

銷量（噸）3656

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

1、多重解

當(dāng)非基變量的檢驗數(shù)為零時，會出現(xiàn)多重解。

2、退化

①當(dāng)在某空格處填入數(shù)值時，恰好該處供應(yīng)量等于需求量，在此填入相應(yīng)的數(shù)值

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

②閉回路調(diào)整時，如出現(xiàn)兩個或兩個以上調(diào)出格的數(shù)值相等，此時只能選擇其中

一個作為調(diào)出格，另一個格中必須填零。

3.3產(chǎn)銷不平衡的運輸問題

相對于標準形式的運輸問題，產(chǎn)銷不平衡問題的求解關(guān)鍵在于將其轉(zhuǎn)化為標

準形式的運輸問題，即產(chǎn)銷平衡問題。

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

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

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

量實際上就是供給的缺口，表示現(xiàn)實中沒有實際的供給，因此，由虛擬產(chǎn)地運往

各銷地的運費為0o

產(chǎn)銷不平衡問題轉(zhuǎn)化為產(chǎn)銷平衡問題之后，利用表上作業(yè)法進行求解的思路

和步驟和前一節(jié)的內(nèi)容完全相同。

\銷地B,B2B3B4B5產(chǎn)量（噸）

產(chǎn)地\

A.31131007

42192804

Aa7410509

銷量（噸）36533

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

能由虛擬產(chǎn)地供給，即，虛擬產(chǎn)地運往該地的單位運輸費用應(yīng)用是一個很大的正

數(shù)M。

、\辱求地區(qū)1234產(chǎn)量

化肥廠

A1613221750

B1413191560

C192023M50

D50

最低需求3070010

最局需求50703060

求地區(qū)1，1”234'4”產(chǎn)量

化肥廠

A16161322171750

B14141319151560

C19192023MM