利用Lingo进行多目标规划中0-1问题
工具/原料
Windows10
Windows10家庭版
实例
1、选课策略问题某学校规定，运筹学专业的学生毕业时必须至少学习过两门数学课、三门运筹学课和两门计算机课.这些课程的编号、名称、学分、所属类别和先修课要求如表1示.那么，毕业时学生最少可以学习这些课程中的哪些课程？如果某个学生既希望选修课程数量少，又希望所获得的学分多，他可以选修哪些课程？
2、表1课程情况
3、模型的建立与求解用xi=1表示选修表1中按编号顺序的9门课程（xi=0表示不选；i=1,2,……9).问题的目标为选修的课程总数最少，即
4、约束条件包括两个方面：第一，每人最少要学习2门数学课、3门运筹学课和2门计算机课.根据表1中对每门课程所属类别的划分，这一约束可以表示为x1+x2+x3+x4+x5>=2（1.2）x3+x5+x6+x8+x9>=3（1.3）x4+x6+x7+x9>=2（1.4）
5、第二，某些课程有先修课程的要求.例如“数据结构”的先修课是“计算机编程”，这意味着如果x槐划儋昴4=1，必须x壅酪认奉7=1，这个条件可以表示为x4<=x7（注意：x4=0时对x7没有限制）.“最优化方法”的先修课是“微积分”和“线性代数”的条件可表为x3<=x1,x3<=x2，而这两个不等式可以用一个约束表示为2x3-x1-x2<=0.这样，所有课程的先修课要求可表为如下的约束:2x3-x1-x2<=0（1.5）x4-x7<=0（1.6）2x5-x1-x2<=0（1.7）x6-x7<=0.（1.8）x8-x5<=0（1.9）2x9-x1-x2<=0.（1.10）由上得到以式（1.1）为目标的函数，以式（1.2）～式（1.10）为约束条件的0-1规划模型.将这一模型输入LINGO（注意加上xi为0-1的约束），求解得到结果为x1=x2=x3=x4=x5=x6=x7=x8=x=1，其他变量为0.对照课程编号，它们是微积分、线性代数、最优化方法、计算机模拟、计算机编程、数学实验，共6门课程，总学分为21.
6、下面将会看到，这个解并不是唯一的，还可以找到与以上不完全相同的6门课程，也满足所给的约束.讨论如果一个学生既希望先修课程数少，又希望所获得的学分数尽可能多，则除了目标（1.1）之外，还应根据表2.9中的学分数写出另一个目标，即MaxW=5x1+4x2+3x4+4x5+3x6+2x7+2x8+3x9（1.11）我们把只有一个优化目标的规划问题称为单目标规划，而将多于一个目标的规划问题称为多目标规划.多目标规划的目标函数相当于一个向量，如目标（1.1）和目标（1.11）可以表示为对一个向量进行优化.V-Min(Z,-W)（1.12）上面符号“V-Min”是“向量最小化”的意思，注意其中已经通过对W取负号而将目标（1.11）中的最大化变成了最小化问题.要得到多目标规划问题的解，通常需要知道决策者对每个目标的重视程度，称为偏好程度.
7、下面通过几个例子讨论处理这类问题的方法.同学甲只考虑获得尽可能多的学分，而不管所修课程的多少，那么他可能以式（1.11）为目标，不用考虑式（1.1），这就组成了一个单目标优化问题.显然，这个问题不必计算就知道最优解是选修所有9门课程.同学乙认为选修课程数最少是基本的前提，那么他可以只考虑目标（1.1）而不管目标（1.11），这就是前面得到的，最少为6门.如果这个解是唯一的，则他已别无选择，只能选修上面的6门课，总学分为21.但是LINGO无法告诉我们一个优化问题的解是否唯一，所以他还可能在选修6门课的条件下，使总学分多于21.为探索这种可能，应在上面的规划问题中增加约束.
8、得到以式（1.1）为目标函数、以式（1.2）～式（1.10）和式（1.13）为约众龊受礻束条件的另一个0-1规划模型.求解后发现会得到紧鋈笆珀不同于前面6门课程的最优解x1=x2=x3=x5=x6=x7=1，其他变量为0，也是最优解.同学丙不像甲、乙那样，只考虑学分最多或以课程最少为前提，而是觉得学分数和课程数这两个目标大致上应该三七开.这时可以将目标函数Z和–W分别乘以0.7和0.3，组成一个新的目标函数Y，有MinY=0.7Z-0.3W=-.08x1-0.5x2-0.5x3-0.2x4-0.5x5-0.2x6+0.1x0.1x8-0.2x9（1.14）得到以式（1.14）为目标、以式（1.2）～式（1.10）为约束的0-1规划模型.输入LINGO求解得到结果为：x1=x2=x3=x4=x5=x6=x7=x8=x9=1,即只有“预测理论”不需要选修，共28学分.
9、实际上，0.7和0.3是Z和–W的权重.一般地将权重氇监煜紊记作k1,k2，且令k1+k2租涫疼迟=1k1>=0,k2<=1，则0-1规划模型的新目标为MinY=k1Z-K2W（1.15）前面同学甲的考虑相当于K1=0,K2=1，同学乙的考虑相当于K1=1,K2=0，这是两种极端情况.通过选取许多不同的K1,K2进行计算，可以发现当K1<2/3时，结果与同学甲相同；而当K1>3/4时，结果与同学乙相同.这是偶然的吗？我们根据给出的数据分析一下.当K1<2/3时，式（1.15）中Y的所有参数都小于0，因此为了使Y取最小值，x4,x6,x7,x8,x9应尽可能取1，这与K1=0,K2=1的情况，即学分数最多是一样的.当K1>3/4时，式（1.15）中的Y的系数中至少有5个大于0，它们分别是x4,x6,x7,x8,x9的系数，因此为了使Y取最小值，x4,x6,x7,x8,x9应尽可能取0，而根据前面的计算知道约束条件已经保证至少要选修6门课，所以x4,x6,x7,x8,x9中最多只能有3个同时取0，这与K1=1,K2=0的情况，即选修的课程数最少是一样的.用0-1变量表示选择策略是常用的方法，而对于“要选甲必选乙”这样的约束，可以用类似于式（1.6）x4<=x7来描述.有些选择问题，如从众多球员中选拔上场队员时，由于相互配合或相互制约的关系，还会遇到诸如“甲乙二人至多选一人”、“甲乙二人至少选一人”、“要选甲必不能选乙”等约束.
10、本例优先考虑一个目标不过是加权系数法的极端情况.而像前面同学乙那样，把一个目标作为约束条件（1.13），解目标的规划模型，也是处理多目标规划的一种常用方法.