2015年6月线性规划.doc

第一部分 线性规划
§1线性规划问题
1. 线性规划问题的数学模型
例1 选用饲料问题
某饲养场饲养动物出售，设每头动物每天至少需700g蛋白质、30g矿物质、100mg维生素。现有五种饲料可供选用，各种饲料每kg营养成分含量及单价如下表，要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。

饲料
蛋白质(g)
矿物质(g)
维生素(mg)
价格()
1
2
3
4
5
3
2
1
6
18
1
0.5
0.2
2
0.5
0.5
1.0
0.2
2
0.8
0.2
0.7
0.4
0.3
0.8

模型建立：
引入决策变量：设每头动物每天需要选用第种饲料；
本题的数学模型为：

例2 杂粮的买进卖出问题

某贸易公司专门经营某种杂粮的批发业务。公司现有库容5000担的仓库。一月一日，公司拥有库存1000担杂粮，并有资金20000百元。估计第一季度杂粮价格如下表。如买进的杂粮当月到货，但需到下月才能卖出，且规定货到付款。公司希望本季度末库存为2000担，问应采取什么样的买进与卖出策略才能使三个月的总利润最大？
1
月份
进货价（百元）
出货价（百元）
一月
二月
三月
2.85
3.05
2.90
3.10
3.25
2.95

1
模型建立
（模型假定：假定每个月是先出货，再进货。）
引入决策变量：设为每月买进的杂粮担数，为每月卖出的杂粮担数
确定目标函数：三个月的总利润

写出约束条件：
存货限制 ； 库容限制
资金限制
期末库存
决策变量的非负约束：

例3 人员安排问题
某昼夜服务的公交线路每天各时间区段所需司机和乘务员的人数如下表，设司机和乘务员分别在各时间区段一开始时上班，并连续工作八个小时，问该公交线路至少需要配备多少名司机和乘务人员？
班 次
时 间
所需人数
1
2
3
4
5
6
6:00~10:00
10:00~14:00
14:00~18:00
18:00~22:00
22:00~2:00
2:00~6:00
60
70
60
50
20
30

模型建立
引入决策变量：用表示有名司机和乘务人员在第班次开始时上班；
确定目标函数：使配备的司机和乘务员总人数最少，即

写出约束条件：为保证第1班所需的司机和乘务员人数，应有
， ， ， ， ；
决策变量的非负约束：
2
2. 线性规划问题的标准形式
对于具体的线性规划问题；目标函数有的是极大化，有的是极小化；约束条件有的是≤，有的是≥，有的是＝；决策变量可以≥0，也可以≤0，还可以不受限制。为了方便线性规划问题的统一求解，我们规定一个标准形式。

… … …

； 其中
标准形式的特点：① 目标函数要求是极大化；② 约束条件要求等式约束；
③ 决策变量满足非负约束；④ 右端常数项非负 。
引入矩阵和向量：记 ---- 目标函数的系数行向量
---- 约束条件系数矩阵 ；
---- 决策变量列向量 ；
---- 右端常数项列向量 ；
---- 的系数列向量
则标准形式的矩阵描述为：
向量描述为：

3. 标准形式的化法
① 极小化化成极大化；如：
② 化不等式约束为等式约束；
如：，其中，并称为松弛变量
如： ，其中，并称为松弛（或剩余）变量
③ 化决策变量满足非负约束；
如：，则令 ，并用去代替
如：符号不限，则令，其中，并用去代替

3
如：，则令，此时有
如：，则令，此时有，并用去代替
练习题

4. 线性规划问题中有关解的概念及线性规划问题的重要性质：
① 可行解：满足所有约束条件的解；
② 可行域：所有可行解构成的集合；
③ 最优解：使目标函数值达到最优时的可行解；
④ 基矩阵，基变量，非基变量，基本解，基本可行解。
为了了解上述概念，我们先看如下例题

对于线性规划问题：
其中A为矩阵，且，B为A的任意一个阶满秩子方阵，则称B为线性规划问题的一个基矩阵；B中列向量所对应的决策变量称为基变量，其余的决策变量称为非基变量；令非基变量的取值为0，得基变量相应的取值，由此得到的解称为规划问题的一个基本解；如果基本解满足非负约束，则称它为基本可行解。

⑤ 重要性质：如果线性规划问题存在可行解，则一定存在基本可行解；
如果线性规划问题存在有界最优解，则它一定存在有界的最优基本可行解，即线性规划问题的最优解可以在基本可行解处得到。

5. 线性规划问题的求解方法—单纯形法
1）单纯形法的基本思想
从线性规划问题的一个基本可行解出发，判断它是否为最优解；如果不是，则将它进行迭代，迭代至下一个基本可行解，每次迭代，要使目标函数值有所改善；这样经过有限次迭代后，最终可以找到最优解或判断问题无界。

4
2）基本可行解的迭代过程
下面通过实例来介绍 例
选取一个基矩阵 ，对应的基变量为 ，非基变量为，
令非基变量的取值为0，得初始基本可行解 ，相应的目标函数值为 .
所谓基本可行解的迭代，指的就是：让一个基变量出基，再让一个非基变量进基。

ⅰ）现在都是非基变量，那么让哪一个非基变量进基呢？
考察 ：让的取值增加一个单位，即让的取值从0增加到1，其它非基变量取值不变，仍为0，得可行解 ，此时目标函数值为 ；目标函数值的改变量为
这个数值3称为非基变量的检验数，记作，即。它表示当非基变量的取值增加一个单位时，可使目标函数值增加3个单位。
同样可得 ，
让的取值增加一个单位，可使目标函数值增加3个单位；让的取值增加一个单位，目标函数值没有改变；让的取值增加一个单位，可使目标函数值增加2个单位；针对极大化问题，我们自然希望目标函数值增加得越多越好，因此选作为进基变量。

针对极大化问题，我们选取最大正检验数所对应的非基变量进基

ⅱ）之中，哪一个基变量出基呢？
由于仍是非基变量，取值为0，故此时的约束条件变为
让的取值增加一个单位，可使目标函数值增加3个单位；的取值增加二个单位，可使目标函数值增加6个单位；如此一来，我们希望的取值增加得越多越好；但由于要保
5
证的取值非负，故的取值不能无限增大，最多可增加到 ；当时，便有，于是出基。
此时新的基本可行解为 ，新的目标函数值为

ⅲ）最优解判别定理
从上面的分析可知，如果所有的检验数，则说明，让任何非基变量的取值增加，都将使目标函数值有所减少，此与极大化目的相违背，由此的最优解判别定理：

针对极大化问题，如果所有非基变量的检验数，则此时的基本可行解便是最优解。

ⅳ）单纯形表格
对于线性规划问题LP：
设B是LP的一个可行基矩阵，在可行基B之下，将矩阵和向量A、X、C分解成：
， ， .
则线性规划问题LP化成：
.
现将上式中的变量与系数分离，建立如下形式的单纯形表格

检验数

其中非基变量的检验数

6
例题： 用表格单纯形法解如下线性规划：

5
4
0
0
0

0

1
3
1
0
0
90
0

2
1
0
1
0
80→
0

1
1
0
0
1
45

5↑
4
0
0
0

0

0

1

0
50
5

1

0

0
40
0

0

0

1
5→

0
↑
0

0

0

0
0
1
2

25
5

1
0
0
1

35
4

0
1
0

2
10

0
0
0

215

从最优单纯形表得知，最佳生产方案为：甲产品生产35件，乙产品生产10件，工厂获利最多，最大利润为

7
6. 用LINDO软件求解线性规划问题
直接输入
max 5x1+4x2
st
x1+3x2<90
2x1+x2<80
x1+x2<45
end

将文件存储并命名后，选择菜单“Solve”，并对提示“DO RANGE (SENSITIVITY) ANALYSIS”（灵敏度分析）回答“是”或“否”。即可得到如下输出结果。
LP OPTIMUM FOUND AT STEP 2
OBJECTIVE FUNCTION VALUE
1) 215.0000
VARIABLE VALUE REDUCED COST
X1 35.000000 0.000000
X2 10.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
2) 25.000000 0.000000
3) 0.000000 1.000000
4) 0.000000 3.000000
NO. ITERATIONS=
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE
COEF INCREASE DECREASE
X1 5.000000 3.000000 1.000000
X2 4.000000 1.000000 1.500000
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
2 90.000000 INFINITY 25.000000
3 80.000000 10.000000 12.500000
4 45.000000 5.000000 5.000000
注意：① LINDO软件中已经规定所有决策变量非负；
② 输入时，乘号省略，式子中不能有括号，右端不能有数学符号；
③ 模型中符号“≤”用“＜＝”形式输入，它与“＜”等效；“≥”用“＞＝”
形式输入，它与“＞”等效；
④ 输入文件中第1行为目标函数，2）、3）、4）是为了标示各约束条件，便于从输出结果中查找相应信息。

8
LINDO输出结果中若干单词的含义
⑴ DO RANGE (SENSITIVITY) ANALYSIS --- 询问是否作灵敏度分析
⑵ LP OPTIMUM FOUND AT STEP 2 --- 单纯形法在两次迭代后得到最优解
⑶ OBJECTIVE FUNCTION VALUE 1) 3360.000 --- 最优目标函数值为 3360.00
⑷ VARIABLE --- 变量
⑸ VALUE --- 数值
⑹ REDUCED COST --- 表示的检验数，即当该决策变量的取值增加一个单位时，目标
函数值的改变量.
⑺ SLACK OR SURPLUS --- 松弛变量或剩余变量的值
⑻ DUAL PRICES ---对偶价格的值，其含义为：当该种资源增加1个单位时，最优值
的增加量，经济学中称之为“影子价格”。
⑼ NO ITERATIONS=2 --- 表示单纯形法进行了2次迭代
⑽ CURRENT COEF 72 --- 当前值
ALLOWABLE INCREASE 24 --- 允许增加值
ALLOWABLE DECREASE 8 --- 允许减少值
表示在最优解不变的条件下，目标函数系数允许变化的范围；

的目标函数系数在区间内变化时，最优基和最优解保持不变。
⑾ RIGHT HAND SIDE RANGES --- 表示的是：约束行的右端常数项的值在什么范围内
变化时，最优基保持不变。
⑿ ROW 2 ,CURRENT RHS 50.00 ,ALLOWABLE INCREASE 10.00 ,
ALLOWABLE DECREASE 6.667 --- 表示第2行约束右端项的当前值为50.00；允许增加值为10.00；允许减少值为6.667。即第2行约束右端的常数项的值在区间内变化时，最优基保持不变。

例题2 用LINDO软件解如下线性规划

直接输入
max 72x1+64x2
st
2)x1+x2<50
3)12x1+8x2<480
4)3x1<100
End
将文件存储并命名后，选择菜单“Solve”，并对提示“DO RANGE (SENSITIVITY) ANALYSIS”（灵敏度分析）回答“是”或“否”。即可得到如下输出结果
9
LP OPTIMUM FOUND AT STEP 2
OBJECTIVE FUNCTION VALUE ----最优目标函数值
1) 3360.000
VARIABLE VALUE REDUCED COST
X1 20.000000 0.000000
X2 30.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES ----对偶价格的值
2) 0.000000 48.000000
3) 0.000000 2.000000
4) 40.000000 0.000000
NO. ITERATIONS= 2 --- 单纯形法在迭代2次后得最优解
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE
COEF INCREASE DECREASE
X1 72.000000 24.000000 8.000000
X2 64.000000 8.000000 16.000000
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
2 50.000000 10.000000 6.666667
3 480.000000 53.333332 80.000000
4 100.000000 INFINITY 40.000000

例4 原油采购与加工
某公司用两种原油A和B混合加工成两种汽油甲和乙。甲、乙两种汽油含原油A的最低比例分别为50%和60%，每吨售价分别为4800元和5600元。该公司现有库存原油A500吨，原油B1000吨，还可以从市场上买到不超过1500吨的原油A。原油A的市场价为：购买量不超过500吨时的单价是10000；购买量超过500吨但不超过1000吨时，超过500吨的部分售价是8000；购买量超过1000吨但不超过1500吨时，超过1000吨的部分售价是6000；该公司应如何安排原油的采购与加工？
模型建立
引入决策变量：设原油A用于生产甲种汽油的数量为，用于生产乙种汽油的数量；
原油B用于生产甲种汽油的数量为，用于生产乙种汽油的数量；
目标函数是利润最大，其中利润等于销售汽油的收入减去购买原油A的支出
当原油A的购买量为时，采购原油A的支出为（单位：千元）

10
写出约束条件：
两种汽油中含原油A的比例要求
；
两种原油的库存限制
； ；
所有决策变量的非负限制
模型求解
求解方法Ⅰ： 将原油A的采购量分解为三个变量，用它们分别表示三种价格采购原油A的吨数，于是
注意：只有当时，才有；此条件可以表示为：
（当时，要保证上式成立，必有；当时，上式中的取值可以是，也可以是 ）
只有当时，才有；此条件可以表示为：
此外

用LINGO软件求解时，按如下方式进行输入
model:
max=4.8*x1+5.6*x2+4.8*x3+5.6*x4-10*y1-8*y2-6*y3;
x1-x3>=0;
2*x2-3*x4>=0;
x1+x2<=500+y1+y2+y3;
x3+x4<=1000;
y1+y2+y3<=1500;
(y1-500)*y2=0;
(y2-500)*y3=0;
y1<=500;
y2<=500;
y3<=500;
end
保存并命名后，按“solve”，可得如下结果：
Local optimal solution found at iteration: 8
Objective value: 4800.000
Variable Value Reduced Cost
X1 500.0000 0.000000
X2 0.000000 0.000000
X3 500.0000 0.000000
11
X4 0.000000 0.4000000
Y1 0.000000 0.4000000
Y2 0.000000 0.000000
Y3 0.000000 0.000000
Row Slack or Surplus Dual Price
1 4800.000 1.000000
2 0.000000 -4.800000
3 0.000000 -2.000000
4 0.000000 9.600000
5 500.0000 0.000000
6 1500.000 0.000000
7 0.000000 -0.3200000E-02
8 0.000000 -0.7200000E-02
9 500.0000 0.000000
10 500.0000 0.000000
11 500.0000 0.000000

注意LINGO软件的输入形式
① 程序以”Model：”开始，每行最后加“；”，并以“end”结束；
② 非负约束可以省略，但乘号*不能省略；
③ 式中可以有括号，右端也可以有数学符号。

12