探究线性规划的实际应用

探究线性规划的实际应用

班级：信息与计算科学1142 姓名：萧明峰 学号：[1**********]9

摘要：在生产管理和经济活动中，经常遇到这些问题，如生产计划问题，即如何合理利用有限的人、财、物等资源，以便得到最好的经济效果；材料利用问题，即如何下料使用材最少；配料问题，即在原料供应量的限制下如何获取最大利润；劳动力安排问题，即如何用最少的劳动力来满足工作的需要；运输问题，即如何制定调运方案，使总运费最小；投资问题，即从投资项目中选取方案，使投资回报最大等等。对于这些问题，都能建立相应的线性规划模型。事实上，线性规划就是利用数学为工具，来研究在一定条件下，如何实现目标最优化。单纯形法是求解线性规划问题的通用方法。

关键词：线性规划；基本可行解；单纯形法；

一、什么是线性规划问题？

线性规划（Linear programming,简称LP）是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。

经营管理中如何有效地利用现有人力、物力完成更多的任务，或在预定的任务目标下，如何耗用最少的人力物力去实现目标。这类统筹规划的问题用数学语言表达，先根据问题要达到的目标选取适当的变量，问题的目标通过用变量的函数形式表示（称为目标函数），对问题的限制条件用有关变量的等式或不等式表达（成为约束条件）。当变量连续取值，且目标函数和约束条件均为线性时，称这类模型为线性规划的模型。有些规划问题的目标函数是非线性的，但往往可以采用分段线性化等方法，转化为线性规划问题。

二、线性规划问题的数学模型

线性规划问题的数学模型由三个要素组成：

1、变量，或称决策变量，是问题中要确定的未知量，它用于表明规划中的用数量表示的方案、措施，可由决策者决定和控制。

2、目标函数，它是决策变量的函数，按优化目标分别在这个函数前加上max或min。

3、约束条件，指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量函数的等式或不等式。

如果规划问题的数学模型中，决策变量的取值是连续的，即可以为整数，也可以为分数、小数或实数，目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式，则该类规划问题的数学模型称为线性规划的数学模型。

三、线性规划问题的标准形式

所谓标准形式是指下列形式：

maxz=∑c

j=1njxj

当实际模型非标准形式时，可以通过以下变换化为标准形式：

minz=∑cjxj

j=1n⎧n⎪∑aijxj=bi(i=1, ,m)s⋅t⋅⎨j=1⎪x≥0(j=1,2, ,n)⎩j①当目标函数为

minz'=-∑cjxj

j=1n时，可令Z′=-Z，而将其写成为

求得最终解时，再求逆变换Z=-Z′即可。

②当s·t·中存在ai1x1+ai2x2+ +ainxn≤bi形式的约束条件时，可引进变量 ⎧xn+1=bi-(ai1x1+ai2x2+ +ainxn)⎨⎩xn+1≥0

便写原条件成为

其中的xn+1称为松驰变量，其作用是化不等式约束为等式约束。

同理，若该约束不是用“≤”号连接，而是用“≥”连接，则可引进松驰变量 ⎧ai1x1+ai2x2+ +ainxn+xn+1=bi⎨⎩xn+1≥0⎧xn+1=(ai1x1+ai2x2+ +ainxn)-bi⎨⎩xn+1≥0

使原条件写成

⎧ai1x1+ +ainxn-xn+1=bi⎨⎩xn+1≥0

四、线性规划问题的解决方法——单纯形法

(1)单纯形法解线性规划问题的理论根据是：

线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。

(2)单纯形法的基本思想是：

先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。

(3)单纯形法的一般解题步骤可归纳如下：

①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。

五、解决实际问题

我们已经知道了单纯形法是从一个初始解开始，不断改进现有的解，知道所要求的目标函数的值被满足为止。那么现在我们来解决一个实际问题。

某工厂生产I、II 两种商品,已知生产单位商品所需的设备台时、A、B 两种原材料的消耗、设备使用台时限额以及原材料的限额如下表所示。该工厂每生产一件商品I可获利3 元，每生产一件商品II 可获利4 元。写出使该工厂所

解：设生产产品 I 的数量为x1，生产产品 II 的数量为x2，所获利润为z ，相应的模型为：

maxz=3x1+4x2

2x1+x2≤40

x1+3x2≤30

x1，x2≥0

将上述问题化为标准形式：

maxz=3x1+4x2+0x3+0x4

2x1+x2+x3=40

x1+3x2+x4=30

x1，x2，x3，x4≥0

用单纯形法求解：

其约束条件系数矩阵的增广矩阵为

p1p2p3p4b

211040 130130

p3，p4是单位矩阵。构成一个基，对应变量x3，x4是基变量。令非基变量x1，x2等于零，即找到一个初始基可行解

X=（0，0，40，30）

以此列出初始单纯形表

图表中有大于零的检验数，故表中基可行解不是最优解。因为σ2>σ1，故确定x2为换入变量。将b列除以p2的同行数字得

θ=min（40，10）=10

由此3为主元素，作为标志对主元素3加上方括号[]，主元素所在行基变量x4为换出变量。用x2替换基变量x4，得到一个新的基p3，p2，按上述单纯形法计算，可以找到新的基可行解，并列出新的单纯形表：

由于表中还存在大于零的检验数σ1，故重复上述步骤：

这时所有检验数均少于零，且基变量中不含人工变量故表中的基可行解 X=（18,4,0,0）就是最优解，代入目标函数得z=70.

六、结语

解决线性规划实际问题需要用到单纯形法，它需要一个已知的基本可行解, 并需把原始线性规划问题化为标准式,而在一般情况下线性规划问题并无明显的基本可行解, 则需增加人工变量以获得基本可行解,这样可能增加计算量,因而单纯形法解线性规划问题的算法仍需更进一步的探究与改良,这将对解决线性规

划问题非常有意义。

参考文献：

[1] 薛毅, 耿美英.运筹学与实验[M].电子工业出版社,2008.9.

[2] 王文波.数学建模及其基础知识详解[M].武汉大学出版社, 2006.

[3] 运筹学教材编写组.运筹学[M].第四版.北京：清华大学出版社，2012.

[4] 徐光辉.运筹学基础手册[M].北京：科学出版社，1999.

[5] 马振华.现代应用数学手册（运筹学与最优化理论卷）[M].北京：清华大学出版社，1998.

[6] 胡运权.运筹学基础及应用[M].第5版.北京：高等教育出版社，2008.

[7] 郭耀煌等.运筹学原理与方法[M].成都：西南交通大学出版社，1994.

[8] 郭耀煌等.运筹学与工程系统分析[M].北京：中国建筑工业出版社，1986.

[9] 胡运权.运筹学习题集[M]，第4版.北京：清华大学出版社，2010.