线性规划
1.概述
线性规划 (简记 LP)是合理利用、 调配资源的一种优化方法,是运筹学的内容。它的基本思路就是在满足一定的约束条件下 ,使预定的目标达到最优.它的研究内容可归纳为两个方面:一是系统的任务已定 ,如何合理筹划 ,精细安排 ,用最少的资源去实现这个任务;二是资源的数量已定 ,如何利用、 分配 ,使任务完成得最多.前者是求极小 ,后者是求极大. 线性规划是在满足企业内、 外部的条件下 ,实现管理目标和极值问题 ,就是要以尽少的资源输入来实现更多的社会需要的产品的产出.数学建模竞赛中很多问题都和数学规划有关 ,不少的模型都可以归结为一组不等式作为约束条件、 几个函数表达式作为目标函数的问题 ,遇到这类问题 ,求解就是关键. 现在通过专门的数学 MAT LAB软件 ,只要将模型中的目标函数系数、 约束条件系数、 不等关系输入计算机 ,就会很快算出结果.与传统的图解法、 单纯形法等比较 ,就显得格外方便 ,其适用领域更为广泛.
2.模型
线性规划模型 ,其一般形式为
m in f = c 1 x1 + c 2 x2 + … + cn xn (1)
a11 x1 + a12 x2 + … + a1n xn <= b 1
a21 x1 + a22 x2 + … + a2n xn <= b 2
… … (2)
am1 x1 + am2 x2 + … + am n xn <= b m
xj >= 0 , j = 1, 2, …, n .(3)
其中 (1)称为目标函数 , (2)称为约束条件 , (3)称为变量约束.线性规划模型的特征是目标函数和约束条件均为线性函数.
3.案例
某地区水源取自某水库 ,水库涵洞底标高为 45m,水输送到调节水池距离为 1470m,调节水池最高水位 35m (高 10m) ,该段距离中要求输水量174L / s ;另一段 ,从调节水池输水到某水厂的距离为4780m,调节水池低水位标高为 30m,水厂水池标高为 17 . 5m,高差 12 . 5m,要求输水量 116L / s . ,可供铺设的输水管有四种不同直径 ,它们的单位长度造价和水头损失列于表中.问应如何适当选择输水管进行铺设 ,既能保证供水 ,又能使造价最低.
表 1 输水管道单位长度造价和水头损失
管径 单价(元 /m) 单位长度水头损失 (m /1000m) 损失 h /m
Q = 174L / s时的水头 Q = 116L / s时的水头
600 110 0. 873 0. 419
500 70 2. 160 1. 030
400 54 6. 760 3. 120
300 36 31. 000 13. 800
解 ①对第一段水库到调节水池 ,设管径为
600、 500、 400、 300的输水营的铺设长度分别为 x1 ,
x2 , x3 , x4 , 为保证供水 ,要求
x1 + x2 + x3 + x4 = 1470
另外 ,要求输水量为 174L / s时 ,该段总水头损失不超过 10m,即
0 . 873×1 + 2 . 160×2 + 6 . 706×3 + 31 . 000×4 <=10 ×1000
而输水管道铺设的且造价为
100×1 + 70×2 + 54×3 + 36×4
得到如下线性规划模型为
min 100×1 + 70×2 + 54×3 + 36×4
s . t .
0 . 873×1 + 2 . 160×2 + 6 . 760×3 + 31 . 000×4<= 10 ×1000
x1 + x2 + x3 + x4 = 1470
x1 , x2 , x3 , x4>= 0
4计算
求解如下:
m f = [ 110, 70, 54, 36 ]′ ;
A = [ 0 . 873, 2 . 160, 6 . 760, 31 . 000 ] ;
b = [ 10000 ] ;
Aeq = [ 1, 1, 1, 1 ];
beq = [ 1470 ] ;
lb = zeros(4, 1) ;
[ x, fval ] = linprog( f,A, b,Aeq, beq, lb)