整数规划的产生和发展报告.pptx

PPT模板下载：/ 行业PPT模板：/
节日PPT模板：/ PPT素材下载：，不需要使用铁矿，此时，对应的xij将全部取零值，故：
由Ai向Bj钢铁的运输量均为非负实数
备选的钢铁厂只有一处
典型的整数规划问题
工厂选址问题
根据如上分析,根据设计变量的取值规则，要么建厂取0，要么不建厂取1，同时该问题还要确定如果选择了厂址，应当如何分配m座铁矿对两个钢铁厂的钢铁供应量xij，而该变量的取值为非负实数即可，故该问题为一混合整数规划问题，且为混合0-1规划，可以归纳为如下形式：
典型的整数规划问题
背包问题
夫妇两人要赴A地进行长途旅行,需要整理行李，现有3个旅行包，其容积大小分别为10升、15升和20升，两人在列出物品清单后根据需要已经整理出了10个包装袋，其中一些包装袋中装的是必带物品，共有7件，其体积大小分别为4升、3升、、、、，尚有8个包装袋可带可不带，不带则可在A地购买，这些可选包装袋的容积和其对应物品在A地的价格如表所示。
试根据上述信息给出一个合理的打包方案。
在这个问题中，我们需要确定的是，选带哪几个可选的包装袋，且将必带物品和选带物品放到哪个旅行包中。为此我们设第i个包装袋是否放在第j个旅行包中，并以此作为设计变量。同时，设第i个包装袋的容积可以用wi i=1,2,3,…,15 来表示，可选包装袋对应的价格用pi (i=8,9,10,…,15)来表示。由于第i个包装袋要么在第j个旅行包中，要么在要么不在，故设只取0和1，且表述如下：
物品
1
2
3
4
5
6
7
8
容积

4






价格
20
50
105
75
55
80
200
100
典型的整数规划问题
背包问题
由于每个旅行包的容积确定,故装入第j个旅行包中的所有包装袋的容积的总和必须小于第j个旅行包的容积，即需要满足约束条件：
由于旅行袋中有7件为必带，故这7个包装袋必然在3个旅行包中的其一，设包装袋的编号为i，则在设计变量xi1、xi2和xi3中必有一个取值为1，另外两个取值为0，其和为1，根据上述分析，对于7件必带的包装袋必须满足如下约束：
对于可选的包装袋，则其要么在某个旅行包中，要么不在旅行包中，设包装袋的编号为i，如果它在某个旅行包中，则设计变量xi1、xi2和xi3取值之和为1，如果它不在旅行包之中，则设计变量xi1、xi2和xi3取值之和为0，故对于可选的包装袋必须满足如下约束：
典型的整数规划问题
背包问题
我们的目标就是使得在到达A地之后,所买物品的价格最低，即不在旅行包中的包装袋的总价格最低，如果某包装袋i不在旅行包中，则有： 故其价格可以用 来表示，故所有不在旅行包中的包装袋的价值f可表达如下
我们确定打包方案的原则就是使得 f 取得最小值，故综合以上分析，该背包问题的数学模型为：
整数规划问题的数学模型
一般形式
在整数规划中还有许多其他典型的问题,例如在第3章中提到的分派问题，还有旅行商问题、下料问题等，其问题均可以归结为如下的一般形式
上述形式是仿照线性规划中的标准型给出的，其中设计变量x为n维的列向量，c为n维的行向量，A为m×n的矩阵，且A行满秩，b为m维列向量，
在模型中， 1 可以是最大化也可以是最小化，对于约束(2)，可以是等式的形式也可以是不等式的形式。对于对设计变量的约束(3)，如果要求x全部分量为整数，则为纯整数规划；如果要求x的部分分量为整数，则为混合整数规划，如果要求x分量的取值只能为0和1，则为0-1规划。
整数规划的求解
直观想法
既然整数规划问题的可行方案数目有限,则我们经过枚举比较之后，总能求出最好方案，这种想法对于维数很低的整数规划问题行得通，但是随着设计变量维数的增加，该方法的计算量是不可想象的，因而此种想法不可行，
另一种想法更为直接，因为整数规划问题实际上是在线性规划问题的基础上增加了整数约束，因而是否可以考虑