数学模型中的0、1变量的使用的案例
2014-11-26惠高峰
惠高峰
摘要：本文通过优化问题的求解，讲述了线性规划的数学模型中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.
