数学建模 选课问题 论文整数规划方法

数学建模 选课问题 论文整数规划方法

河南理工大学

数 学 建 模 论

数学建模 选课问题 论文整数规划方法

文

姓名：

专业班级： 学号：

一、符号说明

我们用xi表示是否选秀课程i，

xi 1表示该课程被选修，

xi 0表示该课程被拒绝；

选秀课程i时必须同时选修课程j，则可以用xj xi表示；

用变量y1，y2分别表示选修的限选课、任选课的学分数，y表示总的学分数（包括2个必修学分）。

一、 模型建立与求解 问题1

则建立数学规划模型：

数学建模 选课问题 论文整数规划方法

18

min xi

i 1

ty1 5x1 5x2 4x3 4x4 3x5 3x6 3x7 2x8, s..

y2 3x9 3x10 3x11 2x12 2x14 x15 x16 x17 x18, y y1 y2 2, y 20,y 6y2,y 3y2;

x1 x5,x2 x7,x8 x9,x6 x10; x4 x11,x5 x12,x7 x13,x6 x14, xi 0,1

上述问题中决策中决策变量只能取0或1，称为0-1规划，是一种特殊的整数规划，下面求解该问题。 程序1如下

Min x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18 Subject to

5x1+5x2+4x3+4x4+3x5+3x6+3x7+2x8-y1=0

3x9+3x10+3x11+2x12+2x13+2x14+x15+x16+x17+x18-y2=0 y1+y2-y=-2 y>=20 6y2-y>=0 3y2-y<=0 x1-x5>=0 x2-x7>=0 x8-x9>=0 x6-x10>=0 x4-x11>=0 x5-x12>=0 x7-x13>=0 x6-x14>=0 end int 18

运行结果为x1 x4 x6 x10 x11 1，其他xi 0，y1 12，y2 6，y 20。

即至少要选课程编号为1，4，6，10，11。

该整数规划的最优解不唯一。一般的，得到一个整数规划的最优解是很困难度的。下面笔者通过对变量的约束惊醒隐式枚举的方法给出具体解，方法如下：在以上的程序中每次添加xi 0(xi 1)(i 1,2,...,18)，这样经过36次运算，得到解如下表所示 表一

数学建模 选课问题 论文整数规划方法

通过对比筛选得最优选课方案如下表所示：表二

数学建模 选课问题 论文整数规划方法

问题分析

通过运行程序得到的最优选课方案共7种，这7种方案所得学分敲好是20，为了得到20学分选5们课程即可，既表二中的7种选课方案。这些结果还反映了课程1、4、11占重要地位，表明该学校以1、4、11这些学科为主要课程。

问题2

建立数学规划模型

max t s..

x

i 1

18

i

y1 5x1 5x2 4x3 4x4 3x5 3x6 3x7 2x8,y2 3x9 3x10 3x11 2x12 2x14 x15 x16 x17 x18,y y1 y2 2,y 20,

y 6y2,

y 3y2;

x1 x5,x2 x7,x8 x9,x6 x10;x4 x11,x5 x12,x7 x13,x6 x14,xi 0,1

数学建模 选课问题 论文整数规划方法

程序1

Min x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+

x17+x18 Subject to

5x1+5x2+4x3+4x4+3x5+3x6+3x7+2x8-y1=0

3x9+3x10+3x11+2x12+2x13+2x14+x15+x16+x17+x18-y2=0 y1+y2-y=-2 y>=20

数学建模 选课问题 论文整数规划方法

3y2-y<=0 x1-x5>=0 x2-x7>=0 x8-x9>=0 x6-x10>=0 x4-x11>=0 x5-x12>=0 x7-x13>=0 x6-x14>=0 end int 18

程序2

max x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+

x17+x18 Subject to

5x1+5x2+4x3+4x4+3x5+3x6+3x7+2x8-y1=0

3x9+3x10+3x11+2x12+2x13+2x14+x15+x16+x17+x18-y2=0 y1+y2-y=-2 y=20

数学建模 选课问题 论文整数规划方法

3y2-y<=0 x1-x5>=0 x2-x7>=0 x8-x9>=0 x6-x10>=0 x4-x11>=0 x5-x12>=0 x7-x13>=0 x6-x14>=0 end int 18