05整数规划

2011春季班三年级超常班 学而思 侯晓琳

第五讲 整数分拆 

整数分拆这一讲属于奥数七大重点专题——计数的基础；培养同学们有序思

考问题的能力——思考问题时要按照一定的顺序，才能做到不重复不遗漏。 

本讲涉及到三方面的内容： 

1. 与整数分拆相关的计数问题（这是本讲的重点）； 

2. 与整数分拆相关的应用题（如何分析题意把实际问题转化成数学问题）； 

3. 与整数分拆相关的最值（最大与最小）问题（数论中最值问题的基础）； 

一、 与整数分拆相关的计数问题 

数数计数最重要的是按照一定的顺序，才能做到不重复不遗漏。 

超常123班学案一：将15个玻璃球分成数量不同的4堆，共有多少种不同

的分法？ 

分析与答：本题相当于把15拆成4个互不相同的非0自然数相加，问

有多少种不同的分拆方法？（注意不能有0，否则就不是4堆了） 

15=1+2+3+9（注意拆分顺序：几个数由小到大排列或有大到小排列保证不重

复） 

=1+2+4+8（注意变化顺序：尽可能多的固定前面的数，变化最后两个数，

并且按顺序依次调整，保证不遗漏） 

=1+2+5+7（1、2开头的已经没有了，即变化后两个数已经调整不出来其他

结果，再按顺序调整倒数第三个数） 

=1+3+4+7 

=1+3+5+6（只变化后三个数已经调整不出来了，最后再调整第一个数） 

=2+3+4+6 

小结：本题不难，希望同学们通过本题理解整数分拆的枚举顺序。有序

枚举，不重不漏。 

例1：从1~12这十二个自然数中选取，把26分拆成四个不同自然数之

和。 

分析与答：体会本题和上题的区别：上题没有给范围，而这道题要求数

的范围在1~12之间。这时孩子们通常会有两种入手角度： 

（1）26=1+2+11+12 

（2）26=12+11+2+1 

那么哪个角度拆分起来既容易且迅速呢？是第二种。方法一里26=1+后

三个数，相当于把25分拆成后三个数的和，而方法而里26=12+后三个数，

相当于把14分拆成后三个数的和，明显14较容易分拆一些。所以，一般地，

第4章 整数规划

判断:

04100011 用分枝定界法求解一个极大化的整数规划问题，任何一个可行解的目标函数值是该问题目标函数值的下界；

04100021 指派问题数学模型的形式同运输问题十分相似，故也可以用表上作用法求解；

04100031效率矩阵的任一行（或列）减去（或加上）任一常数，指派问题最优解不会受到影响；

04100041匈牙利法只能用于平衡分配问题；

04100051对于极大化问题，匈牙利法不能直接求解。

04100061整数规划问题解的目标函数值优于其相应的线性规划问题的解的目标函数。

04100071用割平面法求解整数规划问题，构造的割平面有可能切去一些不属于最优解的整数解。

04100081用分枝定界法求解一个极大化的整数规划问题时，当得到多于一个可行解时，通常可任取其中一个作为下界值，在进行比较剪枝。

04100091分配问题的每个元素都加上同一个常数k，并不会影响最优分配方案。

04100101分配问题的每个元素都乘上同一个常数k，并不会影响最优分配方案。

04100111分配问题域运输问题的数学模型结构形式十分相似，故也可以用表上作业法求解。

04100121隐枚举法也可以用来求解分配问题

简答

04200011 试述分枝定界法求解问题的主要思想。

04200021 试述隐枚举法的步骤。

04200031 试讲述割平面方法的基本原理.

04200041试例举三种应该剪枝的情况。

计算题

分枝定界法

04301012用分枝定界法求解下列整数规划问题

12maxZxx

1212129511414123,xxxxxx0且为整数

04301022用分枝定界法求解下列整数规划问题 12max32Zxx

121212231429,xxxxxx0且为整数

第２６卷第２期　２００９年５月　江苏教育学院学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｊｉａｎｇｓｕ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｅｄｕｃａｔｉｏｎ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅｓ）　Ｖｏ１．２６　Ｎｏ．２　Ｍａｙ，２００９　

整数规划在数学建模竞赛中的应用初探　

胡　明　

（江苏科技大学数理学院，江苏镇江２１２００３）　

摘　要介绍了整数规划的基本概念、基本知识和基本模型，以探讨整数规划在２００５高教社杯全国大学生数学建模竞　赛中的应用为例，使学生初步了解并掌握在数学建模竞赛中怎样利用整数规划的思想、方法建立数学模型．　关键词　整数规划；Ｏ一１整数规划；数学建模竞赛　［中图分类号］　Ｇ６４０　［文献标识码］　Ａ　

数学建模竞赛是由美国工业与应用数学学会在１９８５年发起的一项大学生竞赛活动，目的是促进数学建模的教学，培养学　

生应用数学的能力．我国在１９９２年起开展这项竞赛，现已形成一项全国性的竞赛活动，也是参赛学校最多的一种科技竞赛．２００８　

年全国共有１０２２所高等院校计１２２８４支队伍３万８千多人参加比赛．每年参加数学建模竞赛的学生中相当一部分是大学二、三　

年级的同学，他们刚刚修完高等数学、线性代数和概率论与数理统计等课程，对参加数学建模竞赛所需具备的其它数学知识以　

及数学建模的方法没有更多的了解，怎样使这部分学生能更好地参加数学建模竞赛，成为许多指导教师经常讨论的问题．据不　

完全统计，在以往的数学建模竞赛题中，大概有８０％的问题属于优化问题，属于运筹学的研究范畴，而其中相当一部分又是属于　

整数规划问题，因此尽快掌握运筹学的基本理论，特别是整数规划的基本知识，学会用整数规划的思想、方法建立数学模型显得　

尤为迫切．下面通过介绍整数规划的基本知识，基本线性模型，利用整数规划的思想、方法建立数学模型．　

１　基本知识　

定义１．１…一般的，整数规划的数学模型是　

ｍａｘ（或ｍｉｎ　：∑ｃ　（１．１）　Ｊ＝１’。　『；　。　＝ｂｉ（ｉ＝１，２，…，ｍ）；　（１．２）　

徐州工程学院

数理学院

案例分析报告

课程名称 运筹学及应用

案例分析题目 华南公司投资方案

专 业 信息与计算科学

班 级 13信计1

姓 名 李明军 陈翔 历晓雨 石宝 刘嘉炜 陈伟康

学 号 42 44 13 23 25 40

指导教师 赵建强

成绩等级

2015年 6 月 12 日

目 录

小组成员分工………………………………………………………………………1

一．问题描述………………………………………………………………………2

二．问题分析………………………………………………………………………2

三．模型建立………………………………………………………………………2

四．模型求解与程序设计…………………………………………………………3

五．结果分析………………………………………………………………………5

- 1 - 小组人员详细分工（3-6人）

学号 姓名 具体分工

42 李明军 统筹安排

13 厉晓雨 排版整理

44 陈翔 模型建立

23 石宝 模型求解

25 刘嘉炜 问题分析

40 陈伟康 软件应用 - 2 - 一．问题描述

华南投资公司在实施“九五”后三年及“十五”初期发展规划时，决定投资兴办产业，以增强发展后劲，投资总额为800万元，其中第一年(即1998年)350万元，第二年300万元，第三年150万元。投资方案有：