《运筹学教程》胡云权第5版第3章整数规划.pptxVIP

第三章 整数规划;学习目标;;例如 1. 变量是人数、机器设备台数或产品件数等都要求是整数；;【例1】企业计划生产2000件某种产品，该种产品可利用Ａ、Ｂ、Ｃ设备中的任意一种加工。已知每种设备的生产准备结束费用、生产该产品时的单件成本以及每种设备限定的最大加工数量（件）如下表所示，试建立总成本最小的数学模型。 ; 变量 设xj表示在第 j（j=1,2,3）种设备上加工的产品数量，其生产费用为： 式中Kj是同产量无关的生产准备费用（即固定费用），cj是单位产品成本。设0－1变量yj，令 ; 约束条件;;;【例3】某财团 有 万元的资金，经出其考察选中 个投资项目，每个项目只能投资一次。其中第 个项目需投资金额为 万元，预计5年后获利 （ ）万元，问应如何选择项目使得5年后总收益最大？;;【例4】某人出国留学打点行李，现有三个旅行包，容积大???分别为1000毫升、1500毫升和2000毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。 ;变量：对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中。;整数规划数学模型;目标函数—未带物品购买费用最小;【例5】某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如下表所示。问两种物品各装多少件，所装物品的总价值最大？ ;不考虑x1、x2取整数的约束，称为上述规划的松弛问题，可行域如图； B为最优解：X＝(3.57，7.14)，Z＝35.7。 由于x1 、 x2必须取整数值，可行解集只是图中可行域内的那些整数点； 凑整法：比较四种组合，但（4，7）、（4，8）（3，8）都不是可行解，（3，7）虽属可行解，但代入目标函数得Z=33； 实际问题的最优解是（5，5），Z=35。;;; 在松弛问题的最优单纯形表中，记Q为m个基变量的下标集合，K为n-m个非基变量的下标集合。;割平面法 从X*的非整数分量中选取一个，用以构造一个线性约束条件，将其加入原松弛问题，形成一个新的线性规划，再求解。 若新的线性规划最优解满足整数要求，即为纯整数规划的最优解，否则，重复上述步骤，直到获得整数最优解为止。 新加约束条件基本性质 已获得的不符合整数要求的线性规划最优解不满足该线性约束条件，以使原来的非整数最优解不再出现。 凡整数可行解均满足该线性约束条件，以使整数最优解始终被保留在每次形成的线性规划可行域中。 ;割平面法;;;割平面法;【解】（1）松弛问题的最优表如下（单纯形法）;;割平面法;割平面法;割平面法;;cj;;分支定界法;【例】用分支定界法求解下列规划。;;;;;尽管LP1的解中x1不为整数，但Z5Z因此LP5的最优解就是原整数规划的最优解。;分支定界法;作业;求解0-1规划的隐枚举法;求解0-1规划的隐枚举法;;46;求解0-1规划的隐枚举法;变量组合 ;0-1规划;指派问题;指派问题;【解】此工作分配问题可以采用枚举法求解，即将所有分配方案求出，总分最大的方案就是最优解。本例的方案有4！＝4×3×2×1＝24种，当人数和工作数较多时，方案数是人数的阶乘，计算量非常大。用0－1规划模型求解此类分配问题显得非常简单。;2015年5月4日星期一;指派问题求解方法：匈牙利算法;【定理2 】 若矩阵A的元素可分成“ 0”与非“ 0”两部分，则覆盖“ 0”元素的最少直线数等于位于不同行不同列的“ 0”元素（称为独立元素）的最大个数。;【解】最优分配方案是安排四人工作，使完成工作总时间最少，最小值问题。;第三步：用最少的直线覆盖所有“0”，得;回到第三步:用最少的直线覆盖所有“ 0”，得;画线，;（1）求最大值的指派问题;当人数m大于工作数n时，加上m－n项工作，例如; 将可做多件事的这个人，虚拟出来相同的几个“人”进行指派，且虚拟人的做事费用相同。;【例】某人事部门拟招聘4人任职4项工作，对他们综合考评的 得分如下表（满分100分），如何安排工作使总分最多。;【解】;作业