实验6最优问题求解实验.doc

6．线形规划最优问题求解实验

6.1 实验目的
本实验通过具体问题介绍一些线性最优问题的求解，同时介绍线性规划问题的图解法、软件解法以及当线性规划问题规模较小，并且存在最优解时的理论解法。

6.2 实验内容
线性规划(Linear Programming)是运筹学的一个重要分支，在科学实践中有着广泛的应用，不仅许多实际课题属于线性规划问题，而且运筹学其它分支中的一些问题也可转化为线性规划问题来计算，因此，线性规划在最优化学科中占有重要地位。本实验通过具体问题介绍线性规划的一些基本概念和性质，给出求解线性规划问题的图解法和软件解法以及当线性规划问题规模较小，并且存在最优解时的理论解法。
6.2.1 实验问题
问题1（生产计划问题）某工厂生产条件如表6-1所示：
表6-1　生产条件
车间　
1
2
3
生产单位甲产品需工时
5
2
1
生产单位乙产品需工时
2
3
5
一周可用工时
170
100
150
生产每一件产品的工序必须经过三个车间，生产单位甲产品工厂获利10元，生产单位乙产品工厂获利18元。问厂方如何安排生产才能使每周获得的利润最大？
问题2（运输问题）某产品的产地、产量、需地、需求量、单位产品运输费用如表6-2所示：
表6-2　单位产品运费
产地
产量
需地
1
2
3
4
需量
30
60
50
60
Ⅰ
70
运
输
费
3
11
3
10
Ⅱ
40
1
9
2
9
Ⅲ
90
7
4
10
15
问如何安排运输才能使运费最少？
问题3（人员安排问题）为了城市居民和流动人口的安全，西安市110警察大队要求每天各个时间段都有一定数量的警员值班，随时处理突发事件的发生，由于精力高度集中每人上班时间是连续6小时，中间不休息。下表6-3是一天8个班次所需值班警员的人数情况统计，问：在不考虑时间段中间有警员上班和下班的情况下，西安市110警察大队至少需要多少警员才能满足值班需要？
表6-3
班次
时间段
人数
班次
时间段
人数
1
6:00∽9:00
70
5
18:00∽21:00
80
2
9:00∽12:00
80
6
21:00∽24:00
100
3
12:00∽15:00
65
7
24:00∽3:00
120
4
15:00∽18:00
90
8
3:00∽6:00
90
问题4（任务分配问题）某车间有甲、乙、丙三台车床可用于加工三种零件，这三台车床可用于工作的最多时间分别为700小时、800小时和900小时，需要加工的三种零件的数量分别为300、400和500，不同车床加工不同的零件所用的时间数和费用如下表6-4所示，问：在完成任务的前提条件下，如何分配加工任务才能使得加工费用最低？
表6-4
车床
名称
加工单位零件所需时数
加工单位零件所需费用
可用与工
作的时数
零件1
零件2
零件3
零件1
零件2
零件3
甲
0.6
0.5
0.5
7
8
8
700
乙
0.4
0.7
0.5
8
7
8
800
丙
0.8
0.4
0.6
7
9
8
900
这里提出的问题虽然内容不同，但其涉及的数学知识具有相似之处，都是在一定的条件下求其最大值或者最小值，并且从下面的建立的数学模型也可看到，这些条件都是线性的。
6.2.2 建立数学模型
问题1的数学模型 设甲产品生产数量为，乙产品生产数量为，则工厂获利与变量，之间的关系以及变量应满足的条件可归纳成如下形式：
；
满足
这样该问题就归结为在一定的约束条件下，求，使得最大的约束极值问题。
问题2的数学模型 设第个产地运往第个需地的数量为，单位运价为，第个产地的产量用表示，，第个需地的需求量用表示，，则
总运费为 ，
约束条件 ，，
，，
，，
这样该问题就归结为在一定的约束条件下，求，使得最小的约束极值问题。
问题3的数学模型 可设第个班次开始上班的警员数为，那么根据题意可得下面的数学模型：
，

问题4的数学模型 可设分配给车床甲加工三种零件的数量分别为，分配给车床乙加工三种零件的数量分别为，分配给车床丙加工三种零件的数量分别为，则根据问题的实际要求可得下面的数学模型：
，

上述四例具体意义虽不尽相同，但从数学模型来看，却有共同的特点：求一组非负变量，使得关于这组变量的线性函数在一定的约束条件（关于变量的线性等式或者不等式）下取得最大值或者最小值。我们可把这类问题用下面一般的数学模型表示：
，

这类问题通常称为线性规划问题，常常简记为LP问题。也可以写成下面的矩阵形式：
，
（6-1）
这里为约束矩阵，为价值向量（赋权向量），一组非负变量通常称为决策变量，关于这组决策变量的线性函数通常称为目标函数。
通常在解线性规划问题时都是先将它的一般形式化成下面的标准形式：
，

也可以写成下面的矩阵形式：
，
（6-2）
将一般线性规划问题化成标准形式的线性规划问题，分下面三步完成。
(1) 目标函数的转换：标准形式的线性规划问题是求目标函数的最大值，如果实际问题要求目标函数的最小值，则可通过给目标函数乘以-1来转换。
(2) 约束条件的转换：标准形式线性规划问题的约束条件是一些线性等式，如果实际问题给出的约束条件是线性不等式
，
则可通过引入松驰变量，将不等式化为等式

这里也称为剩余变量。
(3) 变量转换：标准形式的线性规划问题中的变量都是非负的，如某个变量的约束条件为或者，则可令或者，这样变为非负变量；如果某个变量无非负限制(称为自由变量)，则可令

代入原问题，将自由变量替换掉。
注意：也可将标准形式的线性规划模型定义为求目标函数的最小值，二者没有本质的差别。
例6.1 将下列线性规划问题化为标准形式：
，

解 引入松驰变量，再令，代入方程后得
，

即为标准形式。
6.2.3 问题解法
下面我们主要介绍解这类问题的三种方法：图解法、MATLAB软件解法和理论解法。对于某些比较简单的线性规划问题一般采用图解法求其最优解。
(1) 图解法
下面我们通过求问题1的最优解来说明线性规划问题图解法的一般步骤。
解（问题1） 用图解法解该线性规划问题首先要画出满足约束条件的可行域，即下图中的阴影部分D。

Fig.6.1
将目标函数写成，为任意常数时，即为一组平行直线，直线上的点为等值点（做成等值线）。当值由小变大时，直线自下往上平行推移，由于直线10*x1+18*x2=K的斜率大于直线2*x1+3*x2=100的斜率，所以当直线10*x1+18*x2=K自下往上平行推移时最后与可行域相交的是图中的A点，此时A点即为约束条件下目标函数取得最大值的点，A点的坐标为（，），所以该线性规划问题的最大值为。考虑到生产产品的数量应是整数，所以安排生产甲产品的数量应是7件，安排生产乙产品的数量应是28件，每周获得的最大利润是574。
从上述的解题过程可以看出，图解法的步骤可以分为：
1）作出可行域的图形；
2）做目标函数的等值线；
3）将目标函数的等值线自坐标原点开始向上平移，与可行域的最后一个交点，就是最优点；
4）求最优点坐标，及最优值。
(2) 理论解法
观察上面图解法的例子，我们不难发现，最优值点A正是可行域的一个顶点，从下面给出的关于线性规划问题的一些基本性质不难看出，这一现象并非偶然。这里对给出的性质不做证明，感兴趣的读者可以自己给出证明过程。
性质6.1 LP问题的可行域是凸多面体(凸集)，特别地，当目标函数是二元函数时，可行域是凸多边形。
定义6.1设是秩为的阶矩阵，的个线性无关的列构成的子矩阵称为LP问题的一个基(基阵)，的列向量称为基列(基向量)，相应于基列的变量称为基变量，当然也有对应的非基向量和非基变量。
定义6.2 设是秩为的阶矩阵，由

可得，那么

为的一个解，若令，则称

为LP问题的一个基本解；若，则称为LP问题的一个基本可行解，简称基可行解，这时的基称为可行基。
注意：至多有个基，故基本可行解至多有个。
性质6.2 是LP问题可行域的顶点等价于是LP问题的基本可行解。
性质6.3 如果LP问题存在最优解，则最优解一定能在可行域的顶点中取到。
由上面的性质可以看出，若LP问题存在最优解，则它一定是LP问题的一个基本可行解，由于线性规划问题的基本可行解至多有个，所以当较小时，我们可通过求出所有的基本可行解，然后再从这些可行解中取使目标函数值最优的一个，即为线性规划问题的最优解。
例6.2 解下面的线性规划问题：
，

解 首先引入松驰变量,，将上述线性规划问题由一般形式化成标准形式：

现在求其基本可行解。
，
由于每确定一个基矩阵，就能解得一个基本解，下面分别选择不同的基，求出所有基本解，再从中找出基本可行解。
令，解得基本解为；
令，解得基本解为；
令，解得基本解为；
令，解得基本解为；
令，解得基本解为。
以上对于所有的基都进行了计算，得到5个基本解，其中，，，是基本可行解，则不是，因为的第4个分量是负数。然后将上述4个基本可行解代入目标函数进行比较，易知为问题的最优点，此时目标函数的最优值为10。
该线性规划问题也可用图解法求解，可行域为下图中的阴影部分，

Fig.6.2
上图中可行域的顶点分别为O，A，B，C四点，不难得出A点即为问题的最优值点，A点的坐标，与上述通过基本可行解得到的最优值点的答案是一致。
读者不难发现一个更有意思的结果：前面算出的4个基本解，，，的前两个分量刚好分别是上图中可行域的4个顶点的坐标。
通过例子6.2，我们可以得到线性规划问题理论解法的一般步骤：
(1) 将线性规划问题的模型标准化，找出线性规划问题的所有基矩阵；
(2) 对找出的每一个基矩阵求得一个基本解；
(3) 在所有的基本解中找出基本可行解；
(4) 在所有的基本可行解中找出最优解；
(5) 算出最优解处目标函数的最优值。
通过问题1我们可以看到，当线性规划问题是二元规划时，只要有最优解，我们用图解法很容易就可求得它的最优解；从例子6.2可以看到，当线性规划问题是二元以上且“规模较小”时，只要有最优解，用理论解法也可得到它的最优解，但是当较大时，采用理论解法计算量就会很大，显然是不可取的。例如本实验中的问题2，我们若将其化为标准型后就变为：
，
满足条件： ，，
，，
，，
此时，若用解析法求其优化问题的最优解必须借助于计算机，靠手工计算几乎是不可能的。在这种情况下，也可采用单纯形方法求解，有关单纯形方法的详细内容这里就不讲了，感兴趣的读者可以参考相关专业书籍。下面我们介绍用MATLAB软件求其最优值的方法
(3) 软件解法
在前面的实验中我们已经介绍过用MATLAB软件求约束极值的方法，那些方法也可以用来解线性规划问题。这里我们介绍MATLAB软件优化工具箱提供的专门解线性规划问题的函数命令lp和linprog。下面我们以标准形式的线性规划问题为例介绍这两个命令的用法，更详细的介绍读者可在MATLAB软件的工作空间中用命令help lp和help linprog获得。
函数lp有下面几种常用的使用格式：
(1) x=lp(c,a,b)
该命令是用来解规划问题：
, （6-3）
,
(2) x =lp(c,a,b,vlb, vub)
该命令是用来解规划问题：
, (6-4)
,
vlb vub,
这里不等式vlb vub表示变量向量分量的上下限。
(3) x=lp(c,a,b,vlb,vub,x0)
该命令是用来解规划问题（6-4），其中x0是给出的初始点向量。
(4) x=lp(c,a,b,vlb,vub,x0,n)
该命令是用来解规划问题（6-4），其中x0是给出的初始点向量，n表示约束条件中的前n个约束是等式约束。
除此之外，MATLAB软件还提供了函数lp的下面几种用法：
x=lp(c,a,b,vlb,vub,x0,n,display)
[x,lambda]=lp(c,a,b)
[x,lambda,how] = lp(c,a,b)
关于这些命令的具体含义感兴趣的读者可以自己去试验，这里不再讲述。为了增加各种方法的可比性，下面我们用lp函数命令解前面两个例题中的线性规划问题。对于问题1中的线性规划问题可由下面的程序完成。
程序wenti1.m：
c=[-10,-18];
a=[5,2;2,3;1,5];
b=[170;100;150];
vlb=[0;0];
vub=[]; %变量没有上界时，将vub设为空向量
x=lp(c,a,b,vlb,vub)
maxz=-c*x
执行的结果是
x = 7.14285714285713
28.57142857142858
maxz = 5.857142857142857e+002
显然这个结果与前面用图解法得到的结果是一致的。
例6.2中的线性规划问题可由下面的程序完成。
程序lizi2.m：
c=[-1,-3];
a=[1,2;0,1];
b=[8;2];
vlb=[0;0];
vub=[];
x=lp(c,a,b,vlb,vub)
maxz=-c*x
执行的结果是
x = 4
2
maxz = 10
显然这个结果与前面用图解法和理论解法得到的结果是一致的。下面我们用MATLAB软件求问题2的最优解。编写下面的程序：
wenti2.m
vlb=zeros(12,1);
vub=[30;60;50;60;30;40;40;40;30;60;50;60];
c=-1*[3,11,3,10,1,9,2,9,7,4,10,15];
a=[1,1,1,1,0,0,0,0,0,0,0,0
0,0,0,0,1,1,1,1,0,0,0,0
0,0,0,0,0,0,0,0,1,1,1,1
1,0,0,0,1,0,0,0,1,0,0,0
0,1,0,0,0,1,0,0,0,1,0,0
0,0,1,0,0,0,1,0,0,0,1,0
0,0,0,1,0,0,0,1,0,0,0,1];
b=[70;40;90;30;60;50;60];
lp(c,a,b,vlb,vub)
执行的结果是：
ans = 25.0000
45.0000
0
0
-0.0000
15.0000
0.0000
25.0000
5.0000
-0.0000
50.0000
35.0000
由此可得运费最小的运输安排表如下：
表6-5　最优运输安排表
产地
产量
需地
1
2
3
4
需量
30
60
50
60
Ⅰ
70
运
输
费
25
45
0
0
Ⅱ
40
0
15
0
25
Ⅲ
90
5
0
50
35
问题3的软件解法 编写下面的程序：
wenti3.m：
c=[1,1,1,1,1,1,1,1];
a=[-1,0,0,0,0,0,0,-1;-1,-1,0,0,0,0,0,0;
0,-1,-1,0,0,0,0,0;0,0,-1,-1,0,0,0,0;
0,0,0,-1,-1,0,0,0;0,0,0,0,-1,-1,0,0;
0,0,0,0,0,-1,-1,0;0,0,0,0,0,0,-1,-1];
b=[-70;-80;-65;-90;-80;-100;-120;-90];
vlb=[0;0];
vub=[];
x=lp(c,a,b,vlb,vub)
minz=c*x
执行的结果是
x = 40.00000000000002
39.99999999999998
45.00000000000000
44.99999999999999
37.50000000000000
62.50000000000000
57.50000000000000
32.50000000000001
minz = 360
由此可得至少需要警员的人数是40+40+45+45+38+63+58+33=362。
函数linprog有下面一些常用的使用格式：
(1) x=linprog(c,a,b)
(2) x=linprog(c,a,b)
(3) x=linprog(c,a,b,aeq,beq)
(4) x=linprog(c,a,b,aeq,beq,lb,ub)
(5) x=linprog(c,a,b,aeq,beq,lb,ub,x0)
(6) x=linprog(c,a,b,aeq,beq,lb,ub,x0,options)
(7) [x,fval]=linprog(c,a,b)
(8) [x,fval,exitflag] = linprog(c,a,b)
(9) [x,fval,exitflag,output] = linprog(c,a,b)
（10）[x,fval,exitflag,output,lambda]=linprog(c,a,b)
这些函数命令的用法跟函数lp的用法是相同的，这里我们不做详细介绍，只对格式中的各种输入、输出参数做以解。这些命令都是用来解下面形式的线性规划问题：

(6-5)
从中我们不难看出命令中的输入参数c是赋权行向量；是决策向量（未知向量）；是不等式约束条件的系数矩阵；是不等式约束条件的右端常数向量；是等式约束条件的系数矩阵；是等式约束条件的右端常数向量；与分别为变量取值范围的下界和上界；是设定的初始值，当线性规划问题的规模很大时，一般不用初始值选项；格式（6）中options选项是用来指定优化参数，具体可查看命令optimset，不选则使用默认值。
输出参数带回的是LP问题的最优解；输出参数fval带回的是LP问题在最优解处目标函数的最优值minz=c；输出参数exitflag带回的是在求解过程中退出的条件，如果exitflag大于零表示算法收敛到所要求的最优解，如果exitflag等于零表示在解LP问题时已经达到了迭代次数的最大限制，但是算法并没有收敛到所要求的最优解，如果exitflag小于零表示在解LP问题时寻找可行解失败；关于输出参数output和lambda，因为涉及一些专业知识，这里不做解释，感兴趣的读者可用help命令获得。
问题4的软件解法 可编写下面的程序：
wentisi4.m：
c=[7,8,8,8,7,8,7,9,8];
aeq=[1,0,0,1,0,0,1,0,0;0,1,0,0,1,0,0,1,0;0,0,1,0,0,1,0,0,1];
beq=[300;400;500];
a=[0.6,0.5,0.5,0,0,0,0,0,0;
0,0,0,0.4,0.7,0.5,0,0,0;
0,0,0,0,0,0,0.8,0.4,0.6];
b=[700;800;900];
lb=zeros(9,1);
[x,fval,exitflag,output,lambeda]=linprog(c,a,b,aeq,beq,lb)
执行的结果是
Optimization terminated successfully.
x = 98.2599
0.0000
145.7326
0.0000
400.0000
145.9377
201.7401
0.0000
208.3298
fval = 8.9000e+003
exitflag = 1
output = iterations: 4
cgiterations: 0
algorithm: 'lipsol'
lambeda = ineqlin: [3x1 double]
eqlin: [3x1 double]
upper: [9x1 double]
lower: [9x1 double]
返回值exitflag =1说明算法找到了最优解。读者可以执行下面的命令：
[x,fval,exitflag,output,lambeda]=linprog(c,a,b,aeq,beq)
看看将会出现什么结果？
对于一些非线性的约束极值问题和非约束极值问题，MATLAB软件优化工具箱也提供相应的功能函数，这里我们不再过多地涉及，感兴趣的读者可以自己去了解。
6.2.4 内容小结
本次实验我们着重介绍了线性规划问题的几种解法：图解法、理论解法和软件解法，线性规划问题的本征特点一是目标函数是决策变量的线性函数，二是约束条件是决策变量的线性等式或者不等式，可以说它是一种较为简单的而又特殊的约束极值问题。通常能够转化成线性规划问题的实例也很多，诸如：生产决策问题、一般性的投资问题、裁料问题、场址的选择问题、运输问题以及前面提到的人员安排和计划分工等问题。与此相关的内容还有灵敏度分析以及影子价格等等，这里我们不再涉及，感兴趣的读者可以参考有关专业书籍。

6.3 实验任务

用数学软件完成下面的实验任务。
A 组
1 用图解法和计算机软件解下列线性规划问题：
(1) (2)

2 用计算机软件和求基本可行解的方法解下面的线性规划问题：
(1) ( 2 )

B 组
1 某一个商店制定了下半年的订货计划，已知商店库存最大容量为500件，6月底已经存货200件，以后每月进货一次。假设下半年各月份该商品的进价和售价情况如下表15-5所示，问每月份各进货多少才能使得收入最多？
表6-6
月份
7
8
9
10
11
12
进价
28
28
26
25
22
22
售价
29
30
27
26
24
20
2 有A、B、C三个场地，每一个场地都出产一定数量的原料，同时也消耗一定数量的产品，具体数据如下表16-6所示。已知制成每吨产品需要消耗3吨原料，A、B两地，A、C两地和B、C两地之间的距离分别为150千米、100千米和200千米，假设每万吨原料运输1千米的运费为5000元，每万吨产品运输1千米的运费为6000元。由于地区条件的差异，在不同地区设厂的费用不同，由于条件的限制，在B处建厂的规模不能超过5万吨，问：在这三地如何建厂、规模建多大才能使得总费用最小？
表6-7
地点
年产原料（万吨）
年销产品（万吨）
生产费用（万元/万吨）
A
20
7
150
B
16
13
120
C
24
0
100
3 某厂生产三种产品I，II，III，每种产品生产时都要经过A，B两道工序加工。设该厂有两种规格的设备能完成A工序，分别用A1，A2表示；有三种规格的设备能完成B工序，分别用B1，B2，B3表示。产品I可在A，B任何一种规格设备上加工；产品II可在任何规格的A设备上加工，但在完成B工序时，只能在B1设备上加工；产品III只能在A2和B2设备上加工。假定产品I的销售量不超过800单位，已知三种产品在各设备上加工时单件产品耗用的工时数、原材料费、产品销售价格、各种设备有效台时以及满负荷操作时设备的使用费如下表15-7所示。问：如何安排生产计划，才能够使该厂利润最大？

表6-8
设备
产品
设备有效台时
满负荷时设备使用费（元）
I
II
III
A1
5
10
×
6000
300
A2
7
9
12
10000
320
B1
6
8
×
4000
250
B2
4
×
11
7000
783
B3
7
×
×
4000
200
原料费（元/件）
0.25
0.35
0.50

单价（元/件）
1.25
2.00
2.80

15