整数最优选课模型

1、整数最优选课模型摘要： 利用整数规划的相关理论， 考虑选课量最少建立一种单一目标约束的整 数规划模型；学分最少的整数规划模型；选课人数受限的整数规划建模，利用LINDO软件编程，给出了整数规划的解，研究了一个由0-1规划所所描述的大学选课模型，从而得到该模型的最优方案。关键词：整数规划 LINDO软件 选课模型 最优方案。一、问题重述某同学考虑下学期的选课，其中必修课只有一门（2学分），可供选修的限 定选修课（限选课）有8门，任意选修课（任选课）有10门。由于有些课程之 间相互关联，所以可能在选修某门课程时必须同时选修其他某门课程。根据所给数据以及学校对学生选课要求，建立数学模型研究要达到一定

2、学 分所选课程最少的整数规划的最优解；学分最少的情况能最多选课门数的模型； 针对某些课程人数限制建立模型探讨出最优方案。我们利用0-1整数规划建立选课模型二、符号说明我们用Xi表示是否选秀课程i ,Xi =1表示该课程被选修,Xi =0表示该课程被拒绝;选秀课程i时必须同时选修课程 j，则可以用Xj >xi表示;用变量yi，y2分别表示选修的限选课、任选课的学分数,yi,y表示总的学分数（包括 2个必修学分）。模型建立与求解 问题1则建立数学规划模型：L18m in 2 Xii A.s.t. y =5x1 +5x2 +4x3 +4x4 + 3x5 +3x6 +3x7 +2x8,y2 =3

3、X9 +3x10 +3x11 +2X12 +2x14 +X15 +X16 +X17 +X18,y =yi +y2 + 2,y >20, y <6y2,y >3y2；X1 上 X5 J X2 工 X7 ,X4 >X11,X5 >X12,Xi 壬0,1 X7 >X13,Xe >X14,上述问题中决策中决策变量只能取 数规划，下面求解该问题。 程序1如下x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x180或1,称为0-1规划，是一种特殊的整MinSubject to5x1+5x2+4x

4、3+4x4+3x5+3x6+3x7+2x8-y1=03x9+3x10+3x11+2x12+2x13+2x14+x15+x16+x17+x18-y2=0y1+y2-y=-2y>=206y2-y>=03y2-y<=0x1-x5>=0x2-x7>=0x8-x9>=0 x6-x10>=0x4-x11>=0x5-x12>=0x7-x13>=0x6-x14>=0endint 18运仃结果为 Xt = X4 = X6 = X10 = X11 =1，其他 Xi=0 ，y 1 2 ， y 6 ， y=20。即至少要选课程编号为 1，4，6，10,

5、 11。该整数规划的最优解不唯一。一般的，得到一个整数规划的最优解是很困难度的。下面笔者通过对变量的约束惊醒隐式枚举的方法给出具体解，方法如下：在以上的程序中每次添加Xi =0( Xi =1) (i =1,2,18)，这样经过36次运算，得到解如下表所示表约束变量选课方案限选课学分数任选课学分数所得总学分X1=02, 4, 6,10, 1112620X1=11, 2, 6, 10, 1413520X2=01, 4, 6, 10, 1112620X2=11, 2, 6, 10, 1413520X3=02, 4, 6, 10, 1112620X3=11, 3, 4, 11, 15, 1613520

6、X4=01, 2, 6, 10, 1413520X4=12, 4, 6, 10, 1112620X5=01, 4, 6, 10, 1112620X5=11, 4, 5, 11, 12, 1812620X6=01, 2, 4, 11, 1514420X6=11, 2, 6, 10, 1413520X7=01, 2, 6, 10, 1413520X7=12, 4, 7, 11, 13, 1812620X8=01 , 4, 6, 10, 1112620X8=11, 2, 4, 8, 9 , 1116624X9=01 , 4, 6, 10 , 1112620X9=11, 4 , 6 , 8, 9 ,

7、1014622X10=01, 2 , 4, 11, 1514420X10=12, 4, 6, 10, 1112620X11=01, 2, 6, 10, 1413520X11 = 12, 4, 6, 10, 1112620X12=01 , 2, 6, 10 , 1413520X12=11, 4, 5, 11, 12, 1812620X13=01, 2, 6, 10, 1413520X13=12, 4, 7, 11, 13, 1812620X14=02 , 4, 6, 10, 1112620X14=11, 2, 6, 10, 1413520X15=01, 4, 6, 10, 1112620X15=

8、11, 2, 4, 11, 1514420X16=01, 4, 6, 10, 1112620X16=11, 2, 4, 11, 1614420X17=01 , 4, 6, 10 , 1112620X17=11, 2, 4, 11, 1714420X18=01 , 2, 6, 10 , 1413520X18=11, 2, 4, 11, 1814420通过对比筛选得最优选课方案如下表所示：表二选课方案限选课学分数任选课学分数所得总学分1, 4, 6， 10， 11126202, 4, 6， 10， 11126201, 2, 6, 10, 14135201, 2, 4, 11, 15144201,

9、2, 4, 11 , 16144201, 2, 4, 11, 17144201, 2, 4, 11 , 1814420注：其中数字1, 4, 6, 10, 11表示该方案中所选课程的编号，其他的一次类推。问题分析通过运行程序得到的最优选课方案共7种，这7种方案所得学分敲好是 20，为了1、4、得到20学分选5们课程即可，既表二中的7种选课方案。这些结果还反映了课程 11占重要地位，表明该学校以1、4、11这些学科为主要课程。问题2建立数学规划模型-18max送 Xji丄s.t. y =5x1 +5X2 +4X3 +4X4 +3X5 +3x6 +3X7 +2X3,y2 =3x9 +3xio +3

10、xii +2Xi2 +2Xi4 +Xi5 +Xi6 +Xi7 +Xi8,y =y, +y2 + 2,y =20,y <6y2.y >3y2；Xi >X5,X2 > X7,Xg >X9， X6>Xio；X4 >X11,X5 X Xi 2 ,XX13, XX14 ,Xi 迂o,1 程序 1Min x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18Subject to5x1+5x2+4x3+4x4+3x5+3x6+3x7+2x8-y1=03x9+3x10+3x11+2x12+2x13+2x14+x15+x16+x17+x18-y2=0y1+y2-y=-2y>=206y2-y>=03y2-y<=0x1-x5>=0x2-x7>=0x8-x9>=0x6-x10>=0x4-x11>=0x5-x12>=0x7-x13>=0x6-x14>=0endint 18程序 2max x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18Subject to5x1+5x2+4x3+4x4+3x5+3x6+3x7+2x8-y1=03x9+3x10+3x11+