线性规划在工商管理中的应用
摘要线性规划是运筹学的一个重要分支,它被广泛应用于工业、农业、商业等领域,来解决实际中的问题。本文通过介绍线性规划及其在工商管理中应用的实例,来说明它在工商管理中的重要作用。
关键词运筹学;线性规划;方法;应用
1.线性规划在工商管理中运用的广泛性
工商管理[1]是研究工商企业经济管理基本理论和一般方法的学科,它通过运用现代管理的方法和手段来进行有效的企业管理和经营决策,保证企业的生存和发展。在当今社会,随着市场竞争的日益加剧,如何统筹安排,合理利用有限的人力、物力、财力等资源,使总的经济效益最好,已经成为企业经营管理过程中实现利益最优必须解决的问题。例如:
人力资源分配:用最少的劳动力来满足工作的需要?
产品生产计划:合理利用人力、物力、财力等,使获利最大?
套裁下料:如何在保证生产的条件下,下料最少?
配料问题:在原料供应量的限制下如何获取最大利润?
投资问题:从投资项目中选取方案,使投资回报最大?
运输问题:如何制定调运方案,使总运费最小?
这样的问题常常可以化成或近似地化成“线性规划”(Linear Programming, 简记为LP)问题。线性规划所研究的是:在一定条件下,合理安排人力物力等资源,使经济效果达到最好。一般地,求线性目标函数在线性约束条件下的最大值或最小值的问题,统称为线性规划问题[2]。利用线性规划我们可以
解决很多问题,例如上述人力资源分配、计划安排、套裁下料等诸多方面的问题,在本文的后面我们将用线性规划方法对企业在生产中的具体问题进行探讨。2.线性规划的模型
线性规划[2]是运筹学的一个重要分支。自1947年丹捷格(G. B. Dantzig)提出了一般线性规划问题求解的方法——单纯形法之后,线性规划在理论上趋向成熟,在实用中日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策的线性规划问题之后,线性规划的适用领域更为广泛了,它已是现代科学管理的重要手段之一了。
建模过程[3]:
(1)理解要解决的问题,了解解题的目标和条件;
(2)定义决策变量(1,
2
x,…,n x),每一组值表示一个方案;
(3)用决策变量的线性函数形式写出目标函数,确定最大化或最小目标;
(4)用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件。
线性规划问题的一般形式为
目标函数:
max (min) 错误!未找到引用源。
约束条件:
s.t.
()
()
()?
?
?
?
?
?
?
?
?
≥
≥
=
≤
+
+
+
≥
=
≤
+
+
+
≥
=
≤
+
+
+
,
,
,
,
,
,
2
1
2
2
1
1
2
2
2
22
1
21
1
2
12
1
11
n
n
mn
m
m
n
n
n
n
x
x
x
bm
x
a
x
a
x
a
b
x
a
x
a
x
a
b
x
a
x
a
x
a
Λ
Λ
Λ
Λ
Λ
标准形式
max n n x c x c x c z +++=Λ2211
????
?????≥=+++=+++=+++0,,,21221
1222221211212111n n mn m m n n n n x x x bm x a x a x a b x a x a x a b x a x a x a ΛΛΛΛΛ 用矩阵表示即
max 1n
j j j z c x ==∑
1
,1,2,,0,1,2,n
ij j i j j a x b i m x j n =?==???≥=?
∑L L 系数组成的矩阵称为约束矩阵 A=1112121
22212n n m m mn a a a a a a a a a ????????????
L L M M O M L 一般讲,一个经济、管理问题需满足以下条件,才能建立线性规划模型。
(1) 要求解问题的目标函数能用数值指标来反映,且为线性函数;
(2) 存在多种方案和有关数据;
(3) 要求达到的目标是在一定的约束条件下实现的,这些条件可用线性式或不等式来描述。
3.求解线性规划问题常用的方法
3.1图解法
对于只有两个决策变量的线性规划问题,可以在平面直角坐标系上作图表示,取公共部分,然后作出目标函数,使其在公共部分移动至取到最优解。 3.2单纯形法[1] 单纯形法的基本思路:从可行域中某一个顶点开始,判断此顶点是否是最优解,如不是,则再找另一个使得其目标函数值更优的顶点,称之为迭代,再判断此点是否是最优解。直到找到一个顶点为其最优解,就是使得其目标函数值最优的解,或者能判断出线性规划问题无最优解为止。
单纯形法的计算步骤:
(a )建立初始单纯形表;
(b )检验所得的基本可行解是否为最优解:若所有的j σ≤0,则已获得最优
解,停止计算,否则,转入下一步;
(c )基变换:确定()0|max 1>=≤≤j j n
j k σσσ所对应的非基变量k x 为换入变量(变为基变量),确定()lk l ik ik i n i i l a b a a b =???
? ??>==≤≤0|min min 1θθ所对应的基变量l x 为换出变量; (d )进行迭代得新的单纯形表。
3.2.1 大M 法[3]
把人工变量“强行”地加到原来的约束方程中去,就令人工变量在求最大值的目标函数里的系数为-M ,这个方法叫做大M 法。
3.2.2 两阶段法[3]
将加入人工变量后的线性规划划分两阶段求解。
第一阶段:要判断原线性规划是否有基本可行解;