第1节线性规划的数学模型

线性规划(linear programming,LP)是运筹学中最成熟的一个分支,并且是应用最广泛的一个运筹学分支。线性规划属于规划论中的静态规划,即单周期决策,是一种重要的优化工具,能够解决有限资源的最佳分配问题。

一、线性规划的三个要素

决策变量(decision variable)是决策问题待定的量值。决策变量应当完全描述出此问题应当作出的决策 。

约束条件(constraint conditions)是指决策变量取值时受到的各种资源条件的限制。 目标函数(objective function)是指决策变量的函数表达式,表示决策者希望实现的目标,它是衡量决策优劣的准则 。线性规划的决策目标是单一的;同时,目标函数也是决策变量的线性函数。目标函数中变量的系数称为价值系数,反映出每个决策变量单位取值对目标的贡献程度。

二、线性规划模型线性规划模型是目标函数和约束条件都是决策变量的线性函数的

最优化数学模型。 (一)线性规划一般模型

[例1—1]生产计划问题

某厂生产甲、乙两种产品,生产工艺路线为:各自的零部件分别在设备A,B加工,最后都需在设备C上装配。经测算得到相关数据如表1—1所示。

表1—1甲、乙单位产品的生产消耗

产品 设备 A B C 工时消耗(小时) 甲 2 0 3 乙 0 2 4 工时成本 (元/小时) 20 15 10 生产能力 (小时) 16 10 32

据市场分析,甲、乙单位产品的销售价格分别为73元和75元,试确定获利最大的产品生产计划。

解 建立模型过程如下:

(1)决策变量:此问题是要确定甲、乙两种产品的产量,这些待定的量值就称为决策变量。设

x1=生产甲产品的产量 x2=生产乙产品的产量

(2)约束条件:生产产品受到现有设备能力的制约,能力需求量不能突破有效供给量。 如果只考虑目标函数,则随着决策变量x1和x2值的增大,目标函数的值也会很快地增大,但是决策变量x1和x2的值受到三种设备加工能力的限制。

约束条件1:生产单位甲产品需耗2个小时的设备A,设备A加工能力不能超过16个小时,则设备A的约束条件表达为:

2x1≤16

约束条件2:设备B的加工能力约束条件表达为: 2x2≤10

约束条件3:设备C的装配能力也有限,其约束条件表达式为: 3x1+4x2≤32

(3)目标函数:目标是企业利润最大化,用Z表示利润。

根据ABC作业成本法,由表1—1的数据可以计算出产品的生产成本。生产单位甲产品,需要消耗设备A的小时数为2小时,设备C的小时数为3小时;而设备A的单位小时成本为20元/小时,设备C的单位小时成本为10元/小时,因此单位甲产品的生产成本为70元(2×20+3×10),即单位甲产品的获利为3元(73-70)。同理。单位乙产品的生产成本为70元(2×15+4×10),即单位乙产品的获利为5元(75-70)。

企业生产总利润是决策变量x1和x2的线性函数,即 maxZ=3x1+5x2

(4)非负约束:甲、乙产品的产量为非负,表述为: x1≥0,x2≥0

在线性规划数学模型中,决策变量的取值一般会有符号的限制,但如果有些决策变量的取值可以取任意值,既可以取负值,也可以取正值,称该决策变量为无约束变量或自由变量。一般而言,从生产的角度,决策变量的取值都应满足非负的约束。

综上所述,该问题的线性规划模型可以表示为: maxZ=3x1+5x2 s.t.

“ 满足上述全部约束的x1和x2的任意值构成了一个可行解集,否则就是不可行解集。线性规划模型的目标是寻找到最优的可行解,称为最优解。如上例确保生产总利润达到最大的产量组合。

(二)模型隐含假定

(1)线性化假定。当且仅当对于某组常数c1,c2,…,cn, 与决策变量x1,x2,…,xn的函数关系式f(x1,x2,…,xn)=c1x1+c2x2+…+cnxn,称f(x1,x2,…,xn)是线性函数。

例如,f(x1,x2)=3x1+5x2是x1和x2的线性函数,而f(x1,x2)=x1则不是x1和x2的线性函数。对于不等式也应当满足这样的性质。在经济学中,大多考虑函数的非线性特性,如长期成本曲线和利润曲线,一般都是非线性的,通过偏导数寻求最优解。然而,在企业的实际运营决策中,一般考虑某个较短时期的作业计划安排,因此通过线性化,更便于方法的应用。在描述设备生命周期的磨损情况时,存在一条设备故障率和运行时间的浴盆函数曲线,如图1—1所示。这是一个非线性函数。

图1—1 设备磨损浴盆曲线

(2)同比例假定。决策变量变化引起目标函数的改变量和决策变量的改变量成比例;同样,每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例。 在图1—1中,如果具体到某一较短时段,设备的磨损就可以满足同比例性原则。同样,虽然产品售价与时间的关系也有一条长尾曲线(如图1—2所示),但在某一具体较短的时期,也服从同比例性原则。

图1—2 产品售价的长尾效应曲线

(3)可加性假定。每个决策变量对目标函数和约束方程的影响是独立于其他变量的。按照价值属性的可加性原理,目标函数值是每个决策变量对目标函数贡献的总和。

(4)连续性假定。线性规划问题中的决策变量应取连续值。

(5)确定性假定。线性规划问题中的所有参数都是确定的参数 ,不包含随机因素。

三、线性规划的图解方法

本书将为读者介绍线性规划的两种求解方法,即图解法和单纯形法。单纯形法将在第2节中详细介绍。本节主要通过图解法,讨论线性规划模型的可行域、最优解、解的可能情况及其处理策略，图解法就是用图示的方法来求解线性规划问题。

(一)线性规划的可行域

可行域是指满足所有约束条件的解的集合,即所有约束条件共同围成的区域。满足所有约束条件的解,称为可行解。

将例1-1生产计划问题的数学模型中的约束条件绘制在平面图上,其围成的可行域如图1—3所示。

图1—3 图解法可行域3x1+4x2=32是平面(x1,x2)上的一条直线,而3x1+4x2≤32是直线

3x1+4x2=32下方的一个半平面,x1≥0是纵轴右侧的半平面,x2≥0是横轴上方的半平面。所有约束条件的半平面的公共部分,就构成了满足约束条件的解的集合,称为可行域,即图1—3中的阴影部分。

(二)线性规划的最优解

线性规划问题是寻求一组既满足约束条件又使目标函数最优的解,这组解一定在可行域上,究竟是哪一点要由目标函数来判断。我们把可行解中使目标函数最优(极大或极小)的解称为最优解。

这里对图解法求解线性规划问题的步骤进行总结:

首先,在图中画出已建立模型的约束条件对应的等式,按照约束条件不等式的范围在图中标明可行解的范围。

其次,将目标函数对应的直线画在图中,平移目标函数线,定位于最优解点。 最后,通过联立方程求解最优解点的值。

四、线性规划解的可能性

(一)唯一最优解

唯一最优解是在一个顶点上得到最优。

(二)多重最优解

多重最优解是指在两个顶点上同时得到最优,其连线上任意一点都可使目标函数最优 。

(三)无界解

无界解是指线性规划问题的可行域无界,并且目标函数无最优解。

如果出现线性规划模型是无界解,则说明分析管理问题时遗漏了主要的约束条件,需要重新审视建模过程,看约束条件是否有疏漏。

(四)没有可行解

无可行解是指线性规划问题的可行域是空集。

当约束条件相互矛盾时,可行域为空集,也就没有最优解

在管理系统中,常常存在目标冲突,需要进行权衡。

约束条件的冲突可以分为技术性冲突和利害性冲突。后者是因为经济利益而相互矛盾,可以采取经济补偿来解决。 技术性冲突是因为技术因素而互斥,可以通过设定优先次序的方式进行解决,又可细分为技术强冲突和技术弱冲突。如果是技术强冲突,则只能按照约束的重要性进行取舍,放弃其一,保留另一个约束条件,使其起绝对约束作用;如果是技术弱冲突,则限制一个约束的右端有效取值,而调整另一个约束条件的右端取值。