线性规划在现实生活中的应用

线性规划在现实生活中的应用

[1**********]崔钊 [1**********]王源 [1**********]万成 （电子信息工程四区队）

【摘要】：线性规划是运筹学中一种最常用的方法。线性规划在科学决策与经营管理中实效

明显, 但是对于规模较大的线性规划模型, 其求解过程非常烦琐, 不易得出结果。本文简要介绍了线性规划的发展历程以及用ＭＡＴＬＡＢ程序实现了线性规划问题数学模型的求解方法, 并进一步通过对实例模型求解方法的分析比较, 证明所采用的程序方法有效快捷，为我们解决复杂的线性规划问题提供了方便。

【关键词】：线性规划；建模；方案；ＭＡＴＬＡＢ；约束条件; 最优解；

线性规划是运筹学中一种最常用的方法。线性规划是合理利用、调配资源的一种应用数学的方法。它的基本思路就是在满足一定的约束条件下, 使预定的目标达到最优。它的研究内容可归纳为两个方面:一是系统的任务已定, 如何合理筹划, 精细安排, 用最少的资源去实现这个任务; 二是资源的数量已定, 如何利用、分配, 使任务完成得最多. 前者是求极小, 后者是求极大. 线性规划是在满足企业内、外部的条件下, 实现管理目标和极值问题, 就是要以尽少的资源输入来实现更多的社会需要的产品的产出。

一、线性规划及其求解概述

自从1938年由年仅26岁的苏联列宁格勒大学数学教授康托洛维奇提出线性规划后,40年代又由丹捷格(G.B.Dantzig)教授独立地在美国发现, 并找到了一种计算线性规划模型的有效方法, 也就是我们今天所说的“单纯形法”(Simpexmethod)。之后, 在经济学家库普曼斯(T.C.Koopmans)的呼吁下, 许多年轻一代的经济学家, 比如其中的阿罗、萨谬尔逊、西蒙、多夫曼和胡尔威茨等都对线性规划表现出了极大的兴趣, 并在运筹学的某些领域中发挥过重要作用, 他们都因此而获得了诺贝尔奖金。1975年, 康托洛维奇和库普曼斯也因“最优质资源配置理论的贡献”而获诺贝尔经济学奖, 遗憾的是丹捷格却榜上无名。现在, 在运筹学的众多分支学科中, 线性规划已成为研究最为深入, 实用效果也最为明显的一个分支。

有了单纯形法以后, 对于简单的线性规划模型来说, 用相应的方法凭着一支笔和一张纸就能 进行求解, 但是对于规模较大的模型来说, 这种办法就行不通了, 虽然手工列表进行计算从原理上讲并不困难, 但是却非常烦琐, 单调而且容易出错。从生产和管理以及科学研究中提出来的大量实际问题, 其决策变量和约束条件多到十几个、几十个、几百个, 甚至成千上万个, 这些问题就不是人力所能及的了。由于电子计算机的普及, 求解线性规划以及许许多多运筹学问题的软件包也应运而生, 并走向市场, 成为大型科研机构、厂矿企业、学校和普通用户都不可

缺少的一种工具,Matlab 就是其中一个比较常用的软件。

二、线性规划的定义、数学模型

1. 线性规划的定义:根据线性规划模型的基本结构, 在满足一组约束条件下, 求一组变量的值, 使得其成为目标函数的最优解。 (1)变量

变量又叫未知数, 它是实际系统的未知因素, 也是决策系统中的可控因素, 一般称为决策变量, 常引用英文字母加下标来表示, 如X1,X2,X3, „ ,Xn 等。 (2)目标函数

将实际系统的目标, 用数学形式表现出来, 就称为目标函数, 线性规划的目标函数是求系统目标的数值, 即极大值, 如产值极大值、利润极大值或者极小值, 如成本极小值、费用极小值、损耗极小值等等。 (3)约束条件

约束条件是指实现系统目标的限制因素。它涉及到企业内部条件和外部环境的各个方面, 如原材料供应、设备能力、计划指标、产品质量要求和市场销售状态等等, 这些因素都对模型的变量起约束作用, 故称其为约束条件。约束条件的数学表示形式为三种, 即≥、=、≤。线性 规划的变量应为正值。

2. 线性规划研究的是线性目标函数在线性约束条件下取得最大值或最小值的问题。一般地, 线性规划问题的数学模型是: a11x1+a12x2+ „ +a1mxm≤b1 a21x1+a22x2+ „ +a2mxm≤b2 amx1+an2x2+ „ +anmxm≤bm

其中aij(i=1,2,„ ,n;j=1,2,„ ,m),bi(i=1,2,„ ,n) 都是常量,xj(j=1,2,„ ,m) 是非负变量, 求目标函数Z=C1X1+C2X2+ „ +CmXm,的Zmax 或Zmin 。

三、线性规划模型的建立

（一）线性规划问题的提出

公路工程混合料配合比设计是一门新的工程实用技术，它是在满足一定技术指标的前提下，以取得最大经济效益为目标来确定各种材料的最佳配方比例，从而提高工程质量并降低生产成本。它是工程建设中的一个重要环节，同时也是工程技术管理的重要内容。混合料配合比计算，常规方法有式计算和图解法。这两种方法主要通过手工完成，计算工作量大、出错率高、精度低，且都没有考虑生产成本问题，其计算及结果虽然满足规范要求，但混合料总体成本却很少能达到最低。

例:某混凝土厂出售商品混凝土, 原料供应情况如下表(表1):

表1 原料供应情况及成本表

编号 名称 月供应量(方) 单价(元/方) A 碎石 6000 30 B 卵石 4000 25 C 矿渣 13000 35

按工程需要配制混凝土。设各种混凝土骨料的级配限度, 水泥、砂等掺和料及生产费用如表2。

表2 混凝土骨料级配限度及辅料、加工费用表

混凝土种类 骨料级配限度 水泥、砂、掺和料及加工费(元/方)

1 A ≥60% 45

C ≤20%

2 C ≥60% 50

3 A ≤15% 60

C ≤50%

假设三种混凝土的售价均为每方120元; 为简化计算, 设每方骨料生产1方混凝土, 生产的混凝土全部可以出售。问如何配制可使该厂每月获得纯利润最多? (二) 线性规划模型的建立

设xij 表示第j 种混凝土耗费的第i 种原料的数量, 经过分析, 该问题的数学模型如下:

经整理后模型为:

maxZ=45x11+50x12+40x13+40x21+45x22+35x23+30x31+35x32+25x33 化为minz=-（-45x11-50x12-40x13-40x21-45x22-35x23-30x31-35x32-25x33） x11+x21+x31≤6000 x12+x22+x32≤4000 x13+x23+x33≤13000

-0.4x11+0.6x12+0.8x13≤0 -0.2x11-0.2x12-0.8x13≤0 0.6x21+0.6x22-0.4x23≤0 0.85x31-0.15x32-0.15x33≤0 -0.5x31-0.5x32+0.5x33≤0 Xij ≥0, i,j=1,2,3

此题若利用单纯形法求解则需要大量的时间，求解过程十分复杂，在计算过程中极易出错。 单纯形法的求解步骤如下：

①把线性规划问题的约束方程组表达成典范型方程组，找出基可行解作为初始基

可行解。

②若基可行解不存在，即约束条件有矛盾，则问题无解

③若基可行解存在，从初始基可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。

④按步骤3进行迭代, 直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。

⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。

四、利用MATLAB 软件求解线性规划问题

线性规划在科学决策与经营管理中实效明显, 但是对于规模较大的线性规划模型, 其求解过程非常烦琐, 不易得出结果。Matlab 是一个通用数学软件包, 除了可以用其中的优化工具箱来求解线性规划外, 还具有强大的数值计算、绘图、优化和编程等功能。

（一）求解方法及步骤

Matlab 针对某些具体应用领域建立的程序库被称作“工具箱”,Matlab 现有30多个工具箱, 其中优化工具箱(Optimization Toolbox)是应用较为广泛, 影响较大的一个工具箱。应用Matlab 优化工具箱求解线性规划时, 不需要把线性规划化为标准形式, 其相应的形式为: Min fTx s.t.Ax ≤b

它的特点是: ①求目标函数的最小值, 原问题是求最大值的, 要转化为求最小值; ②目标函 数的系数作为列矩阵f; ③约束条件全部为≤常数, 若约束条件中有等式约束以及变量的非负约束也要全部改写或视为≤的约束; ④把约束条件的系数作为矩阵A, 把约束条件中的右端项作为列矩阵b 。具体求解时, 首先是给矩阵f,A,b 赋值。Matlab 给矩阵赋值是逐行进行的,

行之间用分号“; ”隔开, 每行元素之间可以用“, ”号也可用空格隔开, 并且用符号“, ”置于矩阵右上角表示作矩阵的转置运算。赋值完毕, 在命令窗口中调用优化程序linprog, 回车以后即可得到问题的最优解。 （二）对上述问题的求解

A=[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;-0.4,0.6,0.8,0,0,0,0,0,0;-0.2,-0.2,-0.8,0,0,0,0,0,0;0,0,0,0.6,0.6,-0.4,0,0,0;0,0,0,0,0,0,0.85,-0.15,-0.15;0,0,0,0,0,0,-0.5,-0.5,0.5]; f=[-45,-50,-40,-40,-45,-35,-30,-35,-25]; b=[6000,4000,13000,0,0,0,0,0];

[x,fval]=linprog(f,A,b) {ｘ———取得最优时变量ｘ的取值

fval ———返回目标函数在最优解ｘ点的函数值 ｆ———是优化参数ｘ的系数矩阵 Ａ———非等式约束条件函数ｘ前系数矩阵 ｂ———非等式约束条件的矩阵}

最终求得x=6000 2000 2000 0 2000 11000 0 0 0 fval=925000。

五、结束语

线性规划工作的一个最重要任务就是在数量上规划出各种“最优”。线性规划所处理的问题是怎样以最佳的方式在各项经济活动中分配有限的资源, 以便最充分地发挥资源的效能去获取最佳经济效益。线性规划就是拟定活动计划以便达到一个最优结果, 即在所有可行的备选方案中如何选取最佳方案以达到规定目标。例如, 消费者在总收入一定的情况下, 如何购买品使得消费者所获得的效用最大; 总成本固定后, 怎样安排生产要素的投入使总产量最大; 工厂在各材料固定的情况下, 如何最佳地使用原材料使得利润最大等。这类问题都可以用线性规划理论与方法来分析和求解。线性规划是在满足企业内、外部的条件下, 实现管理目标和极值(极小值和极大值) 问题, 就是要以尽少的资源输入来实现更多的社会需要的产品的产出。因此, 线性规划是辅助企业“转轨”、“变型”的十分有利的工具, 它在辅助企业经营决策、计划优化等方面具有重要的作用。线性规划在现代管理中起到了重要的作用。目前, 美国78%的企业应用线性规划解决生产上的问题, 且效果显著。在我国, 随着计算机的普遍发展, 线性规划 也已经成为企业中重要的管理方法。 参考文献:

[1]曹卫华, 郭正. 最优化技术方法及ＭＡＴＬＡＢ的实现[Ｍ].北京:化学工业出版社,2005. [2]胡运权，运筹学教程（第2版）[M].北京:清华大学出版社，2003.

[3]刘懑凤, 等. 运筹学模型与方法教程例题分析与题解. 北京:清华大学出版社,2001. [4]石博强.Matlab 数学计算范例教程[M].北京:中国铁道出版社,2004. [5]苏金明.Matlab 工具箱应用[M].北京:电子工业出版社.2004.