运筹学模型与软件求解(第七章).ppt

1、运筹学模型与软件求解运筹学模型与软件求解中国科学院研究生院中国科学院研究生院 Models and Software Solutions of the Operations Research第七章整数规划模型与实验第七章整数规划模型与实验背包问题背包问题 半场安排最多人员模型半场安排最多人员模型 装货问题模型与试验装货问题模型与试验变量取整数的规划称为整数规划变量取整数的规划称为整数规划所有变量所有变量都取整数的规划称为都取整数的规划称为纯整数规划纯整数规划，部分变量部分变量取整数的规划称为取整数的规划称为混合整数规划混合整数规划。所有变量所有变量都取都取0 0、1 1两个值的规划称为两个值的

2、规划称为0-10-1规划规划部分变量部分变量取取0 0、1 1两个值的规划称为两个值的规划称为0-10-1混合规混合规划划。用用LingoLingo求解背包问题求解背包问题 构造集合构造集合 SETS:ITEMS/ANT_REPEL,BEER,BLANKET,BRATWURST,BROWNIES,FRISBEE,SALAD,WATERMELON/:INCLUDE,WEIGHT,RATING;ENDSETS 属性属性INCLUDE为一个为一个01变量，说明该物品是否包变量，说明该物品是否包含在背包中，用于野餐。含在背包中，用于野餐。WEIGHT说明每一物品的说明每一物品的重量，而重量，而RATI

3、NG存储着该物品的指数值存储着该物品的指数值构造模型（目标函数）构造模型（目标函数）MAX=SUM(ITEMS:RATING*INCLUDE);在这里没有明确说明在这里没有明确说明ITEMS的具体变量，此处是要对的具体变量，此处是要对所有的所有的ITEMS进行操作进行操作构造模型（约束条件）构造模型（约束条件）SUM(ITEMS:WEIGHT*INCLUDE)=KNAPSACK_CAPACITY;要求所有的包含在背包里的物品，总重量不能超过我要求所有的包含在背包里的物品，总重量不能超过我们的设定值们的设定值FOR(ITEMS:BIN(INCLUDE);要求所有的要求所有的INCLUDE是是01

4、变量变量SETS:ITEMS/ANT_REPEL,BEER,BLANKET,BRATWURST,BROWNIES,FRISBEE,SALAD,WATERMELON/:INCLUDE,WEIGHT,RATING;ENDSETSDATA:WEIGHT RATING=1 2 3 9 4 3 3 8 3 10 1 6 5 4 10 10;KNAPSACK_CAPACITY=15;ENDDATAMAX=SUM(ITEMS:RATING*INCLUDE);SUM(ITEMS:WEIGHT*INCLUDE)=KNAPSACK_CAPACITY;FOR(ITEMS:BIN(INCLUDE);二维背包问题与计算

5、二维背包问题与计算 从数学模型的角度，约束条件增从数学模型的角度，约束条件增加了一行加了一行 构造相关的构造相关的LINDOLINDO模型模型整数规划在实际的经济生活中有广泛的应用，特别是线性整整数规划在实际的经济生活中有广泛的应用，特别是线性整数规划更为应用广泛、有效数规划更为应用广泛、有效半场安排最多人员模型半场安排最多人员模型 构造集合构造集合 SETS:SONG/1.7/:LENGTH,Y;ENDSETS构造模型构造模型 !在半场音乐会中，有最多的音乐家参加在半场音乐会中，有最多的音乐家参加;MAX=SUM(SONG:Y);!从音乐的时间角度不可以超过一般时间从音乐的时间角度不可以超过一般时间;SUM(SONG:LENGTH*Y)=HALF;!计算一半的音乐时间计算一半的音乐时间;HALF=SUM(SONG:LENGTH)/2;!要求要求Y变量为变量为01变量变量;FOR(SONG:BIN(Y);装货问题模型与试验装货问题模型与试验 使用使用WinQSBWinQSB软件求解背包问题软件求解背包问题 在在WinQSB软件中选择软件中选择 Dynamic Programming