继上篇数模优化模型

一、选修课程策略问题

某学校规定，运筹学专业的学生毕业时必须至少学习过两门数学课、三门运筹学课和两门计算机课。这些课程的编号、名称、学分、所属类别和先修课要求如表1所示。那么，毕业时学生最少可以学习这些课程中哪些课程。

如果某个学生既希望选修课程的数量少，又希望所获得的学分多，他可以选修哪些课程？

模型的建立

约束条件包括两个方面：

这样，所有课程的先修课要求可表为如下的约束

总的0-1规划模型为：

LINGO程序为：

model:

sets:

item/1..9/:c,x;

endsets

data:

c=5,4,4,3,4,3,2,2,3;

enddata

min=@sum(item(i):x(i));!课程最少;

x(1)+x(2)+x(3)+x(4)+x(5)>=2;

x(3)+x(5)+x(6)+x(8)+x(9)>=3;

x(4)+x(6)+x(7)+x(9)>=2;

x(3)<=x(1);

x(3)<=x(2);

x(4)<=x(7);

x(5)<=x(1);

x(5)<=x(2);

x(6)<=x(7);

x(8)<=x(5);

x(9)<=x(1);

x(9)<=x(2);

@for(item(i):@bin(x(i)));

end

二、最优组队问题

三、图论中的优化模型

1、最短路算法

例1 灾情巡视路线问题(98B)

三、最优树模型及Lingo求解

树：连通且不含圈的无向图称为树．常用T表示。

树枝：树中的边称为树枝，树中度为1的顶点称为树叶 。

图论中最优树的的求解通常有两种算法：

Kruskal算法（或避圈法）和Prim算法（破圈法）.

这里利用LINGO求解最优树。

问题1 某有10个城镇见右图，它们之间的距离见表6。城镇1处有一条河流，现需要从各城镇之间铺设管道，使城镇1处的水可以输送到各城镇，求铺设管道最少的设计方式。