摘 要

线性规划是运筹学的一个重要分支，是研究在线性约束条件下，线性目标函数的极值问题的数学理论和方法。它广泛应用于工业、农业、工商业、交通运输业、军事、经济计划和管理决策等领域，为合理利用有限资源做最优决策提供科学依据。依托计算机提供的强大计算资源，线性规划应用领域更加宽广、使用更加便捷，已经成为现代科学管理的重要手段之一。本文从线性规划基础理论出发，描述了一般线性规划问题求解方法——单纯形法的原理和基本步骤，并总结了已有的改进方法和可能的改进方向，最后结合实例给出用R软件求解的方法。

关键词：运筹学；线性规划；单纯形法；R软件

Abstract

Linear programming (LP, or linear optimization) is an important branch ofoperations research. It is a mathematical method for theoptimization of a linear objective function, subject to linearequality and linear inequality constraints. It provides ascientific basis to make optimal decisions with limited resources,and is widely used in many fields such as industry, agriculture,industry and commerce, transportation, military, economic planningand management decisions and so on. With the powerful computingresources being used, linear programming has become an importanttool for modern scientific management, and its applications aremore and more convenient and broader. This paper shows theprinciples and basic steps for simplexmethod, which is the general method for solving linearprogramming problems, and then discusses the possible improvementof simplex method. Several examples solved by R software are alsogiven as reference.

Key words: Operations research; Linear programming; Simplex method; R software.

1. 引言

线性规划思想早在1832年由法国数学家傅里叶首次提出，是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法^[1]。在经济管理、交通运输、工农业生产等经济活动中，提高经济效益是人们不可缺少的追求，而提高经济效益一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料；二是生产组织与计划的改进，即合理安排人力物力资源。线性规划所研究的是：在一定条件下，合理安排有限的人力、物力、财力等资源，使经济效果达到最好。一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。线性规划被广泛应用于工业、农业、工商业、交通运输业、军事、经济计划和管理决策等领域，是现代科学管理的重要手段之一。

自1974年丹捷格（G. B. Dantzig）提出了一般线性规划问题求解方法——单纯形法之后，线性规划在理论上趋向成熟，在实用中日益广泛与深入^[2]。然而，单纯形法的计算虽然有效，但变量稍多时还是有些繁琐和费时^[3]。随着计算机技术的发展和普及，有成千上万个约束条件和决策变量的线性规划问题可以依托强大的计算资源完美解决，这大大拓宽了线性规划的适用领域。现在，有很多线性规划软件（包）开发得比较成熟，如MATLAB, LINGO, MAPLE等。本文首先给出了一般线性规划问题的描述，探讨了单纯形法的原理和基本步骤，并结合具体实例，使用开源的R软件编程实现。

2. 问题描述

2.1 线性规划问题的共同特征

在生产管理和经营活动中，经常提出一类问题，即如何合理地利用有限的人力、物力、财力等资源，以便得到更好的经济效果。比如广告预算和媒介选择，生产计划，铁路运输等。有一类优化问题具有以下共同特征：

（1）每一个问题都用一组决策变量（x₁，x₂，…，x_n）表示某一方案，这组决策变量的值就代表一个具体方案。一般这些变量取值都是非负且连续的。

（2）要有建模的有关数据，如资源拥有量、消耗资源定额、创造新价值量等，并构成互不矛盾的约束条件，这些约束条件可以用一组线性等式或线性不等式来描述。

（3）都有一个要求达到的目标，它可用决策变量及其有关的价值系数构成的函数（成为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。

满足以上三个条件的数学模型称为线性规划的数学模型。

2.2 线性规划数学模型的一般形式与标准形式

通过研究线性规划问题的共同特征，总结出其数学模型的一般形式如下：

目标函数 （2-1）

满足约束条件…（2-2）

（2-3）

其中，（2-1）式称为目标函数，c_j为价值系数；式（2-2）、式（2-3）称为约束条件；aij称为限额系数；式（2-3）也成为变量的非负约束条件。一般情况下，m<n。可见，线性规划问题有各种不同的形式。为便于讨论，我们规定线性规划的标准形式如下（省略了目标函数、约束条件标记）：

max

在标准形式中规定各约束条件的右端项b_i>0，否则等式两端乘以“-1”。当某一个bi=0时，表示出现退化。可以通过求目标函数相反数或引入松弛变量等方法将一般形式转化为标准形式。标准形式使用求和符号简写如下：

2.3 线性规划的隐含假设

线性规划问题模型是建立在以下隐含的重要假设基础上的。

（1）比例性。是指每个决策变量在约束条件中与在目标函数中数值变化时，按x_j对应的技术系数a_ij与价值系数c_j严格地成比例变化。这里不存在在实际经济活动中的边际效用递减效应。

（2）可加性。决策变量是独立的，决策变量之间不发生关联，且不允许变量之间有交叉。

（3）可分性。决策变量的值具有可分性，即允许非整数值。

（4）确定性。参数c_j，a_ij，b_i都是确定的已知值。

可见，线性规划问题是实际经济管理问题的抽象与近似。

3. 解决方法

前人已经证明，线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点；若线性规划问题有最优解，必可在某个顶点上得到。换言之，线性规划问题的可行解集是一个超多面体，如果存在最优解则必在超多面体的一个顶点取得。虽然顶点数目是有限的（它不大于个），若采用“枚举法”找所有基可行解，然后一一比较，最终可能找到最优解。但当m, n较大时，这种办法是行不通的，所以要探讨如何有效地找到最优解。本文重点介绍单纯形法。

3.1 单纯形法

一般线性规划问题具有线性方程组的变量数大于方程个数，这时有不定的解。单纯形法是在高斯消去法的基础上，发展为求解变量数多于方程数，并且使目标函数值优化的方法。单纯形法按照一定的规则，从可行解的一个顶点转移到另一个顶点，使得目标函数的值不断地得到改进，最后达到最优。从线性方程组中找出一个个单纯形，每一个单纯形可以求得一组解，然后再判断该解使目标函数值增大还是变小，决定下一步选择的单纯形。通过这样迭代，直到目标函数实现最大值或最小值为止。

3.1.1 单纯形表

为了便于理解计算关系，通常设计一种计算表，其功能与增广矩阵相似，称为单纯形表（见表3-1）。

表 3-1 初始单纯形表

每一次迭代都会构造一个新的单纯形表。在初始单纯形表中，X_B列中填入基变量，这里是x₁, x₂, …, x_m；C_B中填入基变量的价值系数，它们是与基变量相对应的，这里是c₁, c₂, …, c_m；b列中填入约束方程组右端的常数；c_j行中填入变量的价值系数c₁, c₂, …, c_n；列的数字是在确定换入变量后，按规则计算后填入；最后一行称检验数行，对应各非基变量x_j的检验数是

3.1.2 解的判别

对线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无界解和无可行解四种情况，因此需要建立对解的判别准则。在标准型下，

(1)最优解判别：若关于非基变量的所有检验数≤0，则当前基本可行解就是最优解。

(2)无穷多最优解判别：若关于非基变量的所有检验数≤0，又存在某个非基变量的检验数＝0，则线性规划问题有无穷多最优解。

(3)无界解：如果某个，而x_j对应的系数列向量P_j中，所有的a_1j,a_2j,…,a_mj都≤0，则该线性规划问题有无界解。

(4)无可行解：求解时添加虚拟的人工变量后才可能出现无可行解，若在最终表中所有cj - zj ≤ 0，而在基变量中还有某个非零的人工变量，这表示原问题无可行解。

还有一种在计算过程中较少出现的现象——退化，在计算时需要考虑。用规则确定换出变量时，若出现两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，出现退化解。退化问题的解决办法可以使用勃兰特规则，有效避免出现循环。

3.1.3 单纯形法的计算步骤

(1)根据数学模型确定初始可行基和初始基可行解，建立初始单纯形表。

(2)计算各非基变量xj的检验数

(3)在中，若有某个σ_k对应x_k的系数列向量，则此问题属无界，终止计算。否则，转入下一步。

(4)根据max(σ_j>0)=σ_k,确定x_k为换入变量，按θ规则计算

可确定x_l为换出变量，转入下一步。

(5)以a_lk为主元素进行迭代（即用高斯消去法或称为旋转运算），把x_k所对应的列向量

将X_B列中的x_l换为x_k，得到新的单纯形表。重复(2)~(5)，直到终止。

3.1.4 单纯形法的R程序设计思路

两阶段法。本想画个流程图的，但难度太大。阅读别人的没有注释的程序，简直比自己写的工作量还大。突然想到这也是个规划问题，但可能不是线性的：

目标：解析R包的simplex函数；

约束条件： 本人的数学水平；

本人计算机水平；

完成作业的deadline。

经过对以上模型分析发现，暂无可行解。故此处略去N多字。

3.2 单纯形法的改进

求解线性规划问题的方法还有很多。从上面对单纯形法原理和步骤的概述中可以看到，单纯形法的优点是：步骤机械化，易于使用计算机操作，如产生初始解、检查检验数和迭代等。但它的缺点也是显而易见的，如计算繁杂，特别是手工计算时很容易出错等。因此出现了许多基于单纯形法的改进，主要包括以下几方面：

3.2.1 改进单纯形法

单纯形法的改进可以基于很多点，但我们通常所说的“改进单纯形法”是指用矩阵的方法描述单纯形法。单纯形法的迭代过程实际上是从一组基到另一组基的变换，每次迭代中真正有用的数字是基变量列数字、基的逆矩阵、非基变量检验数以及最大正检验数所对应的非基变量系数列向量。改进单纯形法避免了计算基本单纯形法中很多与迭代无关的数字，提高了计算效率。

3.2.2 求初始可行基的改进

用单纯形法求线性规划问题时，一般首先要求一个初始可行基，当没有明显的初始可行基时，常见的方法是引进人工变量构造人造基，再用大M法或两阶段法求解。然而，这样做的问题是：

1）由于人工变量的引入，约束方程随着增多，使得计算工作量和计算机的存储量大大增加，线性规划问题显得更加复杂。

2）另一方面，由于最优解将在超多面体顶点取得，而单纯形法每一次的迭代都更逼近最优解，所以初始基的选择很重要，越靠近最优解，迭代步数越少。而引进人工变量的方法并不考虑其与最优解的距离。

近年来出现了一些改进算法，可以较好地提高计算效率，如使用改进的最钝角法则算法，求出的初始可行基比较接近最优基^[4]。还有直接用旋转运算获得初始可行基和初始可行解的方法^[5]，至多加一个人工变量获得可行基的方法^[6]，以及运用非线性规划中外点罚函数法的思想推导出求初始基本可行解的方法^[7]，这些尝试都较好地改进了单纯形法中求初始可行基的过程。

3.2.3 换基法则的改进

在单纯形法迭代过程中，由初始可行基得到最优基往往需要经过多次的换基迭代，因此能否减少换基迭代次数、提高运算速度和效率，是一个值得研究的课题。最大检验数法中，换入换出变量的确定仅从检验数的大小（尤其手工计算时）单方面考虑对目标函数的改善程度，因而难以保证每次迭代使目标函数得到最大改善，会出现在迭代过程中一个非基变量在上一步迭代中刚进入其变量中，而在紧接着的下一步迭代中又被其它非基变量替换出来，增加了迭代次数及运算量。有研究同时考虑了检验数和换入变量取值（约束条件限制）两方面对目标函数改善的影响，通过从目标函数最快增长以快速逼近最优解的角度来确定新的换入换出变量原则^[8,9]。还有研究采取检验数小于零的两个变量同时进基的方法，加快收敛速度^[10]。

3.2.4 含人工变量问题的解法改进

添加人工变量法即在线性规划标准型的约束条件中引入非负人工变量，构造一个单位矩阵作为“初始可行基”，再改变最初的目标函数，用两阶段法或大M法来求解。两阶段法是在第一阶段引入人工变量建立目标函数求解原问题的初始基本可行解；第二阶段从这一初始基本可行解出发，用单纯形法求解原问题。大M法在约束中引入人工变量的同时，令原目标函数中人工变量的系数为(-M)，迭代过程中迫使人工变量退出基变量，取得原问题的最优解。若不能实现（迭代结束时人工变量不全为0）则原问题无解。可看出，大M法的缺点在于大M始终参与计算使迭代过程非常繁琐；而两阶段法的缺点是两个阶段的目标函数不一致。有研究用两阶段法来改良大M法^[11]，有效克服了两种算法的不足，提高了效率。

3.3求解线性规划问题的其他方法

除基本单纯形法外，求解线性规划问题的方法还有如改进单纯形法、对偶单纯形法，等等。在面向不同问题时，有些方法的具体计算和术语可能有所不同，但他们都基于单纯形法。如表上作业法是单纯形法在求解运输问题时的一种简化方法等等。单纯形法果断是求解线性规划问题的一把瑞士军刀！

4. 算例及单纯形法求解过程

由于单纯形法求解线性规划问题的发展比较成熟，R中已经有比较完善的函数。lpSolve包是专门针对求解线性规划/整数规划问题的包，相对专业和成熟，但其求解线性规划是基于改进单纯形法。而R的boot包(package)中内置了simplex函数，使用两阶段基本单纯形法求解线性规划问题。作者测试了以上两个函数，发现lp函数功能更强，考虑问题也更加周全。但由于本文主要聚焦于基本单纯形法，故作者选用simplex函数作为例子，并结合算例说明其了使用方法。程序运行在Windows 7 Professional 64bit平台的R Software中(x64, v3.0.2, http://cran.rstudio.com/bin/windows/base/R-3.0.2-win.exe)。

4.1 函数的参数介绍和使用方法

simplex函数位于boot包内，使用前需要先加载到当前工作空间。可使用如下命令：

>library(boot)

函数定义如下：

simplex <- function (a, A1 = NULL,b1 = NULL, A2 = NULL, b2 = NULL, A3 = NULL, b3 = NULL, maxi =FALSE, n.iter = n + 2 * m, eps = 1e-10)

参数说明：

a：长度为n的向量，给出目标函数的系数。

A1：m1*n矩阵，给出类型的约束。

b1：长度为m1的向量，给出右边的值。与A1对应，并要求所有值非负。

A2：m2*n矩阵，给出类型的约束。

b2：长度为m2的向量，给出右边的值。与A2对应，并要求所有值非负。

A3：m3*n矩阵，给出类型的约束。

b3：长度为m3的向量，给出右边的值。与A3对应，并要求所有值非负。

maxi：逻辑值，默认为FALSE，此时求目标函数的最小化。如求最大化应使其=TRUE。

n.iter：每阶段单纯形法的最大迭代次数。默认为n+2*(m1+m2+m3)。

eps：在相等测试中使用的浮点公差，默认为1e-10。

4.2 算例应用

4.2.1 算例1

某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表4-1所示。

表 4-1 生产单位产品所需的设备台时及A、B两种原材料的消耗

该工厂每生产一件产品I可获利2元，没生产一件产品II可获利3元，问应如何安排计划使该工厂获利最多？

分析：由前文所述，易知该问题是典型的线性规划问题。其数学模型可以表示为：

目标函数：

约束条件：

R软件求解：

>simplex(a=c(2,3),A1=matrix(c(1,4,0,2,0,4),nrow=3),b1=c(8,16,12),maxi=TRUE)

结果如下：

可知，当I产品生产4件，II产品生产2件时，得到最大利润14。

4.1.2 算例2

清华大学出版社《运筹学》第四版教材第二章例12(Page51-52)。本例有两个最优解，根据提炼出的数学模型使用R求解，输入如下命令：

>simplex(a=c(150,150,150,80,80,80),

A1=matrix(c(500,1000,1500,2000,2500,3000,3500,4000,4000,1,

0,500,1000,1500,2000,2500,3000,3500,4000,1,

0,0,500,1000,1500,2000,2500,3000,3500,1,

0,0,0,500,1000,1500,2000,2500,2500,1,

0,0,0,0,500,1000,1500,2000,2500,1,

0,0,0,0,0,500,1000,1500,2000,1),nrow=10),b1=c(5000,9000,12000,16000,18500,21500,25500,30000,33500,11),

A2=matrix(c(4000,2000,3500,4000,1500,3000,4000,1000,2500,

2500,500,2000,2500,0,1500,2500,0,1000),nrow=3),

b2=c(36000,12000,21500),maxi=TRUE)

所得结果如下所示：

可见，函数只给出了一个最优解。从这可以看到，simplex函数对于多重最优解的情况处理不够完善。而作者使用lpSolve包时，可以较好地解决这一问题，返回多个最优解。作者出于好奇心测试了simplex函数对其他解的情况的处理结果，发现无可行解、有唯一最优解以及发生退化现象时程序可以返回正确结果；当有多重最优解时，只能给出一个解；无界解时，程序报错（Error）。由于simplex函数采用二阶段法求解，人工变量的添加方式、初始可行基的计算都有固定流程，当遇到有多重最优解的问题时，根据该固定的初始可行基迭代所得结果也将是固定的，在程序没有采取相应策略对待多重最优解问题时，使用该方法仅能得到一个最优解。这带来的问题是，当我们使用其他解法求解同样问题时，由于初始可行基不一定相同，得到的解也可能不同。可见，该函数不能很好的解决线性规划问题求解中的所有情况，需要更全面的考虑。

5. 总结与讨论

本文本着提高作者线性规划理论水平的原则，从线性规划基础理论出发，描述了一般线性规划问题求解方法——单纯形法的原理和基本步骤，并总结了已有的改进方法和可能的改进方向。作者试图对R包中的simplex函数进行源码解析，但最终没有成功，R包中的函数没有注释真是一件很遗憾的事情。很佩服那些写程序的大神们，线性规划问题写起程序来其实没那么简单，需要把可能的情况全都考虑到。鉴于作者基础数学知识十分不过关，只能借已有的R函数解决线性规划问题。本文最后由浅入深举了几个实际算例，并给出了调用函数的具体命令。从实例的求解中发现，simplex函数并不够完善，需要更周全的考虑。

最后，作者有几点感想：

1)单纯形法很强大，是线性规划的一把瑞士军刀！

2)手工计算真的相当繁杂！

3)运筹学是一门有用的学科！

致 谢

感谢美丽的运筹学老师留了这样一篇作业，感谢班上的所有同学陪我一起上课。感谢系统实验室为我提供了完成作业的各方面资源，包括打印机和纸等。感谢生命，感谢自然。感谢丹捷格在1974年提出了单纯形法，否则我的作业难度会更上一层楼。感谢范德蒙，柯西，凯莱，牛顿，莱布尼茨，在基础数学方面给了全人类启发，否则我们不会有机会上这门课程，更别提要在十一假期充实地写作业了。人生是多么美妙！谨在此献上我对这个世界本身、对人类智慧、对科技进步最诚挚的敬意和最衷心的感谢。

参考文献

[1]百度百科. http://baike.baidu.com/

[2]豆丁网. http://www.docin.com/

[2]《运筹学》教材编写组. 运筹学（第四版）.北京：清华大学出版社，2013

[3]孙焕纯. 运筹学中若干线性目标规划和线性规划的人工智能-代数解法. 运筹学学报.2010.12

[4]李炜. 求线性规划初始可行基的新方法[J]. 运筹与管理,2004,13(1):7-10

[5]范国兵. 线性规划问题的一种改进的单纯形法.海南大学学报(自然科学版). 2007.03

[6]梁平;张相斌;王海娇;阎楠. 避免引入人工变量求线性规划可行基的一个新方法. 数学的实践与认识.2009.10

[7]孟俊婷. 求单纯形法中初始基本可行解的新方法——外点法. 内蒙古科技与经济.2000

[8]王忠吉. 同时考虑换入变量对目标函数影响的单纯形法. 吉林工学院学报:自然科学版. 1998.03

[9]梁俊国;焦俊;董成业. 单纯形法换入换出变量的研究.电力学报. 1995.03

[10] 简金宝. 关于单纯形法二维转轴运算的研究.广西大学学报(自然科学版). 1989.04

[11] 王岚;李彦翔;靳松. 线性规划问题新解——改进大M法. 后勤工程学院学报.2011.05

爱华网本文地址 » http://www.413yy.cn/a/25101016/286859.html