8第八章__整数规划

null第八章 整数规划第八章 整数规划 整数规划的难度远大于一般线性规划Integer Linear Programming学习重点与难点学习重点与难点一、 整数规划数学模型及其类型(了解） 二、 整数规划的实际应用(建模.难点．重点) 三、 整数规划的解法 (一)分枝定界法（难点） (二)指派问题的匈牙利解法(补充、重点)一、整数规划数学模型及其类型一、整数规划数学模型及其类型整数规划（IP）---要求一部分或全部决策变量必须取整数的规划问题； 松弛问题---不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称之为该整数规划问题的松弛问题；整数规划模型的类型整数规划模型的类型纯整数规划模型 混合整数规划模型 0-1整数规划模型整数规划整数线性规划 整数非线性规划全部决策变量必须取整数部分决策变量必须取整数决策变量必须取0或1重点哦！纯整数规划模型纯整数规划模型Xj全部取整数混合整数规划模型混合整数规划模型Xj部分取整数0-1整数规划模型0-1整数规划模型Xj=0或1 (j=1,2,…,n)二、整数规划实际应用二、整数规划实际应用投资场所的选择 固定成本问题 指派问题 分布系统 投资问题 人力资源分配问题 投资组合问题 应急设施选址问题 背包问题1、投资场所的选择1、投资场所的选择例1、京城畜产品公司计划在市区的东南西北四区建立销售门市部，拟议中有10个位置Ai（i=1,2…,10）可供选择，各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况如表所示。 考虑到各地区居民的消费水平及居民居住密集度，规定： 在东区由A1, A2, A3三个点至多选择两个； 在西区A4, A5两个点中至少选一个； 在南区由A6, A7两个点中至少选一个； 在北区由A8, A9, A10三个点中至少选两个； 投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大？null解：设 1 当Ai点被选用 xi= 0 当Ai点没被选用 maxZ=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10 ≤720 x1+x2+x3 ≤2 s.t. x4+x5 ≥1 x6+x7 ≥1 x8+x9+x10 ≥2 xi≥0且xi为0-1变量(i=1,2,…10) 2、固定成本问题2、固定成本问题例2、高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量、不考虑固定费用，每种容器售出一只所得的利润、所用资源的数量、不管每种容器制造的数量是多少，都要支付的固定费用如表。现在要制定一个生产计划，使获得的利润为最大。null设x1、 x2、 x3分别表示小号容器、中号容器和大号容器的生产数量，各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设：这样目标函数可以写为： maxZ=4x1+5x2+6x3-100y1-150y2-200y3约束条件包括三种资源的限量要求外，还避免某种容器不投入固定费用就生产这种不合理情况，所以增加约束：xi≤Myi (i=1,2,3)解：nullxi≤Myi (i=1,2,3)所以原问题的数学规划模型为： 如果生产第i种容器，则xi>0，此时由约束条件知： yi=1 如果不生产第i种容器，则xi=0，此时由约束条件知： yi=1或yi=0 ，但yi=1 不利于目标函数的最大化，因此在问题的最优解中必然是yi=0 maxZ=4x1+5x2+6x3-100y1-150y2-200y3xi≤Myi (i=1,2,3)2x1+4x2+8x3≤ 500 2x1+3x2+4x3≤ 300 x1+2x2+3x3≤ 100xi≥0且为整数，yi =0或1 (i=1,2,3)3、指派问题3、指派问题 例3、有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如表所示，问如何分配任务使完成四项任务的总工时耗费最少？nullnull有n项不同的任务，恰好n个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况不同，现假设必须指派每个人去完成一项任务，怎样把n项任务指派给n个人，使得完成n项任务的总的效率最高，这就是指派问题。模型中：xij 为第 i 个工人是否分配去做第 j 项任务； cij 为第 i 个工人为完成第 j 项任务时的工时消耗； {cij}mm 称为效率矩阵 指派问题的通用数学模型如下： 指派问题的通用数学模型如下：指派问题不但是整数规划，而且是01规划;指派问题有m*m个变量, 2m个约束条件，4、分布系统设计4、分布系统设计例4、某企业在A1地已有一个工厂，其产品的生产能力为30千箱，为了扩大生产，打算在A2 A3 A4 A5地中再选择几个地方建厂。已知A1地的产量、 A2 A3 A4 A5建成厂的产量、那时销售地的销量、产地到销售地的单位运价、在地建厂的固定成本等如表。 （1）问应该在哪几个地方建厂，在满足销售量的前提下，使得其固定成本和总的运输费用之和最小； （2）如果由于政策要求必须在A2 A3地建一个厂，问在哪几个地方建厂？null设xij表示从Ai运往Bj的运输量，为了说明哪个厂址被选中，设：这样目标函数可以写为：minZ=8x11+4x12+3x13+5x21+2x22+3x23+4x31 +3x32 +4x33+9x41+7x42+5x43+10x51+4x52+2x53 +175y2+300y3+375y4+ 500y5 解：nullx21+ x22+ x23 ≤10y2 x31+ x32+ x33 ≤20y3 x41+ x42+ x43 ≤30y4 x51+ x52+ x53 ≤40y5对A1 厂来说产量的约束条件可写成： x11+ x12+ x13 ≤30对 A2 A3 A4 A5 准备选址建设的新厂来说，只有当选为厂址建设，才会有生产量，所以它们的产量限制约束条件可写成： x11+ x21+ x31 + x41 + x51 =30 x12+ x22+ x32 + x42 + x52 =20 x13+ x23 + x33 + x43 + x53 =20满足销售量的约束条件为：nullminZ=8x11+4x12+3x13+5x21+2x22+3x23+4x31 +3x32 +4x33+9x41+7x42+5x43+10x51+4x52+2x53 +175y2+300y3+375y4+ 500y5 所以原问题的数学规划模型为： x11+ x12+ x13 ≤30x21+ x22+ x23 ≤10y2 x31+ x32+ x33 ≤20y3 x41+ x42+ x43 ≤30y4 x51+ x52+ x53 ≤40y5x11+ x21+ x31 + x41 + x51 =30 x12+ x22+ x32 + x42 + x52 =20 x13+ x23 + x33 + x43 + x53 =20xij≥0，yi =0或1 (i=1,2,3,4,5;j=1,2,3)5、投资问题5、投资问题某公司在今后四年内考虑以下四个投资项目选择问题： 项目甲：第二年初需投资，到第四年年末收回本利180%； 要求最大投资额为8万元； 项目乙：从第一年到第三年，每年年初需投资，并于次年年 末收回本利120%； 项目丙：从第一年开始每年年初可购买公债，于当年年末归 还，并加息10%； 项目丁：第一年初需投资，到第二年年末收回本利135%； 第三年初又投资，到第四年年末收回本利130% 此外，为了使每年项目之间保持平衡性，要求每年年末回收的资金全部投资到第二年年初, 该部门现有投资资金30万元。应如何确定这些项目在各年的投资额，使该公司在第四年年末拥有资金的本利总额达到最大？试建立该问题的线性规划模型。 null解： 根据题意，可假设如下决策变量： 第一年 第二年 第三年 第四年 项目甲： x12 项目乙： x21 x22 x23 项目丙： x31 x32 x33 x34 项目丁： x41 x43nullmaxZ=180%x12+120%x23+110%x34+130%x43. x21+ x31+ x41 =30 x12+x22+x32 =110%x31 s.t. x23 +x33+ x43 =120%x21 +110%x32 +135%x41 x34=120%x22+110%x33 x12≤8 x12,x21,x22,x23,x31,x32,x33,x34,x41,x43 ≥0null例5、某公司在今后四年内考虑以下四个投资项目选择问题： 项目甲：第二年初需投资，到第四年年末收回本利180%； 要求最大投资额为8万元； 项目乙：从第一年到第三年，每年年初需投资，并于次年年 末收回本利120%；要求第一年投资额若投资则或为2万元或为4万元或为6万元或为8万元， 其它年份不限； 项目丙：从第一年开始每年年初可购买公债，于当年年末归 还，并加息10%；但规定第一年若投资则最大投 资额为8万元，最小投资额为3万元， 其它年份不限； 项目丁：第一年初需投资，到第二年年末收回本利135%； 第三年初又投资，到第四年年末收回本利130% 此外，为了使每年项目之间保持平衡性，要求每年年末回收的资金全部投资到第二年年初, 该部门现有投资资金30万元。应如何确定这些项目在各年的投资额，使该公司在第四年年末拥有资金的本利总额达到最大？（试建立该问题的线性规划模型） null解： 根据题意，可假设如下决策变量： 第一年 第二年 第三年 第四年 项目甲： x12 项目乙： x21 x22 x23 项目丙： x31 x32 x33 x34 项目丁： x41 x43null项目乙：要求第一年投资额若投资则x21或为2万元或为4万元或为6万元或为8万元， 其它年份不限： X21=2 y21 y21≤4为非负整数 项目丙：但规定第一年若投资则最大投资额为8万元，最小投资额为3万元， 其它年份不限： 引入0-1变量：y31=0或1表示不投资和投资， X31 ≤ 8 y31 X31 ≥ 3 y31nullmaxZ=180%x12+120%x23+110%x34+130%x43. x21+ x31+ x41 =30 x12+x22+x32 =110%x31 x23 +x33+ x43 =120%x21 +110%x32 +135%x41 x34=120%x22+110%x33 x12≤8 X21=2 y21 s.t. y21≤4 X31 ≤ 8 y31 X31 ≥ 3 y31 x12,x21,x22,x23,x31,x32,x33,x34,x41,x43 ≥0 y21为非负整数 y31=0或1三、整数规划的解法三、整数规划的解法分支定界算法 割平面算法 0-1规划的解法 匈牙利解法（指派问题）nullmaxZ=CXmaxZ=CX分支定界算法null整数规划的可行解是其放松问题的可行解整数规划的最优值小于等于放松问题的最优值整数规划的解是可数的，最优解不一定发生在极点；null解法概述 当人们开始接触整数规划问题时，常会有如下两种初始想法： 因为可行数目有限，因此经过一一比较后，总能求出最好方案先放弃变量的整数性要求，解一个线性规划问题，然后用“四舍五入”法取整数解，这种，只有在变量的取值很大时，才有成功的可能性，而当变量的取值较小时，特别是0-1规划时，往往不能成功。温馨提示温馨提示最优解不一定在顶点上达到 最优解不一定是放松问题最优解的邻近整数解 整数可行解远远多于顶点的个数，枚举法不可取算 法 思 想算 法 思 想求解放松问题最优值比边界坏最优解为整数最优值比边界好最优解为非整数且最优值比边界好分 支边 界分 支舍 弃最优解为整数解结 束定界分支的方法分支的方法 如：X=5.6则x≤5和x≥6maxZ=CXmaxZ=CXmaxZ=CXnull小技巧：平行的分支中取目标函数值较大者优先分支定界的方法定界的方法当前得到的最好整数解的目标函数值---下界 分支后计算出的松弛问题的最优值（较大者）---上界 说明： 初始下界采用观察法找到一个整数解，其目标函数值即为下界；下界是逐渐增大的； 初始上界为计算出的松弛问题的最优值，下界是逐渐减少的。 剪枝的方法剪枝的方法1、无可行解的分枝 2、整数解，但其目标函数值小于当前下界； 3、下一层具有比上一层较大的目标函数值，则剪掉上层。null maxZ=x1+x2x1+9/14x2≤ 51/14 -2x1+x2≤ 1/3 x1，x2 ≥0，且取整数 例、用分支定界法求解下列整数规划问题： 其松弛问题为：求解其松弛问题得其最优解：x1=3/2， x2=10/3 最优值：Z=29/6 确定问题的上界为Z`=29/6； 通过观察法可得一个整数可行解x1=0， x2=0 ，将其目标函数值Z=0作为下界Z`=0； 然后进行分支和重新定界，得出求解过程如图： maxZ=x1+x2x1+9/14x2≤ 51/14 -2x1+x2≤ 1/3 x1，x2 ≥0nullx1≤1x1≥2x2≤2x2≥3x1≤2x1≥3Z`=29/6 Z`=0Z`=41/9 Z`=0Z`=61/14 Z`=0Z`= Z`= 4 剪枝剪枝取Z较大者优先分支分支定界法解整数规划的一般步骤分支定界法解整数规划的一般步骤1、求整数规划A的松弛问题B的解 2、确定整数规划A的最优目标函数值的初始上界和下界； 3、任取一个非整数解将规划问题分为两支，并求解 4、修正整数规划A的最优目标函数值的上下界； 5、继续求解，直到上下界并为整数解为止。null maxZ= 6x1 +5 x2 2x1 + x2 ≤9 5x1 +7 x2 ≤35 x1, x2 ≥0 x1, x2取整数 第一步,不考虑变量的整数约束,求相应LP(问题1)的最优解： x1=28/9，x2 =25/9，Z1=293/9 第二步,定界过程 这个解不满足整数约束，这时目标函值Z1是整数规划的目标上界； 因为x1=x2=0是整数规划问题的可行解，所以下界为0。 第三步,分枝过程 将不满足整数约束的变量x1进行分枝，x1称为分枝变量，构造两个新的约束条件： x1≤ [28/9]=3， x1 ≥ [28/9] +1=4 举 例null这样就把相应的线性规划的可行域分成两个部分，如图所示:问题2：maxZ= 6x1 +5 x2 问题3： maxZ= 6x1 +5 x2 2x1 + x2 ≤9 2x1 + x2 ≤9 5x1 +7 x2 ≤35 5x1 +7 x2 ≤35 x1≤3 x1 ≥4 x1, x2 ≥0 x1, x2 ≥0 x1, x2取整数 x1, x2取整数null求解相应的线性规划的最优解 问题2相应的线性规划的最优解：x1=3，x2 =20/7，Z2=226/7 问题3相应的线性规划的最优解：x1=4，x2 =1，Z3=29 第四步，定界过程 LP3的解满足整数约束，不必再分枝，它的目标函数值是29，大于原有下界0，则新的下界为29； 现有上界为未分枝子问题中目标函数最大值，即为226/7。 LP2的解仍不满足整数约束的要求，它的目标函数值226/7大于等于现有下界，则应继续分枝。 第五步，分枝过程 将不满足整数约束的变量x2进行分枝，构造两个新的约束条件： x2≤ [20/7]=2， x2 ≥ [20/7] +1=3 null问题4：maxZ= 6x1 +5 x2 问题5： maxZ= 6x1 +5 x2 2x1 + x2 ≤9 2x1 + x2 ≤9 5x1 +7 x2 ≤35 5x1 +7 x2 ≤35 x1≤3 x1 ≤ 3 x2≤2 x2 ≥3 x1, x2 ≥0 x1, x2 ≥0 x1, x2取整数 x1, x2取整数null求解相应的线性规划的最优解 问题4相应的线性规划的最优解： x1=3，x2 =2，Z4=28 问题5相应的线性规划的最优解：x1=14/5，x2 =3，Z5=159/5 第六步，定界过程 LP4的解满足整数约束，不必再分枝，它的目标函数值是28，小于原有下界29，则下界仍为29； 现有上界为未分枝子问题中目标函数最大值，即为159/5。 LP5的解仍不满足整数约束的要求，它的目标函数值159/5大于现有下界29，则应继续分枝。 第七步，分枝过程 将不满足整数约束的变量x1进行分枝，构造两个新的约束条件： x1≤ [14/5]=2，x1≥ [14/5] +1=3 null问题6：maxZ= 6x1 +5 x2 问题7： maxZ= 6x1 +5 x2 2x1 + x2 ≤9 2x1 + x2 ≤9 5x1 +7 x2 ≤35 5x1 +7 x2 ≤35 x1≤3 x1 ≤3 x2 ≥3 x2 ≥3 x1≤2 x1 ≥ 3 x1, x2 ≥0 x1, x2 ≥0 x1, x2取整数 x1, x2取整数null求解相应的线性规划的最优解： 问题6相应的线性规划的最优解： x1=2，x2 =25/7，Z6=209/7 问题7相应的线性规划的最优解：无最优解 第八步，定界过程 LP7无最优解，不必再分枝，下界仍为29； 现有上界为未分枝子问题中目标函数最大值，即为209/7。 LP6的解仍不满足整数约束的要求，它的目标函数值209/7大于现有下界29，则应继续分枝。 第九步，分枝过程 将不满足整数约束的变量x2进行分枝，构造两个新的约束条件： x2≤ 3， x2≥ 4 null问题8：maxZ= 6x1 +5 x2 问题9： maxZ= 6x1 +5 x2 2x1 + x2 ≤9 2x1 + x2 ≤9 5x1 +7 x2 ≤35 5x1 +7 x2 ≤35 x1≤3 x1 ≤3 x2 ≥3 x2 ≥3 x1≤2 x1≤2 x2≤3 x2 ≥4 x1, x2 ≥0 x1, x2 ≥0 x1, x2取整数 x1, x2取整数null求解相应的线性规划的最优解 问题8相应的线性规划的最优解： x1=2，x2 =3，Z8=27 问题9相应的线性规划的最优解：x1=7/5，x2 =4，Z9=142/5 第十步，定界过程 LP8的最优解，满足整数约束，不必再分枝，下界仍为29； 现有上界为未分枝子问题中目标函数最大值，即为29。 虽然LP9的解仍不满足整数约束的要求，它的目标函数值142/5小于现有下界29，则不再继续分枝。 上界=下界，得整数规划问题的最优解： x1=4，x2 =1，Z=29null分枝定界过程x1≤3x1 ≥4x2≤2x2 ≥3x1≤2x1 ≥3x2≤3x2 ≥4补充： 指派问题及匈牙利法 问题的提出 例8、 有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如表所示，问如何分配任务使完成四项任务的总工时耗费最少？补充： 指派问题及匈牙利法 指派问题的数学模型 指派问题的数学模型模型中：xij 为第 i 个工人分配去做第 j 项任务； cij 为第 i 个工人为完成第 j 项任务时的工时消耗； {cij}mm 称为效率矩阵任务分配问题不但是整数规划，而且是01规划 任务分配问题有2m个约束条件，但有且只有m个非零解，是自然高度退化的,有著名的匈牙利算法 二 匈牙利法 二 匈牙利法定理 1 如果从效率矩阵{cij}mm中每行元素分别减去一个常数 ui，从每列元素分别减去一个常数 vj ，所得新的效率矩阵{bij }mm的任务分配问题的最优解等价于原问题的最优解。 证明：略 定理 2 若方阵中一部分元素为零，一部分元素非零，则覆盖方阵内所有零元素的最少直线数等于位于不同行、不同列的零元素的最多个数。 证明：略 匈牙利法的基本思路： 根据定理 1 变换效率矩阵，使矩阵中有足够多的零。若矩阵中存在 m 个不同行不同列的零，就找到了最优解 若覆盖变换后的效率矩阵零元素的直线少于m 条，就尚未找到最优解，设法进一步变换矩阵，增加新的零.匈牙利法的步骤： 匈牙利法的步骤： 第一步：变换效率矩阵 使每行每列至少有一个零，同时不出现负元素 行变换：找出每行最小元素，从该行各元素中减去之 列变换：找出每列最小元素，从该列各元素中减去之-7 -7 -8 -7行变换列变换-4null第二步：在变换后的系数矩阵中确定 独立零元素 独立零元素-----指位于不同行不同列的零元素。 确定独立零元素的方法：首先在只有一个零元素的行（或列）中对零元素加圈，因为这表示此人只能做该事（或此事只能由该人来做）。每圈一个0，同时把位于同行和同列的其他零元素划去，这表示此事已不能再由其他人来做（或此人已不能做其他事），如此反复进行，直到系数矩阵中所有零元素都被圈去或划去为止。在此过程中，如遇到在所有的行和列中，零元素都不止一个时，可任选其中一个零元素加圈，同时划去同行和同列中其他零元素。当过程结束时，被划圈的零元素即为独立零元素。null独立零元素个数为4个，而m=4答：最优分配方案为 x14= x22= x31 = x43 =1，其余为0， 即甲 D ，乙 B ，丙 A ，丁 C ，Z=33最优解为：null 若独立零元素有m个，则表示已可确定最优指派方案，此时，令解矩阵中和独立零元素对应位置上的元素为1，其他元素为0，即得出最优解矩阵；若独立零元素少于m个，则表示还不能确定最优指派方案。此时需要确定能覆盖所有零元素的最少直线数目的直线集合； null-4 -2 -3 -3行变换列变换-1独立零元素个数为3个，而m=4，继续例题确定最少覆盖直线数目的方法：确定最少覆盖直线数目的方法：对没有划圈的行打√；（没事情干的人） 在已打√的行中，对Ø所在列打√ ；（该人可干的事） 在已打√的列中，对◎所在行打√ （该事被干的人） 重复2 （该人还可干的事）和3 （该事还被干的人） ，直到再也不能找到可以打√ 的行或列为止； 对没有打√的行画一横线，对打√的列画一垂线，这样就得到了覆盖所有零元素的最少直线数目的直线集合。null提示：最少直线的个数正好等于独立零元素的个数第三步：继续变换系数矩阵第三步：继续变换系数矩阵方法是：在未被直线覆盖的元素中找出一个最小元素。对未被直线覆盖的元素所在的行中各元素都减去这一最小元素。对被直线覆盖的元素所在的列中各元素都加上这一最小元素（或列），返回第二步。未被直线覆盖的元素中最小值为1-1 -1 +1null-1 -1 +1+1-1答：最优分配方案为 x13= x21= x32 = x44 =1，其余为0， 即甲C，乙A，丙B，丁D，Z=15最优解为：未被直线覆盖的元素中最小值为1指派问题举例指派问题举例某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司对新商店的建造费用的报价如表，商业公司应当对5家建筑公司怎样分配建造任务，才能使总的建造费用最少？null有一份中文说明书,需译成英、日、德、俄四种文字，现有甲、乙、丙、丁四人。他们将中文说明书翻译成不同语种的说明书所需时间如表，问应指派何人去完成何工作，使所需总时间最少？ 英 日 德 俄 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9课堂练习题一nullnull A B C D E 甲 12 7 9 7 9 乙 8 9 6 6 6 丙 7 17 12 14 9 丁 15 14 6 6 10 戊 4 10 7 10 9课堂练习题二null以上匈牙利解法只适用于形式的指派问题，即: （1）目标函数求最小 （2）人与事情的数目相同 （3）每人必须做且只能做一件事情 （4）每一件事情必须且只能由一人做进一步讨论null非标准形式的指派问题： （1）目标函数求最大 （2）人与事情的数目不相同 （3）某人可以做多件事情 （4）某事一定不能由某人做 对于非标准形式的指派问题的求解： 首先需要转化为标准形式的指派问题； 然后再利用匈牙利解法求解。非标准形式的指派问题非标准形式的指派问题（1）最大化的指派问题 设最大化指派问题效率矩阵C=(cij)n×n其中最大元素为m。 令B=(bij)n×n=(m-cij)n×n 则以B为系数矩阵的最小化指派问题和以C为系数矩阵的最大化指派问题有相同的最优解。null 英 日 德 俄 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9最大元素为16假设系数矩阵中的数据表示每人所获得的收益Cij=16-=非标准形式的指派问题非标准形式的指派问题（2）人数与事数不等的指派问题 若人少事多，则添上一些虚拟的“人”，这些虚拟的“人”做各事的费用系数可取0，理解为这些费用实际上不会发生。 若人多事少，则添上一些虚拟的“事”，这些虚拟的“事”被各人做的费用系数同样也取0。null 英 日 德 俄 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 Cij= 英 日 德 甲 2 15 13 乙 10 4 14 丙 9 14 16 丁 7 8 11非标准形式的指派问题非标准形式的指派问题（3）一个人可以做几件事的指派问题 若某个人可以做几件事，则可将该人化作相同的几个“人”来接受指派。这几个“人”做同一件事的费用系数当然都一样。null 英 日 德 俄 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9 2 15 13 4 2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9 7 8 11 9假设甲可以做两件事情,丁也可以做两件事情 2 15 13 4 0 0 2 15 13 4 0 0 10 4 14 15 0 0 9 14 16 13 0 0 7 8 11 9 0 0 7 8 11 9 0 0非标准形式的指派问题非标准形式的指派问题（4）某事一定不能由某人做的指派问题 若某事一定不能由某人做，则可将相应的费用系数取作足够大的数M。 null 英 日 德 俄 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9假设甲一定不能翻译英语非标准形式的指派问题举例非标准形式的指派问题举例某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司对新商店的建造费用的报价如表，商业公司应当对5家建筑公司怎样分配建造任务，才能使总的建造费用最少？非标准形式的指派问题举例非标准形式的指派问题举例为了保证工程质量，经过研究决定，舍弃建筑公司A1和A2 ，而让技术力量较强的建筑公司A3 、A4和A5来承建。根据实际情况，可以容许每家建筑公司承建一家或二家商店。求使总费用最少的指派方案。null6 9 12 8 7 6 7 14 6 10 6 9 12 10 6A3 A4 A56 9 12 8 7 9 12 8 7 6 7 14 6 10 6 7 14 6 10 6 9 12 10 6 6 9 12 10 6A3 A3 A4 A4 A5 A50 0 0 0 0 0null后面是自学内容，不做要求后面是自学内容，不做要求1、人力资源分配问题1、人力资源分配问题某个中型百货商场对售货人员（周工资200元）的需求经统计如下表 为了保证销售人员充分休息，销售人员每周工作5天，休息2天。问应如何安排销售人员的工作时间，使得所配售货人员的总费用最小？模型假设模型假设每天工作8小时，不考虑夜班的情况； 每个人的休息时间为连续的两天时间； 每天安排的人员数不得低于需求量，但可以超过需求量问题问题分析因素 不可变因素：需求量、休息时间、单位费用； 可变因素：安排的人数、每人工作的时间、总费用； 方案 确定每天工作的人数，由于连续休息2天，当确定每个人开始休息的时间就等于知道工作的时间，因而确定每天开始休息的人数就知道每天开始工作的人数，从而求出每天工作的人数。 变量 每天开始休息的人数 约束条件 1.每人休息时间2天，自然满足。 nullnull目标函数：总费用最小，总费用与使用的总人数成正比。由于每个人必然在且仅在某一天开始休息，所以总人数等于模 型模 型全部取整数，i=1…7练习：应急选址问题练习：应急选址问题 某城市要在市区设置k个应急服务中心,经过初步筛选确定了m个备选地，现已知共有n个居民小区，各小区到各备选地的距离为 为了使得各小区能及时得到应急服务，要求各小区到最近的服务中心的距离尽可能的短，试给出中心选址方案。问题分析问题分析 该问题与传统的选址问题的主要区别在于其目标不再是要求费用最小，而是要求最长距离最短。也就是离服务中心距离最远的小区离最近的服务中心距离最小。 变量：当中心的位置确定下来后，各小区对应的最近中心也就确定，所以真正的变量也就是小区的位置。设 问题分析问题分析 为了便于说明问题引入间接变量，第i小区是否由第j个中心服务 以及最远的距离 约束条件 小区服务约束问 题 分 析问 题 分 析最远距离约束 中心个数约束 目标函数：最远距离 最小模 型模 型投资组合问题证券投资：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润。 项目投资：财团或银行把资金投入到若干项目中以获得中长期的收益最大。投资组合问题案 例案 例某财团有 万元的资金，经出其考察选中 个投资项目，每个项目只能投资一个。其中第 个项目需投资金额为 万元，预计5年后获利 （ ）万元，问应如何选择项目使得5年后总收益最大？模 型模 型变量—每个项目是否投资 约束—总金额不超过限制 目标—总收益最大null课堂练习课堂练习 设有n个投资项目，其中第j个项目需要资金aj万元，将来可获利润cj万元.若现有资金总额为b万元，则应选择哪些投资项目，才能获利最大？设z为可获得的总利润（万元），则该问题的数学模型为s.t.解: 设null邮递包裹 把形状可变的包裹用尽量少的车辆运走 旅行背包 容量一定的背包里装尽可能的多的物品背包问题( Knapsack Problem)实 例实 例某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。 null问题分析问题分析变量—对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中null约束包裹容量限制必带物品限制选带物品限制null目标函数—未带物品购买费用最小模 型模 型旅游售货员问题旅游线路安排 预定景点走且只走一次 路上时间最短 配送线路—货郎担问题 送货地到达一次 总路程最短旅游售货员问题案 例案 例有一旅行团从 出发要遍游城市 ，已知从 到 的旅费为 ，问应如何安排行程使总费用最小？模 型模 型变量—是否从i第个城市到第j个城市 约束 每个城市只能到达一次、离开一次null避免出现断裂 每个点给个位势 除了初始点外要求前点比后点大null目标—总费用最小nullnull一个旅行者,为了准备旅行的必须用品,要在背包内装一些最有用的东西,但有个限制,最多只能装b公斤的物品,而每件物品只能整个携带,这样旅行者给每件物品规定了一个“价值”以表示其有用的程度,如果共有n件物品,第j件物品aj公斤,其价值为cj.问题变成:在携带的物品总重量不超过b公斤条件下,携带哪些物品,可使总价值最大?解：如果令xj=1表示携带物品j，xj=0表示不携带物品j，则问题表示成0-1规划: Max Z = Σcjxj s.t. Σajxj  b xj=0或1null考虑资金分配问题，在今后3年内有5项工程考虑施工，每项工程的期望收入和年度费用（千元）如表。假定每一项已经批准的工程要在整个3个内完成，目标是要选出使总收入达到最大的那些工程. 把这个问题表示成一个0—1整数规划模型.null解：设（i=1、2、3、4、5） 则该问题的数学模型为： Min=20x1+40x2+20x3+15x4+30x5 s.t.练习 一公司考虑在四个城市：北京、上海、广州和武汉设立库房.这些库房负责向三个地区：华北、华中和华南地区发运货物，每个库房每月可处理货物1000件，在北京设库房每月的成本为4.5万元，上海为5万元，广州为7万元，武汉为4万元.每个地区的月平均需求量为华北为每月600件，华中每月700件，华南每月800件.发运货物的费用（元/件）见表. 公司希望在满足地区需求的前提下使平均月成本最小，且还要满足以下条件： (1) 如果在上海设库房，则必须也在武汉设库房； (2) 最多设立三个库房； (3) 武汉和广州不能同时设立库房. 请写一个满足上述要求的整数规划模型. 练习null解：设xij为从第i个库房发运到第j个地区的货物量，其中i=1、2、3、4分别代表北京、上海、广州和武汉，j=1 、2、3分别代表华北、华中和华南，cij表示从第i个库房发运到第j个地区的货物的单位费用。 ci表示在第i个地区设立库房的月成本.则该问题的数学模型为： Min Z= 例7、分枝定界法举例 Min Z= x1+4x2 s.t. 2x1+ x2  8 x1+2x2  6 x1,x2  0且为整数 例7、分枝定界法举例 : 松弛问题: 用图解法(或单纯形法)可解得相应的松驰问题的最优解为 （10/3，4/3）Z=26/3为各分枝的下界。 Min Z= x1+4x2 s.t. 2x1+ x2  8 x1+2x2  6 x1,x2  0null 0 1 2 3 4 5 6 8 7 6 5 4 3 2 1x1x2p等值线BAC（10/3，4/3）null（P1） Min Z= x1+4x2 s.t. 2x1+ x2  8 x1+2x2  6 x1  3 x1,x2  0 用图解法可解得（P1）的最优解（3，3/2）Z=9由于松弛问题的解不是整数解因此选 x1进行分枝,分成两枝: (P1) x1  3 (P2) x1  4 （P2） Min Z= x1+4x2 s.t. 2x1+ x2  8 x1+2x2  6 x1  4 x1,x2  0 用图解法可知P2 无可行解.null 0 1 2 3 4 5 6 8 7 6 5 4 3 2 1x1x2p选 x1进行分枝： (P1) x1  3 (P2) x1  4 为空集 P1A（10/3，4/3）等值线BCD（3，3/2）n