数学模型中的0、1变量的使用的案例

惠高峰

摘要：本文通过优化问题的求解，讲述了线性规划的数学模型中0、1变量的使用方法和技巧，并利用LINGO软件进行了编程测试，提高数学模型中变量的使用方法。

关键词：Lingo软件 0、1变量

数学优化问题在管理数学当中是一个并不复杂的问题，但是对于变量的使用，尤其是0、1变量的使用，学生们会产生很大迷惑，以下通过一些例子来讲述一下0、1变量的灵活使用。公司在各地有4项业务，选定了4位业务员去处理。由于业务能力、经验和其它情况不同，4位业务员去处理4项业务的费用（单位：元）各不相同，见右表。

应当怎样分派任务，才能使总的费用最小？

问题分析与求解：这是一个最优指派问题。引入如下变量：xij=1 若分派第i个人做每j项业务0 若不分派第i个人做第j项业务

设矩阵a（4，4）为指派矩阵，其中a（i，j）为第i个业务员做第j项业务的业务费。则可以建立如下模型：

minZ=■■aijxij s.t■xij=1 j=1，2，3，4■xij=1 i=1，2，3，4xij=0或1 i，j=1，2，3，4

LINGO程序如下：

MODEL：

SETS：

person/1..4/；

task/1..4/；

assign（person，task）：a，x；

ENDSETS

DATA：

a=1100，800，1000，700，

600，500，300，800，

400，800，1000，900，

1100，1000，500，700；

ENDDATA

min=@sum（assign：a*x）；

@for（person（i）：@sum（task（j）：x（i，j））=1）；

@for（task（j）：@sum（person（i）：x（i，j））=1）；

@for（assign（i，j）：@bin（x（i，j）））；

END

得到的结果如下：

x（1，1）=0，x（1，2）=0，x（1，3）=0，x（1，4）=1；

x（2，1）=0，x（2，2）=1，x（2，3）=0，x（2，4）=0；

x（3，1）=1，x（3，2）=0，x（3，3）=0，x（3，4）=0；

x（4，1）=0，x（4，2）=0，x（4，3）=1，x（4，4）=0；

最小费用为2100元。

即第1个业余员做第4项业务，第2个业余员做第2项业务，即第3个业余员做第1项业务，第4业余员做第3项业务。总费用达到最小，为2100元。

有五项设计任务可供选择。各项设计任务的预期完成时间分别为3，8，5，4，10（周）设计报酬分别为7，17，11，9，21（万元）。设计任务只能一项一项地进行，总的期限为20周。选择任务时必须满足下面要求：①至少完成3项设计任务。②若选择任务1，必须同时选择任务2。③任务3和任务4不能同时选择。

应当选择哪些任务，才能使总的设计报酬最大？

分析与求解：这是一个0-1整数规划问题。

设0-1变量xi如下：xi=0 第i项设计任务未选上1 第i项设计任务被选上

设各项设计任务的完成时间为ti（i=1，2，…，5）表示，设计报酬为mi（i=1，2，…，5）表示。则容易得到目标函数：maxZ=■mixi。根据题目要求分别列出约束条件如下：

总期限为避免20周，则约束条件为■tixi？燮20

至少完成3项设计任务，则■xi？叟3

若选择任务1，必须同时选择任务2，则x2？叟x1。

任务3和任务4不能同时选择，则x3+x4？燮1，该约束表达式表明任务3和任务4至多只能选择1个。

因此对该问题建立的数学模型如下：

maxZ=■mixi s.t■tixi？燮20■xi？叟3x2？叟x1x3+x4？燮1x1，x2，x3，x4=0或1

LINGO程序如下：

MODEL：

SETS：

mat/1..5/：m，t，x；

ENDSETS

DATA：

m=7，17，11，9，21； ！定义报酬数组；

t=3，8，5，4，10； ！定义完成时间；

ENDDATA

max=@SUM（mat（i）：m（i）*x（i））； ！定义目标函数；

@SUM（mat（i）：t（i）*x（i））<=20；！期限约束 ；

@SUM（mat（i）：x（i））>=3； ！至少完成3项任务；

x（2）>=x（1）； ！若选择任务1，必须同时选择任务2；

x（3）+x（4）<=1； ！任务3和任务4不能同时选择；

@FOR（mat（i）：@BIN（x（i）））； ！使各变量为0-1变量；

END

得到的解为x（1）=1，x（2）=1，x（3）=1，x（4）=0，x（5）=0。最大报酬为35万元。

即在满足各种约束条件下，选择设计任务1，2，3，可使总报酬达到最大为35万元。

参考文献：

[1]肖华勇.实用数学建模与软件应用[M].西安：西北工业大学出版社，2008.

[2]周义仓，郝孝良.数学建模实验[M].西安：西安交通大学出版社，2007.