《【教学课件】第3章整数线性规划.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第3章整数线性规划.ppt（61页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、整数线性规划模型特点整数线性规划模型特点决策变量：决策变量：x1,.,xn表示要寻求的方案，每一组值就是一个方案；全部（或部分）变量要求取整数约束条件：线性等式或不等式约束条件：线性等式或不等式目标函数：目标函数：Z=(x1 xn)线性式，求线性式，求Z极极大或极小大或极小第第3章章 整数线性规划整数线性规划整数线性规划的标准形式：整数线性规划的标准形式：货物货物 体积体积(米米3/箱箱)重量重量(百公斤百公斤/箱箱)利润利润(千元千元/箱箱)甲甲 5 2 20 乙乙 4 5 10 装运限制装运限制 24 13 例例1、集装箱运货、集装箱运货1、整数线性规划问题举例、整数线性规划问题举例解：设
2、解：设X1 ,X2 为甲、乙两货物各托运箱数为甲、乙两货物各托运箱数maxZ=20 maxZ=20 X1+10 X25X1+4X2 242X1+5X2 13X1,X2 0 0X1,X2为整数为整数例例2、背包问题、背包问题背包可再装入背包可再装入8单位重量，单位重量，10单位体积物品单位体积物品物品物品 名称名称 重量重量 体积体积 价值价值 1 书书 5 2 20 2 摄像机摄像机 3 1 30 3 枕头枕头 1 4 10 4 休闲食品休闲食品 2 3 18 5 衣服衣服 4 5 15 解：解：Xi为是否带第为是否带第 i 种物品种物品maxZ=20X1+30X2+10X3+18X4+15X
3、55X1+3X2+X3+2X4+4X5 82X1+X2+4X3+3X4+5X5 10Xi为为0,1 背包问题是整数线性规划的一个典型例子，许多背包问题是整数线性规划的一个典型例子，许多实际问题都可归结为该问题。实际问题都可归结为该问题。(1)、Xi为为i 物品携带数量物品携带数量 ai为为i 物品单位重量物品单位重量 ci为为i 物品重要性估价物品重要性估价 b为最大负重为最大负重(2)、投资决策投资决策 Xi为在为在i 地区建厂规模地区建厂规模 ai为在为在i 地区建厂基建费用地区建厂基建费用 ci为在为在i 地区建厂单位利润地区建厂单位利润 b为最大资本为最大资本(3)、Xi 取取0或或1
4、时，可作项目投资模型时，可作项目投资模型旅游线路安排：旅游线路安排：（1）预定景点走且只走一次；（）预定景点走且只走一次；（2）路上时间最短）路上时间最短配送线路配送线路货郎担问题：货郎担问题：（1）送货地到达一次；（）送货地到达一次；（2）总路程最短总路程最短例例3、旅游售货员问题、旅游售货员问题问题：有一旅行团从问题：有一旅行团从 出发要遍游城市出发要遍游城市 ，已知从，已知从 到到 的旅费为的旅费为 ，问应如何安排行，问应如何安排行程使总费用最小？程使总费用最小？注：注：M为充分大的整数。为充分大的整数。模型模型变量是否从i第个城市到第j个城市约束 每个城市只能到达一次、离开一次避免出现
5、断裂每个点给个位势，除了初始点。要求前点比后点大。目标总费用最小01决策变量的应用决策变量的应用 可用于相互排斥计划中可用于相互排斥计划中例例1、运输方式：火车、船。、运输方式：火车、船。火车：火车：5X1+4X2 24 (体积体积)船：船：7X1+3X2 45 (体积体积)货物货物 体积体积(米米3/箱箱)重量重量(百公斤百公斤/箱箱)利润利润(千元千元/箱箱)甲甲 5 2 20 乙乙 4 5 10 装运限制装运限制 24 13 maxZ=20X1+10X2 2X1+5X2 135X1+4X2 24+MX37X1+3X2 45+M(1-X3)X1,X2 0 整数整数X3为为0或或1 M0当当
6、 X3=0 =0 火车火车 X3=1 =1 船船 例例2、ai1x1+ai2x2+ainxn b bi i(i=1,m)互相排斥互相排斥m个约束，只有一个起作用个约束，只有一个起作用ai1x1+ainxn b bi i+yi M M (i=1,m)y1+ym=m-1yi为为0或或1 M0上述问题的特征上述问题的特征n特征特征变量整数性要求n来源来源问题本身的要求；引入的逻辑变量的需要n性质性质可行域是离散集合2、整数线性规划解法整数线性规划解法ILP可行域为其相应线性规划问题的可行域的子集可行域为其相应线性规划问题的可行域的子集例例1、LP:X=(4.8,0)maxZ=96 ILP:X=(4,
7、1)maxZ=90 x1x262O6.5(4.8,0)with(simplex):maximize(20*x1+10*x2,5*x1+4*x2=24,2*x1+5*x2=13,NONNEGATIVE );用用Maple求解过程求解过程(1)、四舍五入法、四舍五入法 可估近似解，例中可估近似解，例中X=(4,0),Z=80 80 Z*96，0Z*-80 with(simplex):maximize(40*x1+90*x2,9*x1+7*x2=56,7*x1+20*x2 f:=(x1,x2)-40*x1+90*x2;b:=evalf(238/131);a:=evalf(630/131);f(a,b
8、);maximize(40*x1+90*x2,9*x1+7*x2=56,7*x1+20*x2=70,x1 f(4,2.1);maximize(40*x1+90*x2,9*x1+7*x2=56,7*x1+20*x2=5,NONNEGATIVE );evalf(f(5,11/7);maximize(40*x1+90*x2,9*x1+7*x2=56,7*x1+20*x2=70,x1=4,x2 evalf(f(4,2);maximize(40*x1+90*x2,9*x1+7*x2=56,7*x1+20*x2=70,x1=3,NONNEGATIVE );evalf(f(10/7,3);evalf(10/
9、7);MAPLE求解程序求解程序解为解为X1=49/9X2=1Z=307.8（7）无解）无解 maximize(40*x1+90*x2,9*x1+7*x2=56,7*x1+20*x2=5,x2 evalf(f(49/9,1);evalf(49/9);maximize(40*x1+90*x2,9*x1+7*x2=56,7*x1+20*x2=5,x2=2,NONNEGATIVE );(1)4.8091.817S0=0355.890(2)42.1S0=0349.0(3)51.571S0=0341.39(4)42S0=0340(5)1.4283340327.12(6)5.4441340307.76(7
10、)无解无解X1 4X1 5X2 2X2 1X2 2X2 3分枝定界法一般步骤分枝定界法一般步骤:(min)(1)、(A),先解先解(A)的松弛问题的松弛问题(B)(2)、(B)无可行解无可行解(A)无可行解。无可行解。(B)最优解符合最优解符合(A)要求，停。要求，停。(B)最优解不符合最优解不符合(A)要求，转要求，转(3)。(3)、估整数解、估整数解S0，作上界，作上界(4)、选、选(B)解中不符合整数条件的分量解中不符合整数条件的分量Xj(Xj=bj)分分枝，作枝，作(B)的后续问题的后续问题(C)、(D)。(C)：(B）加约束）加约束Xj bj (D)：(B)加约束加约束Xj bj+1
11、(5)、解、解(C)、(D)剪枝条件：剪枝条件：(C)，(D)无可行解无可行解 (C)，(D)对应的目标值对应的目标值Sc S0 (C)，(D)对应的目标值对应的目标值Sc=12;x3+x4+x5+x6+x7=15;x1+x4+x5+x6+x7=12;x1+x2+x5+x6+x7=14;x1+x2+x3+x6+x7=16;x1+x2+x3+x4+x7=18;x1+x2+x3+x4+x5=19;gin(x1);gin(x2);gin(x3);gin(x4);gingin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7);(x5);gin(x6
12、);gin(x7);EndSolution ReportGlobal optimal solution found at iteration:9 Objective value:4400.000 Variable Value Reduced Cost X1 5.000000 0.000000 X2 2.000000 0.000000 X3 8.000000 0.000000 X4 0.000000 0.000000 X5 4.000000 0.000000 X6 0.000000 66.66667 X7 3.000000 0.000000注解注解该问题本质上是个整数规划问题，放松的线性规划的最
13、优解是个整数解，所以两规划等价。定义整数变量用函数gin(x1)gin(x7);0-1整数变量为bin(x1)案例案例2：背包问题：背包问题 某人出国留学打点行李,现有3个旅行包,容积分别为1000ml、1500ml和2000ml,根据需要列出需带物品清单,其中必带物品7件,其体积分别为400、300、150、250、450、760、190(单位ml)。尚有10件待选物品,如果不带将在目的地购买,通过网络查询可以得知其在目的地的价格(单位$)。这些物品的容量及价格分别见下表,试给出一个合理的安排方案把物品放在三个旅行包里。物品12345678910体积200350500430320120700
14、420250100价格1545100705075200902030问题分析问题分析变量变量对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中 约束约束 包裹容量限制 必带物品限制 选带物品限制目标函数未带物品购买费用最小模型model:sets:wps/wp1.wp17/:tj,jg;bg/1.3/:r;links(wps,bg):x;EndsetsMin=Min=sum(wps
15、(i):jg(i)*(1-x(i,1)-x(i,2)-x(i,3);for(bg(j):sum(wps(i):tj(i)*x(i,j)=r(j);for(wps(i)|i#le#7:sum(bg(j):x(i,j)=1);for(wps(i)|i#gt#7:sum(bg(j):x(i,j)=1);for(links(i,j):Bin(x(i,j););data:tj=400 300 150 250 450 760 190 200 350 500 430 320 120 700 420 250 100;jg=0 0 0 0 0 0 0 15 45 100 70 50 75 200 90 20 3
16、0;r=1000 1500 2000;EnddataendSolution ReportGlobal optimal solution found at iteration:12060 Objective value:200.0000 7，14，171，10，13，152，3，4，5，6Bag IBag IIBag III案例3：应急选址问题 某城市要在市区设置k个应急服务中心,经过初步筛选确定了m个备选地，现已知共有n个居民小区，各小区到每个备选地的距离为 为了使得各小区能及时得到应急服务，要求各小区到最近的服务中心的距离尽可能的短，试给出中心选址方案。问题分析问题分析:该问题与传统的选址问题的主要区别在于其目标不再是要求费用最小，而是要求最长距离最短。也就是离服务中心距离最远的小区离最近的服务中心距离最小。变量变量：当中心的位置确定下来后，各小区对应的最近中心也就确定，所以真正的变量也就是小区的位置。设 问题分析问题分析 为了便于说明问题引入间接变量，第i小区是否由第j个中心服务 以及最远的距离 小区约束条件小区约束条件:最远距离约束最远距离约束:中心个数约束中心个数约束:目标函数：最远距离目标函数：最远距离 最小最小 模 型