第六章--线性规划

第六章 线性规划

线性规划是最简单的约束优化问题。这是因为线性规划的目标函数和约束函数都是线性函数。

1.线性规划的标准形式

n

min

c

j

xj

j 1n

s.t. aijxj bi,i 1,2,...,m

j 1

xj 0,j 1,2,...,n(m n)

为简便，标准形式还可写成：

mincT

x

s.t.Ax b

x 0

其中：x x1,x2, ,xT

n c c1,c2, ,cT

n b b1,b2, ,

bT

n

a a1n

A 11

am1

amn

还可以写成：

mincT

x

ns.t. xjaj b

j 1

x 0

其中a [aT

j

1j,a2j,...,amj]

称c1,c2,...,cn为变量x1,x2,...,xn的价格系数，c为价格系数向量。

2.化为标准形式的方法

考虑线性规划的一般形式：

t

min

c

j 1t

j

xj

，p 1,2,...,u ，q u 1,...,u v ，r u v 1,...,m

。

s.t. apjxj bp

j 1t

aqjxj

j 1

bq

arjxj

j 1

t

br

xj 0 ，j 1,2,...,t

假定所有的bi

0,i 1,2,...,m

在线性规划的标准形式中，除要求各变量非负外，只存在等式约束。为此，采用如下方法来消除不等式约束。

1)松弛变量

对于" "约束，可以引入松弛变量使它变为等式约束。 考虑 apjxj

j 1t

bp

，引入新变量x

t p

0

，使之变成等式约束， apjxj xt p

j 1

t

bp

。

2)剩余变量

对于" "约束，可以引入剩余变量使它变为等式约束。 考虑 aqjxj

j 1t

bq

，引入新变量x

t q

0

，使 aqjxj

j 1

t

xt q bq

。

在引入u个松弛变量、v个剩余变量后，线性规划将含有t u v n个变量，

m

个等式约束，从而化成了标准形式。

新引入变量的价格系数全部设为零，因此目标函数中不会出现新变量。

t

min

c

j

xj

j 1t

s.t. apjxj xt p bp

，p 1,2,...,u j 1 t

aqjxj

xt q bq

，q u 1,...,u v

j 1

t

arjxj

br

，r u v 1,...,m

j 1

xj 0 ，j 1,2,...,t u v

例：把线性规划

min 3x1 4x2

s.t. x1 2x2 4

x1 x2 1 x1 x2 3

x1 0,x2 0

化为标准形式。

对于第一个约束引入松弛变量x3

0

，对于第一个约束引入剩余变量

x4 0，于是标准形式为：

min 3x1 4x2

s.t. x1 2x2 x3 4

x1 x2 x4 1 x1 x2 3

x1 0,x2 0,x3 0,x4 0

3)自由变量

以上讨论都要求变量的取值是非负的。实际问题中某些变量可能没有这种约束，也就是说某些变量可以任意取值，这种变量称为自由变量。此时可按下述两种方法将其消除。

①假定xi是自由变量，引入两个变量x

i

0

，x

i

0

，令x

i

xi xi

，然后将

此式代到线性规划的目标函数和约束函数中就能将自由变量xi消除。在求出新线性规划的最优点后，再利用此式即可定出xi。

②假定xi是自由变量，取一个包含xi的等式约束

ak1x1 ak2x2 ... akixi ... aknxn bk

由上式解出xi并将其代到线性规划的目标函数和其它约束函数中就能将自由变量xi消除。

3.单纯形法的基本理论

线性规划的容许集一般是一个凸多面体，其次，由于目标函数是线性的，因此它的等值面是超平面。因此，目标函数的最优值必在凸多面体的某个顶点达到。

单纯形法的基本思想是：从容许值的一个顶点出发进行迭代计算，在它所有相邻的顶点中选择使目标函数值有较大下降的某个顶点代替原来的顶点。如果最优点存在，那么经过有限次迭代必定求得最优点。

1)凸集

凸集是一种点的集合，形象地说，它的内部没有洞，边界不向内凹。 定义1:设x1,x2,...,xl是Rn中的l个已知点。若对于某点x Rn存在常数

1, 2,..., l 0且 i 1，使得x

i 1l

l

i 1

i

xi

，则称x是x1,x2,...,xl的凸组合。

定义2:设集合C

R

n

。如果对于任意两点x1,x2 C，它们的任意凸组合仍然

属于C，那么称集合C为凸集。

特别地，若C中仅包含一点，则该点也是凸集。

定义3: Rn中有限个确定点的所有凸组合的集合称为凸多面体。

定义4：若凸集C中的点不能表示成这个集合中另外两个不同点的凸组合，则称该点为极点。

2)线性规划解的性质

设线性规划的容许集为D xAx

b,x 0

定理1:若线性规划有容许解，则其容许集D是凸集。 证明：①若D中仅包含一点，根据凸集定义，D就是凸集。 ②设x1和x2是容许解

考虑x1和x2的任意凸组合x 1x1 2x2，其中 1 0， 2根据上述条件可知：x 0，Ax于是x D。

定理2:若线性规划的容许集D是凸多面体，则目标函数的最优值一定在D的某个极点处达到。

证明：设凸多面体D有有限个极点，设用x1,x2,...,xl表示。

假定目标函数的最优值不在上述极点上达到，则一定存在一点x0，使得：

cx0 cxj，j 1,2,...,l

T

T

0且 1 2 1。

1Ax1 2Ax2 b

因为x0 D，可表达成x1,x2,...,xl的凸组合，即

l

x0

j 1

j

xj

，其中

l

j

0，

j 1

l

j

1。

于是有c

T

x0 …… 此处隐藏：5976字，全部文档内容请下载后查看。喜欢就下载吧 ……