在线性规划模型中一类决策变量的引进

陈永鹏

摘 要： 在本文讨论了利用某一些时间段的开始时刻引进相关的决策变量，从而建立一些线性规划模型。

关键词： 开始时刻 决策变量 线性规划模型

在建立线性规划模型时，决策变量的引入至关重要，良好的决策变量能使目标函数与约束条件的描述很清晰，从而易于建立起相关的线性规划模型。有一类线性规划问题会涉及某一些时间段的开始时刻，我们可以从开始时刻入手引进相关的决策变量，以下就处理两个具体的例子。

例1.某储蓄所每天的营业时间为上午9：00到下午17：00，根据经验，每天不同时间段所需要的服务员的数量为：

储蓄所可以雇佣全时和半时两类服务员。全时服务员每天报酬为100元，从上午9：00到下午17：00工作，但中午12：00到下午14：00之间必须安排1小时的午餐时间；储蓄所每天可以雇佣不超过3名的半时服务员，每个半时服务员必须连续工作4小时，报酬为40元。问：储蓄所应该如何雇佣全时和半时两类服务员，才能使费用最少？

问题分析：通过全时服务人员在什么时刻开始午餐，可以把他们分成两类人员，一类是12～13进行午餐的，另一类是13～14进行午餐的。由此设x1，x2分别表示12～13，13～14进行午餐的全时服务人员。对于半时服务人员，考察他们在什么时刻开始工作可以分成五类人员。可以设y1，y2，y3，y4，y5分别表示9～10，10～11，11～12，12～13，13～14开始工作的半时服务人员。那么该问题相关的决策变量就引入好了。例1的模型如下所示：

min=100*x1+100*x2+40*y1+40*y2+40*y3+40*y4+40*y5；

x1+x2+y1>4；x1+x2+y1+y2>3；x1+x2+y1+y2+y3>4；

x2+y1+y2+y3+y4>6；x1+y2+y3+y4+y5>5；x1+x2+y3+y4+y5>6；

x1+x2+y4+y5>8；x1+x2+y5>8；y1+y2+y3+y4+y5<3；

例2.有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）。由于4名同学的专业背景不同，因此每人在三个阶段的面试时间也不同，如表所示。这4名同学约定他们全部面试以后一起离开公司。假定现在的时间是早上8：00，请问他们最早何时能离开公司？

通过以上两个例子，我们可以看出在这种类型的问题中，按上述方式引进决策变量，能把问题描述得非常清晰，从而建立相应的模型，运用lingo软件进行求解，就可以圆满解决问题。

参考文献：

[1]谢金星，薛毅.优化建模与LINDO/LINGO软件[M].北京：清华大学出版社，2005.