线性规划模型

线 性 规 划 模 型

一、建立模型

线性规划问题：求多变量线性函数在线性约束条件下的最优值。 线性规划问题的一般形式：

n

minz

n

c

j1

j

xj

s.t. aijxjbi

j1

i1,2,,m

x1,x2,,xn0 [说明] ……

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

n

minz

n

c

j1

j

xj

s.t. aijxjbi(0) i1,2,,m

j1

x1,x2,,xn0

[说明] 任意线性规划问题可化为标准形式。具体如下：

1. 目标函数标准化 maxzmin(z) 2. 约束条件标准化

假设约束条件中有不等式约束

ai1x1ai2x2ainxnbi 或 ai1x1ai2x2ainxnbi

引入新变量xn1,xn2（称为松弛变量），则以上两式等价于以下两式： ai1x1ai2x2ainxnxn1bi ai1x1ai2x2ainxnxn2bi

xn10

xn20

3. 自由变量标准化

若变量xj无约束，可引入两个新变量xj',xj"，令 xjxj'xj",

xj',xj"0.

故以下我们只考虑标准形式，也可以用矩阵形式表示为 minzc'x s.t.

Axb

x0 一般要求，rk(Amn)m,

mn

.

例1 某工厂制造A,B两种产品，制造产品A每吨需用煤9吨，用电4千瓦，3个工作日；制造产品B每吨需用煤5吨，用电5千瓦，10个工作日。已知制造产品A和B每吨分别获利7000元和12000元。现该厂只有煤360吨，电200千瓦，工作日300个可以利用，问A,B两种产品各应生产多少吨才能获利最大？

[解] x1,x2分别表示A,B两种产品的计划生产数（单位：吨），f表示利润（单位：千元），则 f7x112x2

耗煤量为9x15x2，耗电量为4x15x2，耗工作日3x110x2，于是得规划模型： maxf7x112x2

9x15x2360



4x15x2200



3x10x30021x1,x20

s.t.

例2 设某工厂有甲、乙、丙、丁四个车间，生产A、B、C、D、E、F六种产品，根据机车性能和以前的生产情况，得知生产每单位产品所需各车间的工作时数、每个车间在一个季度工作时数的上限以及产品的价格，如下表所示：

问：每种产品每季度各应生产多少，才能使这个工厂每季度生产总值达到最大？

[解] 以x1~x6分别表示每季度生产A、B、C、D、E、F的单位数，于是它们需满足

x10.03x2

x3x4

0.08x5

x6



850700



100

900



0.01

0.02

0.010.010.030.05

0.03

0.02

0.03

0.05

x1,x2,,x60

目标函数为 maxf0.40x10.28x20.32x30.72x40.64x50.60x6 引入松弛变量x7,x8,x9,x10，化成标准型

ming0.40x10.28x20.32x30.72x40.64x50.60x6

0.01

0.02

s.t. 



0.01

0.01

0.030.05

0.02

0.03

j1,2,,10

0.030.031

1

0.05

0.08

1

x11x10850

700100 900



xj0,

二、线性规划问题求解

1. 可行域几何特征

满足约束条件的解称为可行解，所有可行解构成的集合称为可行域，满足目标式的可行解称为最优解。

定理1 （1）线性规划问题的可行域是一个凸多边形；

（2）线性规划问题如果存在最优解，则最优解必在可行域的顶点处达到。

可行域的顶点称为基本可行解。

2. 单纯形法

基本思想：从可行域的一个顶点（基本可行解）出发，转换到另一个顶点，并且使目标函数值逐步减小，有限步后可得到最优解。

将系数矩阵A表示为 A(a1,a2,,an)，其中aj是m维向量，是A的第j列。

由于rk(A)m，故A中有m个线性无关的列，不妨设A中前m个列线性无关，即a1,a2,,am线性无关。

记A=（E，F），E称为基础解矩阵。XE(x1,x2,,xm)'，XF(xm1,,xn)'，

CE(c1,,cm)'，CF(cm1,,cn)'，则规划问题可写成

''

XECFXF minzCE

s.t.

EX

E

FX

F

b

XE0,XF0

对矩阵(E,F,b)作初等变换，使E化为单位矩阵，即 (E,F,b)(Im,E1F,E1b)

记bE1b(b1,,bm)'，GE1F(gij)，LCF'CE'G(l1,,lnm)'

minzCE'E1bL'XF s.t. XEGX

F

b

XE0,XF0

可以看出，若b0，则XEE1bb,XF0是可行解，又若L0，则是最优解。

若存在lk0，(1knm)，并且G的第k列中元素均0，则可取

xj0,jm1,m2,,n,jmk

.

并令 XEbGXF,xmk0

于是X(XE,XF)是可行解，并且 zCE'E1blkxmk，由于lk0，故z无下界，即此时没有最优解。

仍设存在lk0，(1knm)，由上述讨论知，若假设问题有最优解，则G的第k列元素中至少有一个0，于是可进行变量置换，即用原来的一个非基变量与一个基变量置换位置，且使得目标函数值下降，这是一次迭代，经有限次这样的迭代，便可得到最优解。

单纯形法步骤： 第一步：A=（E，F）.

第二步：计算bE1b,GE1F,LCF'CE'G. 第三步：若L0，则XEb,XF0为最优解，STOP

若有lk0，而所有gik0,i1,2,m，则无最优解，STOP 否则，存在i使得gik0，取

bibi

gik0 Qmin

1imggikik

将A中的第mk列（F中的第k列）与A中的第i列（也是E中的第i列）互换位置，构成新的基础解阵E*，然后回到第一步。

由于单纯形法能保证每步迭代均使得目标函数严格下降，故不会出现重复现象，所以经有限步迭代后必可得到最优解。

例3 求解线性规划问题

minz0.40x10.28x20.32x30.72x40.64x50.60x6

0.01



0.02

s.t. 



0.010.010.030.05

0.030.031

1

0.02

0.03

j1,2,,10

0.05

0.08

1

x11x10850

700100 900



xj0,

[解] 显然，有一个基础解阵为E(a7,a8,a9,a10)=I4，于是F(a1,,a6)，

CF'(0.40,0.28,0.32,0.72,0.64,0.60)，CE'(0,0,0,0)，b'(850,700,100,900)

计算得：bE1bb，GE1FF，LCF'CE'GCF' 由于这时所有lk0，任取一个作为进入变量，例如x1，计算 Qmin

1im

bigi1

b1b2700850700

gi10min,, min

0.010.020.02g11g21

故退出变量为x8.新的基变量为 x7,x1,x9,x10，基础解阵为

1



E

1

相应地 F



0.010.02

1

11 E1

0.030.05

0.02

0.03

0.01

0.010.050.03

0.550

1



 1

0.010.01

0.03



 0.080.0052.5

0.03

0.03

 0.08

0.5

501

GEF



bE

1

0.02

0.03

0.05

b(500,35000,100,900)'

CE'(0,0.4,0,0)， CF'(0,0.28,0.32,0.72,0.64,0.60)

LCF'CE'GCF'(20,0,0,1,0,0)(20,0.28,0.32,0.28,0.64,0.60)'

可选取的引入变量为x2,x3,x5,x6，取x2为引入变量，计算

bib1b3100500100

Qmin gi20min,min,1imggg0.010.020.0232i212

故x9为退出变量。新的基变量为x7,x1,x2,x10.以下迭代过程省略。再经过一次迭代得到最优解为：x135000,x25000,x33000。

三、整数规划

割平面法，分支定界法（自学）

四、0-1规划

例4 （AMCM-88B）要把七种不同规格的包装箱装到两辆铁路平板车上去，各包装箱宽、高均相同，但厚度t（厘米）与重量w（公斤）不同。下表给出各包装箱的厚度、重量及数量。

每辆平板车有10.2米长的地方可用来装包装箱，载重40吨。由于当地货运限制，对c5,c6,c7类包装箱总数有一个特别限制：该类箱子总厚度不超过302.7（厘米）。试把包装箱装到平板车上去使得浪费空间最小。

1. 问题分析

题中所有的包装箱共重89吨，而两辆平板车只能载80吨，因此不能都装下，问题是装哪些箱子，使剩余空间最小。

2. 模型

设 xij第i辆车装Cj类箱子的个数， i1,2;j1,2,7 自然约束 xijZ；

箱数约束 x1jx2jnj；j1,2,7

重量约束 2xi13xi2xi30.5xi44xi52xi6xi740,厚度约束

0.487xi10.520xi20.613xi30.720xi40.487xi50.520xi60.640xi710.2,

i1,2

i1,2

特别约束 0.487xi50.520xi60.64xi73.027

目标函数

2

i1,2

maxz

[0.487x

i1

i1

0.520xi20.613xi30.720xi40.487xi50.520xi60.640xi7]

补充题3* 求解平板车装载问题。

例5 生产率问题

某车间有四项工作需要完成，现已找到四个人做这些工作，经过试用，得到这四个人做每一项工作的相对生产率指数，列表如下

假定每个人只能分派一项工作，并希望分派后总的生产率最高，应如何分派工作？

穷举，4！种分法。 令 xij则目标函数

z5x117x1210x133x143x216x228x234x24

4x313x326x332x34x414x422x4310x44max

1,0

分派第i个人做第j项工作

否则

每个人做一项工作

每项工作有一人做

4

xij1

j1

4

xij1

i1

i1,2,3,4

j1,2,3,4

线 性 规 划 模 型

一、建立模型

线性规划问题：求多变量线性函数在线性约束条件下的最优值。 线性规划问题的一般形式：

n

minz

n

c

j1

j

xj

s.t. aijxjbi

j1

i1,2,,m

x1,x2,,xn0 [说明] ……

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

n

minz

n

c

j1

j

xj

s.t. aijxjbi(0) i1,2,,m

j1

x1,x2,,xn0

[说明] 任意线性规划问题可化为标准形式。具体如下：

1. 目标函数标准化 maxzmin(z) 2. 约束条件标准化

假设约束条件中有不等式约束

ai1x1ai2x2ainxnbi 或 ai1x1ai2x2ainxnbi

引入新变量xn1,xn2（称为松弛变量），则以上两式等价于以下两式： ai1x1ai2x2ainxnxn1bi ai1x1ai2x2ainxnxn2bi

xn10

xn20

3. 自由变量标准化

若变量xj无约束，可引入两个新变量xj',xj"，令 xjxj'xj",

xj',xj"0.

故以下我们只考虑标准形式，也可以用矩阵形式表示为 minzc'x s.t.

Axb

x0 一般要求，rk(Amn)m,

mn

.

例1 某工厂制造A,B两种产品，制造产品A每吨需用煤9吨，用电4千瓦，3个工作日；制造产品B每吨需用煤5吨，用电5千瓦，10个工作日。已知制造产品A和B每吨分别获利7000元和12000元。现该厂只有煤360吨，电200千瓦，工作日300个可以利用，问A,B两种产品各应生产多少吨才能获利最大？

[解] x1,x2分别表示A,B两种产品的计划生产数（单位：吨），f表示利润（单位：千元），则 f7x112x2

耗煤量为9x15x2，耗电量为4x15x2，耗工作日3x110x2，于是得规划模型： maxf7x112x2

9x15x2360



4x15x2200



3x10x30021x1,x20

s.t.

例2 设某工厂有甲、乙、丙、丁四个车间，生产A、B、C、D、E、F六种产品，根据机车性能和以前的生产情况，得知生产每单位产品所需各车间的工作时数、每个车间在一个季度工作时数的上限以及产品的价格，如下表所示：

问：每种产品每季度各应生产多少，才能使这个工厂每季度生产总值达到最大？

[解] 以x1~x6分别表示每季度生产A、B、C、D、E、F的单位数，于是它们需满足

x10.03x2

x3x4

0.08x5

x6



850700



100

900



0.01

0.02

0.010.010.030.05

0.03

0.02

0.03

0.05

x1,x2,,x60

目标函数为 maxf0.40x10.28x20.32x30.72x40.64x50.60x6 引入松弛变量x7,x8,x9,x10，化成标准型

ming0.40x10.28x20.32x30.72x40.64x50.60x6

0.01

0.02

s.t. 



0.01

0.01

0.030.05

0.02

0.03

j1,2,,10

0.030.031

1

0.05

0.08

1

x11x10850

700100 900



xj0,

二、线性规划问题求解

1. 可行域几何特征

满足约束条件的解称为可行解，所有可行解构成的集合称为可行域，满足目标式的可行解称为最优解。

定理1 （1）线性规划问题的可行域是一个凸多边形；

（2）线性规划问题如果存在最优解，则最优解必在可行域的顶点处达到。

可行域的顶点称为基本可行解。

2. 单纯形法

基本思想：从可行域的一个顶点（基本可行解）出发，转换到另一个顶点，并且使目标函数值逐步减小，有限步后可得到最优解。

将系数矩阵A表示为 A(a1,a2,,an)，其中aj是m维向量，是A的第j列。

由于rk(A)m，故A中有m个线性无关的列，不妨设A中前m个列线性无关，即a1,a2,,am线性无关。

记A=（E，F），E称为基础解矩阵。XE(x1,x2,,xm)'，XF(xm1,,xn)'，

CE(c1,,cm)'，CF(cm1,,cn)'，则规划问题可写成

''

XECFXF minzCE

s.t.

EX

E

FX

F

b

XE0,XF0

对矩阵(E,F,b)作初等变换，使E化为单位矩阵，即 (E,F,b)(Im,E1F,E1b)

记bE1b(b1,,bm)'，GE1F(gij)，LCF'CE'G(l1,,lnm)'

minzCE'E1bL'XF s.t. XEGX

F

b

XE0,XF0

可以看出，若b0，则XEE1bb,XF0是可行解，又若L0，则是最优解。

若存在lk0，(1knm)，并且G的第k列中元素均0，则可取

xj0,jm1,m2,,n,jmk

.

并令 XEbGXF,xmk0

于是X(XE,XF)是可行解，并且 zCE'E1blkxmk，由于lk0，故z无下界，即此时没有最优解。

仍设存在lk0，(1knm)，由上述讨论知，若假设问题有最优解，则G的第k列元素中至少有一个0，于是可进行变量置换，即用原来的一个非基变量与一个基变量置换位置，且使得目标函数值下降，这是一次迭代，经有限次这样的迭代，便可得到最优解。

单纯形法步骤： 第一步：A=（E，F）.

第二步：计算bE1b,GE1F,LCF'CE'G. 第三步：若L0，则XEb,XF0为最优解，STOP

若有lk0，而所有gik0,i1,2,m，则无最优解，STOP 否则，存在i使得gik0，取

bibi

gik0 Qmin

1imggikik

将A中的第mk列（F中的第k列）与A中的第i列（也是E中的第i列）互换位置，构成新的基础解阵E*，然后回到第一步。

由于单纯形法能保证每步迭代均使得目标函数严格下降，故不会出现重复现象，所以经有限步迭代后必可得到最优解。

例3 求解线性规划问题

minz0.40x10.28x20.32x30.72x40.64x50.60x6

0.01



0.02

s.t. 



0.010.010.030.05

0.030.031

1

0.02

0.03

j1,2,,10

0.05

0.08

1

x11x10850

700100 900



xj0,

[解] 显然，有一个基础解阵为E(a7,a8,a9,a10)=I4，于是F(a1,,a6)，

CF'(0.40,0.28,0.32,0.72,0.64,0.60)，CE'(0,0,0,0)，b'(850,700,100,900)

计算得：bE1bb，GE1FF，LCF'CE'GCF' 由于这时所有lk0，任取一个作为进入变量，例如x1，计算 Qmin

1im

bigi1

b1b2700850700

gi10min,, min

0.010.020.02g11g21

故退出变量为x8.新的基变量为 x7,x1,x9,x10，基础解阵为

1



E

1

相应地 F



0.010.02

1

11 E1

0.030.05

0.02

0.03

0.01

0.010.050.03

0.550

1



 1

0.010.01

0.03



 0.080.0052.5

0.03

0.03

 0.08

0.5

501

GEF



bE

1

0.02

0.03

0.05

b(500,35000,100,900)'

CE'(0,0.4,0,0)， CF'(0,0.28,0.32,0.72,0.64,0.60)

LCF'CE'GCF'(20,0,0,1,0,0)(20,0.28,0.32,0.28,0.64,0.60)'

可选取的引入变量为x2,x3,x5,x6，取x2为引入变量，计算

bib1b3100500100

Qmin gi20min,min,1imggg0.010.020.0232i212

故x9为退出变量。新的基变量为x7,x1,x2,x10.以下迭代过程省略。再经过一次迭代得到最优解为：x135000,x25000,x33000。

三、整数规划

割平面法，分支定界法（自学）

四、0-1规划

例4 （AMCM-88B）要把七种不同规格的包装箱装到两辆铁路平板车上去，各包装箱宽、高均相同，但厚度t（厘米）与重量w（公斤）不同。下表给出各包装箱的厚度、重量及数量。

每辆平板车有10.2米长的地方可用来装包装箱，载重40吨。由于当地货运限制，对c5,c6,c7类包装箱总数有一个特别限制：该类箱子总厚度不超过302.7（厘米）。试把包装箱装到平板车上去使得浪费空间最小。

1. 问题分析

题中所有的包装箱共重89吨，而两辆平板车只能载80吨，因此不能都装下，问题是装哪些箱子，使剩余空间最小。

2. 模型

设 xij第i辆车装Cj类箱子的个数， i1,2;j1,2,7 自然约束 xijZ；

箱数约束 x1jx2jnj；j1,2,7

重量约束 2xi13xi2xi30.5xi44xi52xi6xi740,厚度约束

0.487xi10.520xi20.613xi30.720xi40.487xi50.520xi60.640xi710.2,

i1,2

i1,2

特别约束 0.487xi50.520xi60.64xi73.027

目标函数

2

i1,2

maxz

[0.487x

i1

i1

0.520xi20.613xi30.720xi40.487xi50.520xi60.640xi7]

补充题3* 求解平板车装载问题。

例5 生产率问题

某车间有四项工作需要完成，现已找到四个人做这些工作，经过试用，得到这四个人做每一项工作的相对生产率指数，列表如下

假定每个人只能分派一项工作，并希望分派后总的生产率最高，应如何分派工作？

穷举，4！种分法。 令 xij则目标函数

z5x117x1210x133x143x216x228x234x24

4x313x326x332x34x414x422x4310x44max

1,0

分派第i个人做第j项工作

否则

每个人做一项工作

每项工作有一人做

4

xij1

j1

4

xij1

i1

i1,2,3,4

j1,2,3,4