《整数线性规划》课件

运筹帷幄之中决胜千里之外运筹学课件整数线性规划IntegerLinearProgramming1整数规划整数规划问题与模型整数规划算法计算软件应用案例2整数规划问题实例特点模型分类3应用案例投资组合问题旅游售货员问题背包问题4投资组合问题背景实例模型5背景证券投资：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润。项目投资：财团或银行把资金投入到若干项目中以获得中长期的收益最大。6案例某财团有万元的资金，经出其考察选中个投资项目，每个项目只能投资一个。其中第个项目需投资金额为万元，预计5年后获利（）万元，问应如何选择项目使得5年后总收益最大？7模型变量—每个项目是否投资约束—总金额不超过限制目标—总收益最大89旅游售货员问题背景案例模型10背景旅游线路安排预定景点走且只走一次路上时间最短配送线路—货郎担问题送货地到达一次总路程最短11案例有一旅行团从出发要遍游城市，已知从到的旅费为，问应如何安排行程使总费用最小？12模型变量—是否从i第个城市到第j个城市约束每个城市只能到达一次、离开一次13避免出现断裂每个点给个位势除了初始点外要求前点比后点大14目标—总费用最小1516背包问题背景案例模型17背景邮递包裹把形状可变的包裹用尽量少的车辆运走旅行背包容量一定的背包里装尽可能的多的物品18实例某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。

19物品12345678910体积200350500430320120700420250100价格154510070507520090203020问题分析变量—对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中21约束包裹容量限制必带物品限制选带物品限制22目标函数—未带物品购买费用最小23模型24特征—变量整数性要求来源

问题本身的要求引入的逻辑变量的需要性质—可行域是离散集合2526线性整数规划模型一般整数规划模型0-1整数规划模型混合整数规划模型27一般整数规划模型280-1整数规划模型29混合整数规划模型30算法与线性规划的关系分支定界算法割平面算法近似算法31与线性规划的关系放松的线性规划可行解是放松问题的可行解最优值大于等于放松问题的最优值整数规划323334注释最优解不一定在顶点上达到最优解不一定是放松问题最优解的邻近整数解整数可行解远多余于顶点，枚举法不可取35分支定界算法算法思想算法步骤算例注释36算法思想隐枚举法求解放松问题最优值比界坏最优解为整数最优值比界好最优解为非整数最优值比界好分支边界分支舍弃37分支的方法383940定界当前得到的最好整数解的目标函数值分支后计算放松的线性规划的最优解整数解且目标值小于原有最好解的值则替代原有最好解整数解且目标值大于原有最好解的值则删除该分支其中无最优解非整数解且目标值小于原有最好解的值则继续分支非整数解且目标值大于等于原有最好解的值则删除该分支其中无最优解41选一分支写出并求解放松问题，同时从分支集中删除该分支判定是否为整数解初始分支为可行解集，初始界为无穷大判定是否分支集空是停止当前最好解为最优解是否42判定最优值是否小于当前界判定最优值是否小于当前界是否按非整数变量分支并加入分支集否是以最优解替代当前最好解最优值替代当前界43算例44454647注释求解混合整数规划问题，只对整数变量分支，对非整数变量不分支。48对0-1整数规划分支时49分枝问题解可能出现的情况情况2,4,5

找到最优解情况3

在缩减的域上继续分枝定界法情况6

问题1的整数解作为界被保留，用于以后与问题2的后续分枝所得到的解进行比较，结论如情况4或550分枝定界法举例

例4解：松弛问题的最优解为x1=2.5,x2=2,OBJ=23

由x1=2.5得到两个分枝如下：51表4.2.3分枝问题的松弛解问题II的解即原整数问题的最优解可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程当存在很多变量有整数约束时，分枝即广又深，在最坏情况下相当于组合所有可能的整数解一般整数规划问题属于一类未解决的难题，NP-complete，只有少数特殊问题有好的算法，如任务分配问题、匹配问题52算法思想算法步骤算例割平面算法53算法思想由放松问题的可行域向整数规划的可行域逼近方法—利用超平面切除要求整数解保留放松问题最优值增加54割平面生成方法条件--保留整数解删除最优解55整数可行解最优基可行解565758596061正则解62算法步骤求放松问题的最优基可行解判断是否为整数解是停止得到最优解否在单纯性表中加入一列利用对偶单纯性算法求最优解63算例(1,1.5)64656667686970计算软件整数变量定义

LinDo

一般整数变量:GIN<Variable>0-1整数变量:INT<Variable>

LinGo

一般整数变量:@GIN(variable_name);0-1整数变量：@BIN(variable_name);算例71算例

max3x1+5x2+4x3subjectto2x1+3x2<=15002x2+4x3<=8003x1+2x2+5x3<=2000endginx1ginx3724.6任务分配问题例4.6.1有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如表4.6.1，问如何分配任务使完成四项任务的总工时耗费最少？73任务分配问题的数学模型模型中：xij

为第i个工人分配去做第j

项任务；

aij

为第i

个工人为完成第j

项任务时的工时消耗；

{aij}m

m

称为效率矩阵运输问题是任务分配问题的松弛问题任务分配问题不但是整数规划，而且是0

1规划任务分配问题有2m个约束条件，但有且只有m个非零解，是自然高度退化的任务分配是两部图的匹配问题，有著名的匈牙利算法下面介绍一种适合手算的算法(出自清华教科书)74

4.6.1清华算法定理1

如果从效率矩阵{aij}m

m中每行元素分别减去一个常数ui，从每列元素分别减去一个常数vj

，所得新的效率矩阵{bij}m

m的任务分配问题的最优解等价于原问题的最优解。证明：略定理2

若方阵中一部分元素为零，一部分元素非零，则覆盖方阵内所有零元素的最少直线数等于位于不同行、不同列的零元素的最多个数。证明：略清华算法的基本思路：根据定理1

变换效率矩阵，使矩阵中有足够多的零。若矩阵中存在m

个不同行不同列的零，就找到了最优解若覆盖变换后的效率矩阵零元素的直线少于m条，就尚未找到最优解，设法进一步变换矩阵，增加新的零75清华算法的步骤：例4.6.1第一步：变换效率矩阵，使每行每列至少有一个零行变换：找出每行最小元素，从该行各元素中减去之列变换：找出每列最小元素，从该列各元素中减去之第二步：检查覆盖所有零元素的直线是否为m条划线规则1、逐行检查，若该行只有一个未标记的零，对其加()标记，将()标记元素同行同列上其它的零打上*标记。若该行有二个以上未标记的零，暂不标记，转下一行检查，直到所有行检查完；76清华算法的步骤：例4.6.12、逐列检查，若该列只有一个未标记的零，对其加()标记，将()标记元素同行同列上其它的零打上*标记。若该列有二个以上未标记的零，暂不标记，转下一列检查，直到所有列检查完；3、重复1、2后，可能出现三种情况：a.

每行都有一个(0)，显然已找到最优解，令对应(0)位置的xij=1；b.

仍有零元素未标记，此时，一定存在某些行和列同时有多个零，称为僵局状态，因为无法采用1、2

中的方法继续标记。4、打破僵局。令未标记零对应的同行同列上其它未标记零的个数为该零的指数，选指数最小的先标记()；采用这种方法直至所有零都被标记，或出现情况a，或情况c

。77清华算法的步骤：例4.6.1c.

所有零都已标记，但标有()的零的个数少于m；

开始划线过程：

对没有标记()的行打

对打

行上所有其它零元素对应的列打

再对打

列上有()标记的零元素对应的行打

重复

，直至无法继续

对没有打

的行划横线，对所有打

的列划垂线

划线后会出现两种情况：(1)

标记()的零少于m个，但划有m条直线，说明矩阵中已存在m个不同行不同列的零，但打破僵局时选择不合理，没能找到。回到b

重新标记；(2)

少于m条直线，到第三步；78清华算法的步骤：例4.6.1第三步：进一步变换；

在未划线的元素中找最小者，设为

对未被直线覆盖的各元素减去

对两条直线交叉点覆盖的元素加上

只有一条直线覆盖的元素保持不变以上步骤实际上仍是利用定理1第四步：抹除所有标记，回到第二步，重新标记；79清华算法的步骤：例4.6.1答：最优分配方案为x13=x21=x34=x42=1，其余为0，即甲

C，乙

A，丙

D，丁

B，OBJ=2080

4.6.2关于清华算法的适用条件要求所有aij

0若某些aij

<0，则利用定理1进行变换，使所有bij

0目标函数为min型对于max型目标函数，将效率矩阵中所有aij

反号，则等效于求min型问题；再利用定理1进行变换，使所有bij

0，则可采用清华算法打破僵局时选择不当的结果：

结果仅出现3个标记()，但却划出4条线，

说明什么？！81线性规划有关的英文词汇Operational/operationsresearch运筹学Linearprogramming线性