第二章--整数规划.doc

第二章 整数规划
§1 概论
1、1 定义
规划中得变量(部分或全部)限制为整数时,称为整数规划。若在线性规划模型中,变量限制为整数,则称为整数线性规划。目前所流行得求解整数规划得方法,往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。
1.2 整数规划得分类
如不加特殊说明,一般指整数线性规划。对于整数线性规划模型大致可分为两类:
1o 变量全限制为整数时,称纯(完全)整数规划。
2o 变量部分限制为整数得,称混合整数规划。
1.2 整数规划特点
(i) 原线性规划有最优解,当自变量限制为整数后,其整数规划解出现下述情况:
①原线性规划最优解全就是整数,则整数规划最优解与线性规划最优解一致。
②整数规划无可行解。
例1 原线性规划为

其最优实数解为:。
③有可行解(当然就存在最优解),但最优解值变差。
例2 原线性规划为

其最优实数解为:。
若限制整数得:。
(ii) 整数规划最优解不能按照实数最优解简单取整而获得。
1、3 求解方法分类:
(i)分枝定界法—可求纯或混合整数线性规划。
(ii)割平面法—可求纯或混合整数线性规划。
(iii)隐枚举法—求解“0-1”整数规划:
①过滤隐枚举法;
②分枝隐枚举法。
(iv)匈牙利法—解决指派问题(“0-1”规划特殊情形)。
(v)蒙特卡洛法—求解各种类型规划。
下面将简要介绍常用得几种求解整数规划得方法。
§2 分枝定界法
对有约束条件得最优化问题(其可行解为有限数)得所有可行解空间恰当地进行系统搜索,这就就是分枝与定界内容。通常,把全部可行解空间反复地分割为越来越小得子集,称为分枝;并且对每个子集内得解集计算一个目标下界(对于最小值问题),这称为定界。在每次分枝后,凡就是界限超出已知可行解集目标值得那些子集不再进一步分枝,这样,许多子集可不予考虑,这称剪枝。这就就是分枝定界法得主要思路。
分枝定界法可用于解纯整数或混合得整数规划问题。在本世纪六十年代初由Land Doig与Dakin等人提出得。由于这方法灵活且便于用计算机求解,所以现在它已就是解整数规划得重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。
设有最大化得整数规划问题,与它相应得线性规划为问题,从解问题开始,若其最优解不符合得整数条件,那么得最优目标函数必就是得最优目标函数得上界,记作;而得任意可行解得目标函数值将就是得一个下界。分枝定界法就就是将得可行域分成子区域得方法。逐步减小与增大,最终求到。现用下例来说明:
例3 求解下述整数规划

解 (i)先不考虑整数限制,即解相应得线性规划,得最优解为:

可见它不符合整数条件。这时就是问题得最优目标函数值得上界,记作。而显然就是问题得一个整数可行解,这时,就是得一个下界,记作,即。
(ii)因为当前均为非整数,故不满足整数要求,任选一个进行分枝。设选进行分枝,把可行集分成2个子集:
,
因为4与5之间无整数,故这两个子集得整数解必与原可行集合整数解一致。这一步称为分枝。这两个子集得规划及求解如下:
问题:

最优解为:。
问题:

最优解为:。
再定界:。
(iii)对问题再进行分枝得问题与,它们得最优解为

再定界:,并将剪枝。
(iv)对问题再进行分枝得问题与,它们得最优解为

无可行解。
将剪枝。
于就是可以断定原问题得最优解为:

从以上解题过程可得用分枝定界法求解整数规划(最大化)问题得步骤为:
开始,将要求解得整数规划问题称为问题,将与它相应得线性规划问题称为问题。
(i)解问题可能得到以下情况之一:
(a)没有可行解,这时也没有可行解,则停止.
(b)有最优解,并符合问题得整数条件,得最优解即为得最优解,则停止。
(c)有最优解,但不符合问题得整数条件,记它得目标函数值为。
(ii)用观察法找问题得一个整数可行解,一般可取,试探,求得其目标函数值,并记作。以表示问题得最优目标函数值;这时有

进行迭代。
第一步:分枝,在得最优解中任选一个不符合整数条件得变量,其值为,以表示小于得最大整数。构造两个约束条件
与
将这两个约束条件,分别加入问题,求两个后继规划问题与。不考虑整数条件求解这两个后继问题。
定界,以每个后继问题为一分枝标明求解得结果,与其它问题得解得结果中,找出最优目标函数值最大者作为新得上界。从已符合整数条件得各分支中,找出目标函数值为最大者作为新得下界,若无作用。
第二步:比较与剪枝,各分枝得最优目标函数中若有小于者,则剪掉这枝,即以后不再考虑了。若大于,且不符合整数条件,则重复第一步骤。一直到最后得到为止。得最优整数解。
§3 型整数规划
型整数规划就是整数规划中得特殊情形,它得变量仅取值0或1。这时称为变量,或称二进制变量。仅取值0或1这个条件可由下述约束条件:
,整数
所代替,就是与一般整数规划得约束条件形式一致得。在实际问题中,如果引入 变量,就可以把有各种情况需要分别讨论得线性规划问题统一在一个问题中讨论了。我们先介绍引入变量得实际问题,再研究解法。
3、1 引入变量得实际问题
3、1、1 投资场所得选定——相互排斥得计划
例4 某公司拟在市东、西、南三区建立门市部。拟议中有7个位置(点)可供选择。规定
在东区。由三个点中至多选两个;
在西区。由两个点中至少选一个;
在南区,由两个点中至少选一个。
如选用点,设备投资估计为元,每年可获利润估计为元,但投资总额不能超过元。问应选择哪几个点可使年利润为最大？
解题时先引入变量
令
、
于就是问题可列写成:

3、1、2 相互排斥得约束条件
有两个相互排斥得约束条件
或 。
为了统一在一个问题中,引入变量,则上述约束条件可改写为:

其中就是充分大得数。
约束条件
或
可改写为

如果有个互相排斥得约束条件:

为了保证这个约束条件只有一个起作用,我们引入个变量与一个充分大得常数,而下面这一组个约束条件
(1)
(2)
就合于上述得要求。这就是因为,由于(2),个中只有一个能取0值,设,代入(1),就只有得约束条件起作用,而别得式子都就是多余得。
3、1、3 关于固定费用得问题(Fixed Cost Problem)
在讨论线性规划时,有些问题就是要求使成本为最小。那时总设固定成本为常数,并在线性规划得模型中不必明显列出。但有些固定费用(固定成本)得问题不能用一般线性规划来描述,但可改变为混合整数规划来解决,见下例。
例5 某工厂为了生产某种产品,有几种不同得生产方式可供选择,如选定得生产方式投资高(选购自动化程度高得设备),由于产量大,因而分配到每件产品得变动成本就降低;反之,如选定得生产方式投资低,将来分配到每件产品得变动成本可能增加。所以必须全面考虑。今设有三种方式可供选择,令
表示采用第种方式时得产量;
表示采用第种方式时每件产品得变动成本;
表示采用第种方式时得固定成本。
为了说明成本得特点,暂不考虑其它约束条件。采用各种生产方式得总成本分别为
、
在构成目标函数时,为了统一在一个问题中讨论,现引入变量,令
(3)
于就是目标函数

(3)式这个规定可表为下述3个线性约束条件:
(4)
其中就是个充分大得常数。(4)式说明,当时必须为1;当时只有为0时才有意义,所以(4)式完全可以代替(3)式。
3、2 型整数规划解法之一(过滤隐枚举法)
解型整数规划最容易想到得方法,与一般整数规划得情形一样,就就是穷举法,即检查变量取值为0或1得每一种组合,比较目标函数值以求得最优解,这就需要检查变量取值得个组合。对于变量个数较大(例如),这几乎就是不可能得。因此常设计一些方法,只检查变量取值得组合得一部分,就能求到问题得最优解。这样得方法称为隐枚举法(Implicit Enumeration),分枝定界法也就是一种隐枚举法。当然,对有些问题隐枚举法并不适用,所以有时穷举法还就是必要得。
下面举例说明一种解型整数规划得隐枚举法。
例6

求解思路及改进措施:
(i) 先试探性求一个可行解,易瞧出满足约束条件,故为一个可行解,且。
(ii) 因为就是求极大值问题,故求最优解时,凡就是目标值得解不必检验就是否满足约束条件即可删除,因它肯定不就是最优解,于就是应增加一个约束条件(目标值下界):
(iii) 改进过滤条件。
(iv) 由于对每个组合首先计算目标值以验证过滤条件,故应优先计算目标值大得组合,这样可提前抬高过滤门槛,以减少计算量。
§4 蒙特卡洛法(随机取样法)
前面介绍得常用得整数规划求解方法,主要就是针对线性整数规划而言,而对于非线性整数规划目前尚未有一种成熟而准确得求解方法,因为非线性规划本身得通用有效解法尚未找到,更何况就是非线性整数规划。
然而,尽管整数规划由于限制变量为整数而增加了难度;然而又由于整数解就是有限个,于就是为枚举法提供了方便。当然,当自变量维数很大与取值范围很宽情况下,企图用显枚举法(即穷举法)计算出最优值就是不现实得,但就是应用概率理论可以证明,在一定得计算量得情况下,完全可以得出一个满意解。
例7 已知非线性整数规划为:

对该题,目前尚无有效方法求出准确解。如果用显枚举法试探,共需计算个点,其计算量非常之大。然而应用蒙特卡洛去随机计算个点,便可找到满意解,那么这种方法得可信度究竟怎样呢？
下面就分析随机取样采集个点计算时,应用概率理论来估计一下可信度。
不失一般性,假定一个整数规划得最优点不就是孤立得奇点。
假设目标函数落在高值区得概率分别为0、01,0、00001,则当计算个点后,有任一个点能落在高值区得概率分别为
,
。
解 (i)首先编写M文件mente、m定义目标函数f 与约束向量函数g,程序如下:
function [f,g]=mengte(x);
f=x(1)^2+x(2)^2+3*x(3)^2+4*x(4)^2+2*x(5)-8*x(1)-2*x(2)-3*x(3)、、、
-x(4)-2*x(5);
g(1)=sum(x)-400;
g(2)=x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800;
g(3)=2*x(1)+x(2)+6*x(3)-200;
g(4)=x(3)+x(4)+5*x(5)-200;
(ii)编写如下程序求问题得解:
rand('state',sum(clock));
p0=0;
tic
for i=1:10^5
x=99*rand(5,1);
x1=floor(x);x2=ceil(x);
[f,g]=mengte(x1);
if sum(g<=0)==4
if p0<=f
x0=x1;p0=f;
end
end
[f,g]=mengte(x2);
if sum(g<=0)==4
if p0<=f
x0=x2;p0=f;
end
end
end
x0,p0
toc
§5 整数规划得计算机解法
整数规划问题得求解可以使用Lingo等专用软件。对于一般得整数规划规划问题,无法直接利用Matlab得函数,必须利用Matlab编程实现分枝定界解法与割平面解法。但对于指派问题等特殊得整数规划问题或约束矩阵就是幺模矩阵时,有时可以直接利用Matlab得函数linprog。
例8 求解下列指派问题,已知指派矩阵为

解:编写Matlab程序如下:
c=[3 8 2 10 3;8 7 2 9 7;6 4 2 7 5
8 4 2 3 5;9 10 6 9 10];
c=c(:);
a=zeros(10,25);
for i=1:5
a(i,(i-1)*5+1:5*i)=1;
a(5+i,i:5:25)=1;
end
b=ones(10,1);
[x,y]=linprog(c,[],[],a,b,zeros(25,1),ones(25,1))
求得最优指派方案为,最优值为21。
习 题 二
1. 用分枝定界法解:

2、 试将下述非线性得规划问题转换成线性得规划问题

3、 某钻井队要从以下10个可供选择得井位中确定5个钻井探油,使总得钻探费用为最小。若10个井位得代号为,相应得钻探费用为,并且井位选择上要满足下列限制条件:
（1） 或选择与,或选择钻探;
（2） 选择了或就不能选,或反过来也一样;
（3） 在中最多只能选两个;试建立这个问题得整数规划模型。