第三讲整数规划。
一、整数规划模型。
12年，第一题，15分）一家公司打算在甲地、乙地或甲乙两地新建工厂，一地至多建一个工厂，并且在甲乙两地至多建一个仓库，仓库位置随工厂地点而定（即，如某地有工厂，该地可设仓库或不设仓库；但如该地不设工厂，则该地一定不设仓库），若总资本可用量为20（百万元），其他数据如下表所示，问一个最大化净现值收益的决策是什么？只建模不求解。
例：一辆货车的有效载重量是20吨，载货有效空间是35立方米。现有六件货物可选择运输，每件货物的重量、体积及收入见下表。
另外，货物2和货物3不能混装；如果装载货物4，就必须装载货物5。问怎样安排货物装载才能使收入最大，建立数学模型（不用求解）。
例：某大型企业每年需要进行多种类型的员工培训。假设共有需要培训的需求（如技术类、管理类）为6种，每种需求的最低培训人数为ai，i=1,..
6，可供选择的培训方式（如内部自行培训、外部与高校合作培训）有5种，每种的最高培训人数为bj，j=1,..5。又设若选择了第1种培训方式，则第3种培训方式也要选择。
记xij为第i种需求由第j种方式培训的人员数量，z为培训总费用。费用的构成包括固定费用和可变费用，第j种方式的固定培训费用为hj（与人数无关），与人数xij相应的可变费用为cij。如果以成本费用为优化目标，试建立该培训问题的结构优化模型。
二、分支定界法。
07年，第三题15分）设有整数规划问题如下，其松弛问题的最优解为（7/6，8/3），若要用分支定界法求其整数解，需要对其进行分支（仅作一级分支，不要求求解）。是以x1为分之对象，用示意图表示其分支问题的可行域，并写出可行域的约束方程。
三、割平面法。
11年，第五题，10分）对于max型整数规划问题，若其松弛问题的最优单纯形表中有一行数据如表3。
表3要求：(1) 给出其对应的割平面方程；
2) 写出在下一步两个分枝问题中各要增加的约束条件。
解： 08年，第三题，15分）某全整数规划问题（决策变量x1，x2，x3全为整数）的松弛问题（略去整数要求）的最优单纯形表为：
1) 若用分支定界法求其整数解，写出在下一步分支问题重要增加的约束条件；
2) 若用割平面法求整数解，写出割平面方程，将其加到上表，并简述继续求解的步骤。
解：（1）松弛问题中，求的非整数解，因此在下一步分支问题中需要增加两个约束条件。
2）由最终计算表中得到变量间的关系式：
分解移项得。
引入松弛变量x6，得到等式。
将这新的约束方程加到原表中，得下表。
以x3为换入变量，以-7为转轴元素，运用对偶单纯形法继续迭代，如果所有变量的值全为非负整数，则终止，否则，继续添加切割方程。
四、0-1整数规划的隐枚举法。
05年，第二题，20分）某公司有5个项目被列入投资计划，各项目的投资额和期望投资净收益见下表：
该公司只有600万元资金可用与投资，由于技术上的原因，投资受到以下约束：
1) 在项目中必有一项被选中；
2) 项目只能选中一项；
3) 项目5可能被选中的前提是项目1必须被选中。
如何在上述条件下选择一个最好的投资方案，使投资净收益最大？
1) 建立求解该问题的0-1规划模型；
2) 叙述求解0-1规划问题方法的基本步骤。
解： 2) 求解0-1整数规划的隐枚举方法的基本步骤（假设求最大值）：
1) 试探法找出一个可行解，求出目标函数z值；
2) 根据条件及（1）中的z值增加约束条件（过滤条件）
3) 对所有的约束条件按顺序排列，对每个解代入约束条件进行筛选；
4) 若遇到z值超过过滤条件的右边值，则改变过滤条件，继续做，直到求出最优解。
五、指派问题。
求指派问题就可归结为设法变换系数矩阵，使其含有n个独立0元素。
在原指派问题的效益矩阵中同行同列加上某一常数，所得指派问题与原问题同解。
指派问题是一类特殊的运输问题n=m, ai=bi=1
求解指派问题的步骤（匈牙利法）
第一步：变换效率矩阵，使每行每列至少有一个零。
行变换：找出每行最小元素，– 从该行各元素中减去之。
列变换：找出每列最小元素，– 从该列各元素中减去之。
第二步：试求最优指派方案。
1、逐行检查，若该行只有一个未标记的零，对其加( )标记，将( )标记元素同列上其它的零打上*标记。若该行有二个以上未标记的零，暂不标记，转下一行检查，直到所有行检查完；
2、逐列检查，若该列只有一个未标记的零，对其加( )标记，将( )标记元素同行上其它的零打上*标记。若该列有二个以上未标记的零，暂不标记，转下一列检查，直到所有列检查完；
3、重复后，可能出现三种情况：
情况a.每行都有一个(0)，显然已找到最优解，令对应(0)位置的xij =1；
情况b.仍有零元素未标记，此时，一定存在某些行和列同时有多个零，称为僵局状态，因为无法采用中的方法继续标记。
情况c.所有零都已标记，但标有( )的零的个数少于n；转下一步。
4、打破僵局。令未标记零对应的同行同列上其它未标记零的个数为该零的指数，选指数最小的先标记( )采用这种方法直至所有零都被标记，或出现情况a，或情况c。
第三步：开始划线过程，以确定系数矩阵中能找到多少个独立的零元素：
对没有标记( )的行打√
对打√ 行上所有其它零元素对应的列打 √
再对打√列上有( )标记的零元素对应的行打 √
重复以上步骤， 直至无法继续。
对没有打√的行划横线， 对所有打√的列划竖线。
第四步：进一步变换；
在未划线的元素中找最小者， 设为δ
对未被直线覆盖的各元素减去δ
对两条直线交叉点覆盖的元素加上δ
只有一条直线覆盖的元素保持不变。
06年，第四题，20分）某公司要分派3个推销员去3个地区推销某种产品，要求每个推销员只能去一个地区，每个地区只需一个推销员，各推销员在各地区推销该产品的预期费用见下表：求使总费用最少的指派方案。
解：因此，最优指派方案为：。
09年，第六题，15分）有五个工人甲、乙、丙、丁、戊，要指派他们分别完成5种工作a、b、c、d、e，每人做各种工作所消耗的时间如下，求最优指派使总的消耗时间为最小？
解：因此，最优指派方案为：
目标函数为min型。
对于max型目标函数，将效率矩阵中所有 cij 反号，则等效于求min型问题；再利用定理1进行变换，使所有 cij ’ 0，则可采用上述算法。
要求所有cij 0
若第i行有部分cij <0，令ki=min，则第i行所有元素加上| ki |即可。
系数矩阵（cij）为方阵。
若不满足，可添加行或列，相应的cij=0；
例：现要在五个工人中确定四个人来分别完成四项工作中的一项工作，由于每个人的技术特长不同，他们完成各项工作所需的工时也不同，每个工人完成每项工作所需的工时见下表，试找出一个工作分配方案，使总工时最小。
例：从甲、乙、丙、丁、戊五人中挑选四人去完成四项工作，一直每人完成各项工作的时间如下表所示。规定每项工作只能由一个人单独完成，每个人最多承担一项工作，假定甲必须保证分配到工作，丁因某种原因不愿意承担第四项工作，在满足上述条件下，如何分配工作使完成四项工作总的花费时间最少？
解：例：已知指派问题各人完成各项工作的效率矩阵如下表所示。用匈牙利法分别求下述两种情况下的最优解：
1）指定甲完成两项工作，乙、丙、丁各完成一项工作。
2）某人兼完成两项工作，其余每人完成一项工作。解：（1）
运筹学讲义
第六讲排队论。x y zx处填写表示相继到达间隔时间的分布 y处填写表示服务时间的分布 z处填写并列的服务台的数目c.c 1 单服务台，c 1 多服务台。表示相继到达间隔时间和服务时间的各种分布的符号 m 负指数分布。d 确定型。ek k阶爱尔朗分布。gi 一般相互独立的时间间隔的分布。g 一般服务...
运筹学讲义
第三部分图与网络分析。图与网络分析部分内容框架。图与网络的基本概念。图连通图。图的矩阵表示。树与最小树。最短路问题。图论在网络分析的应用最大流问题。最小费用最大流问题。第四章图与网络分析。1.图与网络的基本概念。一 图及其分类。本章研究的图与平面几何中的图不同，我们只关心图中有多少个点，点与点之间有...
管理运筹学 讲义 A
第二章对偶理论与灵敏度分析。duality theory and sensitivity analysis 第一节单纯形法的矩阵描述。用矩阵描述单纯形法求解过程比较简便，也有助于加深对单纯形法的理解。设有线性规划问题，用矩阵形式表示，在约束条件中加入松弛变量，将其化成标准型 式中i为m m的单位阵。...