第05章 整数规划ppt课件.ppt

《第05章 整数规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章整数规划(IntegerProgramming,IP)本章内容整数规划的数学模型及解的特点解纯整数规划的割平面法分支定界法0-1型整数规划指派问题整数规划问题投资组合问题旅游售货员问题背包问题应用案例投资组合问题背景证券投资：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润项目投资：财团或银行把资金投入到若干项目中以获得中长期的收益最大。投资组合问题案例某财团有万元的资金，经出其考察选中个投资项目，每个项目只能投资一个。其中第个项目需投资金额为万元，预计5年后获利万元，问应如何选择项目使得5年后总收益最大？投资组合问题模型变量—每个项

2、目是否投资约束—总金额不超过限制目标—总收益最大旅游售货员问题背景旅游线路安排预定景点走且只走一次路上时间最短；配送线路—货郎担问题送货地到达一次总路程最短；旅游售货员问题案例有一旅行团从出发要遍游城市，已知从到的旅费为，问应如何安排行程使总费用最小？旅游售货员问题模型变量—是否从i第个城市到第j个城市；约束—每个城市只能到达一次、离开一次；目标—总费用最小；背包问题背景邮递包裹把形状可变的包裹用尽量少的车辆运走旅行背包容量一定的背包里装尽可能的多的物品背包问题实例某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和20

3、00毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。物品12345678910体积200350500430320120700420250100价格1545100705075200902030背包问题模型变量—对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的

4、包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中约束包裹容量限制：必带物品限制：选带物品限制：目标函数未带物品购买费用最小背包问题模型背包问题模型s.t.整数规划问题特征—变量整数性要求；来源问题本身的要求；引入的逻辑变量的需要；性质—可行域是离散集合；线性整数规划模型一般整数规划模型0-1整数规划模型混合整数规划模型一般整数规划模型整数线性规划线性数学问题模型的一般形式为0-1整数

5、规划模型混合整数规划模型令问题模型为：例2现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj(j=1,2,…，n)。此外，由于种种原因，有三个附加条件：第一，若选择项目1，就必须同时选择项目2。反之，则不一定；第二，项目3和项目4中至少选择一个；第三，项目5、项目6和项目7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大?属于0-1规划问题整数规划问题解的特点（IP）问题的松弛问题∩≤松弛问题的最优值是原整数规划的目标函数值的上界。注释最优解不一定在顶点上达到最优解不一定是放松问题最优

6、解的邻近整数解整数可行解远多余于顶点，枚举法不可取本章内容整数规划的数学模型及解的特点解纯整数规划的割平面法分支定界法0-1型整数规划指派问题割平面法的基本思想：若整数规划IP的松弛规划L0的最优解不是整数解，对L0增加一个约束条件，得线性规划L1，此过程缩小了松弛规划的可行解域，在切去松弛规划的最优解的同时，保留松弛规划的任一整数解，因此整数规划IP的解均在L1中，若L1的最优解为整数解，则得IP的最优解。若L1的最优解不是整数解，重复以上步骤，由于可行解域在不断缩小，且保留IP所有的整数解，总可以在有限次后得到IP的最优解.割平面法由放松问题的可行

7、域向整数规划的可行域逼近方法—利用超平面切除要求整数解保留放松问题最优值向最优解逼近目标得到的新的可行域的某个整数坐标的极点恰好是问题的最优解割平面法非基变量下标集合符号[*]表示不超过“*”的最大整数，f(*)表示“*”的非负真分数。Gomory约束L0的最优单纯形表：x1…xi…xmxm+1…xm+j…xn解检0…0…0λ1…λm+j…λnz-z0x11…0…0a1m+1…a1m+j…a1nb10︰︰︰︰︰︰︰︰xi0…1…0aim+1…aim+j…ainbi0︰︰︰︰︰︰︰︰xm0…0…1amm+1…amm+j…amnbm0源方程------对应

8、于生成行i的割平面x1…xi…xmxm+1…xm+j…xn解检0…0…0λ1…λm+j…λnz