高中综合素质评价-三清山简介

3.2.2 线性规划数学模型

教学目的：会建立简单 的线性规划问题的数学模型，熟练掌握线性规划问题的标准形和线性规划问题的图
解法，掌握线性规划问 题的单纯形法，了解两阶段法。
内 容：1. 线性规划问题的数学模型
2. 图解法
3．单纯形法
4. 两阶段法
教学重点: 线性规划问题的数学模型、两个变量的线性规划问题的图解法、单纯形法
教学难点: 线性规划问题的数学模型建立，两阶段法
教 具：多媒体课件
教学方法: 启发式教学，精讲多练
教学过程：
1.引入新课：
本节介绍线性规划问题的数学 模型，两个变量的线性规划问题的图解法。本节介绍线性规划问
题的单纯形法及两阶段法。
2.教学内容：
一、线性规划问题的数学模型
【例1】 某生产车间生产甲、乙两 种产品，每件产品都要经过两道工序，即在设备A和设备B上加工，但两种产品的
单位利润却不相同。已 知生产单位产品所需的有效时间（单位：小时）及利润见表3-10。问生产甲、乙两种产品各多少
件， 才能使所获利润最大。
表1 甲、乙产品资料

甲 乙 时间（小时）
3 2 60
设备A
2 4 80
设备B

单位产品利润 50元件 40元件
解 该问题所需确定的是甲、乙两种产品的产量。先建立其数学模型。
设
x
1
, x
2
分别表示产品甲和乙的产量。
x
1
,x
2
称为 决策变量
。根据问题所给的条件有

3x
1
2x
2
60


2 x4x80

12
又因产量
x
1
,x
2
不能是负值，故
以上是决策变量
x
1
,x
2
受限的 条件，把它们合起来称之为约束条件：
x
1
0,x
2
0


上述问题要确定 的目标是：如何确定产量
x
1
和
x
2
，才能使所获利润为最 大。利润的获取和
x
1
,x
2
密切相关，以
f
表< br>示利润，则得到一个线性函数式

3x
1
2x
2
60


2x
1
4x
2
80
x,x0

12
f=50x
1
+40x
2

所给问题目标是要使线性函数
f
取得最大值（用max表示），即目标函数是
max
f=50x
1
+40x
2

综上所述，本例的数学模型可归结为：
max
f=50x
1
+40x
2


3x
1
2x
2
60

s.t.

2x1
4x
2
80


x0,x0
2
1
这里“s.t.”是“subject to”的缩写，表示“在 … 约束条件之下”，或者说“约束为…”。

1

【例2】已知某配送 中心现有Ⅰ、Ⅱ、Ⅲ三种原材料，可加工出A、B两种产品，每吨原材料加工情况及对A、B两种产
品的 需求情况见表2。
表2

加工件数
产品

原材料
Ⅰ
3
0
1千元吨
Ⅱ
2
1
1千元吨
Ⅲ
0
2
1千元吨
需要件数
300
100

A
B
单价

问如何配用原材料，既满足需要，又使原材料耗用的总成本最低？
解 因目标是原材料耗用的 总成本最低（用min表示），故设Ⅰ、Ⅱ、Ⅲ种原材料需求量分别为
x
1
,x
2
,x
3
，则问题可写
成如下数学模型：
minf=
x
1
+x
2
+x
3


3x
1
2x
2
300

s.t.

x
2
2x
3
100


x0(j 1,2,3)

j
（1）每一个问题都求一组变量，称为决策变量，这组变量取值一般 都是非负的；
（2）存在一定的限制条件，称为约束条件，通常用一组线性方程或线性不等式来表示；
（3）都有一个目标要求的线性函数，称为目标函数，要求目标函数达到最大值或最小值．
一 般地，约束条件和目标函数都是线性的，我们把具有这种模型的问题称为线性规划问题，简称线性规划．
一个线性规划问题的数学模型的一般形式：
求一组决策变量
x
1
, x
2
,,x
n
的值，使

max
（ 或
min
）
fc
1
x
1
c
2
x
2
c
n
x
n
，

a
1 1
x
1
a
12
x
2


a< br>1n
x
n
(,)b
1
,


a
21
x
1
a
22
x
2

< br>a
2n
x
n
(,)b
2
,


s.t.





axax

ax(,)b,
mnn m

m11m22


x
j
0(j1,2,< br>
,n).
其中
a
ij
,b
i
,c
j
(i1,2,,m;i1,2,,n)
为已知常数．
一个线性规划问题的数学模型，必须含有三大要素：决策变量，约束条件与目标函数．
满足约束条件的一组变量的取值：
00
，
x
1
x1
0
,x
2
x
2
,,x
n
x< br>n
称为线性规划问题的一个可行解．使目标函数取得最大（或最小）的可行解称为最优解，此时， 目标函数的值称为最优
值．
二、图解法
【例3】用图解法求解例1的线性规划问题
max
f=50x
1
+40x
2


3x
1
2x
2
60

s.t.

2x1
4x
2
80


x,x0

12
解 在平面直角坐标系
x
1
ox
2
中作直线
l
1:3x
1
2x
2
60
l
2
:2x
1
4x
2
80

如图1所示。


2

图1

图1阴影部分里所有点（包括边界上的点），满足该问 题的所有约束条件。这个范围以外的点，则不能同时满足上述各
约束条件。
满足所有约束条件的点称为可行点。每一点代表该线性规划问题的一个可行方案，即一个可行解。
所有可行点的集合，称为该问题的可行域，，故该问题的可行解有无数个。
能使目标函数值达到最优值（最大值或最小值）的可行解，这种解称为最优可行解，简称最优解。
将目标函数写成：50x
1
+40x
2
= k，其中
k< br>为任意常数。当
k
为不同值时，此函数表示相互平行的直线，称为等值线。
令< br>k
=0，得到的直线50x
1
+40x
2
= 0，叫做0等值线。
先作通过原点的0等值线
l
3
: 50x
1
+40x
2
= 0
它与可行域的交点为
(0, 0)
。将这条直线沿目标函数增大的右上方平移，过顶点E时，
f
在可行域中取最大值 ；如继续向
右上方平移，则等值线将离开可行域（等值线与可行域没有交点）。故E点坐标就是最优解。
求直线l
1
和l
2
交点E的坐标，即解方程组

3x
1
2x
2
60



2x
1
4x
2
80
得到x
1
=10， x
2
=15，这时最优值
f=50x
1
+40x
2
=1100。
即例1中，甲产品产量为10件，乙产品产量为15件时，所获利润最大，最大利润为1100元。
图解法求解线性规划问题的步骤如下：
（1）在平面直角坐标系x
1
ox< br>2
内，根据约束条件作出可行域的图形。
（2）作出目标函数的0等值线，即目标函数值等于0的过原点的直线。
（3）将0等值线沿 目标函数增大的方向平移，当等值线移至与可行域的最后一个交点（一般是可行域的一个顶点）
时，该交 点就是所求的最优点。若等值线与可行域的一条边界重合，则最优点为无穷多个。
′′′′
（ 4）求出最优点坐标（两直线交点坐标可联立直线方程求解），即得到最优解(x
1
, x
2
)，及最优值
f
（x
1
, x
2
）。
【例4】 用图解法解线性规则问题
min
f=-20x
1
-40x
2


3 x
1
2x
2
60

s.t.

2x< br>1
4x
2
80


x,x0

12
解 在直角坐标系
x
1
ox
2
中作直线
l
1
:3x
1
2x
2
60
l
2
:2x
1< br>4x
2
80

如图3-3所示,得可行域OCEA。
作0等值线
l
3
:20x
1
+40x
2
=0


3

图3-3


该等值线
l< br>3
斜率与
l
2
斜率相等，所以
l
2
l
3
。当
l
3
向右上方平移时，
x
1
,x
2
都变大，这时
f=-20x
1
-40x
2
变小。当
（10，15）
和
A
(0，20)
都是此问题的最优
l
3
与边界线
AE
重合时，目标函数值最小。故边界
AE
上的所有点，包 括两个端点
E
解，此时目标函数的最优值为：
10，15）
=f(0，

f
（
20)=-800

这是线性规划问题有无穷多个最优解的情况。
【例5】用图解法解线性规划问题
max
f=x
1
+x
2


x
1
x
2
1

s.t.

x
1
2x< br>2
0


x,x0

12
解 在直角坐标系
x
1
ox
2
中, 作直线
l
1:x
1
x
2
1
l
2
:x
12x
2
0
得可行域，如图3-4所示的阴影部分，它是无界区域。
作0等值线
l
3
:x
1
+x
2
=0



图3-4
并将
l
3
:x
1
+x
2
=0
向右上方平移，因可行域无界，目标函数
f=x
1
+x2
的值趋于无穷大，所以该线性规则无最优
解。
【例6】 用图解法解线性规划问题
max
f=5x
1
+3x
2


x
1
x
2
3

s.t.

x
1
x
2
6


x,x0

12
解 在直角坐标系
x
1
ox
2
中作直线，

4

l
1
:x
1
+x
2
=3
l2
:x
1
+x
2
=6

图3-5

如图3-5所示，可知可行域为空集，所以此问题没有可行解，当然也没有最优解。
由上述几例可见，线性规划问题的解的情况可以归结为：
①有可行解且有惟一最优解；
②有可行解且有无穷多最优解；
③有可行解但无最优解；
④无可行解。
上述结论对于两个以上变量的线性规划问题也是适用的。

三、单纯形法
1．线性规则问题的标准形
形如
max
fc
1
x1
c
2
x
2
c
n
x
n


a
11
x
1
a
12
x< br>2


a
1n
x
n
b
1


a
21
x
1
a
22
x
2


a
2n
x
n
b
2
s.t.





axax

axb
mnnm
< br>m11m22


x
j
0(j1,2,

,n)
称为线性规划问题的标准形式，简称标准形．
①求目标函数的最小值．
m in
fc
1
x
1
c
2
x
2
 c
n
x
n

令
Zf
，则可将求
m in
f
转化成求
max
Z
，即
max
Zc< br>1
x
1
c
2
x
2
c
nx
n

②约束条件为不等式的，则引入一个非负变量
x
ni< br>，将线性不等式转化为线性方程，其中
x
ni
称为松弛变量．
对于
a
i1
x
1
a
i2
x
2
 a
in
x
n
b
i
(i1,2,m)
，引入< br>x
ni
0
，在不等式的左边加上变量
x
ni
， 于是不等式化为
a
i1
x
1
a
i2
x
2
a
in
x
n
x
ni
b
i< br>
对于
a
i1
x
1
a
i2
x2
a
in
x
n
b
i
(i1,2, m)
，引入
x
ni
0
，在不等式的左边减去变量
xni
，于是不等式化为
a
i1
x
1
a
i 2
x
2
a
in
x
n
x
nib
i

③若
b
i
0
时，可在约束条件a
i1
x
1
a
i2
x
2
a< br>in
x
n
b
i
的两边同乘以
1
，化为
a
i1
x
1
a
i2
x
2
 a
in
x
n
b
i

④如果有某个变量
x
j
无非负约束，那么可引进两个非负的变量
x

j
,x

j

，令
x
j
x

j
x

j
，代入约束条件和目标函数
中，使全部变量都非负．
【例7】将下面的线性规划问题化为标准形：
min
f2x
1
2x
2
3x
3


5


x
1
x
2
x
3
12

x3x2x15

123
s.t .


3xxx10
23

1


x
1
0,x
2
0
解 （1）令
Zf
，则目标函数为
max
Z2x
1
2x
2
3x
3
．
（2）引进松弛变量
x
4
0,x
5
0
，使约束 条件为不等式的转化为等式：
x
1
x
2
x
3
x
4
12

x
1
3x
2
2x3
x
5
15

（3）将
3x
1
 x
2
x
3
10
变为
3x
1
x
2
x
3
10

（4）
x
3
无非负限制，令
x
3
x
7
 x
6
，其中
x
7
0,x
6
0
，将其代 入目标函数及约束条件，得
max
Z2x
1
2x
2
3(x
7
x
6
)

x
1
x
2
(x
7
x
6
)x
4
12
x
1
3x
2
2(x
7
x
6
) x
5
15

3x
1
x
2
x
6
x
7
10

于是，该线性规划的标准形为
max
Z2x
1
2x
2
3x
6
3x
7


x
1
x
2
x
4
x6
x
7
12

x3xx2x2x15

12567

s.t.


3xxxx10< br>267

1

x
j
0,(j1,2,3,4,5 ,6,7)

2. 单纯形法
定义１ 设线性规划的标准形为
maxfc
1
x
1
c
2
x
2
c< br>n
x
n


a
11
x
1
 a
12
x
2


a
1n
x
n< br>b
1


a
21
x
1
a
22
x
2


a
2n
x
n
 b
2

s.t.





axax

axb
mnnm

m11m22

x
j
0(j1,2,

,n)
如果变量
x
j
只在某一个约束方程中系数为１，在其余约束方程中系数均为０，则称
x
j
为该约束条件的一个基变量；
如果每个等式约束条件都有一个基变量，则称等式约束条件为这 些基变量的典型方程组．
不失一般性，若线性规划的约束条件是典型方程组，则
n
个 变量的线性规划问题的典型方程组为
max
fc
1
x
1
c
2
x
2
c
n
x
n

 a
1,m1
x
m1


a
1n
x< br>n
b
1

x
1


x
2
a
2,m1
x
m1


a
2n
x
n
b
2




st



x
m
a
m,m1< br>x
m1


a
mn
x
n
b< br>m



x
j
0(j1,2,

,n)
x
1
,x
2
,,x
m
是基变量，称变量
x
m1
,x
m2
,

,x
n
为非基变量．
令非基变量
x
m1
0,x
m2
0, ,x
n
0
，可求得约束方程的一个解为

6

x
1
b
1
,x
2
b
2
,, x
m
b
m
,x
m1
0,x
m2
 0,,x
n
0
．
此解称为基本解．
在基本解中，若所有的< br>b
i
0(i1,2,,m)
，则称此解为基本可行解．
定理1 如果线性规划问题有最优解，那么最优解必是某个基本可行解。
由等式约束条件得

x
1
b
1
a
1,m1
x
m1


a
1n
x
n


x
2
b
2
a
2,m1
x
m1


 a
2n
x
n






x
m
b
m
a
m,m1
x
m1

a
mn
x
n

将其代入目标函数，得

ff
0


m1
x
m1


m2
x
m2

n
x
n

此式就是目标函数用非基变量表示的式子．式中系数

m1
,

m2


n
称为非基变量的检验数．
定理2 设
m1
,

m2
,

,

n
是非基变量的检验数，则
(1) 若非基变量的所有检验数

j
0（
jm1,m2,,n
），则基本可行解就是最优解；
(2) 若非基 变量的所有检验数

j
0
（
jm1,m2,,n
），且其中有一个检验数等于０，则有无穷多个最优
解；
(3) 若存在非基变量
x
mk
的检验数

mk
0
，且
x
m k
对应的系数列均小于等于０，即
a
1,mk
0,a
2,mk
0,,a
m,mk
0
，则该线性规划问题无最优解．
单纯 形法的基本思路是对可行域这一凸多边形的一个顶点（第一个基本可行解）出发进行检验，如果不是最优，则换一个（迭代）更优的顶点（另一个基本可行解），使一次比一次更接近最优解（逐步优化），直到取得最优 解为止。
由定理1知道，线性规划问题的最优解可以通过只考虑它的基本可行解来确定。
【例8】用单纯形法求解例1的线性规划问题
max
f=50x
1
+40x
2


3x
1
2x
2
60

s.t.

2x1
4x
2
80


x,x0

12
解 先引入松弛变量
x
3
,x
4
，将问题化为标准形式：
ma xf=50x
1
+40x
2
+0x
3
+0x
4

3x
1
2x
2
x
3
60< br>
s.t.

2x
1
4x
2
+x
4
80


x（

j
0j1,2,3,4 ）
目标函数改写为
-f+50x
1
+40x
2
+0x
3
+0x
4
=0
，将约束条件的增广矩阵和改写后的目标函数的系数填入下 表中，
得到的表称为单纯形表。
表1
单纯形表
x
1
x
2
x
3
x
4
基变量
x
3
x
4

3 2 1 0
2 4 0 1
50 40 0 0
b
60
80
0
-
f

单纯形表中，约束条件的系数矩阵中出现一个2阶单位矩阵，
b
列非负，目标函数行对应于单位矩阵的元素为0，这时
其余的元素即为检验数。
系数矩阵中已有2阶单位矩阵，其所在的列对应的变量x
3
，x
4
是基变量， 变量 x
1
，x
2
是非基变量。令x
1
=0，x
2
=0，由标
（0）T
准形式等式可得x
3
=60，x
4=80，于是得到一个基本可行解，记为X=（0，0，60，80），这是初始可行解，其对应的目
(0)
标函数值f

= 0，将其填入表中右下角。它表示：没有安排生产甲、乙产品，利润为0元。
由定理2最优解判定准则知，当所有检验数非正时，这个解就是最优解，否则解仍可改善。

7

观察表1中检验数，50、40均为正数，解仍可改善。若将x
1
或x
2
变为非零变量都可使目标函数值增加。其中x
1
的系数更大，它能让目标函数增加较快，故先将x
1
转变为基变量，这时称之为进基变量，之后有一 个基变量被换出，称为出基变
量。变量调换完成之时，即可得到一个改善后的基本可行解。具体调换程序 如下：确定x
1
为进基变量后，x
1
可由原来的零
值变为正值，x< br>2
仍为非基变量，取为零。方程组就为

3x
1
x
3
60



2xx80

14
当
x
1
增加时，对
f 的贡献是正数，当然x
1
取值越大越好。但要求变量非负，即
x
3
603x
1
0


x
4
802x
1
0

则解得
< br>6080

60
x
1
min

,

20

323

这就是说，要使换基后，所对应的解仍为基 本可行解，
x
1
只能由0增大到20，这时x
3
由60下降为0，x
4
由80下降为20，基变量
x
3
变为非基变量，这一过程称为出基 。这种确定出基变量的方程叫做最小比值法。
最小比值法：在单纯形表中，将b列元素与进基变量列对 应的正元素作比值，取比值最小者所对应的基变量出基。
进基变量x
1
列与出基变量 x
3
行（x
3
的系数为1）交叉处的元素称为主元。这里确定主元及出基变量 的方法是，

6080

，故3为主元，其所在行为主元行，主元行对应的基 变量x
3
为出基变量。将主元用
min

,

=m in
{
20,40
}
=20
32

中括号标志， 见表2。
表2
基变量
x
3
x
4

x
1
x
2
x
3
x
4
[3] 2 1 0
2 4 0 1
b
60
80
0 50 40 0 0
对主元行作初等变换，使主元变为1，得表3。
表3
-
f
基变量
x
3
x
4
x
1
x
2
x
3
x
4
1 23 13 0
2 4 0 1
b
20
80
0 50 40 0 0
作行初等变换，将主元列其余元素变为0，得表4。
表4
x
1
x
2
x
3
x
4
基变量
x
1
x
4

1 23 13 0
0 83 -23 1
-
f
b
20
40
0 203 503 0 -1000
(1) T(1)
新基变量为x
1
，x
4
，令非基变量x
2
，x
3
为0，得一基本可行解：
X
= (20，0，0，40)，对应目标函数值f

= 1000。
观察表3-15中检验数，仍有正数
-
f
20
，故其所在列对应变量
x
2
确定为进基变量。
3

2040

88
最小比值
min
,
，故主元为，为离基变量。对进行标志，得表5。
x
=min30,15=1 5
{}

4
28
33


33








8

表5
基变量
x
1
x
4
x
1
x
2
x
3
x
4
1 23 13 0
0 [83] -23 1
b
20
40
-1000 0 203 -503 0
对主元行作初等变换，使主元变为1，得表6。
表6
-
f
基变量
x
1
x
2
x
3
x
4
b
20
15
-1000
1 23 13 0
x
1
0 1 -14 38
x
4
-
f 0 203 -503 0
作行初等变换，将主元列其余元素变为0，得表7。
表7
基变量
x
1
x
2

x
1
x
2
x
3
x
4
1 0 12 -14
0 1 -14 38
(2)
b
10
15
0 0 - 453 -208 -1100
T (2)
表7中检验数非正，得最优解：
X
= (10，15，0，0)，对应目标函数值f= 1100。它表示：甲产品生产10件，乙产
品生产15件时，利润最大，最大利润为1100元。
上述求解过程可用表8综述之：
表8 单纯形表
x
1
x
2
x
3
x
4
b
序号 基变量
Ⅰ

x
3
x
4
[3] 2 1 0
2 4 0 1
50 40 0 0
1 23 13 0
0 [83] -23 1
0 203 -503 0
1 0 12 -14
0 1 -14 38
0 0 -453 -208
60
80
0
20
40
-1000
10
15
-1100
-
f
-
f
Ⅱ

x
1
x
4
-
f
Ⅲ

x
1
x
2
-
f

T
因表中 检验数非正，得最优解
X
=（10，15，0，0），除去松弛变量后得
f(10,1 5)=1100
。
【例9】用单纯形法求解线性规划问题
min
f=-20x
1
-40x
2


3 x
1
2x
2
60

s.t.

2x< br>1
4x
2
80


x,x0

12
解 引入松弛变量x
3
，x
4
，得标准形式：
maxZ=20x
1
+40x
2
+0x
3
+0x
4

< br>3x
1
2x
2
x
3
60

s .t.

2x
1
4x
2
x
4
80< br>

x0(j1,2,3,4)

j




9

表9
单纯形表
序号

Ⅰ


Ⅱ

Ⅲ
基变量
x
3
x
4
-
Z
x
3
x
2
-
Z
x
1
x
2
-
Z
x
1
x
2
x
3
x
4
3 2 1 0
2 [4] 0 1
20 40 0 0
[2] 0 1 -12
12 1 0 14
0 0 0 -10
1 0 12 -14
0 1 -14 38
0 0 0 -10
b
60
80
0
20
20
-800
10
15
-800

(1)
T
由表9（Ⅱ）可知，检验数非正，这时已有最优解：
X=（0，20，20，0），除去松弛变量后得目标函数最大值Z
（0，20）=800。又因非基 变量x
1
的检验数也为零，令x
1
为进基变量，目标函数值并不会改变。再迭 代一次，由表3-12
(2)
T
（Ⅲ）得另一最优解：
X
=（10， 15，0，0），除去松弛变量后目标函数最大值仍是Z（10，15）=800。故原规划问题的
目标 函数的最小值为
f=-800
。
【例10】用单纯形法解线性规划问题
maxfx
2
2x
3
x
4


x
1
2x
2
x
3
11


s.t.

2x
1
2x
2
x
4
4


x0(j1,2,3,4)

j
解 约束条件是典型方程组，
x
3
、
x
4
是基变量，
x
1
、
x
2
是非基变量，由此得表10．
表10
x
1
x
2
x
3
x
4
b
序号 基变量
x
3
1 2 1 0 11

x
4
2 -2 0 1 4
Ⅰ
0 -1 -2 -1 0
-
f
此表中检验行中各检验数已经非正，但却得不到最优解。这是因为在 单纯形表中，目标函数必须只用非基变量表示，即
目标函数中，基变量的系数必须是零。由此对行做初等 变换，将基变量的系数化为零，得单纯形表，并进行换基迭代，
其过程见表11。

表11
x
1
x
2
x
3
x
4
b
序号 基变量
x
3
1 2 1 0 11

x
4
[2] -2 0 1 4
Ⅰ
4 1 0 0 26
-
f
x
3
0 [3] 1 -12 9

x
1
1 -1 0 12 2
Ⅱ
0 5 0 -2 18
-
f
x
2
0 1 13 -16 3

x
1
1 0 13 13 5
Ⅲ
0 0 -53 -76 3
-
f
T
由表11（Ⅲ）知，检验数非正，得最优解：
X
= (5，3，0，0)，对应目标函数最优值f= -3。
四、两阶段法
设线性规则问题的标准形为
max
fc
1
x
1
c2
x
2
c
n
x
n


a
11
x
1
a
12
x
2

< br>a
1n
x
n
b
1


a
21
x
1
a
22
x
2


 a
2n
x
n
b
2

s.t.





axax

axb
mnnm

m11m22


x
j
0(j1, 2,

,n)
其约束条件不是典型方程组．

10

两阶段法是由以下两个阶段构成的解法．
第一阶段：引入新变量
y< br>1,
y
2
,,y
m
（称为人工变量），构造一个辅助线性规 则问题
max
Zy
1
y
2
y
m


a
11
x
1
a
12
x
2

a
1n
x
n
y
1
b
1


a
21
x
1
a
22
x
2


a
2n
x
n
y
2b
2


s.t.





axax

axyb
mnnmm

m11m22


x
j
0,y
i
 0(j1,2,

,n;i1,2,

,m)
应用单纯形法，求 出辅助线性规则问题的最优解．如果最优值
Z0
，并且人工变量均已出基，说明所有的人工变
量也都缩小到零，这时原问题的基本可行解也就得到了，便可划去人工变量，得到原问题的初始单纯形表 ，进入第二阶
段；否则原问题无可行解，求解结束．
第二阶段：在第一阶段所得的初始单纯形 表的基础上，用单纯形法进行换基迭代，求出最优解．
【例11】求解线性规则问题：
maxf3x
1
x
2
x
3



x
1
2x
2
x
3
11

s.t.


4x
1
 x
2
2x
3
3

2x
1
x
3
1



x
j
0,(j1,2,3)
解 引进松弛变量
x
4
,x
5
，将其化为标准形．
maxf 3x
1
x
2
x
3
0x
4
0x5



x
1
2x< br>2
x
3
x
5
11
s.t.


4x
1
x
2
2x
3
x
4
3

2x

1
x
3
1


x
j
0,(j1,2,3,4,5)
应用两阶段法．
第一阶段：第二、第三约束等式中暂缺基变量，分别引入人工变量
y
1,
y
2
，作辅助线性规则问题
maxZy
1
y
2



x
1
2x
2
x
3
x
5
11

s.t.


4x
1
x
2
2x3
x
4
y
1
3

2x
1x
3
y

2
1


x
j
0,(j1,2,3,4,5);y
1
0,y
2
0
由约束条件二、三中解出
y
1,
y
2
，则
Z
用非 基变量表示为
Z6x
1
x
2
3x
3
x
4
4

用单纯表进行换基迭代如下表12
辅助问题的最优值Z0
，且人工变量
y
1,
y
2
均已出基，于是进入第 二阶段．

表12
序
号
基变量
x
1
x
2
x
3
x
4
x
5
y
1
y
2
b
x
5
1 -2 1 0 1 0 0
11
Ⅰ
y
1
-4 1 2 -1 0 1 0
3

y
2
-2 0 [1] 0 0 0 1
1
-
Z -6 1 3 -1 0 0 0
4

11

3 -2 0 0 1 0 -1
x
5
10
y
1
0 [1] 0 -1 0 1 -2
1
Ⅱ
x
3
-2 0 1 0 0 0 1
1

1
-
Z 0 1 0 -1 0 0 -3
3 0 0 -2 1 2 -5
x
5
12
x
2
0 1 0 -1 0 1 -2
1
Ⅲ
x
3
1
-2 0 1 0 0 0 1

0
-
Z 0 0 0 0 0 -1 -1
第二阶段：在第一阶段的表Ⅲ中划去人工变量

y
1 ,
y
2

所在的列，并将
- Z
行换成-f行，即得原 线性规划问题的初始单
纯形表．必须注意：填-f行前，须将
f
用非基变量表示．对表 Ⅲ 最后一次换基迭代可知
x
2
x
4
1
，
x
3
2x
1
1
，
x
5
3x
1
2x
4
12
，
从而
f3x
1
x
2
x
3
3x
1
(x
4
1) (2x
1
1)
x
1
x
4
2
．
用单纯形法进行求解过程，如表13．
表13
序
号
基变量
x
1
x
2
x
3
x
4
x
5
b
x
5
[3] 0 0 -2 1
12
Ⅰ
x
2
0 1 0 -1 0
1

x
3
-2 0 1 0 0
1
-
f 1 0 0 -1 0
2
x
1
1 0 0 -23 13
4
Ⅱ
x
2
0 1 0 -1 0
1

x
3
0 0 1 -43 23
9
-
f 0 0 0 -13 -13
-2


可得最优解为
x
1
4,x
2
1,x
3
9,x
4
0,x
5
0
．
原线性规划问题的最优解为
x
1
4,x
2
1,x< br>3
9
，最优值
f(4,1,9)2
．
【例12】解线性规划问题：
maxf3x
1
2x
2
x
3



3x
1
6x
2
3x
3
 4x
4
12

s.t.


3x
1
x
3
6

6x
2
x
3
4x

4
6


x
j
 0,(j1,2,3,4).
解 引进人工变量
y
1
,y
2
,y
3
，作辅助线性规划问题．
maxZy
1
y
2
y
3


3x
1
6x
2
3x
3
4x
4
y
1
12
s.t.


3x
1
x
3
y
2
6

6x
2
x
3
4x

4
y
3
6


x
j
0,y
i
0(j1,2,3,4;i1,2,3).
用 非基变量表示
Z
：
Z4x
2
6x
3
20
．
对辅助问题用单纯形表进行换基迭代，如表14．




12

表14
序
号
Ⅰ

基变量
x
1
x
2
x
3
x
4
y
1
y
2
y
3
b
12
6
6
24
6
6
1
12
2
0
1
0
Ⅱ

Ⅲ

y
1
3 6 3 -4 1 0 0
y
2
3 0 -1 0 0 1 0
y
3
0 [6] -1 -4 0 0 1
-
Z -6 1 3 -1 0 0 0
y
1
[3] 0 4 0 1 0 -1
y
2
3 0 -1 0 0 1 0
x
2
0 1 -16 -23 0 0 16
-
Z 6 0 3 0 0 0 -2
x
1
1 0 43 0 13 0 -13
y
2
0 0 [-5] 0 -1 1 1
x
2
0 1 -16 -23 0 0 16
-
Z 0 0 -5 0 -2 0 0
表14最后一行检验数均非正，最优值
Z0
，
但此时人工变量y
2
尚未出基，可采用下述方法让人工变量出基：在
未出基的那个人工变量所在行的非人工变量 列中任选一个非零元素，此处选-5为主元，进行迭代。y
2
出基x
3
进基，得单
纯形表15。
表15
序
号
Ⅳ

基变量
x
1
x
2
x
3
x
4
y
1
y
2
y
3
b
2
0
1
0
x
1
1 0 0 0 115 115 -115
x
3
0 1 0 0 115 -115 -115
x
2
0 0 1 -23 130 -130 215
-
Z 0 0 0 0 -1 -1 -1
表15中检验数均非正，最优值Z=0，划去人工变量，进入第二阶段得表16。
表16
序
号
Ⅴ

基变量
x
1
x
3
x
2
x
1
x
2
x
3
x
4
1 0 0 0
0 0 1 0
0 1 0 -23
3 -2 1 0
1 0 0 0
0 0 1 0
0 0 0 -23
0 0 0 -43
b
2
0
1
0
2
0
1
-4
-
f
Ⅵ

x
1
x
3
x
2
-
f
【例13】解线性规划问题

由于检验数非正，所以原问题最优解为x
1
=2，x
2
=1，x
3
=0，最优值f=4。
maxfx
1
2x
2


x
1
2x
2
x
3
1


s.t.

x
1
2x
2
x
3
6



x0,(j1,2,3)

j
解 引进松弛变量x
4

、
x
5
，将线性规划问题化为标准型为

maxfx
1
2x
2


x
1
+2x
2
x
3
x
4
=1


s.t.

x
1
2x
2
+x
3
x
5
=6


x0,(j1,2,3,4,5)

j
约束条件不是典型方程组，应用两 阶段法，引进人工变量y
1
，

y
2
，
作辅助线性规划问题．

13

maxZy
1
-y
2


x
1
+2x
2
x
3
x
4
y
1
=1


s.t.

x
1
2x
2
+x
3
x
5
y
2
=6


x0,y0(j1,2,3,4,5;i=1 ,2)
i

j

得表18，对其进行初等行变换。
序
基变量
x
1
x
2
x
3
x
4
x
5
y
1
y
2
号
Ⅰ

y
1
-1 2 -1 -1 0 1 0
y
2
-1 -2 1 0 -1 0 1
b
1
6
0
1
6
-
Z
Ⅱ

0 0 0 0 0 -1 -1
y
1
-1 2 -1 -1 0 1 0
y
2
-1 -2 1 0 -1 0 1
7
-2 0 0 -1 -1 0 0
非基变量的检验数均非正，当前基本可行解是最优解，最优值Z=-
7<0,可知原线性规划问题无可行解，当然也无
最优解。
对比较复杂的线性 规划问题，用两阶段法求解的过程也相当繁冗，计算量都比较大．随着计算机技术的发展，线性
规划数学 模型可利用数学规划软件求出最优解，软件可从运筹学网站上下载使用．

课堂练习 1. 用图解法解线性规划问题：
-
Z
minf5x
1
x
2


x
1
2x
2
8

2x2x12


2
s.t.

1

5x
1< br>x
2
10


x
1
,x
20


2. 将线性规划问题化为标准型：

maxf3x
1
x
2



3x
1
x
2
8

< br>s.t.

4x
1
3x
2
6


x0


2

3. 某工厂生产A、B、C三种产品，每种产品都是利用同一种原材料加工而成，每种产品每生产一件所需的原材料< br>数、加工工时、每件产品的利润以及工厂现有的原材料数和加工工时见下表：
类 目
原材料t
加工工时h
利润万元

小结
1. 建立简单的线性规划问题的数学模型；
2. 两个变量的线性规划问题的图解法：
（1）在 平面直角坐标系x
1
ox
2
内，根据约束条件作出可行域的图形。
（2）作出目标函数的0等值线，即目标函数值等于0的过原点的直线。

14
A
2
100
20
B
1
300
30
C
2
200
10
现有资源
7
1100

问工厂应该制定什么样的生产计划，才能获得最大利润？试建立线性规划问题数学模型。

（3）将0等值线沿目标函数增大的方向平移，当等值线移至与可行域的最后一个交点（一般是可行域 的一个顶点）
时，该交点就是所求的最优点。若等值线与可行域的一条边界重合，则最优点为无穷多个。
3、单纯形法
4、两阶段法

课后作业
：
习题3.2.2 1、2（1）、（3）、4（2）、（3）


15