Models and Software Practice of the Operations Research

Presentation on theme: "Models and Software Practice of the Operations Research"— Presentation transcript:

1 Models and Software Practice of the Operations Research
运筹学模型与软件实践 Models and Software Practice of the Operations Research 中国科学院研究生院

2 第七章　整数规划模型与实验 背包问题 半场安排最多人员模型 装货问题模型与试验

3 变量取整数的规划称为整数规划 所有变量都取整数的规划称为纯整数规划，部分变量取整数的规划称为混合整数规划。
所有变量都取0、1两个值的规划称为0-1规划 部分变量取0、1两个值的规划称为0-1混合规划。

4

5

6 用Lingo求解背包问题

7 构造集合 SETS: ITEMS / ANT_REPEL, BEER, BLANKET, BRATWURST, BROWNIES, FRISBEE, SALAD, WATERMELON/: INCLUDE, WEIGHT, RATING; ENDSETS 属性INCLUDE为一个0－1变量，说明该物品是否包含在背包中，用于野餐。 WEIGHT说明每一物品的重量，而RATING存储着该物品的指数值

8 MAX = @SUM( ITEMS: RATING * INCLUDE);
构造模型（目标函数） MAX ITEMS: RATING * INCLUDE); 在这里没有明确说明ITEMS的具体变量，此处是要对所有的ITEMS进行操作

9 构造模型（约束条件） @SUM( ITEMS: WEIGHT * INCLUDE) <= KNAPSACK_CAPACITY;
要求所有的包含在背包里的物品，总重量不能超过我们的设定值 @FOR( INCLUDE)); 要求所有的INCLUDE是0－1变量

10 SETS: ITEMS / ANT_REPEL, BEER, BLANKET, BRATWURST, BROWNIES, FRISBEE, SALAD, WATERMELON/: INCLUDE, WEIGHT, RATING; ENDSETS DATA: WEIGHT RATING = ; KNAPSACK_CAPACITY = 15; ENDDATA MAX ITEMS: RATING * INCLUDE); @SUM( ITEMS: WEIGHT * INCLUDE) <= KNAPSACK_CAPACITY; @FOR( INCLUDE));

11 二维背包问题与计算

12 从数学模型的角度，约束条件增加了一行 构造相关的LINDO模型 整数规划在实际的经济生活中有广泛的应用，特别是线性整数规划更为应用广泛、有效

13 半场安排最多人员模型

14 构造集合 SETS: SONG/1..7/: LENGTH, Y; ENDSETS

15 构造模型 ! 在半场音乐会中，有最多的音乐家参加; MAX = @SUM( SONG: Y); ! 从音乐的时间角度不可以超过一般时间;
@SUM( SONG: LENGTH * Y) <= HALF; ! 计算一半的音乐时间; HALF SONG: LENGTH)/ 2; ! 要求Y变量为0－1变量; @FOR( Y));

16 装货问题模型与试验

17

18

19

20

21

22

23 使用WinQSB软件求解背包问题 在WinQSB软件中选择 Dynamic Programming

24

25

26

27