运筹学完整教案

第一章线佐规划与单纯形法

L按学计划

第T—次课-2学,时

结论；第一章第1下、第2工、第3节

授课生节

授课方式□7理论课□词论课口实验课口习题课□其他

了解线性规划模型的背景、掌握建模方法以及线性规划的标准形式。

课堂教学

掌握两个决策变量线性规划问题可行域（凸柒）、最优解的位置；了^尢解（无界解、无可行解）、自解（唯

目的及要求

—哈王.书名个解〉由n.何章We

重点：线性规划的数学模型及其标准形。在数学模型中,要求熟悉矩阵形式：在标准形中,要求学生掌握

课堂教学非标准形式的刀中具体情形及其相应的标准化万法；如何用几何的方法求两个决策娈量的线性规划问题的

最优解。

重点及难点

难点：线性规划的基本概念,例如基、基变量、基解、基可行解和可行基：多个最优解如何表示。

教学过程教学方法及手段

引言

多媒体讲解

运筹学医型.运筹学发展历史与现状,研究方法：考核方法与教学大

纲等。

实例讲解

1.1线性规划问题及其数学模型

教学过程

线性粉划的数字模型：

变呈的确定、约束条件与目标函数。

1.2线性规划问题的标准形式

线性规划的标准形式及非标准形式的标准化处理。

1.3线性规划可题的解

基、基娈量、基解、基可行解和◎行基.

络收课一^时

第一章第4节

授课苛节

授课方式□、,理论课□讨论课口实验课。习题课口其他

课堂教学掌握单纯形法思想以及具体操作过程。

目的及要求

课堂教学雷点：隼纯形法迭代过程：（1）换入基变量的确定；（2）换出基变量的确定；（3）判定当前解己经最优。

重点及难点难点：单纯形法思想。

教学过程教学过程教学方法及手段

1.4单臾形法

多媒体讲解

单纯形数表的构造,要注意代数形式和表格形式的一一对应性。

实例讲解

单纯形法迭代过程：（1）涣入基变量的确定；（2）怏出基变录的确定；

（3）判定当前解已经最优。

新欣课一^时

第一苣第5节

授课堂节

授课方式□《理论课□讨论课口实给课。习题课□其他

课堂教学掌握人工变盘法的基本思想以及大M法和两阶段法的求解。

目的及要求

课室教学毒点：人工变良法的基本思想。

重点及难点难点：大M法和两阶段法的求解。

教学过程教学方法及手段

多媒体讲解

1.5单纯形法的进一步讨论及小结

教学过程

人工变量去的思想,大M法和两阶段法的求解思路和步骤。实例讲解

单纯形法小结

2、课件

11然性规划问题及其数学模型

级性规划模型的建立就是将现实同领用数学的语言表达出来。

例I：某工厂要安排生产【、［两种产品,每单位产品生产所需的设备、材料消耗及其利润如下表所示。问应如何安排生产

计划使工厂获利最多?

1II

设备128台时

原材料4016kg

A

原材料B0412kg

单位产品的利润：兀）23

解：设生产产品1、n的数量分别为X1和x?

首先.我们的目标足要获得国大利润，斯

maxz2x3x

i

其次,该生产计划受到一系列现实条件的约束.

设备台时约束：生产所用的设备台时不用超过所糊台的设备台洞,如

x2x8

12

原材料约束：生产所用的两种源忖料B不行超过用用有的原材料总数.即

4x16

।

4x12

2

非负约束：■湎的旺3被必，痴排负的r即

x.x0

12

由此可得该问题的数学规划模箜：

maxz2x3x

l2

x2x8

I2

4x16

4x112

2

x,x0

I2

总，结：

线性规划的一股建模步骡如下

(I)魂定决策变望

确定决策变星就是将问题中的未知堡用变量来表示.如例1中的Xi和x?。确定决策变星是建立数学规划模型的关键所在。

(2)储定目标函数

确定目标函数就是将问题所追求的目标用决策变量的函数表示出来。

(3)确定约束条件

将现实的约束用数学公式表示山来。

线性规划数学模型的特点

(1)有一个追求的目标,该目标可表示为一组变量的线性曲数,根据问题的不同.追求的目标可以是最大化.也可以是最

化。

(2)问磔中的的束条件表示现实的限制，可以用线性等式或不等式表示。

(3)问题用一组决策变量表示一神方案,一般说来.问题有多神不同的建选方案,线性规划模型正式要在这众多的万案中找

到最优的决策方案(便目标函数最大或最小'从选择方案的角度肯，这是规划问霞.从目标国数最大或最小的角度看,这是最

优化问卷.

1.2线性规划问题的标准形式

根据问题的性质，线性规划有多种形式，目标函数有要求最大化的，也有要求最小化的；约束条件可以是或"”

的不等式，也可以是三'；虽然决策变量一般是非负的，但也可是无约束的，即,可以在(')取值。为了分析问题的

简化，一般规定如下的标准形式：

max;LCXCX…CX

1122nn

axax...axb

iti122In1I

axax...)QXb

2112222nn2

axax“XXb

mlIm22mnnm

X,X,..x0

I2n

非标准形式转化为标准形式：

（|）若目标函数要求实现最小化minz.则可令z'z可将原问题也目标函数转化为maxz1即可。

（2）若约束方程为“”.则可在•”的左边加上非负的松弛变量；若约束万程为“则可在•”的左边减去非

负的剩余变呈。

（3）若存在取值无约束的变量X,则可令xxX"X',X"0

kkkk**kk

例：将如下问题转化为标准形式：

minzx2x

12

2x3x6

I2

xx4

I2

xx3

XIO,X无约束

2

解：

首先，用二X4替换X2.其中,X$40；

其次,在第一个约束条件的左院加上非负的松弛变星

再次.在第二个约束条件的左建减去非负的刺余变量x；

6

最后.令z'Z,招求minz或为求max4由此，可得标准形如下：

maxz'x2x2xOxOx

i3456

2x3x3xx6

I345

XXXx4

I346

xxx3

134

XK,x,x,x0

13456

13线性规划问题的解

首先.符线性问题的标准形式用矩阵和向重形式表示如下:

maxzCX

AXB

X0

其中C(C,CX(XK，.必Bbb,.b>

12*n12n12m

aa...a

II12In

aa...a

A21222n

aa…a

mlm2mn

L可行解和最优解

满足约束条件的所有解X（x।,x%加网西线性规划问题的可行解，其中•使目标函数达到最大的可行解成为

最优解。

2、基和基解

设A为约束万程组的mn维矩阵,其秩为m。设B为矩阵A中的mm阶非奇异于矩阵（|B。）,则称B

为线性规划的一个基。

不妨设前m个变量的系数矩代为线性规划的一个基.则XR（X；X2，M）T为对应于这个基的基变量。用高斯

消去法可求得一个解

X（X,X,,.X0,.O）r

I2n

该解得非零分量的数目不大于方程个数m,称X为基解。

3、基可行解

若基解X满足非负约束，则称其为基可行解。丸

可行基

对应于基可行解的基.成为可行基。

14单纯形法

一、单纯形表

考家一种最简单的形式：目标函数最大化、所有约束条件均为.…。利用所有约束条件化为等号的方法.在每个约束条件

的左端加一个松弛变量,并整理.重新对变量及系数矩阵进行编号.得

将其与目标函数的变换形式zcqCX...£xCx...,cx。附n1个

||22minIinInn

m

变H、m1个方程的方程组。若将z看成不参与基变换的基变%它与XX,•5的系数用成一个基，利用初等变换

将c；c2”G变孤零,则可得

zxx...xxxb

12mm1n

010...0a...ab

Ijn1In1

001...0a24n1…a2nb2

000...1aab

m.m1ninm

mmm

100...0cca...ccacb

m1iinilnliSIii

i1i1i1

据此,可设计如下的数表

cc•••Cc…c

jrnmln

cX卜x…xx…x

BB1in1n

m

cxbi...oa…a

111IjnIIn1

cxbo...oa...a

2222jn12n2

Cxbo...ia-a

inmmjn1mnm

m

0m・・・in

CZ

jjccacca

m1im1niin

i1i1

又口列表示基变量,在这里为X

nI2

CfJ为基变量X1K%X,对肉的价值系数;

b列为约束方程的右端I页；

Cj行为所有变H的价值系数；

i列的数字是在确定换入变量后，按规则计算后填入；

最后一行为各变营的检验数，尤其要注意的是非基变量的检胎领。

例,求解

maxz2x3x

x2x8

I2

4x116

4x12

2

x,x0

12

首先将其转换为标准形式.

maxz2x3xOxOxOx

12345

x2xx8

123

4xx16

14

4xx12

25

x,x,x,x,x0

12345

泡道初始单纯形表如下：

Cj23000

CXbxxXXX

BB12345

0X81

1004

3

0X1640010

4

X

012014)0013

5

CjZj2000

由上表可得初始基可行解

X<o)(pO8J6J2)r

由于X［和X的检验数大于零,表明上述解不是最优解.由于X2的检骆数更大.所以,先以X2为换入变量。根想规

则,可确定X$为换出变量,计算得新表如下:

c.2

J3000

CXbXXXXX

BB12345

X

020i0-1/22

3in

0X16400104

4

3X301001/4

2

CZ

2000-3/4

可得新解X。)O32J60)r,目标函数取值z9。

X的检脸数为2.换入。根据规则,可确定x为换出变量,计算得新表如下

13

C

23000

j

i

CXbXXXXX

BB1234

010-1/2

2X21

1

0X800-41⑵4

4

X

3301001/412

2

CZ

00-201/4

jj

行新解⑵(?3P80)r.目标函数取值Z13

0

X

规则,可确定为换出变量.

*御检验数为1/4,换入。根据X3计算等：

C

23000

i

CXbXXXXX

BB12345

2X4

1001/40

1

0X400-21/21

5

3X2011/2-1/80

2

CL

00-3/2-1/80

jJ

得解X<3)(42004”.目标函数取值z14。由于所有的检验都小于零,达到最优.PS：如

果日标函数是求最小化.则,检脸数的成忧波则为检典数大于零“

单纯形法的进一步讨论及小结

一、人工娈量法

如果初始约束条件不全足小于等于号，则不能直接得到初始基(毋位基)和初始基可行解,此时必须要构造人工变量。在

迭代结束后,如果最后基变量中不再含有非零的人工变量，表示原问题与解；反之，则表示无可行解。

例:

minz3xxx

123

x2xx11

123

4xx2x3

123

2xx1

13

x,x,x0

I23

在第一个约束条件中加入松弛变里X4；在第二个均束条件中加入剩余变盘X5和人工变量*6；在第三个约束条件中加入

X

人工变虽7o

(I)大M法:

在一个线性规划问题的约束条件中加入人工变量后,要求人工变量对目标函数值不产生影响.可假定人工变量在目标齿数中的

系数为GM)(M为很大的正数),这样在目标函数要实现最大化时，必须招人工变量从基变量中换出，否则目标函数不会实现最

大化。

涧上例求解.加入人工变量后,规划问题变成

minz3xxxOxOxMMx

I23457

X

X2xXX11

123

4xX2xXx3

i2356

2xXX1

i37

x,x,X,x,x,x,x0

1234567

然后,利用单纯形法求解,详见P33。

(2)时阶段法

第一阶段：不考虑原问题是否有基可行解；给原线性规划问题加上人工变星后,构造仅含人工变量的目标函数和要求实现最

小化：然后用单纯形法求解.若得到该规处闱最优解为零.说明原问题存在基可行解.否皿」原问题无可行解.停止计篓。

第二阶段：将第一阶段的最重计算表出去人工变量.换回原目标的数的系数作为第二阶段计算的初始表.利用单纯形法求解。

前一个例子的两阶段法求解如下：

均造出第一阶段的数学模型如下：

minzxx

67

x2xXX11

123

4xx2xxx3

12356

2xXX1

i37

x,x,x,x,x,x,x0

1234567

C

j000001

cXbXXXXXX

BB1234567

X

0111-211000II

34120-1103/2

6

X

1-20HI00011

7

CZ

6-I-30100

jj

c

0000011

j

cXbXXXXXXX

BB1234567

X

0io3-20100-1-

4

X

1i0(II00-11-21

6

X

0i-20I0001-

3

cz

0-100100

jj

000001i

j

cXbXXXXXXX

BB1234567

X

0123001-22-5-

4

0Xlni0n-i1-71

2

X

01•2010001-

3

00

()00

c.z11

JJ

x

得最优解X(032000”由于人工变量xQ说明x(0JJJ20)r是原问题的基可

67

行解,可进行第二阶段运算。利用单纯形法，从下表开始:

C

-31100

j

CXbXXXXX

BB1234<

0X12

131001-2

4

1x,0100-1

2

1八)-20100-

3

CZ01

-100

jj

00

c-311

j

i

CXbXXXXX

BB12345

-3X&

1001/3-2/3-

1

1x,0100-11

2

)X90012/3-4/3-

3

CZ

0001/31/3

JJ

二、解的退化

所有的检验数均°

1、基变量中有非零的人工变量.无可行解：

2、臬非基变量的检验数为零,有无穷多解；

0p°,则有无界解。

对于任一检配涿U.若对应的系数向量「j

单纯形法小结

x0不需处理

J

变量Xj0小X，xX0

7jj'J

X无约束今XXX,X',X"0

.9