运筹学教案设计

《运筹学》教案

（本教案适用于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