下载文档原格式
整数规划的数学模型及解的特点整数规划IP (integer programming)：在许多规划问题中，如果要求一部分或全部决策变量必须取整数。
例如，所求的解是机器的台数、人数、车辆船只数等，这样的规划问题称为整数规划，简记IP 。
松弛问题(slack problem)：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。
若松弛问题是一个线性规化问题，则该整数规划为整数线性规划(integer linear programming)。
一、整数线性规划数学模型的一般形式∑==nj jj x c Z 1min)max(或中部分或全部取整数n j nj i jij x x x mj ni x b xa ts ,...,,...2,1,...,2,10),(.211==≥=≥≤∑=整数线性规划问题可以分为以下几种类型1、纯整数线性规划(pure integer linear programming)：指全部决策变量都必须取整数值的整数线性规划。
有时，也称为全整数规划。
2、混合整数线性规划(mixed integer liner programming)：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。
3、0—1型整数线性规划(zero —one integer liner programming)：指决策变量只能取值0或1的整数线性规划。
1 解整数规划问题0—1型整数规划0—1型整数规划是整数规划中的特殊情形，它的变量仅可取值0或1，这时的⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤+≥+≤-+=且为整数0,5210453233max 2121212121x x x x x x x x x x z变量xi 称为0—1变量，或称为二进制变量。
0—1型整数规划中0—1变量作为逻辑变量(logical variable)，常被用来表示系统是否处于某一特定状态，或者决策时是否取某个方案。
第3章 整数规划3.1 整数规划的数学模型一个规划问题中要求部分或全部决策变量是整数，则这个规划称为整数规划。
当要求全部变量取整数值的，称为纯整数规划(Pure Integer Programming ，IP )，要求一部分变量取整数值的，称为混合整数规划(Mixed Integer Programming ，MIP )，决策变量全部取0或1的规划称为0－1整数规划(Binary Integer Programming ，BIP )，如果模型是线性的，称为整数线性规划（Integer Linear Programming, ILP ）。
本章只讨论整数线性规划。
求解整数规划问题时，如果先不能考虑对变量的整数约束，作为一般线性规划问题来求解，当解为非整数时再用舍入凑整方法寻求最优解，这样得到的解有可能不是整数规划的可行解或是可行解而不是最优解。
【例3.1】某人有一背包可以装10公斤重、0.025m 3的物品。
他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如表3－1所示。
问两种物品各装多少件，所装物品的总价值最大。
表3－1【解】设甲、乙两种物品各装x 1、x 2件，则数学模型为⎪⎩⎪⎨⎧≥≤+≤++=且均取整数,0,255.22108.02.134max 21212121x x x x x x x x Z (3.1)如果不考虑x 1、x 2取整数的约束（称为式（3.1）的松弛问题），线性规划的可行域如图3-1中的阴影部分所示。
图3-1用图解法求得点B 为最优解：X ＝(3.57，7.14)，Z ＝35.7。
由于x 1，x 2必须取整数值，整数规划问题的可行解集只是图中可行域内的那些整数点。
用凑整法求解时需要比较四种组合，但（4，7）、（4，8）（3，8）都不是可行解，（3，7）虽属可行解，代入目标函数得Z =33,并非最优。
实际上问题的最优解是（5，5），Z =35。
即两种物品各装5件，总价值35元。
第三章 整数规划模型一． 提出问题：工厂选址某企业欲建工厂，可选厂址有A 1、A 2、A 3、A 4四处，每个地址至多可建一个工厂，在各地址建立工厂的生产能力、在各地址经营工厂单位时间的固定成本、产品运往各需求点的单位运费如下表：问应如何选择厂址和安排运输计划，才能得到经济上花费最少的方案 二． 分析问题 1． A 1、A 2、A 3、A 4各处都有可能建厂，用变量y[i]来表示是否建厂y[i]=⎩⎨⎧地址不建厂在地址建厂在i i 01i=1,2,3,4;2． 设从i 地址运到j 需求点的运输量可设为x[i][j]为整数 3．运到各点的量应不小于需求(x[1][j]+x[2][j]+x[3][j]+x[4][j]>=b[j])； 4．各厂的生产总量不超过生产能力（x[i][1]+x[i][2]+x[i][3]+x[i][4]<=d[i]*y[i] i=1,2,3,4）；5． 运到各需求点的量如何计算b1[j]=x[1][j]+x[2][j]+x[3][j]+x[4][j]j=1,2,3,4; 6． 各厂的生产总量a1[i]= x[i][1]+x[i][2]+x[i][3]+x[i][4]; 7． 目标函数：总费用z=建厂费用+ 运输费用8．运输费用=单位运输费用*运输量（从i 地址运到j 需求点单位运输费用c[i][j]已知，从i 地址运到j 需求点的运输量可设为x[i][j]） 三． 模型建立根据分析建立整数规划模型： 设1(1,2,,4)0i i y i ⎧==⎨⎩ 在处建厂否则，ij x i j 表示从点运到点的货物数量(i,j=1,2,,4)，建立如下整数规划模型：4441114141..(1,2,,4)(1,2,,4)0,0ii ijiji i j iji i j ijj i ij i m in z ay cx s t xd y i xb j x y =====⎧=+⎪⎪⎪≤=⎪⎨⎪⎪≥=⎪⎪≥=⎩∑∑∑∑∑ 或1其中(,1,2,,4)ijc i j i j = 表示从点到点的单位运费，i i a A 为点处建厂经营的单位固定成本(i=1,2,,4)， j b j 表示需求点B 处的需求量(j=1,2,,4)，(1,2,,4)i i d A i = 表示处的生产能力。
整数规划模型整数规划模型是一种数学模型，用于解决优化问题。
在整数规划中，决策变量必须是整数。
这种模型广泛应用于工程、科学、运筹学和管理等领域。
整数规划模型的一般形式如下：\[\text{maximize} \quad c^Tx\]\[\text{subject to} \quad Ax \leq b\]\[x_j \text{整数} , j = 1,2,...,n\]其中，c是一个n维向量，表示目标函数的系数；x是n维向量，表示决策变量；A是m×n维矩阵，表示约束条件的系数矩阵；b是一个m维向量，表示约束条件的上界。
整数规划模型的目标是找到一个满足约束条件的决策变量向量x，使得目标函数值最大或最小。
由于决策变量必须是整数，所以整数规划模型要比普通的线性规划模型更复杂。
整数规划模型可以应用于许多实际问题。
例如，一个公司要决定生产哪种产品以最大化利润，但每种产品有一定的生产限制，需要整数规划模型来确定生产量；一个配送中心要决定如何分配物流资源以最小化成本，但每个分配决策都必须是整数，需要整数规划模型来求解。
求解整数规划模型可以使用多种算法。
例如，分支定界算法通过将问题分解为一个个子问题，并通过剪枝策略来减少搜索空间，最终找到最优解；约简与延迟约束算法通过线性松弛将整数规划转化为一个松弛线性规划问题，并通过迭代加入约束条件来逼近整数解。
整数规划模型的求解过程需要注意一些问题。
首先，由于整数规划是一个NP难问题，没有通用的多项式时间算法可以解决所有情况。
其次，整数规划模型可能有多个最优解，求解算法可能只能找到其中一个最优解。
最后，整数规划模型的求解过程可能需要大量的计算资源和时间。
总之，整数规划模型是一种重要的数学模型，可以用于解决各种实际优化问题。
但由于其复杂性和求解困难，需要合理选择算法和求解策略来获得满意的结果。
