运筹学模型与软件求解,中国科学院研究生院,Models and Software Solutions of the Operations Research,第七章整数规划模型与实验,背包问题 半场安排最多人员模型 装货问题模型与试验,变量取整数的规划称为整数规划所有变量都取整数的规划称为纯整数规划，部分变量取整数的规划称为混合整数规划。所有变量都取0、1两个值的规划称为0-1规划部分变量取0、1两个值的规划称为0-1混合规划。,用Lingo求解背包问题,构造集合,SETS: ITEMS / ANT_REPEL, BEER, BLANKET, BRATWURST, BROWNIES, FRISBEE, SALAD, WATERMELON/: INCLUDE, WEIGHT, RATING;ENDSETS,属性INCLUDE为一个01变量，说明该物品是否包含在背包中，用于野餐。 WEIGHT说明每一物品的重量，而RATING存储着该物品的指数值,构造模型（目标函数）,MAX = SUM( ITEMS: RATING * INCLUDE);,在这里没有明确说明ITEMS的具体变量，此处是要对所有的ITEMS进行操作,构造模型（约束条件）,SUM( ITEMS: WEIGHT * INCLUDE) = KNAPSACK_CAPACITY;,要求所有的包含在背包里的物品，总重量不能超过我们的设定值,FOR( ITEMS: BIN( INCLUDE);,要求所有的INCLUDE是01变量,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);,二维背包问题与计算,从数学模型的角度，约束条件增加了一行 构造相关的LINDO模型整数规划在实际的经济生活中有广泛的应用，特别是线性整数规划更为应用广泛、有效,半场安排最多人员模型,构造集合,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);,装货问题模型与试验,使用WinQSB软件求解背包问题,在WinQSB软件中选择 Dynamic Programming,