运筹基础课程 6

1Lecture6

IntegerProgrammingSchoolofBusinessAdministrationHunanUniversityLecturer:Dr.E-mail:

2LectureOutlineIntegerProgrammingProblem&itsCharacteristicsSolutionofIntegerProgrammingZero-OneIntegerProgrammingAssignmentProblem31.ThepresentationofIPProblemInmanypracticalproblems,thedecisionvariablesactuallymakesenseonlyiftheyhaveintegervalues.变量是人数、机器设备台数或产品件数等对某一个项目要不要投资的决策问题，可选用一个逻辑变量x,当x=1表示投资,x=0表示不投资人员的合理安排问题，当变量xij=1表示安排第i人去做j工作，xij=0表示不安排第i人去做j工作4MathematicalModelofIP整数规划(IP)数学模型的一般形式:max(min)z=ΣcjxjΣaijxj

bi(i=1,2,…,m,j=1,2,…,n)

xj

0且部分或全部是整数j=1ns.t.Example15某工厂生产甲、乙两种产品，已知生产这两种产品需要消耗材料A和B，有关数据如下表所示。问这两种产品应各自生产多少才能使工厂利润最大？ProductsMaterialsProduct1Product2RHSA(kg)5424B(kg)2513Profit(¥/Product)20001000ModelofExample16Supposex1,x2arethenumberofproduct1and2respectively.7ThreeTypesofIPProblemsIPPureIP

alldecisionvariablesarerequiredtohave integervalues.Mixed-IP

some,butnotall,ofthedecisionvariablesarerequiredtohaveintegervalues.Zero-oneIP allthedecisionvariablesmusthaveintegersolutionvaluesof0or1.82.SolutionofIP设想1：

既然只取整数，通过枚举法是否可行呢？对60个变量只取0/1的情形，设想计算机每秒能比较1,000,000个方式，比较完260种方式，大约需要360世纪！设想2：

先按一般线性规划问题求解，然后把求得到的最优解取整，这可行吗？9OneExamplemaxz=2000x1+1000x25x1+4x2

242x1+5x2

13x1,x2

0变量x1,x2表示两种货物的箱数

按一般的线性规划求解，其最优解为(4.8,0)64.82.66.5Z＝9600Z＝9000Z＝8000x1x2(5,0)?s.t.10可行域：OABD内整数点放弃整数要求后，最优解B(9.2,2.4)Z0=58.8，而原整数规划最优解I(2,4)Z0=58，实际上B附近四个整点(9,2)(10,2)(9,3)(10,3)都不是原规划最优解。O1234567891054321xx11xx22I(2,4)B(9.2,2.4)ADAnotherExample求下列问题：maxZ=3x1+13x22x1+9x2

4011x1-8x2

82x1,x2

0,且取整数值s.t.O1234567891054321x1x2I(2,4)B(9.2,2.4)AD设想3：求出可行域的“整点凸包”（包含所有整点的最小多边形OEFGHIJ），则可在此凸包上求线性规划的解，即为原问题的解。EFGHIJ求“整点凸包”十分困难12IP经典求解法——分枝定界法(BBM)对整数规划（IP），若不考虑整数要求，对应的问题（LP）称为（IP）的松驰问题

松弛问题的可行域包含原问题的可行域若两者都有最优解，则松弛问题的最优目标值优于原问题的最优目标值若松弛问题的最优解为整数解，则最优解就是原问题的最优解松弛问题13BBM求解步骤以求max为例，记原问题(IP)为A，松弛问题(LP)为B求松弛问题B的最优解B的最优解即为A的最优解计算结束原问题A也无可行解计算结束若B有最优解，且符合整数条件若B无可行解若B有最优解，但不符合整数条件一般取xj=0(j=1,2,…,n)试探用试探法找出A的一个可行解其目标函数值作为下界松弛问题B的最优目标值作为上界分枝：在B的最优解中任选一非整数变量xj构造两个约束条件xj≤[bj],xj≥[bj]+1分别加入B，得到两后继问题B1,B2定界：求解后继问题，以目标函数最大者作为新的上界，从满足整数条件的各分枝中找出目标函数值最大者作新的下界

?结束Yes剪枝：各分枝若其无可行解或其目标函数值小于下界，则剪去该枝No对剩余的各分枝15解：不考虑整数条件，求解对应松弛问题的最优解得x1=4.81,x2=1.82,最优值z＝355.88于是，LP0:maxz=40x1+90x2s.t.9x1+7x2≤567x1+20x2≤70x1,x2≥0分枝定界法举例maxz=40x1+90x2s.t.9x1+7x2≤567x1+20x2≤70x1,x2≥0,且为整数用试探法寻找原整数规划问题一可行解，显然,x1=0,x2=0，为一可行解，对应目标值z=0,于是，任取松弛问题一非整数变量，这里取x1,将两约束条件x1≤4,x1≥5,分别加入原松弛问题，构造两个新的问题（分枝）LP1:maxz=40x1+90x2s.t.9x1+7x2≤567x1+20x2≤70x1≤4x1,x2≥0LP1':maxz=40x1+90x2s.t.9x1+7x2≤567x1+20x2≤70x1≥5x1,x2≥016求解两个分枝，结果分别为：X1=4,x2=2.1,z=349X1=5,x2=1.57,z=341分枝定界法举例maxz=40x1+90x2s.t.9x1+7x2≤567x1+20x2≤70x1,x2≥0,且为整数修改上下界，这里上界下界仍然为由于上下界不相等，继续下面步骤。。。判断是否需要剪枝，这里两个分枝都有可行解，且各分枝的最优目标值在上下界之间，因而不需要剪枝继续对剩余的各分枝进行再分枝，如此反复Z=349X2=2.1X1=4LP1Z=341X2=1.57X1=5LP1'Z=340X2=2X1=4LP2Z=327X2=3X1=1.42LP2‘Z=356X2=1.82X1=4.81LP0无可行解LP2’‘’Z=308X2=1X1=5.44LP2’‘x1≤4x1≥5x2≤2x2≤1x2≥2x2≥318整数规划OR求解Module→IntegerProgramming193.0-1IntegerProgramming

许多实际决策问题中要求回答“是/否”、“有/无”,这类问题可借助0-1整数变量，将复杂的问题变得简单。

0-1整数规划是整数规划的特殊情形，其变量xj只能取0或1

该条件可用如下约束来描述：

xj≤1，

xj≥0，

xj∈Z200-1规划的经典求解法－隐枚举法求解0-1整数规划6(1,1,1)1(1,1,0)z≥8√√√√8(1,0,1)3(1,0,0)3(0,1,1)-2(0,1,0)z≥5√√√√5(0,0,1)z≥0√√√√0(0,0,0)过滤条件约束条件abcdZ值(x1,x2,x3)依次检验过滤条件和约束条件220-1规划建模案例例1(相互排斥的计划)：某公司有5个项目被列入投资计划，各项目的投资额和期望投资收益如下表所示：项目投资额（万元）投资收益121016023002103150604130805260180该公司只有600万元资金可用于投资，由于各种原因有以下约束：(1)项目1、2、3中必须且只能投资一项(2)项目3、4中必须且只能投资一项(3)项目5被选中的前提是项目1必须选中设xi=1项目i被选中0项目i未被选中i=1,2,3,4,5210x1+300x2+150x3+130x4+260x5≤600（1）确定决策变量（2）确定目标函数（3）确定约束条件maxz=160x1+210x2+60x3+80x4+180x5公司只有600万元资金可用于投资项目1、2、3中必须且只能投资一项x1+x2+x3=1项目3、4中必须且只能投资一项x3+x4=1项目5被选中的前提是项目1必须选中x5≤x1maxz=160x1+210x2+60x3+80x4+180x5s.t.210x1+300x2+150x3+130x4+260x5≤600x1+x2+x3=1x3+x4=1x5≤x1

xi=0或1,i=1,2,3,4,5求解(OR)数学模型25ABC利润(元/件)C1C2Ⅰ0.30.20.30.225Ⅱ0.70.10.50.440每周工时250100150120

例2(相互排斥的约束):某产品有Ⅰ和Ⅱ两种型号，需要经过ABC三道工序，单位工时、利润、各工序每周工时限制如表所示。问：工厂如何安排生产，才能使总利润最大(C工序有两种工作方式C1和C2供选择，产品为整数）0-1规划案例（1）确定决策变量

设Ⅰ和Ⅱ两种型号的产量分别为x1和x2（2）确定目标函数

maxz=25x1+40x2（3）确定约束条件A、B两道工序每周工时约束

0.3x1+0.7x2≤2500.2x1+0.1x2≤100工序C有两种加工方式，其每周工时约束

0.3x1+0.5x2≤1500.2x1+0.4x2≤120这两个约束是互斥的，只能选一个！为了将两个约束条件统一到一个问题中，引入0-1变量：于是，前述互斥约束条件可统一为：

0.3x1+0.5x2≤150＋My10.2x1+0.4x2≤120+My2

y1+y2=1其中M是充分大的正数数学模型maxz=25x1+40x20.3x1+0.7x2≤2500.2x1+0.1x2≤1000.3x1+0.5x2≤150＋My10.2x1+0.4x2≤120+My2y1+y2=1x1,x2≥0,x1,x2∈Zy1,y2

∈{0,1}s.t.

一般的，在建立数学模型时，若需要从p个约束条件中选择q个约束，则可引入P个0－1变量再构造约束条件组，即可达到目的300-1规划案例例3(固定成本问题):

某公司须购买50,000个灯泡。三个供应单位：A公司,每个3元，至少订购量为20,000个,至多30,000个B公司,每个5元,至少10,000个C公司,每个1元，另加固定费20000元,订购量0～30,000内任选公司决定从一家或两家购买，采取怎样的订购方案可使所花费用最少？解：设xA表示从A公司购买的灯泡数

xB表示从B公司购买的灯泡数

xC表示从C公司购买的灯泡数1从A公司购买0不从A公司购买YA=1从B公司购买0不从B公司购买YB=1从C公司购买0不从C公司购买YC=数学模型Minz=3xA+5xB+xC+20000YCxA+xB+xC≥50000xA≥20000YAxA≤30000YA

xB≥10000YBxB≤MYBxC≤30000YCYA+YB+YC≤2xA,xB,xC≥0,xA,xB,xC

∈Z

YA,YB,YC

∈{0,1}求解(OR)s.t.0-1背包问题33有一个背包容积为v，现有n种物品可装入，物品i的重量为wi，体积为vi(i=1,2,…,n)。试问应该如何装包，使得在不超过容积的前提下，总重量最大。xi=1物品i装入背包0物品i不装入背包344.什么是指派问题？

设n个人被分配去做n件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第i个人去做第j件工作的的效率（时间或费用）为Cij(i=1.2…n;j=1.2…n)并假设Cij≥0。问应如何分配才能使总效率（收益）最高，或总时间最少？35指派问题的数学模型1个人做1件事1件事1个人做设决策变量xij=1分配第i个人去做第j件工作0相反(i,j=1,2,…,n)36求解指派问题的方法——匈牙利法

指派问题是0-1规划的特例，也是运输问题的特例，当然可用整数规划，0-1规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法——匈牙利法(HungarianMethodorHungarianAlgorithm)

37匈牙利解法原理——性质1设一个指派模型的效益矩阵为[Cij].若[Cij]的第i行元素均减去一个常数ui(称为该行的行位势)，第j列元素均减去一个常数vj(称为该列的列位势)，得到一个新的效益矩阵[C’ij=Cij-ui-vj]，则以[C’ij]为效益矩阵的指派问题的最优解与原[Cij]的最优解相同。（同解变换）示例(-4)39匈牙利解法原理——性质2若矩阵C的元素可分为“0”与非“0”两部分，则覆盖0元素的最少直线数恰好等于位于不同行不同列的0元素(独立0元素)的最大个数。i1i2irj1j2jr40匈牙利解法步骤

第一步：变换指派问题的系数矩阵（cij）为(bij)，使在(bij)的各行各列中都出现0元素，即

(1)从（cij）的每行元素都减去该行的最小元素；

(2)再从所得新系数矩阵的每列元素中减去该列的最小元素。

第二步：进行试指派，以寻求最优解。在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤为：

(1)给只有一个0元素的行中的0元素加圈，记作◎；然后划去◎所在列的其它0元素，记作Ø；表示该列所代表的任务已指派完，不必再考虑别人了。

(2)给只有一个0元素的列中的0元素加圈，记作◎；然后划去◎所在行的0元素，记作Ø，表示该人已被占用，不必再考虑其他工作了。

(3)反复进行(1)，(2)两步，直到尽可能多的0元素都被圈出和划掉为止。(4)若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，则从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。

（5）若◎元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到。若m<n,则转入下一步。

第三步：作最少的直线覆盖所有0元素。

(1)对没有◎的行打√号；

(2)对已打√号的行中所有含Ø元素的列打√号；

(3)再对打有√号的列中含◎元素的行打√号；(4)重复(2)，(3)直到得不出新的打√号的行、列为止；

(5)对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有0元素的最少直线数l。l应等于m，若不相等，说明试指派过程有误，回到第二步(4)，另行试指派；若l＝m<n，须再变换当前的系数矩阵，以找到n个独立的0元素，为此转第四步。第四步：变换矩阵(bij)以增加0元素。在没有被直线覆盖的所有元素中找出最小元素，然后打√各行都减去这最小元素；打√各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。

例一：

任务人员ABCD甲215134乙1041415丙9141613丁78119249742◎Ø◎ØØ◎◎分配方案

有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？

任务人员ABCD甲67112乙4598丙31104丁5982例二：求解过程如下：第一步，变换系数矩阵：－5第二步，试指派：◎◎◎ØØ

找到3个独立零元素但m=3<n=

4

第三步，作最少的直线覆盖所有0元素：

◎◎◎ØØ√√√独立零元素的个数m等于最少直线数l，即l＝m=3<n=4；

第四步，变换矩阵(bij)以增加0元素：没有被直线覆盖的所有元素中的最小元素为1，然后打√各行都减去1；打√各列都加上1，得如下矩阵，并转第二步进行试指派：000000得到4个独立零元素，所以最优解矩