运筹学教学课件

第二章线性规划

主要内容：1、线性规划问题及数学模型

2、线性规划问题的解及其性质

3、图解法

4、单纯形法

5、大M法和两阶段法

重点与难点：线性规划数学模型的建立：一般形成转化为标准型的方法：单纯形法

的求解步骤。

要求：理解本章内容，掌握本章重点与难点问题；深刻理解线性规划问题的基

本概念、基本性质，熟练掌握其求解技巧；培养解决实际问题的能力。

§1线性规划的数学模型及解的性质

一、数学模型（一般形式）

例1已知某市有三种不同体系的建筑应予修建，其耗用资源数量及可用的资源限

量如下表，问不同体系的面积应各建多少，才能使提供的住宅面积总数达到最大?

造价（元/n?）钢材(kg/m2)水源(kg/m2)砖（块加）人工（工日/H?）

砖混结构105121102104.5

大板结构137301903.0

大模结构122251803.5

资源限量11000万元2000万千克15000万块14700万块400万工日

解：设三种体系的建筑面积依次为为,工2，七万平方米,

则目标函数为maxz=$+々

105%)+137尤2+122X3<11000

12%1+30X2+25X3<2000

110x,+190X4-180X<15000

约束条件为■23

21Ox,<14700

4.5X]+3X2+3.5X3<400

x.>0j=1,2,3

例2某工厂要安排生产甲、乙两种产品。已知:

煤耗（T"）电耗(kwh/T)油耗(T/T)单价（万元/T）

甲产品9437

乙产品451012

资源限量360T200kwh300T

问：如何安排两种产品的生产数量，才能使总产值最高?

解：设修，工2分别为甲、乙两种产品的生产量：

贝］目标函数为maxz=7%+12x2

9x1+4%2工360

4x1+5x2<200

约束条件为13~十10人於30。

Xj>0,j=1,2

从以上两例可以看出，它们都属于一类优化问题。它们的共同特征：

①每一个问题都有一组决策变量（项…猫）表示某一方案；这组决策变量的值

就代表一个具体方案。一般这些变量的取值是非负的。

②存在一定的约束条件，这些约束条件可以用一组线性等式或不等式来表示。

③都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示;

按问题的不同，要求目标函数实现最大化或最小化。

满足以上三个条件的数学模型称为线性规划的数学模型。其一般形式为：

目标函数max（min）z=c/I+。2》2+…+c”x”

ax

w\+al2x2+---+alnxn<（>>=>1

a2}xx+a22x2+---+a2nxn<（>,=X

约束条件=；；：

+。,“2彳2+…+amnxn<（>=>„,

Xj>0,/=1,2,…,〃

可行解：满足约束条件的一组决策变量，称为可行解。

最优解：使目标函数取得最大（小）值的可行解，称为最优解。

最优值：目标函数的最大（小）值，称为最优值。

二、标准型

(-)问题的标准形式:

maxz=臼玉+c2x2H---Fcnxn

+anx2H---Fa]nxn=bx

如Xi+a22x2+--+a2nxn=b2

%,内+%,2£+…+a,“"x”=bm

XjNO,/=1,2,…,〃

其中bt>0i=1,2,•••,???tn<n

注意：任何一个一般型都可转化为一个标准型。

（二）标准型的表示方法：

n

1、和式形式：叱二斗0

JT

几

£%jXj="（i=1,2,…，加）

<）=1

Xj>0=

LJ

2、矩阵形式：maxz—

AX=b

<

X>0

其中C=[01，,2，•••，]——价格系数向量

bi~

,b2

b=.

*

,——资源向量（限定系数向量）

bm

“21，a22，•一，。2n

A—

约束条件系数矩

aml，am2，.一，amn

阵

X,*2,**■，

J!L・决策变量

3、向量形式：maxz=c/i+44+…+

X1片+元2尸2TX〃Pn=b

<

x.>0

<J

p%

其中♦为约束条件系数矩阵A的第j歹1]。

（三）一般型化为标准型的方法

I、minz=CX

引进新的目标函数Z'=-Z,则可化为maxZ'=-CX

2、不等式约束

①许+ai2x2+・・・+〃.<b{

引进新的非负决策变量，使得无〃+1

沏%+ai2x2+…+ainxn+z+]=々

%〃+i称为松弛变量，在目标函数中，其价格系数为0。

H--------F

②+Qil2ai.nx^n>b.i

引进新的非负决策变量x„+1，使得

%X|+ai2x2+---+ainxn-"

称为剩余变量，在目标函数中，其价格系数为0。

、若〃<°

3即%/]+十以元+…+十沅匕

2=bt<0

aXaX

可变为-aiXxxi22inn=—bi>0

4、若某个变量与无非负限制，称为自由变量。

令Xj=x'j-x"jX；>ox；>0

例3将下列问题化为标准型

maxz=7项+12x2

9.+4X2<360

4、i+5X<200

<2

3x1+10x2<300

%>0,x2>0

解：标准型为

maxz=lxx+12X2+0x3+0x4+0x5

9,+412+X3=360

4x]+5x2+x4=200

<

+10x2+x5=300

lJ>0/=123,4,5

例4将下列问题化为标准型

minz=一七+3X2-7x3

玉-2X2+3X3<7

2%-x2+/24

<

-5X]+%+4X3=6

>0£无约束

解：令Z=—Z,标准型为：

maxz-xx-3X2+7x3+0x4+0x5

X

%-2X2+33+x4=7

2%-x2+x3-x5=4

—5匹+%2+4/—6

,%2，X4,X5>0元3无约束

XQ~~XQ--甘

令J3

则标准型为：

maxz'=X1-3X2+7乂-7^+0x4+0x5

X]-2X2+-3%3+%=7

2xi-x2+%3-%3-x5=4

<

-5x1+々+4%]-4£=6

X],%2，%3，,%5~~~0

三、线性规划问题的解

标准型maxz=CX

AX=b

X>0

a\\"12ain

“21a22。2n

A==［片，尸2,…，

a

aml。m2mnmxn

记P\尸2…Pn

秩rank（A）=mm<n

PilRz，…EmB=［尸〃,巴2，…,Pim］

1、基阵：若列向量是线性无关的，则称为LP

问题的一个基阵。基矩阵中每个列向量称为基向量。

由非基向量组成的矩阵称为非基矩阵，记为N

94100

A=45010

例如:3100

-10o--94-

取耳=色,尸4，尸/=010——线性无关，则M=45

_001310

'91O'-4O"

401——线性无关，则N?=50

52=[P„A^]=

300_101

2、基变量：基矩阵中各列向量对应的变量称为基变量，记为X"=卜”,玉2,…,"了。

如4=忸3，6，4]，则基变量为》3，“4,工5。

对应于非基向量的变量称为非基变量，记为X“=[x”,“+2、x,J

3、基本解：设基矩阵为6=忸,q,…,匕],则非基矩阵N=[4+”•••,？]

A=[B；N]X=B

「x-

那么，约束方程WMB=b即BXB+NXN=8------有无穷解

1XN_

令XN=0贝IJ6XB=/>XB=B7b

RTb

那么，约束方程组的解X=°,将其称为LP问题的基本解。

0

R-1卜

注意：基本解不一定是可行解，若6则称X=为LP问题的基本可行解，

0

对应于基本可行解的基矩阵，称为可行基。

4、最优解：对应于某一可行基，使目标函数获得最优值的基本可行解，称为最优

解。最优解所对应的基矩阵称为最优基。

举例说明：maxz=7x,+12x2+0x3+0x4+0x5

9%j+4X2+九3=360

4xj+5X2+X4=200

3%1+10x2+x5=300

xl,x2,xi,x4,x5>0

9410o-

A—45010

约束矩阵

310001

-100

B1=区，乙，川二010

若取基矩阵

001

94—

W45

则非基矩阵310

基变量

360

B-xb=Ib=b=200

300

...基本解为X=（0,0,360,200,3007是基本可行解

194

若取基矩阵殳=（鸟,4,6）045

0310

00

10

N2

则01

x

X4

84

•.・％/=20

24

/.X=(20,24,84,0,0)7基本可行解

注意：基本可行解与可行域的顶点坐标是一一对应的。

§2图解法--主要解决二维线性规划问题

一、按约束条件，绘出解的可行域图形

maxz=7x,+12x2

9%j+4X2<360

411+5X2<200

3%j+10x2<300

xl9x2>0

可行域：可行解的全体称为可行域。

7Z

Y---------X-I------

将等值线2112沿法线方向向上平移至（2°，24）点时截距最大,

那么最优解为（20,24）I

二、解的情况

最优解有以下几种情况：

（1）有唯一的最优解。

（2）有多个最优解。如上例中，若maxz—4%]+5x2，就有无穷

多解。

（3）有无界解：若有可行解，但无有限最优解，则称其为有无界解（这种情况在约

束条件考虑不周全时出现）。

如：maxz=x]+x2

-+x2<4

<x]-x2<2

%,>0,x2>0

(4)无可行解(约束条件有矛盾)

如：maxz=2+2X2

Xj+X2<1

一2

<x]2X2>

x19x2>0

结论：

①约束集合一定是凸条边形（二维）；

②若有最优解，则一定可在多边形顶点获得。

§3单纯形法

单纯形法的基本思路是：根据问题的标准，从可行域中某个基本可行解（一个顶点）

开始，转换到另一个基本可行解（顶点）；并且使目标函数达到最大值时，问题就得到

了最优解。即

初始顶点X0（可行域一顶点）：型网的幽.>X,,巡喇的财•>x2——>­­——>X*（最优解）

I111

ZoWZ|WX2wwz*

一、单纯形法的求解步骤

（1）寻找初始可行基舔，并计算初始基本可行解；x°=°°="°

L0

（2）检验基本可行解是否最优；

（3）寻找更好的可得基；

（4）重复（2）,（3）。

1、初始可行基的确定

i）若A中含有m阶单位矩阵I，则取B0=Io此时，XBu=B-'b=b20

•，,3。是可行基

ii）若A中不含有m阶单位矩阵，就采用人造基的方法。即增加人工变量把原问题化

为含有/的等价问题。（下一节重点讲）

3x}+x2=8

<

5x}+2X2+3X3=20

例:

x}x2x3>0

需增加人工变量"4'%5化为

因为系数数阵A中不含有单位矩阵,

3/+x2+工4=8

<51]+2X2+3X3+x5=20

>0j=l,2,…,5

<J

010

A-

则|_52

301

叫=（尸4,尸5）=

注意：松驰变量、剩余变量的价值系数取为0,而人工变量的价值系数取值为大M。

2、检验

B-'b

X=

基本可行解0

对应的目标函数值z=cx=c"

0

非基变量价值系数

基变量价值系数：

-X~\[X

对任意可行解X=B变化AX=b为[5N]B=b

_XN__XN_

即BXB+NXN=b

BXB=b-NXNnXH^B-'b-B'NXN

将其代入目标函数得：

r]IXfi]

z=cx=&cj=CBXB+CNXN

_AN_

=—bNxJ+CvX”

=CBB-'b+(CN-CBB'N)XN

-XN>0.•.当Gv-gB—N40时，Z的最大值是C*”

R-l卜

即乂=为最优解。

0

这里，我们称每个％=Cj-C*TPj为检验数。

当8=/时-，基本可行解x=b

0

检验数%-CliB'Pj

第i个基变量的价格系数

第/个非基变量的价格系数

h

如果x=为最优解，则最优值为x*=CM

_oj

判断定理：（对标准型maxZ来讲）

\B-xb

CT.<0X=

（i）若所有/一,则o为最优解。

（2）若所有4°,且有某个°"%二°,则LP问题有无穷多个最优解。

\B-xb

/T>oX=

（3）若有某个U攵/"，则0不是最优解。

⑷当3=/时，若有一个>。，且对一切i=1，2,…，小都

有〃％"°,则有无界解（或无最优解）。

3、基变换：确定新的基矩阵的过程

（1）换入变量的确定

选择bj>°中的最大者所对应的变量X左作为换入变量，即

max^crcr>。｝=（Jk

（2）换出变量的确定：用最小比值规则（。规则）

ekl

设(八)」J(B'P)

则取X［为换出变量

b

0=min<;>0」

当=/时,a，k

6aik,alk

则取xi为换出变量,aik称为主元素

（3）新基矩阵的确定

xxx2%/+1Xn

a\\anaM-\alMa\na\k

ai\a22a2l-\a2M,,,a2na2k

B=

amlam2aml-\aml+\amnamk

如:maxz=7百+12x2+0x3+0x4+0x5

911+4X2+%=360

4%+5X+%=200

<2

32+10%245=300

Xj>0,J=1,2,…,5

■94100-

A=45010

解：［310001

一100

叫=伊3，P4，4)=010

取初始基矩阵八八Y

B-xbb

X==(0,0,360,200,3007

基可行解00

m

cy—c•—/cd-

检验数：JJ乙i1J

z=l

/=q一(。3%1++。5〃31)=7_0=7

+。4。22+。5“32)=12—0—12

巧〉0

**•X不是最优解，换入变量为（丁0"2〉2）

bikb

*:0=min<aik〉0>=

aik

.1360200300、300b.

(4510)10生2

・・换出变量为X5

（基变量中的第3个变量）,主元素为〃32

增广矩阵变换

94100360

45010|200

310001!300

94100360

第3行除10>45010200

0.31000.130

7.8010-0.4240

>2.5001-0.550%4

0.31000.130

100

.B\010=(尸3,尸4尸2)

••新的基矩阵001

新基可行解X=(0,30,240,50,0)7

C

检验数：—\一+，4“21+02。31)

=7—12x0.3=3.4

=0—12x0.1=—1.2

X不是最优解。

二、单纯形表：（将上述过程列成表格，便于理解）

对每一个可行基，作一个单纯形表，包括①基可行解②检验数%③。和主元素。

G。2…C”G"+i…G

Un

CBXBbA142人"iA/n+lM

1

C}x}仇0…0出…％”*

1a

C2x2b20…00,"+1…2n

cmxn,b,n°°…0…amn

%

XB列中填入基变量，这里是无1，12'・・・,九加

列中填入基变量的价值系数，与基变量一一对应，这里是

cc•

b列中填入约束方程组右端的常数；

j行中填入各变量的价值系数Cj,C2,...,Cw;

e列的数字是在确定换入变量后，按。规则计算出来的比值；

ax

j行为检验数行，对应各非基变量j的检验数。

例：（按上例）

maxz=7%j+12x2+Ox3+0x4+Ox5

9%j+4X2+x3=360

4&+5X2+X4=200

3x}+10x2+%=300

x.>0,j=12,--.,5

<J

解:

712000

3

XBbX]xX3X4X5

CB2

0x33609410090

0X42004501040

0X53003[10]00130

%712

0X32407.8010-0.430.77

0x450[2.51001-0.520

12x2300.31000.1100

%3.4-1.2

0x384001-3.121.16

7x,201000.4-0.2

12x224010-0.120.16

-1.36-0.52

最优解为x=(20,24,84,0,0)7

最优值为Z=7x20+12x24=428

§4单纯形法的进一步讨论

一、人工变量法

1、大M法

在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对结目标函数值

不受影响，为此我们假定人工变量在目标函数中的系数为（-M）（M为任意大的正数）,

这样目标函数实现最大化时，必需把人工变量换出。

例5maxZ=3jj-x2-x3

再-2X2+x3<11

V-4匹+4+233>3

—2%|+=1

Xj,x2,x3>0

试用大M法求解

解：化为标准型

maxZ=3xt-x2-x3+0x4+0x5-Mx6-Mx7

X]-2X2+XJ+工4=11

—4%1+%2+2工3-工5+工6=3

—21]+£+X：—1

>0,J=l,2,...,7

3-1-100-M-M

0

CBXBbX1X2X3X4X5X6X7

0X4111-21100011

-MX63-4120-1103/2

-MX71-20[1]0001-1

%3-6M-1+M-1+3M-M

0X4103-10100-1-

-MX610[1]00-11-21

-1X31-2010001-

%1-1+M-M1-3M

0X412[3]001-22-54

-1X210100-11-2-

-1X31-2010001-

*1-1-M-l-M-l

3Xi41001/3-2/32/3-5/3

-1X210100-11-2

-1X390012/3-4/34/3-7/3

%-1/3-1/3-M+l/3-M-l/3

最优解X=（4,1,9）"最优值Z=2

2、两阶段法

前面介绍了大M法，但在电子计算机求解含有人工变量的线性规划问题时，只能

用很大的数代替M,这就可能造成计算上的错误。故再介绍两阶段法。

第一阶段：不考虑原问题是否存在基可行解；给原问题加入人工变量，并构成仅含

人工变量的目标函数0和要求实现最小化，然后用单纯形法求解上述模型，若得到

。=0,这说明原问题存在基可行解，可以进行第二阶段计算。否则，原问题无可行解,

应停止计算。

第二阶段：将第一阶段计算得到的最终表，除去人工变量，将目标函数行的系数换

为原问题的目标函数系数，作为第二阶段计算的初始表。

例6maxz=3/-x2-x3

x}-2X2+x3<11

-4Xj+.+2X>3

*3

-2%j+/=]

%1,x2,x3>0

试用两阶段法求解。

解：第一阶段：

min①=%+/(maxco=-x6-x7)

1]-2X2+/+X4=11

—4xj+X-)+213—尤5+=3

V

—2xj+83+与=1

Xj>0j=12,…,7

0000011e

CBXBbXlX2X3X4X5X6X7

0X4111-21100011

1X63-4120-1103/2

1X71-20[1]00011

6-1-31

0X4103-20000-1-

1X610[1]00-11-21

0X31-2010001-

0-113

0X412[3]001-22-5

0X210100-11-2

0X31-2010001

0011

bj

最优解为X=（0,1,1,12,0,0,0）7

第二阶段：

3-1-100A

cz

CBXBbXiX2X3X4X5

0123001-24

X4

-1X210100-1-

-1X31-20100-

1-1

3X|41001/3-2/3-

-1X210100-11

-1X310012/3-4/3-

-1/3-1/3

原问题的最优解为：X=（4,1,9）7,最优值为Z=2

二、退化（极少出现）

单纯形法计算中用。规划确定换出变量时，有时存在两个以上相同的最小比值，这

样在下一次迭代中就有…个或几个基变量等于零，这就出现了退化解，当出现退化时，

进行多次迭代，而基从与,当，…，又返回到吕，即出现计算过程的循环，使永远达不到

最优解。为解决这个问题我们介绍勃兰特规则：

（1）当存在两个或两个以上最大检验数时，选取力>0中下标最小的非基变量%,为

换入变量，即％=min（加）>0）；

（2）当按。规则计算时，存在两个或两个以上最小比值时，选取下标最小的基变

量为换出变量。

三、单纯形法小结

类型Maxmin

检验数

%=〃一'?(yJ=cj-CliB-'Pj

判别

一切o-j<0,最优一切（7y>0,最优

确定进基变量4q=max{%>0/(yk=min{*<0)

确定出基变量历2。b

0=min<>,=---l0=min-

有唯一最优解

一切(Ty<0一切巴>0

第三章线性规划的对偶理论及灵敏度分析

主要内容：1、对偶问题及其性质；

2、对偶单纯形法；

3、灵敏度分析。

重点与难点：对偶问题与原问题的对应关系，对偶问题的基本性质，对偶单纯形法

的求解步骤，灵敏度分析的方法。

要求：理解线性规划对偶问题的性质，熟练掌握对偶单纯形法的求解步骤和灵

敏度分析的方法和技巧，能够用这些数学方法解决实际问题。

§1对偶问题的对称形式

一、对偶问题

弓I例，某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需要的

设备台时及A、B两种原材料的消耗，该工厂每生产一件产品甲可获利2元，每生产一

件产品乙可获利3元，问应如何安排计划才能使该工厂获利最多？

甲乙

设备128台时

原材料A4016kg

原材料B0412kg

解：设工1、12分别为甲、乙两种产品的产量

则目标函数maxz=2%+3x2

修+2X2<8

4元]<16

<4X2<12

约束条件

x^x2>0

(i)

假设该工取定彳节生产与乙产品，而将其出租或出售。这时要考虑每种资源的

定价问题，设>1'>2'>3分别为出租单位设备台时的租金和出让单位原材料

A、B的附加额。

作一比较：若用一个单位台时和4个单位原材料A生产一件产品甲，可获利2元，

那么生产每件产品甲的第备台时和导材料出租和出让的收入应不低于生产一件甲产品

的利润。即：％+4y2-2

同理，将生产每%产品的身备台时和号材料出租和出让的收入应不低于生产一件

乙产品的利润。即：2yl+4%23

将工厂所有设备台时和资源都出租和出让，其收入为

。=8,+16%+12为

对工厂来说，。越大越好；但对接受者来说，支付的愈少愈好，所以工厂只能在满

足2所有产品的利润前提下，使其总收入尽可能小，才能实现其愿望。为此，得到如下

模型：

min口=8%+16y2+12y3

%+4为22

<2M+4y3>3⑵

y/0,J=1,2,3

我们就称(2)为模型(1)的对偶问题。

一般地，设原问题为

maxz=C]%]+c2x2+・・・+cnxn

+42%2〈仇

a2]xl+a22x2+・・・+。2〃兀〃-^2

内+《“2X2+…+a,“.Z<b,n

>0,j=1,2,…，〃

则其对偶问题为:

minty=4月+b2y2+---+b„yn

知弘+a21y2+---+affllyffl>c,

。22y2+…+册2｛上

<::::

+«2„y2+---+a„„,y,„>c„

y,0,i=1,2,­••,/«

矩阵形式:

原问题对偶问题

maxz=cXminco=Yb

AX\YA>C(实际为A'(2C')

X>0[y>0

二、原问题与对偶问题的关系

原问题（或对偶问题）对偶问题（或原问题）

目标函数maxz目标函数min。

n个n个

变

>0>

<0<

量

无约束=

m个m个

变

<>0

><0

量

=无约束

约束条件右端项目标函数变量的系数

目标函数变量的系数约束条件的右端项

例1求下列问题的对偶问题

minz=2的+3x2-5x3+x4

X[+々-3X3+x4>5

2x+2.-x<4

<l4

x2+x3+x4=6

X]<0,X2,X3>0，Z无约束

解：

max/=5%+4为+6y3

必+2y222

H+为43

一3%+2y2+为“5

)'i一为+%=1

7120,为<0,%无约束

§2对偶问题的基本性质

一、对称性：对偶问题的对偶是原问题。

证：设原问题为maxz=cX

AX<b

<

X>0

则其对偶问题为：niino)=Yb

[YA>C

\y>o

对上式两边取负号，得-minco=-Yb

-YA<-C

、y>0