四、线性规划法

线性规划法是数学规划法中一种最成熟、应用最广泛的方法。它主要解决的问题是如何最大限度地发挥有限资源的作用，找出其合理利用人力、物力和财力的有效途径。线性规划法在区域地理规划中应用十分广泛。

（一）线性规划解法简介 1.线性规划问题的标准型。

将各种具体的线性规划问题，可抽象成下述线性规划问题的标准形式：

目标函数Maxz = c1 x1 + c2 x2 +Λ +cn xn

满足约束条件：

 a 11 X1 + a12 X2 +Λ +a 1n Xn = b1

 a X + a X +Λ +a X = b

 21 1 22 2 2 n n 2

Λ Λ Λ Λ Λ Λ Λ Λ Λ Λ Λ Λ Λ Λ

a X + a X +Λ +a X = b

 m1 1

m2 2

mn n m

 X 1 , X2 mΛ Λ , Xn ≥0

可简写为：

Max z = CX

AX = b

X≥0

C = (c1 ,c 2 ,Λ Λ c n )为价值向量

X = (x , x ,Λ Λ x ) ^T 为决策变量向量

 a11

a 12 Λ Λ

a1n 

A＝Λ Λ Λ Λ Λ Λ Λ Λ  为系数矩阵

 a a Λ Λ a 

mn

b = (b1 , b 2 ,Λ Λ

b ) ^T

为限定向量。通常bi ≥ 0

2.线性规划的解法。线性规划的基本解法是单纯形法或改进单纯形法。单纯形法的基本思路是：根据问题的标准型，从一个基本可行解开始，转换到另一个基本可行解，并且使目标函数的值逐步增大；当目标函数达到最大值时，问题就得到了最优解。其主要方法如下：

①初始基本可行解的确定。对于各种线性规划问题的形式，通过加入松驰变量、人工变量后，化为标准型。这时即可直接观察到存在 m 个线性独立的单位向量（可行基）。令非单位向量对应的变量（非基变量）为零，则单位向量对应的变量（基变量）等于相应的限定向量，即求得了初始基本可行解。

②最优性检验。最优性检验的目的是检验基本可行解是否是最优解。检验公式为：

σj=cj+zj （8·2·14） j 非基变量标号，共有 n－m 个cj—非基变量对应的价值系数

m

（zj = ∑

i= 1

ci a ij

(ci —基变量对应的价值系数，a ij—第j个非可行基向

量元素）

检验标准是：

如果对于所有 j 都有σj≤0，则基本可行解为最优解；

如果有某些σj＞0，则问题尚未达到最优解。需进行变量变换。若有两个以上的σj＞0，一般选 v＞0 中的最大者作为换入变量。

③换出变量的确定。换出变量确定的计算公式：

θ = Min ( bi a

i a i1

> 0) (l为换入变量标号） （8·2·15）)

bi—原基变量的基本可行解值 aij—换入变量对应的系数列向量元素

④换出变量对应的系数向量的变量。变换公式：

 1 (i = k)

 a kl

E_kl =  a

(i = 1,2,Λ m)

（8·2·16）

− i1

(i ≠ k)

 a k1

k—换出变量所在行标号 l—换入变量对应的系数列向量标号

⑤求新的基本可行解。公式如下：

b i + b k • Ei1

(i ≠ k)

bi ' = b

k • Ei1

(i = k) (i = 1,2,Λ m) (8 • 2 • 17)

bi’—新基本可行解bi——原基本可行解

⑥单纯形表。用单纯形法解线性规划问题。需多次迭代运算，用单纯形表进行迭代运算十分方便。单纯形表的一般形式如下（见表 8—12）：

表 8 — 12

CB— 基变量对应的价值量XB 基变量向量

b— 基变量所对应的基本可行解的值3.单纯形法的计算步骤。

第一步：找出初始可行基，确定初始基本可行解，建立初始单纯形表。第二步： 检查对应于非基变量的检验数σj＞0，则已得到最优解，停止

计算。否则转入下一步。

第三步：在所有σj＞0 中，若有一个σk 对应 xk 的系数列向量 PK≤0，则问题无解，停止计算，否则，转入下一步。

第四步：根据 Max， 确定 X1 为换入变最。根据θ规则：

θ = min ( bi a > 0) = b k

i a i1 a k

确定 XK 为换出变量，得到主元素 ak1。

第五步：互换“X1⋯⋯Xn”行中 X1 与 XK 的位置。将换出变量（XK）对应的系数列向量变换公式（8.2.16）计算出新的系数列向量代替之。用 X1 代替XB 向量中的 XK。

第六步：根据公式（8.2.17）计算出新的基本可行解。至此，得到新的单纯形表，再以此为起点重复上述步骤，直到得到最优解为止。

在区域地理规划实际应用线性规划法时，往往由于模型庞大，很难用手工计算，一般都依据上述解法的原理、编制成计算机程序，利用计算机运算。

（二）线性规划在区域地理规划中的应用

线性规划法在区域地理规划中应用十分广泛，它既可用于区域综合发展规划，又可用于区域专项发展规划。其基本思路一般是在各类资源的限制下， 取得最大效益。在区域地理规划中，应用线性规划法构建模型时，应注意以下几点：第一，变量一般根据规划对象的组成要素设置。在区域综合发展规划中，由于规划对象组成要素众多，往往选取主要要素构成交量集，可降低模型的复杂性。第二，区域地理规划往往是多目标的、而线性规划是单目标规划，因此一般选取最重要的目标作为目标函数，其它目标转为约束条件。如在区域综合发展规划中，多把经济效益作为目标函数，把社会效益、生态效益等转为约束条件。第三，对规划目标有影响的各种因素构成约束条件集。在区域综合发展规划中，约束条件集应包括：社会需求约束、生态平衡约束、自然资源供给约束、人力资源供给约束、资金供给约束、部门间联系约束等。现以某县畜牧业发展规划模型设计为例，说明线性规划模型设计的特点。

1. 变量设置。根据该县畜牧业的主要畜种组成，模型变量设置如下：

1. 目标函数。该模型选择总产值为直接目标，即畜牧业总产值达到最大。Maxz=67.1x1+1706.5x2+10.30x3+124.03x4+16.55x5+7.11x6

   ＋

120x7+40.6x8+387.65x9

上述系数为各畜禽的产值系数。

1. 约束方程。该模型设计了如下约束方程。

①饲料约束：

302.4x1 ＋ 4020x2 ＋ 3.23x3 ＋ 393.33x4 ＋ 40.5x5 ＋ 25.22x6 ＋ 36.5x8 ≤

810000000

②耕地约束： 11000≤x9≤120000

③肉、蛋、奶需求约束77.76x1≥86586400

8.55x3+0.63x5+1.06x6≥17963400

6.40x8≥39785600

7680x2＋640x4≥61314000

④皮毛需求约束： 0.57x3300000

0.8x5≥400000

20x7≥200000

0.7x8≥15000

⑤饲养和投资能力约束：

x1≤1400000 x2≤2000

x3≤600000 x4≤238000

x5≤ 600000 x6≤ 16000000

x7≤15000 x8≤25000

⑥非负约束：

x1,x2,x3,x4,x5,x6,x7,x8,x9≥0

上述模型加入松驰变量后，便化成了线性规划的标准形式。利用计算机程序运算，即可得到最优解如下：