规划中的变量 (部分或全部) 限制为整数时, 称为整数规划。 若在线性规划模型中,变量限制为整数,则称为整数线性规划。
1、原线性规划有最优解, 当自变量限制为整数后, 其整数规划解出现下述情况:
2、整数规划最优解不能按照实数最优解简单取整而获得
对有约束条件的最优化问题 (其可行解为有限数) 的所有可行解空间恰当地进行系统搜索,这就是分枝与定界内容。把全部可行解空间反复地分割为越来越小的子集,称为分枝。对每个子集内的解集计算一个目标下界(对于最小值问题) ,这称为定界。
在每次分枝后, 凡是界限超出已知可行解集目标值的那些子集不再进一步分枝,这样,许多子集可不予考虑,这称剪枝。这就是分枝定界法的主要思路。
例 1
求
解:
1、先不考虑整数限制,直接按照线性规划求解,将此线性规划问题视为 B,得
再取 x1 = x2 = 0,得到 z 为 0,那么,以上便可求出可行解 z 的上下界
2、任选 x1 和 x2 进行分枝,取 x1 <= 4,x1 >= 5
可得
对 z 再定界,有
3、对 x2 进行分枝,取 x2 <= 2,x2 >= 3,有
再定界,有
4、若再对 x2 以 1 进行分支定界,无可行解,那么,可推断,最优解为
0-1 整数规划指的是变量 xj 仅能取 0 或 1,即
题目描述:某公司拟在市东、西、南三区建立门市部。拟议中有 7 个位置 Aj(j = 1, 2, 3...7)可供选择,规定
Aj 点的投资为 bj 元,每年利润为 cj 元,投资总额不能超过 B 元,问如何选择可使年利润最大?
解:
引入变量 xj,令
那么问题可写为
1、
可写为
M 为充分大的数
2、
可写为
例 2
某工厂为了生产某种产品,有三种方式可供选择:
要求最小化生产成本。
解:
第 j 种生产方式的总成本为
引入 0 - 1 变量 yj,为
于是目标函数为
对于(3)式的规定,可改写为
前者和后者分别为充分小和充分大的数
穷举法是最容易想到的一种方法,但是计算量太大,因此设计一种仅检查变量取值的组合的一部分,称为过滤隐枚举法。分枝定界法也为过滤隐枚举法的一种。
例 3
解题思路:
前面讲的是线性整数规划,接下来说明非线性整数规划的问题,当数据量很大时,采用穷举法得到最优解不符合现实,但是应用概率理论可以证明,在一定的计算量的情况下,完全可以得出一个满意解。
例 4
解:
若采用穷举法,共 1010 个点,可随机分析 106 便可达到最优。
mente.m 如下:目标函数 f ,约束向量函数 g
mainint.m 如下:
上面代码中 sum(g <= 0) == 4 的原因是题目中 4 个约束条件需全部满足。
采用 0 - 1 整数规划求解,使用到的 MATLAB 函数为 bintprog
例 5
解:
MATLAB 程序如下:
解得
bintprog 函数说明如下:参考 https://www.jianshu.com/p/9ad0f6d0a7df
x 是解向量,f 是矩阵系数
A是一个矩阵,b是一个向量
例 6
求 max=193x1+191x2+187x3+186x4+180x5+185x6;
st.
x5+x6>=1;
x3+x5>=1;
x1+x2<=1;
x2+x6<=1;
x4+x6<=1;
x1+x2+x3+x4+x5+x6=1;
解:
f=[-193;-191;-187;-186;-180;-185;];
a=[0 0 0 0 -1 -1;0 0 -1 0 -1 0;1 1 0 0 0 0;0 1 0 0 0 1;0 0 0 1 0 1];
b=[-1,-1,1,1,1]‘;
aeq=[1 1 1 1 1 1];
beq=[3];
x=bintprog(f,a,b,aeq,beq)
某公司用两种原油( A和B )混合加工成两种汽油(甲和乙) 。甲、乙两种汽油含 A 原油的最低比例分别为 50%和 60%,每吨售价分别为 4800 元和 5600 元。该公司现有原油 A和B 的库存量分别为 500 吨和 1000 吨, 还可以从市场上买到不超过 1500吨的原油 A。原油 A的市场价为:购买量不超过 500 吨时的单价为 10000 元/吨;购买量超过 500 吨单不超过 1000 吨时,超过 500 吨的部分 8000 元/吨;购买量超过 1000 吨时,超过 1000 吨的部分 6000 元/吨。该公司应如何安排原油的采购和加工。
设购买的 A 为 x 吨,那么支出 c(x) 为
设 A 用于生产甲、乙的数量分别为 x11,x12,B 用于生产甲、乙的数量分别为 x21,x22,那么利润为
限制条件为
解法一
将 x 分解为三个量 x1,x2,x3,分别表示采集 10 千元/吨、8 千元/吨、6 千元/吨的 A 的数量,那么
目标函数变为
注意,只有当 x1 = 500 时,才可以 8 千元/吨的价格购买 x2,也就是
同理,只有当 x2 = 500 时,才可以 10 千元/吨的价格购买 x3,也就是
即
解法二
引入 0 - 1 问题,z1 =1,z2 =1,z3 =1 表示以 6 千元/吨、8 千元/吨、10 千元/吨的价格采购 A,上述问题转化为
解法三
成本函数的曲线为
分别记 b1 = 0,b2 = 500,b3 = 1000,当 x 属于第一个小区时,
同理,当 x 属于第二个小区时,
当 x 属于第三个小区时
当 x 属于第 k 个小区时, zk = 1,否则 zk = 0,那么
原文:https://www.cnblogs.com/sgKurisu/p/15108506.html