8第八章-整数规划课件

第八章整数规划整数规划的难度远大于一般线性规划IntegerLinearProgramming1第八章整数规划整数规划的难度远大于一般线性规划Inte学习重点与难点一、整数规划数学模型及其类型(了解）二、整数规划的实际应用(建模.难点．重点)三、整数规划的解法(一)分枝定界法（难点）(二)指派问题的匈牙利解法(补充、重点)2学习重点与难点一、整数规划数学模型及其类型(了解）2一、整数规划数学模型及其类型整数规划（IP）---要求一部分或全部决策变量必须取整数的规划问题；松弛问题---不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称之为该整数规划问题的松弛问题；3一、整数规划数学模型及其类型整数规划（IP）---要求一部分整数规划模型的类型纯整数规划模型混合整数规划模型0-1整数规划模型整数规划整数线性规划整数非线性规划全部决策变量必须取整数部分决策变量必须取整数决策变量必须取0或1重点哦！4整数规划模型的类型纯整数规划模型整数规划整数线性规划全部决策纯整数规划模型Xj全部取整数5纯整数规划模型Xj全部取整数5混合整数规划模型Xj部分取整数6混合整数规划模型Xj部分取整数60-1整数规划模型Xj=0或1(j=1,2,…,n)70-1整数规划模型Xj=0或1(j=1,2,…,n)7二、整数规划实际应用投资场所的选择固定成本问题指派问题分布系统设计投资问题人力资源分配问题投资组合问题应急设施选址问题背包问题8二、整数规划实际应用投资场所的选择81、投资场所的选择例1、京城畜产品公司计划在市区的东南西北四区建立销售门市部，拟议中有10个位置Ai（i=1,2…,10）可供选择，各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况如表所示。考虑到各地区居民的消费水平及居民居住密集度，规定：在东区由A1,A2,A3三个点至多选择两个；在西区A4,A5两个点中至少选一个；在南区由A6,A7两个点中至少选一个；在北区由A8,A9,A10三个点中至少选两个；投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大？A1A2A3A4A5A6A7A8A9A10投资额10012015080709080140160180利润3640502220302548586191、投资场所的选择例1、京城畜产品公司计划在市区的东南西北四解：设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≤2s.t.x4+x5≥1x6+x7≥1x8+x9+x10≥2xi≥0且xi为0-1变量(i=1,2,…10)10解：设102、固定成本问题例2、高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量、不考虑固定费用，每种容器售出一只所得的利润、所用资源的数量、不管每种容器制造的数量是多少，都要支付的固定费用如表。现在要制定一个生产计划，使获得的利润为最大。资源小号容器中号容器大号容器限量金属板（t)劳动力(人/月)机器设备(台/月)221432843500300100利润（万元）456固定费用（万元）100150200112、固定成本问题例2、高压容器公司制造小、中、大三种尺寸的金设x1、x2、x3分别表示小号容器、中号容器和大号容器的生产数量，各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设：yi=1,当生产第i种容器即xi>0时；0,当不生产第i种容器即xi=0时这样目标函数可以写为：maxZ=4x1+5x2+6x3-100y1-150y2-200y3约束条件包括三种资源的限量要求外，还避免某种容器不投入固定费用就生产这种不合理情况，所以增加约束：xi≤Myi(i=1,2,3)解：12设x1、x2、x3分别表示小号容器、中号容器和大号容器的xi≤Myi(i=1,2,3)所以原问题的数学规划模型为：如果生产第i种容器，则xi>0，此时由约束条件知：yi=1如果不生产第i种容器，则xi=0，此时由约束条件知：yi=1或yi=0，但yi=1不利于目标函数的最大化，因此在问题的最优解中必然是yi=0maxZ=4x1+5x2+6x3-100y1-150y2-200y3xi≤Myi(i=1,2,3)2x1+4x2+8x3≤5002x1+3x2+4x3≤300x1+2x2+3x3≤100xi≥0且为整数，yi=0或1(i=1,2,3)s.t.13xi≤Myi(i=1,2,3)所以原问题的数学规划模例3、有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如表所示，问如何分配任务使完成四项任务的总工时耗费最少？3、指派问题14例3、有四个熟练工人，他们都是多面手，有四项任务要他1515有n项不同的任务，恰好n个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况不同，现假设必须指派每个人去完成一项任务，怎样把n项任务指派给n个人，使得完成n项任务的总的效率最高，这就是指派问题。模型中：xij

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

项任务；

cij

为第i

个工人为完成第j

项任务时的工时消耗；

{cij}mm称为效率矩阵16有n项不同的任务，恰好n个人可分别承担这些任务，但由于每人特指派问题的通用数学模型如下：指派问题不但是整数规划，而且是01规划;指派问题有m*m个变量,2m个约束条件，17指派问题的通用数学模型如下：指派问题不但是整数规划，4、分布系统设计例4、某企业在A1地已有一个工厂，其产品的生产能力为30千箱，为了扩大生产，打算在A2A3A4A5地中再选择几个地方建厂。已知A1地的产量、A2A3A4A5建成厂的产量、那时销售地的销量、产地到销售地的单位运价、在地建厂的固定成本等如表。（1）问应该在哪几个地方建厂，在满足销售量的前提下，使得其固定成本和总的运输费用之和最小；（2）如果由于政策要求必须在A2A3地建一个厂，问在哪几个地方建厂？产地\销售地B1B2B3产量(千箱)A184330A2A3A4A55491023743452102030

40销售量(千箱)302020固定成本175300375500184、分布系统设计例4、某企业在A1地已有一个工厂，其产品的生设xij表示从Ai运往Bj的运输量，为了说明哪个厂址被选中，设：yi=1,当Ai厂址被选中时；0,当Ai厂址没被选中时这样目标函数可以写为：minZ=8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32

+4x33+9x41+7x42+5x43+10x51+4x52+2x53+175y2+300y3+375y4+500y5

解：19设xij表示从Ai运往Bj的运输量，为了说明哪个厂址被选中，x21+x22+x23≤10y2x31+x32+x33≤20y3x41+x42+x43≤30y4x51+x52+x53≤40y5对A1厂来说产量的约束条件可写成：

x11+x12+x13≤30对

A2A3A4A5准备选址建设的新厂来说，只有当选为厂址建设，才会有生产量，所以它们的产量限制约束条件可写成：

x11+x21+x31+x41+x51=30x12+x22+x32+x42+x52=20x13+

x23+x33+x43+x53=20满足销售量的约束条件为：20x21+x22+x23≤10y2对A1厂来说产量的约minZ=8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32

+4x33+9x41+7x42+5x43+10x51+4x52+2x53+175y2+300y3+375y4+500y5

所以原问题的数学规划模型为：s.t.x11+x12+x13≤30x21+x22+x23≤10y2x31+x32+x33≤20y3x41+x42+x43≤30y4x51+x52+x53≤40y5x11+x21+x31+x41+x51=30x12+x22+x32+x42+x52=20x13+

x23+x33+x43+x53=20xij≥0，yi=0或1(i=1,2,3,4,5;j=1,2,3)21minZ=8x11+4x12+3x13+5x21+2x22+5、投资问题某公司在今后四年内考虑以下四个投资项目选择问题：项目甲：第二年初需投资，到第四年年末收回本利180%；要求最大投资额为8万元；项目乙：从第一年到第三年，每年年初需投资，并于次年年末收回本利120%；项目丙：从第一年开始每年年初可购买公债，于当年年末归还，并加息10%；项目丁：第一年初需投资，到第二年年末收回本利135%；第三年初又投资，到第四年年末收回本利130%此外，为了使每年项目之间保持平衡性，要求每年年末回收的资金全部投资到第二年年初,该部门现有投资资金30万元。应如何确定这些项目在各年的投资额，使该公司在第四年年末拥有资金的本利总额达到最大？试建立该问题的线性规划模型。225、投资问题某公司在今后四年内考虑以下四个投资项目选择问题：解：根据题意，可假设如下决策变量：第一年第二年第三年第四年项目甲：x12项目乙：x21x22x23

项目丙：x31x32x33x34

项目丁：x41x4323解：23maxZ=180%x12+120%x23+110%x34+130%x43.

x21+x31+x41=30x12+x22+x32=110%x31s.t.x23+x33+x43=120%x21+110%x32+135%x41x34=120%x22+110%x33x12≤8x12,x21,x22,x23,x31,x32,x33,x34,x41,x43

≥024maxZ=180%x12+120%x23+110%x34+1例5、某公司在今后四年内考虑以下四个投资项目选择问题：项目甲：第二年初需投资，到第四年年末收回本利180%；

要求最大投资额为8万元；项目乙：从第一年到第三年，每年年初需投资，并于次年年末收回本利120%；要求第一年投资额若投资则或为2万元或为4万元或为6万元或为8万元，其它年份不限；项目丙：从第一年开始每年年初可购买公债，于当年年末归还，并加息10%；但规定第一年若投资则最大投资额为8万元，最小投资额为3万元，其它年份不限；项目丁：第一年初需投资，到第二年年末收回本利135%；第三年初又投资，到第四年年末收回本利130%

此外，为了使每年项目之间保持平衡性，要求每年年末回收的资金全部投资到第二年年初,该部门现有投资资金30万元。应如何确定这些项目在各年的投资额，使该公司在第四年年末拥有资金的本利总额达到最大？（试建立该问题的线性规划模型）25例5、某公司在今后四年内考虑以下四个投资项目选择问题：25解：根据题意，可假设如下决策变量：第一年第二年第三年第四年项目甲：x12项目乙：x21x22x23

项目丙：x31x32x33x34

项目丁：x41x4326解：26项目乙：要求第一年投资额若投资则x21或为2万元或为4万元或为6万元或为8万元，其它年份不限：X21=2y21y21≤4为非负整数项目丙：但规定第一年若投资则最大投资额为8万元，最小投资额为3万元，其它年份不限：引入0-1变量：y31=0或1表示不投资和投资，X31≤8y31X31≥3y3127项目乙：要求第一年投资额若投资则x21或为2万元或为4万元或maxZ=180%x12+120%x23+110%x34+130%x43.x21+x31+x41=30x12+x22+x32=110%x31x23+x33+x43=120%x21+110%x32+135%x41x34=120%x22+110%x33x12≤8X21=2y21s.t.y21≤4X31≤8y31X31≥3y31x12,x21,x22,x23,x31,x32,x33,x34,x41,x43

≥0y21为非负整数y31=0或128maxZ=180%x12+120%x23+110%x34+1三、整数规划的解法分支定界算法割平面算法0-1规划的解法匈牙利解法（指派问题）29三、整数规划的解法分支定界算法29整数规划其松弛规划maxZ=CXmaxZ=CX分支定界算法30整数规划其松弛规划maxZ=CXmaxZ=CX分支定界算法3整数规划的可行解是其放松问题的可行解整数规划的最优值小于等于放松问题的最优值整数规划的解是可数的，最优解不一定发生在极点；31整数规划的可行解是其放松问题的可行解整数规划的最优值小于等于解法概述当人们开始接触整数规划问题时，常会有如下两种初始想法：因为可行方案数目有限，因此经过一一比较后，总能求出最好方案先放弃变量的整数性要求，解一个线性规划问题，然后用“四舍五入”法取整数解，这种方法，只有在变量的取值很大时，才有成功的可能性，而当变量的取值较小时，特别是0-1规划时，往往不能成功。32解法概述先放弃变量的整数性要求，解一个线性规划问题，然后用“温馨提示最优解不一定在顶点上达到最优解不一定是放松问题最优解的邻近整数解整数可行解远远多于顶点的个数，枚举法不可取33温馨提示最优解不一定在顶点上达到33算法思想求解放松问题最优值比边界坏最优解为整数最优值比边界好最优解为非整数且最优值比边界好分支边界分支舍弃最优解为整数解结束定界34算法思想求解放松问题最优值比边界坏最优解为整数最优值比分支的方法如：X=5.6则x≤5和x≥6maxZ=CXmaxZ=CXmaxZ=CX35分支的方法如：X=5.6则x≤5和x≥6maxZ=CXma小技巧：平行的分支中取目标函数值较大者优先分支36小技巧：平行的分支中取目标函数值较大者优先分支36定界的方法当前得到的最好整数解的目标函数值---下界分支后计算出的松弛问题的最优值（较大者）---上界说明：初始下界采用观察法找到一个整数解，其目标函数值即为下界；下界是逐渐增大的；初始上界为计算出的松弛问题的最优值，下界是逐渐减少的。37定界的方法当前得到的最好整数解的目标函数值---下界37剪枝的方法1、无可行解的分枝2、整数解，但其目标函数值小于当前下界；3、下一层具有比上一层较大的目标函数值，则剪掉上层。38剪枝的方法1、无可行解的分枝38maxZ=x1+x2x1+9/14x2≤51/14-2x1+x2≤1/3x1，x2≥0，且取整数s.t.

例、用分支定界法求解下列整数规划问题：其松弛问题为：求解其松弛问题得其最优解：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/3x1，x2≥0s.t.39maxZ=x1+x2x1+9/14x2≤51/14s.tSx1=3/2，x2=10/3Z=29/6S1x1=1，x2=7/3Z=10/3S2x1=2，x2=23/9Z=41/9S21x1=33/14，x2=2Z=61/14S22无可行解S211x1=2，x2=2Z=4S222x1=3，x2=1Z=4x1≤1x1≥2x2≤2x2≥3x1≤2x1≥3Z`=29/6Z`=0Z`=41/9Z`=0Z`=61/14Z`=0Z`=Z`=4剪枝剪枝取Z较大者优先分支40SS1S2S21S22S211分支定界法解整数规划的一般步骤1、求整数规划A的松弛问题B的解2、确定整数规划A的最优目标函数值的初始上界和下界；3、任取一个非整数解将规划问题分为两支，并求解4、修正整数规划A的最优目标函数值的上下界；5、继续求解，直到上下界并为整数解为止。41分支定界法解整数规划的一般步骤1、求整数规划A的松弛问题B的maxZ=

6x1+5x22x1+x2≤95x1+7x2≤35x1,x2≥0x1,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举例42maxZ=6这样就把相应的线性规划的可行域分成两个部分，如图所示:••••••••••5x1+7x2=352x1+x2=9x1x2123125344x1=3x1=4问题2：maxZ=

6x1+5x2问题3：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≥4x1,x2≥0x1,x2≥0x1,x2取整数x1,x2取整数43这样就把相应的线性规划的可行域分成两个部分，如图所示:•••求解相应的线性规划的最优解问题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

44求解相应的线性规划的最优解44••••••••••5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3问题4：maxZ=

6x1+5x2问题5：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≤2x2≥3x1,x2≥0x1,x2≥0x1,x2取整数x1,x2取整数x2=2

x2=345••••••••••5x1+7x2=352x1+求解相应的线性规划的最优解问题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

46求解相应的线性规划的最优解46问题6：maxZ=

6x1+5x2问题7：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≥3x2≥3x1≤2x1≥3x1,x2≥0x1,x2≥0x1,x2取整数x1,x2取整数x2=2

x2=3••••••••••5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3x1=247问题6：maxZ=6x1+5x2求解相应的线性规划的最优解：问题6相应的线性规划的最优解：x1=2，x2=25/7，Z6=209/7问题7相应的线性规划的最优解：无最优解第八步，定界过程LP7无最优解，不必再分枝，下界仍为29；现有上界为未分枝子问题中目标函数最大值，即为209/7。LP6的解仍不满足整数约束的要求，它的目标函数值209/7大于现有下界29，则应继续分枝。第九步，分枝过程将不满足整数约束的变量x2进行分枝，构造两个新的约束条件：x2≤3，x2≥4

48求解相应的线性规划的最优解：48问题8：maxZ=

6x1+5x2问题9：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≥3x2≥3x1≤2x1≤2x2≤3x2≥4x1,x2≥0x1,x2≥0x1,x2取整数x1,x2取整数••••••••••5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3x2=3x1=2x2=2

x2=449问题8：maxZ=6x1+5x2求解相应的线性规划的最优解问题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=2950求解相应的线性规划的最优解50分枝定界过程x1≤3x1≥4x2≤2x2≥3x1≤2x1≥3x2≤3x2≥451分枝定界过程x1≤3x1≥4x2≤2x2≥3x1≤2x1问题的提出例8、有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如表所示，问如何分配任务使完成四项任务的总工时耗费最少？补充：指派问题及匈牙利法

52补充：指派问题及匈牙利法52指派问题的数学模型模型中：xij

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

项任务；

cij

为第i

个工人为完成第j

项任务时的工时消耗；{cij}mm称为效率矩阵任务分配问题不但是整数规划，而且是01规划任务分配问题有2m个约束条件，但有且只有m个非零解，是自然高度退化的,有著名的匈牙利算法53指派问题的数学模型模型中：xij为第i个工人分二匈牙利法定理1如果从效率矩阵{cij}mm中每行元素分别减去一个常数ui，从每列元素分别减去一个常数vj，所得新的效率矩阵{bij}mm的任务分配问题的最优解等价于原问题的最优解。证明：略定理2若方阵中一部分元素为零，一部分元素非零，则覆盖方阵内所有零元素的最少直线数等于位于不同行、不同列的零元素的最多个数。证明：略匈牙利法的基本思路：根据定理1变换效率矩阵，使矩阵中有足够多的零。若矩阵中存在m

个不同行不同列的零，就找到了最优解若覆盖变换后的效率矩阵零元素的直线少于m条，就尚未找到最优解，设法进一步变换矩阵，增加新的零.54二匈牙利法定理1如果从效率矩阵{cij}m匈牙利法的步骤：

第一步：变换效率矩阵使每行每列至少有一个零，同时不出现负元素行变换：找出每行最小元素，从该行各元素中减去之列变换：找出每列最小元素，从该列各元素中减去之9171671271416817141779119-7-7-8-721090507909690242行变换列变换-42105050390929020255匈牙利法的步骤：第一步：变换效率矩阵917第二步：在变换后的系数矩阵中确定独立零元素

独立零元素-----指位于不同行不同列的零元素。确定独立零元素的方法：首先在只有一个零元素的行（或列）中对零元素加圈，因为这表示此人只能做该事（或此事只能由该人来做）。每圈一个0，同时把位于同行和同列的其他零元素划去，这表示此事已不能再由其他人来做（或此人已不能做其他事），如此反复进行，直到系数矩阵中所有零元素都被圈去或划去为止。在此过程中，如遇到在所有的行和列中，零元素都不止一个时，可任选其中一个零元素加圈，同时划去同行和同列中其他零元素。当过程结束时，被划圈的零元素即为独立零元素。56第二步：在变换后的系数矩阵中确定56独立零元素个数为4个，而m=421050503909290202210505039092902020001010010000010答：最优分配方案为x14=x22=x31=x43=1，其余为0，即甲D，乙B，丙A，丁C，Z=33最优解为：917167127141681714177911957独立零元素个数为4个，而m=42105若独立零元素有m个，则表示已可确定最优指派方案，此时，令解矩阵中和独立零元素对应位置上的元素为1，其他元素为0，即得出最优解矩阵；若独立零元素少于m个，则表示还不能确定最优指派方案。此时需要确定能覆盖所有零元素的最少直线数目的直线集合；58若独立零元素有m个，则表示已可确定最优指派方案，此时，41075276333444663-4-2-3-30631054100111330行变换列变换-10621053100011320独立零元素个数为3个，而m=4，继续例题5941075-406确定最少覆盖直线数目的方法：对没有划圈的行打√；（没事情干的人）在已打√的行中，对Ø所在列打√；（该人可干的事）在已打√的列中，对◎所在行打√（该事被干的人）重复2（该人还可干的事）和3（该事还被干的人），直到再也不能找到可以打√的行或列为止；对没有打√的行画一横线，对打√的列画一垂线，这样就得到了覆盖所有零元素的最少直线数目的直线集合。60确定最少覆盖直线数目的方法：对没有划圈的行打√；（没事情干的0621053100011320提示：最少直线的个数正好等于独立零元素的个数610621提示：最少直线的第三步：继续变换系数矩阵方法是：在未被直线覆盖的元素中找出一个最小元素。对未被直线覆盖的元素所在的行中各元素都减去这一最小元素。对被直线覆盖的元素所在的列中各元素都加上这一最小元素（或列），返回第二步。未被直线覆盖的元素中最小值为10621053100011320-1-1+1051004201001232062第三步：继续变换系数矩阵方法是：在未被直线覆盖的元素中找出一-1-10400031020022210+1+1-105100420100123200010100001000001答：最优分配方案为x13=x21=x32=x44=1，其余为0，即甲C，乙A，丙B，丁D，Z=15最优解为：未被直线覆盖的元素中最小值为14107527633344466363-10400+1+1-10指派问题举例某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司对新商店的建造费用的报价如表，商业公司应当对5家建筑公司怎样分配建造任务，才能使总的建造费用最少？B1B2B3B4A148715A2A3A4A576669979171214121486

10B51210710664指派问题举例某商业公司计划开办五家新商店。为了尽早建成营业，有一份中文说明书,需译成英、日、德、俄四种文字，现有甲、乙、丙、丁四人。他们将中文说明书翻译成不同语种的说明书所需时间如表，问应指派何人去完成何工作，使所需总时间最少？英日德俄甲215134乙1041415丙9141613丁78119课堂练习题一65有一份中文说明书,需译成英、日、德、俄四种文字，现有甲、乙、215134104141591416137811900010100100000106621513400ABCDE甲127979乙89666丙71712149丁15146610戊4107109课堂练习题二67ABC以上匈牙利解法只适用于标准形式的指派问题，即:（1）目标函数求最小（2）人与事情的数目相同（3）每人必须做且只能做一件事情（4）每一件事情必须且只能由一人做进一步讨论68以上匈牙利解法只适用于标准形式的指派问题，即:进一步讨论68非标准形式的指派问题：（1）目标函数求最大（2）人与事情的数目不相同（3）某人可以做多件事情（4）某事一定不能由某人做对于非标准形式的指派问题的求解：首先需要转化为标准形式的指派问题；然后再利用匈牙利解法求解。69非标准形式的指派问题：69非标准形式的指派问题（1）最大化的指派问题设最大化指派问题效率矩阵C=(cij)n×n其中最大元素为m。令B=(bij)n×n=(m-cij)n×n则以B为系数矩阵的最小化指派问题和以C为系数矩阵的最大化指派问题有相同的最优解。70非标准形式的指派问题（1）最大化的指派问题70英日德俄甲215134乙1041415丙9141613丁7811921513410414159141613781191413126122172039857最大元素为16假设系数矩阵中的数据表示每人所获得的收益Cij=16-=71英日德非标准形式的指派问题（2）人数与事数不等的指派问题若人少事多，则添上一些虚拟的“人”，这些虚拟的“人”做各事的费用系数可取0，理解为这些费用实际上不会发生。若人多事少，则添上一些虚拟的“事”，这些虚拟的“事”被各人做的费用系数同样也取0。72非标准形式的指派问题（2）人数与事数不等的指派问题72英日德俄甲215134乙1041415丙9141613

21513410414159141613

0

0

0

0Cij=英日德甲21513乙10414丙91416丁78112151301041409141607811073英日德非标准形式的指派问题（3）一个人可以做几件事的指派问题若某个人可以做几件事，则可将该人化作相同的几个“人”来接受指派。这几个“人”做同一件事的费用系数当然都一样。74非标准形式的指派问题（3）一个人可以做几件事的指派问题74英日德俄甲215134乙1041415丙9141613丁78119215134

2151341041415914161378119

78119假设甲可以做两件事情,丁也可以做两件事情21513400

215134001041415009141613007811900

781190075英日德非标准形式的指派问题（4）某事一定不能由某人做的指派问题若某事一定不能由某人做，则可将相应的费用系数取作足够大的数M。

76非标准形式的指派问题（4）某事一定不能由某人做的指派问题76英日德俄甲215134乙1041415丙9141613丁78119

M

151341041415914161378119假设甲一定不能翻译英语77英日德非标准形式的指派问题举例某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司对新商店的建造费用的报价如表，商业公司应当对5家建筑公司怎样分配建造任务，才能使总的建造费用最少？B1B2B3B4A148715A2A3A4A576669979171214121486

10B51210710678非标准形式的指派问题举例某商业公司计划开办五家新商店。为了尽非标准形式的指派问题举例为了保证工程质量，经过研究决定，舍弃建筑公司A1和A2，而让技术力量较强的建筑公司A3、A4和A5来承建。根据实际情况，可以容许每家建筑公司承建一家或二家商店。求使总费用最少的指派方案。79非标准形式的指派问题举例为了保证工程质量，经过研究决定，舍弃B1B2B3B4A148715A2A3A4A576669979171214121486

10B5121071066

9128767146106912106A3A4A5691287912876714610671461069121066912106A3A3A4A4A5A500000080B1B2B3B4A148715A2791714B5121谢谢！本章结束81谢谢！本章结束81后面是自学内容，不做要求82后面是自学内容，不做要求821、人力资源分配问题某个中型百货商场对售货人员（周工资200元）的需求经统计如下表

为了保证销售人员充分休息，销售人员每周工作5天，休息2天。问应如何安排销售人员的工作时间，使得所配售货人员的总费用最小？星期一二三四五六七人数12151214161819831、人力资源分配问题某个中型百货商场对售货人员（周工资200模型假设每天工作8小时，不考虑夜班的情况；每个人的休息时间为连续的两天时间；每天安排的人员数不得低于需求量，但可以超过需求量84模型假设每天工作8小时，不考虑夜班的情况；84问题分析因素不可变因素：需求量、休息时间、单位费用；可变因素：安排的人数、每人工作的时间、总费用；方案确定每天工作的人数，由于连续休息2天，当确定每个人开始休息的时间就等于知道工作的时间，因而确定每天开始休息的人数就知道每天开始工作的人数，从而求出每天工作的人数。变量每天开始休息的人数约束条件

1.每人休息时间2天，自然满足。

85问题分析因素不可变因素：需求量、休息时间、单位费用；85

3.变量非负约束：863.变量非负约束：86目标函数：总费用最小，总费用与使用的总人数成正比。由于每个人必然在且仅在某一天开始休息，所以总人数等于87目标函数：总费用最小，总费用与使用的总人数成正比。由于每个人模型全部取整数，i=1…788模型全部取整数，i=1…788练习：应急选址问题

某城市要在市区设置k个应急服务中心,经过初步筛选确定了m个备选地，现已知共有n个居民小区，各小区到各备选地的距离为为了使得各小区能及时得到应急服务，要求各小区到最近的服务中心的距离尽可能的短，试给出中心选址方案。89练习：应急选址问题某城市要在市区设置k个应急服务中心,问题分析

该问题与传统的选址问题的主要区别在于其目标不再是要求费用最小，而是要求最长距离最短。也就是离服务中心距离最远的小区离最近的服务中心距离最小。

变量：当中心的位置确定下来后，各小区对应的最近中心也就确定，所以真正的变量也就是小区的位置。设

90问题分析该问题与传统的选址问题的主要区别在于其目标不问题分析

为了便于说明问题引入间接变量，第i小区是否由第j个中心服务以及最远的距离

约束条件

小区服务约束91问题分析为了便于说明问题引入间接变量，第i小区是否问题分析最远距离约束中心个数约束目标函数：最远距离最小92问题分析最远距离约束92模型93模型93证券投资：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润。项目投资：财团或银行把资金投入到若干项目中以获得中长期的收益最大。投资组合问题94证券投资：把一定的资金投入到合适的有价证券上以规避风险并获得案例某财团有万元的资金，经出其考察选中个投资项目，每个项目只能投资一个。其中第个项目需投资金额为万元，预计5年后获利（）万元，问应如何选择项目使得5年后总收益最大？95案例某财团有万元的资金，经出其考察选中个投模型变量—每个项目是否投资约束—总金额不超过限制目标—总收益最大96模型变量—每个项目是否投资969797课堂练习

设有n个投资项目，其中第j个项目需要资金aj万元，将来可获利润cj万元.若现有资金总额为b万元，则应选择哪些投资项目，才能获利最大？设z为可获得的总利润（万元），则该问题的数学模型为s.t.解:设98课堂练习设有n个投资项目，其中第j个项目需要资金aj万元邮递包裹把形状可变的包裹用尽量少的车辆运走旅行背包容量一定的背包里装尽可能的多的物品背包问题(KnapsackProblem)99邮递包裹背包问题(KnapsackProblem)99实例某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。

100实例某人出国留学打点行李，现有三个旅行包，容积大小分别为物品12345678910体积200350500430320120700420250100价格1545100705075200902030101物品12345678910体积200350500430320问题分析变量—对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中102问题分析变量—对每个物品要确定是否带同时要确定放在哪个包裹里约束包裹容量限制必带物品限制选带物品限制103约束包裹容量限制必带物品限制选带物品限制103目标函数—未带物品购买费用最小104目标函数—未带物品购买费用最小104模型105模型105旅游线路安排预定景点走且只走一次路上时间最短配送线路—货郎担问题送货地到达一次总路程最短旅游售货员问题106旅游线路安排旅游售货员问题106案例有一旅行团从出发要遍游城市，已知从到的旅费为，问应如何安排行程使总费用最小？107案例有一旅行团从出发要遍游城市107模型变量—是否从i第个城市到第j个城市约束每个城市只能到达一次、离开一次108模型变量—是否从i第个城市到第j个城市108避免出现断裂每个点给个位势除了初始点外要求前点比后点大109避免出现断裂109目标—总费用最小110目标—总费用最小110111111一个旅行者,为了准备旅行的必须用品,要在背包内装一些最有用的东西,但有个限制,最多只能装b公斤的物品,而每件物品只能整个携带,这样旅行者给每件物品规定了一个“价值”以表示其有用的程度,如果共有n件物品,第j件物品aj公斤,其价值为cj.问题变成:在携带的物品总重量不超过b公斤条件下,携带哪些物品,可使总价值最大?解：如果令xj=1表示携带物品j，xj=0表示不携带物品j，则问题表示成0-1规划:MaxZ=Σcjxjs.t.Σajxjbxj=0或1112一个旅行者,为了准备旅行的必须用品,要在背包内装一些最有用的工程费用（千元）收入（千元）12312345543781794681021102040201530最大的可用基金数（千元）252525—

考虑资金分配问题，在今后3年内有5项工程考虑施工，每项工程的期望收入和年度费用（千元）如表。假定每一项已经批准的工程要在整个3个内完成，目标是要选出使总收入达到最大的那些工程.把这个问题表示成一个0—1整数规划模型.113工程费用（千元）收入123151820最大的可用基金数（解：设（i=1、2、3、4、5）则该问题的数学模型为：Min=20x1+40x2+20x3+15x4+30x5s.t.114解：设（i=1、2、3、4、5）114

一公司考虑在四个城市：北京、上海、广州和武汉设立库房.这些库房负责向三个地区：华北、华中和华南地区发运货物，每个库房每月可处理货物1000件，在北京设库房每月的成本为4.5万元，上海为5万元，广州为7万元，武汉为4万元.每个地区的月平均需求量为华北为每月600件，华中每月700件，华南每月800件.发运货物的费用（元/件）见表.公司希望在满足地区需求的前提下使平均月成本最小，且还要满足以下条件：