第二章整数规划
§1 概论
1.1定义
规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。
1.2 整数规划的分类
如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类：
1。变量全限制为整数时，称纯（完全）整数规划。
2。变量部分限制为整数的，称混合整数规划。
1.2整数规划特点
（i）原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：
①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。
②整数规划无可行解。
例1原线性规划为
min z x-i x2
2x1 4X25, x10, x20
5 5
其最优实数解为：X1 0,X2,mi nz
4 4
③有可行解（当然就存在最优解），但最优解值变差。
例2原线性规划为
min z X-I X2
2X14X26, X1 0, X2 0
其最优实数解为：X1 0,X2 - ,min z 3
。
2 2
若限制整数得：X1 1,X21,min z2。
（ii）整数规划最优解不能按照实数最优解简单取整而获得。 1.3求解方法分类：
（i ）分枝定界法一可求纯或混合整数线性规划。
（ii）割平面法一可求纯或混合整数线性规划。
（iii）隐枚举法一求解“ 0-1 ”整数规划：
①过滤隐枚举法；
②分枝隐枚举法。
（iv）匈牙利法一解决指派问题（“ 0-1 ”规划特殊情形）v）蒙特卡洛法一求解各种类型规
划。
下面将简要介绍常用的几种求解整数规划的方法。
§ 2分枝定界法
对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，
这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。
分枝定界法可用于解纯整数或混合的整数规划问题。在本世纪六十年代初由Land Doig和Dakin等人提出的。由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂
选址问题、背包问题及分配问题等。
设有最大化的整数规划问题A，与它相应的线性规划为问题B，从解问题B开始，
若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的上界，记作
z ;而A的任意可行解的目标函数值将是z*的一个下界z。分枝定界法就
是将B的可行域分成子区域的方法。逐步减小z和增大z，最终求到z*。现用下例来
说明：
例3求解下述整数规划
Max z 40%| 90X2
9x! 7X256
7x! 20X2 70
X20且为整数
解（i）先不考虑整数限制，即解相应的线性规划B，得最优解为：
X1 4.8092,X2 1.8168, Z 355.8779
可见它不符合整数条件。这时z是问题A的最优目标函数值z*的上界，记作z。而X i 0,X2 0显然是问题A的一个整数可行解，这时z 0 ,是z*的一个下界，记作z，即0 z* 356。
（ii）因为X i,X2当前均为非整数，故不满足整数要求，任选一个进行分枝。设选X i 进行分枝，把可行集分成2个子集：
X1[4.8092] 4，X1[4.8092] 1 5
因为4与5之间无整数，故这两个子集的整数解必与原可行集合整数解一致。这一步称为分枝。这两个子集的规划及求解如下：
问题B1: Max z 40X-I 90X2
9X17 X256
7X-I 20X270
0 X-I 4,X20
最优解为：X i 4.0, 2.1, z
1349。
问题B2 : Max z 40X-| 90X2
9X17X256
7X120X270
X i 5,X2 0
最优解为：X i
5.0,
X
1.57,z1341.4
再定界：*
0 z
349。
(iii)对问题B i再进行分枝得问题Bn和B12，它们的最优解为B11 : x14, x22,z11340
B12: x1 1.43, x2 3.00, z12 327.14
再定界：340 z* 341，并将B12剪枝。
(iv)对问题B2再进行分枝得问题B21和B22，它们的最优解为
B21 :为 5.44, X2 1.00, Z22 308
B22无可行解。将B21 , B22剪枝。
于是可以断定原问题的最优解为：
x14, x2 2, z 340
从以上解题过程可得用分枝定界法求解整数规划(最大化)问题的步骤为：
开始，将要求解的整数规划问题称为问题A，将与它相应的线性规划问题称为问
题B。
(i)解问题B可能得到以下情况之一：
(a)B没有可行解，这时A也没有可行解，则停止.
(b)B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解，则
停止。
(c)B有最优解，但不符合问题A的整数条件，记它的目标函数值为Z。
(ii)用观察法找问题A的一个整数可行解，一般可取X j 0, j 1, ,n，试探，求得其目标函数值，并记作Z。以z*表示问题A的最优目标函数值；这时有
*
z z Z
进行迭代。
第一步：分枝，在B的最优解中任选一个不符合整数条件的变量x j，其值为b j , 以[b j]表示小于b j的最大整数。构造两个约束条件
X j [b j]和X j [b j] 1
将这两个约束条件，分别加入问题B，求两个后继规划问题B1和B2。不考虑整数条件求解这两个后继问题。
定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出
最优目标函数值最大者作为新的上界z。从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界z，若无作用z 0。
第二步：比较与剪枝，各分枝的最优目标函数中若有小于z者，则剪掉这枝，即
以后不再考虑了。若大于z，且不符合整数条件，则重复第一步骤。一直到最后得到
z* z为止。得最优整数解x*, j 1, , n。
§ 3 0 1型整数规划
0 1型整数规划是整数规划中的特殊情形，它的变量X j仅取值0或1。这时X j称为0 1变量，或称二进制变量。X j仅取值0或1这个条件可由下述约束条件：
0 X j 1，整数
所代替，是和一般整数规划的约束条件形式一致的。在实际问题中， 如果引入 0 1变
量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。
我们
先介绍引入0 1变量的实际问题，再研究解法。
3.1弓I 入0 1变量的实际问题
3.1.1投资场所的选定一一相互排斥的计划
例4 某公司拟在市东、西、南三区建立门市部。拟议中有 7个位置(点)
A(i 1,2, ,7)可供选择。规定
在东区。由A 1,A,A 3三个点中至多选两个； 在西区。由A 4,A 两个点中至少选一个； 在南区，由A 6,A 7两个点中至少选一个。
如选用A 点，设备投资估计为 b i 元，每年可获利润估计
为 G 元，但投资总额不能 超过B 元。问应选择哪几个点可使
年利润为最大？
1,2, ,7)
于是问题可列写成:
其中M 是充分大的数。 约束条件
Max
z
CX i
7
i 1
b
i 1
)iXi
B
X 1 X 2 X 3
2
X 4 X 5 1 X 6 X 7 1,
7
X i
解题时先引入0 1变量X j (i 令
X i
1,当A 点被选中, 0,当Aj 点没被选中.
1,2, ,7.
3.1.2相互排斥的约束条件
有两个相互排斥的约束条件
5x 1 4X 2 24 或 7x 1 3X 2
1变量y ，则上述约束条件可改写为:
yM (1 y)M
45。
为了统一在一个问题中，引入
5x 1 4x 2 7x 1 3x 2 y 0或1
24 45
第二章 人力资源规划与工作计划 第一节人力资源规划工作目标 一、总体目标 确保企业在生存与发展过程中，在需要的岗位、需要的时间及时获得各种所需的人，从而最大限度地开发和利用人力资源，实现企业目标。 二、目标分解 1.人力资源规划要保证企业总体人员需求，建立强有力的人才储备，确保企业业务和管理对人才需求的数量和质量，协调企业和个人的利益。 2.在对企业现有人力资源状况进行分析的基础上，根据企业各分支机构、部门的编制合理准确地预测出企业人力供需状况的具体数据，并根据这些数据进行工作部署。 第二节工作事项描述 一、预测人力资源供应及需求数据，制定有关政策和措施。 二、整合、分析、统计和评估现有人力资源，并提交相关人力资源分析报表。 三、根据组织整体发展战备编制《人力资源规划书》。 四、制定《人力资源部年度工作计划》及《人力资源部月度工作计划与预算》。 第三节工作事项细化执行 一、起草人力资源规划书 人力资源规划一般在年初根据企业现有人力资源状况和业务发展情况制定，同时要考虑到人员流动对企业产生的影响。 （一）什么是人力资源规划 人力资源规划是指为使企业在定时期稳定地拥有一定素质和必要数量的人力，以实现包括个人利益在内的该组织的目标而制定的一套措施，从而求得人员需求量和人员拥有量之间在企业未来发展过程中的相互匹配。匹配包括以下三方面的含义： 1.适应企业环境的变化，从企业的目标与任务出发，要求人力资源的质量、数量和结构动态适应其特定的生产资料和生产技术条件的要求； 2.组织目标实现与个人利益满足的一致性； 3.保证人力资源与未来组织发展各阶段的动态协调。 （二）人力资源规划要实现的目标 1.得到并保持一定数量具备特定技能、知识结构和能力的人员，充分利用现有人力资源。 预测企业中潜在的人员过剩或人力不足的问题。2. 3.建设同支训练有素、运作灵活的劳动力队伍，增强企业适应未知环境的能力。 4.减少企业在关键技术环节对外部招聘的依赖性。 （三）人力资源规划的主要内容 1.需要多少员工？
四、把下列线性规划问题化成标准形式： 2、minZ=2x1-x2+2x3 五、按各题要求。建立线性规划数学模型 1、某工厂生产A、B、C三种产品，每种产品的原材料消耗量、机械台时消耗量以及这些资源的限量，单位产品的利润如下表所示： 根据客户订货，三种产品的最低月需要量分别为200，250和100件，最大月销售量分别为250，280和120件。月销售分别为250，280和120件。问如何安排生产计划，使总利润最大。 2、某建筑工地有一批长度为10米的相同型号的钢筋，今要截成长度为3米的钢筋90根，长度为4米的钢筋60根，问怎样下料，才能使所使用的原材料最省?
1． 某运输公司在春运期间需要24小时昼夜加班工作，需要的人员数量如下表所示： 每个工作人员连续工作八小时，且在时段开始时上班，问如何安排，使得既满足以上要求，又使上班人数 最少? 五、分别用图解法和单纯形法求解下列线性规划问题．并对照指出单纯形迭代的每一步相当于图解法可行 域中的哪一个顶点。
六、用单纯形法求解下列线性规划问题： 七、用大M法求解下列线性规划问题。并指出问题的解属于哪一类。
八、下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为maxZ=5x 1+3x 2，约束形式为“≤”，X 3，X 4为松驰变量．表中解代入目标函数后得Z=10 (1)求表中a ～g 的值 (2)表中给出的解是否为最优解? （1）a=2 b=0 c=0 d=1 e=4/5 f=0 g=－5 （2） 表中给出的解为最优解 第四章 线性规划的对偶理论 五、写出下列线性规划问题的对偶问题 1．minZ=2x 1+2x 2+4x 3 六、已知线性规划问题 应用对偶理论证明该问题最优解的目标函数值不大于25
第二章计划 一、名词解释 1、人力资源规划 是根据组织的战略目标，科学预测组织在未来环境变化中的人力资源供给与需求状况，制定必要的人力资源获取、利用、保持和开发策略，确保组织在数量上和质量上的需求，使组织和个人获得长远利益。 2、德尔菲法 是获得专家对影响组织发展的某一问题的一致意见的程序化方法。 一、选择题 1. A 2B 3. C 4. B 5．A 6 B 7 D 二、判断题 1.错误。劳动力构成的重大转变要求管理人员更多地关注人力资源计划，因为这些变化不仅影响员工的招募，而且影响员工选拔、训练、薪酬、激励的方法。 2.错误。在平衡人力资源供给和需求的过程中，不可能是单一的供不应求或者供大于求，企业人力资源还常常出现结构失衡。 3.错误。人力资源计划过程的三个步骤：评价现有的人力资源；预估将来需要的人力资源；制定满足未来人力资源需要的行动方案。 4.正确5．正确。6．正确。 7．错误。人力资源计划的主要内容即预测组织未来人力资源的供需状况，以及考虑这两者之间的匹配 8. 错，不是当前是长久 三、简答题 1. 简述对组织外部人力资源供给进行预测的时候，考虑的主要影响因素有哪些？ 对组织外部人力资源供应进行预测的时候，考虑的主要影响因素有：（1）影响组织外部人力资源供给的全国乃至全球性因素，（2）影响组织外部人力资源供给的地区性因素；（3）政府的方针、政策和法规；（4）劳动力市场发育状况；（5）人口发展趋势；（6）科学技术的发展；（7）劳动力就业意识和择业心理；（8）外部人力资源供给渠道；（9）工会。 2. 组织人力资源需求大于供给时有哪些平衡方法？各种方法分别有什么利弊？
科学出版社《运筹学》教材 第一章引言 第二章线性规划，姜林 第三章对偶规划，姜林 第四章运输问题，姜林 第五章整数规划，姜林 第六章非线性规划，姜林 第七章动态规划，姜林 第八章多目标规划，姜林 第九章图与网络分析，熊贵武 第十章排队论，熊贵武 第十一章库存论，王勇 第十二章完全信息博弈，王勇 第十三章不完全信息博弈，王勇 第十四章决策论与影响图 第十五章运筹学模型的计算机求解 成年人每天需要从食物中摄取的营养以及四种食品所含营养和价格见下表。问 如何选择食品才能在满足营养的前提下使购买食品的费用最小？ 食品名称热量(kcal) 蛋白质(g) 钙（mg）价格（元）猪肉1000 50 400 14 鸡蛋800 60 200 6
大米900 20 300 3 白菜200 10 500 2 营养需求量 2000 55 800 解：设需猪肉、鸡蛋、大米和白菜各需 x1,x2,x3,x4斤。则热量的需求量为： 2000 20090080010004 3 2 1 x x x x 蛋白质 某工厂要做100套钢架，每套有长 3.5米、2.8米和2根2.4米的圆钢组成（如右图）已知原 料长12.3米，问应如何下料使需用的原材料最省。 解：假设从每根 12.3米的原材料上截取 3.5米、2.8米和2根2.4 米，则每根原材料需浪费 1.2米，做100套需浪费材料 120米，现 采用套裁的方法。 方案一二三四五六3.5 2.8 2.4 0 0 5 0 4 0 1 2 1 1 3 0 2 0 2 2 1 1 合计剩余 12 0.3 11.2 1.1 11.5 0.8 11.9 0.4 11.8 0.5 12.2 0.1 现在假设每种方案各下料x i （i=1、2、3、4、5、6），则可列出方程： minZ=0.3x 1+1.1x 2+0.8x 3+0.4x 4+0.5x 5+0.1x 6 约束条件： x 3+x 4+2x 5+2x 6=100 4x 2+2x 3+3x 4+x 6=100 5x 1+x 3+2x 5+x 6=200 ,,,800 50030020040055 102060503000 2009008001000. .23614min 4 3214 3 2 1 4 32 14 32 14321x x x x x x x x x x x x x x x x t s x x x x z
WORD格式可以编辑XXX有限责任公司 人 力 资 源 规 划
目录 第一章总则..........................................................................................1... 第二章人力资源规划的内容..............................................................1.. 第三章人力资源规划的编制..............................................................2.. 第四章附则..........................................................................................5... 附件一人力资源规划程序.................................................................6... 附件二人力资源净需求评估表..........................................................7.. 附件三按类别的人力资源净需求......................................................8.. 附件四人力资源规划表.....................................................................9...
第六章整数规划 用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域(在图上用“×”标出)。 1、 max z=3x1+2x2 . 2x1+3x2≤12 2x1+x2≤9 x1、x2≥0 解： 2、 min f=10x1+9x2 . 5x1+3x2≥45 x1≥8 x2≤10 x1、x2≥0
求解下列整数规划问题 1、 min f=4x1+3x2+2x3 . 2x1-5x2+3x3≤4 4x1+x2+3x3≥3 x2+x3≥1 x1、x2、x3=0或1 解：最优解（0，0，1），最优值：2 2、 min f=2x1+5x2+3x3+4x3 . -4x1+x2+x3+x4≥2 -2x1+4x2+2x2+4x2≥4 x1+x2-x2+x2≥3 x1、x2、x3、x3=0或1 解：此模型没有可行解。 3、max Z=2x1+3x2+5x3+6x4 . 5x1+3x2+3x3+x4≤30 2x1+5x2-x2+3x2≤20 -x1+3x2+5x2+3x2≤40 3x1-x2+3x2+5x2≤25 x1、x2、x3、x3=正整数 解：最优解（0，3，4，3），最优值：47 4、 min z =8x1 +4 x2+3 x3+5 x4+2 x5＋3 x6＋4 x7＋3 x8+4 x9+9 x10+7 x11+ 5 x12 +10 x13+4 x14+2 x15+175 x16+300 x17+375 x18 +500 x19 约束条件x1 + x2+x3≤30 x4+ x5＋ x6-10 x16≤0 x7+ x8＋ x9-20 x17≤0 x10+ x11＋ x12-30 x18≤0 x13+ x14＋ x15-40 x19≤0 x1 + x4+ x7+x10+ x13＝30 x2 + x5+ x8+x11+ x14＝20 x3 + x6+ x9+x12+ x15＝20 x i为非负数（i=1,2…..8） x i为非负整数（i=9,10…..15） x i为为0－1变量（i=16,17…..19） 解：最优解（30，0，0，0，0，0，0，0，0，0，0，0，0，20，20，0，0，0，1），最优值：860 一餐饮企业准备在全市范围内扩展业务，将从已拟定的14个点中确定8个点建立分店，由于地理位置、环境条件不同，建每个分店所用的费用将有所不同，现拟定的14个店的费用情况如下表：
《运筹学》课程学习指南 第二章线性规划模型 （一）学习指导 1．本章的学习内容 1）线性规划模型及其单纯形法 2）线性规划的对偶理论及其灵敏度分析 3）线性规划问题案例建模及讨论 4）递阶练习 2．本章的教学目的 1）掌握线性规划问题数学模型的基本形式； 2）比较熟练地使用单纯形法； 3）了解使用LINGO软件求解线性规划模型的过程； 4）能够利用LINGO软件进行初步的灵敏度分析及拓展研究； 5）具备基本的建模能力。 3．本章的教学重点 1）单纯形法的步骤； 2）利用LINGO软件进行灵敏度分析； 3）基本问题的建模及利用LINGO软件求解并拓展分析。4．本章的教学难点 1）确定入基变量和出基变量的原则； 2）原问题变量与对偶变量之间的关系； 3）利用LINGO软件进行灵敏度分析并对结果给予解释； 4）建立实际问题的数学模型。 5．本章的计划学时数
本章共计10学时，具体分配如下： 1）线性规划模型实例：2学时 2）线性规划问题的数学模型：2学时 3）求解线性规划模型的单纯形法及LINGO程序：2学时 4）线性规划的对偶理论、灵敏度分析及其应用：2学时 5）线性规划问题案例建模及讨论：2学时 （二）学习建议 1．对前期基础扎实，准备继续深造学生的学习建议 1）准确、熟练运用单纯形法求解线性规划模型； 2）掌握相关的理论推导、证明； 3）能够准确地建立一般问题的线性规划模型。 2．对于热衷于运筹学的应用，准备参加数学建模竞赛学生的学习建议1）掌握单纯形法的基本步骤及解题思路； 2）能够对较为复杂实际问题建立线性规划模型； 3）熟练应用LINGO软件求解线性规划问题； 4）能够对实际问题进行拓展研究。 3．对于其他学生的学习建议 1）掌握单纯形法的基本步骤及解题思路并熟练计算； 2）能够准确地建立简单问题的线性规划模型。 第三章线性规划模型 （一）学习指导 1．本章的学习内容 1）运输问题的数学模型 2）表上作业法
教学基本文件模板 课程教学大纲： 《运筹学》课程教学大纲 课程编号： 课程名称：运筹学/Operational Research 课程总学时/学分：72/4 （其中理论60学时，实验12学时） 适用专业：适用本科四年制信息管理与信息系统专业 一、课程简介 本课程的授课对象是信息管理与信息系统专业本科生，属管理类专业专业基础必修课。《运筹学》是以定量分析为主来研究经济管理问题，将工程思想和管理思想相结合，应用系统的、科学的、数学分析的方法，通过建模、检验和求解数学模型获得最优决策方案。本课程的主要内容包括线性规划、运输问题、整数规划、目标规划、动态规划、网络分析等与经济、管理和工程领域密切相关的运筹学分支的基本模型、方法和应用。运用科学的模型化方法来描述、求解和分析问题，从而支持决策。 二、教学目的和任务 本课程旨在使同学们正确、全面地掌握各级管理工作中已被广泛应用、发展比较成熟的最优化理论与方法，并能运用所学理论和方法解决管理工作中出现的各种优化问题，为后续课程奠定定量分析基础。在已学过高等数学、微积分、线性代数等课程基础上学习本课程，通过教授、自学、复习、作业练习、辅导、上机等教学环节达到上述目的。学习中要注意到学科系统性，数学概念和逻辑的严密性、准确性和完整性，但不偏重纯数学方法论证。注重基本概念、基本思路、基本方法、算法步骤的掌握，了解各种方法特点和实用价值，提高建立模型、分析求解能力和技巧。应注重实际应用中建立模型，选择可行求解的理论方法，运用计算机工具求解这三方面训练的有机结合。 三、教学基本要求 信息管理与信息系统专业的学生应系统地学习《运筹学》的全部内容。系统掌握线性规划、运输问题、目标规划、整数规划、动态规划、图与网络分析的理论和方法；能借助Excel、Lingo等电子计算手段，运用所学理论和方法解决实际问题。通过该课程的学习，进一步培养学生的分析问题和解决问题的能力。四、教学内容与学时分配 绪论（2学时） 第一节运筹学的定义与发展简史 1、运筹学名称的来历； 2、运筹学的发展简史。 第二节运筹学研究的基本特征与基本方法
运筹学（Operational Research）复习资料 第一章绪论 一、名词解释 1.运筹学：运筹学是应用分析、试验、量化的方法，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。 二、选择题 1.运筹学的主要分支包括（ABDE ） A图论B线性规划C非线性规划D整数规划E目标规划 2. 最早运用运筹学理论的是（ A ） A . 二次世界大战期间，英国军事部门将运筹学运用到军事战略部署 B . 美国最早将运筹学运用到农业和人口规划问题上 C . 二次世界大战期间，英国政府将运筹学运用到政府制定计划 D . 50年代，运筹学运用到研究人口，能源，粮食，第三世界经济发展等问题上 第二章线性规划的图解法 一、选择题/填空题 1.线性规划标准式的特点： （1）目标函数最大化（2）约束条件为等式（3 决策变量为非负（4 ) 右端常数项为非负2. 在一定范围内，约束条件右边常数项增加一个单位： （1）如果对偶价格大于0，则其最优目标函数值得到改进，即求最大值时，最优目标函数值变得更大，求最小值时最优目标函数值变得更小。 （2）如果对偶价格小于0，则其最优目标函数值变坏，即求最大值时，最优目标函数值变小了；求最小值时，最优目标函数值变大了。 （3）如果对偶价格等于0，则其最优目标函数值不变。 3.LP模型（线性规划模型）三要素： （1）决策变量（2）约束条件（3）目标函数 4. 数学模型中，“s·t”表示约束条件。 5. 将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左端加上松弛变量。 6. 将线性规划模型化成标准形式时，“≥”的约束条件要在不等式左端减去剩余变量。7．下列图形中阴影部分构成的集合是凸集的是A
-16- 第二章 整数规划 §1 概论 1.1 定义 规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。 1.2 整数规划的分类 如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类： 1o 变量全限制为整数时，称纯（完全）整数规划。 2o 变量部分限制为整数的，称混合整数规划。 1.2 整数规划特点 （i ） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况： ①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 ②整数规划无可行解。 例1 原线性规划为 21min x x z += 0,0, 5422121≥≥=+x x x x 其最优实数解为：4 5 min ,45,021===z x x 。 ③有可行解（当然就存在最优解），但最优解值变差。 例2 原线性规划为 21min x x z += 0,0, 6422121≥≥=+x x x x 其最优实数解为：2 3 min ,23,021===z x x 。 若限制整数得：2min ,1,121===z x x 。 （ii ） 整数规划最优解不能按照实数最优解简单取整而获得。 1.3 求解方法分类： （i ）分枝定界法—可求纯或混合整数线性规划。 （ii ）割平面法—可求纯或混合整数线性规划。 （iii ）隐枚举法—求解“0-1”整数规划： ①过滤隐枚举法； ②分枝隐枚举法。 （iv ）匈牙利法—解决指派问题（“0-1”规划特殊情形）。 （v ）蒙特卡洛法—求解各种类型规划。 下面将简要介绍常用的几种求解整数规划的方法。 §2 分枝定界法 对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，
第二讲人力资源战略 一、人力资源战略的定义 人力资源战略是指企业为实现其战略目标而制定的一系列有关人力与人才资源开发与管理的总体规划，是企业发展战略的重要组成部分，是抓住组织的战略目标和目的，并将他们转化为前后一致的、整体化的、完善的员工管理计划和政策，是“从人力资源的“质”和“量”入手，评估目前人力资源的质量与企业目前及未来发展变化所需之间的差距，并能够满足这些要求的过程”。 人类已经进入知识经济时代。这个时代的市场竞争归根结底是人才的竞争，因此企业的人力资源战略核心应该是以人为本。所谓以人为本就是要符合人的本性需求。马斯洛把人的需求分为五个层次,即：生理、安全、归属和爱、自尊、自我实现。因此，现代企业的以人为本人力资源战略就应该充分考虑到人的需求层次，并通过各种渠道去满足不同层次的需求，只有这样才能真正的吸引人才、留住人才。事实上，任何一个层次的需求我们都是不能忽略的。 1、生理需求 首先在生理需求方面，体现在公司的人力资源战略上就是要建立合理的薪酬、福利待遇体系，使员工寝食无忧，只有这样他才能够全身心的投入工作。沃尔玛的人力资源战略就非常重视员工生理需求的充分满足，并将此种需求与企业利益挂钩，实现双赢。利润分享计划：每个在沃尔玛工作两年以上的并且每年工作1000小时的员工都有资格分享公司当年利润。此项计划使员工的工作热情空前高涨。之后，山姆又推出了雇员购股计划，让员工通过工资扣除的方式，以低于市值15%的价格购买股票。这样员工利益与公司利益休戚相关，实现了真正意义上的“合伙”。沃尔玛公司还推行了许多奖金计划，最为成功的就是损耗奖励计划。如果某家商店能够将损耗维持在公司的既定目标之内，该店每个员工均可获得奖金，最多可达200美元。这一计划也大大降低了公司的损耗率，节约了经营开支。 2、安全需求 人们在满足了基本的生理需求后，就会产生新的需求———安全需求，主要包括安全、稳定、依赖、免收恐吓、焦躁与混乱的折磨，对体制法律、秩序、界限的依赖等等。 那么具体体现在人力资源战略中，就是要为员工建立一个相对安全、稳定的工作大环境，这个大环境既包括物质环境也包括精神环境，例如公司的各种安全防护措施要完善，工作环境要尽量保证员工的身体健康；制度的建立与实施要考虑到员工的感受；保证一个相对稳定的员工队伍，频繁裁人的公司会让员工失去稳定感，从而会诱发主动跳槽等等。 3、归属的需求 现代社会中各方面压力的增大加剧了人们对于归属感的渴望，人们希望能够真正团结起来，共同地应对外来危险，共同地面对同一件事情，人们会在别人对自己的协助中获得满足。广大的足球球迷在观看比赛中所表现出的巨大热情、同仇敌忾的凝聚力，正是现代人追求归属感的有力证据。 那么，作为企业的人力资源战略，要想最大限度激发员工的工作热情，就必须通过各种方式让员工在企业中找到归属感。例如丰田公司建立的“公司内的团体活动”就使员工找到了归属感。它设立的“亲睦团体”是同学、同乡或具有相同兴趣爱好的人加入到其中，为了避免机构庞大，它还按照各种条件分成更小的团体，这样可以使参加者更加随意，亲近地接触，这增加员工的归属感，培养团队意识很。每个人都可以同时属于多个团体，为了这种聚会，公司建造了体育馆、集会大厅、会议室等设施，供自由使用，在这种团体中领导人是互选的，且采取轮换制。这些团体都有一个共同的条件，那就是把这些团体作为会员相互之间沟通亲睦、自我启发、有效地利用业余时间和不同职务的会员相互交流的场所。这些团体都
运筹学知识点： 绪论 1.运筹学的起源 2.运筹学的特点 第一章线性规划及单纯形法 1.规划问题指生产和经营管理中如何合理安排，使人力、物力等各种资源得到充分利用，获得最大效益。 2.规划问题解决两类问题：一是给定一定数量的人力、物力等资源，研究如何充分利用，以发挥其最大效果；二是已给定计划任务，研究如何统筹安排，用最少的人力和物力去完成。 3.规划问题的数学模型包含三个组成要素：决策变量、目标函数（单一）、约束条件（多个）。 线性规划问题的数学模型要求：决策变量为可控的连续变量，目标函数和约束条件都是线性的。 4.线性规划问题的标准形式：目标函数为极大、约束条件为等式、决策变量为非负、变量为非负 5.划标准型时添加的松驰变量、剩余变量和人工变量 6.理解可行解、最优解、基、基解、基可行解等概念，且掌握各类解间的关系 7.用图解法理解线性规划问题的四种解的情况：无穷多最优解、无界解、无可行解、唯一最优解 8.用图解法只有解决两个变量的决策问题 9.线性规划问题存在可行解，则可行域是凸集。 10.线性规划问题的基可行解对应线性规划问题可行域的顶点。 11.线性规划问题的解进行最优性检验：当所有的检验数小于等于零时为最优解；尤其当检验数小于零时（即不等于零）有唯一最优解；当某个非基变量检验数为时，有无穷多最优解；当存在某个检验数大于零且对应的系数又小于等于零时，有无界解。 12.单纯形法的计算过程，可能出计算题 13.入单纯形表前首先要化成标准形式。 14.确定换出变量时根据θ值最小原则，且要求公式中对应的系数大于零。 15.当线性规划中约束条件为等式或大于等于时，划为标准型后，系数矩阵中又不包含单位矩阵时，需要添加人工变量构造一个单位矩阵作为基。 16.人工变量的系数为足够大的一个负值，用—M代表 17.一般线性规划问题的数学建模题（生产计划问题、人才资源分配问题、混合
第二章 整数规划 §1 概论 1.1 定义 规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。 1.2 整数规划的分类 如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类： 1o 变量全限制为整数时，称纯（完全）整数规划。 2o 变量部分限制为整数的，称混合整数规划。 1.3 整数规划特点 （i ） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况： ①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 ②整数规划无可行解。 例1 原线性规划为 21m i n x x z += 0,0, 5422121≥≥=+x x x x 其最优实数解为：4 5 min ,45,021===z x x 。 ③有可行解（当然就存在最优解），但最优解值变差。 例2 原线性规划为 21m i n x x z += 0,0, 6422121≥≥=+x x x x 其最优实数解为：2 3 min ,23,021===z x x 。 若限制整数得：2min ,1,121===z x x 。 （ii ） 整数规划最优解不能按照实数最优解简单取整而获得。 1.4 求解方法分类： （i ）分枝定界法—可求纯或混合整数线性规划。 （ii ）割平面法—可求纯或混合整数线性规划。 （iii ）隐枚举法—求解“0-1”整数规划： ①过滤隐枚举法； ②分枝隐枚举法。 （iv ）匈牙利法—解决指派问题（“0-1”规划特殊情形）。 （v ）蒙特卡洛法—求解各种类型规划。 下面将简要介绍常用的几种求解整数规划的方法。 §2 分枝定界法 对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子
第五章整数规划 一、填空题 1．用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的（）。 2．在分枝定界法中，若选Xr=4／3进行分支，则构造的约束条件应为（）。 3．已知整数规划问题P0，其相应的松驰问题记为P0’，若问题P0’无可行解，则问题P。（）。 4．在0 - 1整数规划中变量的取值可能是（）或（）。 5．对于一个有n项任务需要有n个人去完成的分配问题，其解中取值为1的变量数为（）个。 6．分枝定界法和割平面法的基础都是用（）求解整数规划。 7．若在对某整数规划问题的松驰问题进行求解时，得到最优单纯形表中，由X。所在行得X1+1／7x3+2／7x5=13／7，则以X1行为源行的割平面方程为（）。 8．在用割平面法求解整数规划问题时，要求全部变量必须都为（）。 9．用（）求解整数规划问题时，若某个约束条件中有不为整数的系数，则需在该约束两端扩大适当倍数，将全部系数化为整数。 10．求解纯整数规划的方法是割平面法。求解混合整数规划的方法是（）。 11．求解0—1整数规划的方法是隐枚举法。求解分配问题的专门方法是（）。 12．在应用匈牙利法求解分配问题时，最终求得的分配元应是（）。 13.分枝定界法一般每次分枝数量为（）个. 二、单选题 1．整数规划问题中，变量的取值可能是（）。 A．整数B．0或1C．大于零的非整数D．以上三种都可能 2．在下列整数规划问题中，分枝定界法和割平面法都可以采用的是A（）。 A．纯整数规划B．混合整数规划C．0—1规划D．线性规划 3．下列方法中用于求解分配问题的是（）。 A．单纯形表B．分枝定界法C．表上作业法D．匈牙利法 三、多项选择
《运筹学》综合练习题 第一章线性规划及单纯形法 1、教材43页——44页1.1题 2、教材44页1.4题 3、教材45页1.8题 4、教材46页1.13题 5、教材46页1.14题 6、补充：判断下述说法是否正确 ●LP问题的可行域是凸集。 ●LP问题的基本可行解对应可行域的顶点。 ●LP问题的最优解一定是可行域的顶点,可行域的顶点也一定是最优解。 ●若LP 问题有两个最优解,则它一定有无穷多个最优解. ●求解LP问题时,对取值无约束的自由变量，通常令 " - ' = j j j x x x ,其中∶ ≥ " ' j j x x ,在用单纯 形法求得的最优解中,不可能同时出现 " ' j j x x . ●当用两阶段法求解带有大M的LP模型时，若第一阶段的最优目标函数值为零，则可断言原LP模型 一定有最优解。 7、补充：建立模型 （1）某采油区已建有n个计量站B1，B2…B n，各站目前尚未被利用的能力为b1，b2…b n（吨液量/日）。为适应油田开发的需要，规划在该油区打m口调整井A1，A2…A m，且这些井的位置已经确定。根据预测，调整井的产量分别为a1，a2…a m（吨液量/日）。考虑到原有计量站富余的能力，决定不另建新站，而用原有老站分工管辖调整井。按规划要求，每口井只能属于一个计量站。假定A i到B j的距离d ij已知，试确定各调整井与计量站的关系，使新建集输管线总长度最短。 （2）靠近某河流有两个化工厂(见附图)，流经第一个工厂的河流流量是每天500万立方米；在两个工厂之间有一条流量为每天200万立方米的支流。第一个工厂每天排放工业污水2万立方米；第二个工厂每天排放工业污水1.4万立方米。从第一个工厂排出的污水流到第二个工厂之前，有20%可自然净化。根据环保要求，河流中工业污水的含量不应大于0.2%，若这两个工厂都各自处理一部分污水，第一个工厂的处理成本是1000元/万立方米，第二个工厂的处理成本是800元/万立方米。试问在满足环保要求的条件下，每厂各应处理多少污水，才能使总的污水处理费用为最小?建立线性规划模型。 第 1 页共 6 页
第一章人力资源规划概述 1.案例分析/论述题 人力资源规划的过程： 从宏观上包括人力资源规划制定和人力资源规划实践。 从中观上包括人力资源态势分析、人力资源发展预测、人力资源规划编制、人力资源规划实施、人力资源规划控制和人力资源规划修订。 人力资源规划的主要步骤进行阐释：①人力资源信息收集②人力资源现状分析③人力资源发展预测④人力资源战略选择⑤人力资源对策组合⑥人力资源规划的实施与控制⑦人力资源规划的评价与修订 2.人力资源规划的分类 按规划设计的时间期限可以分为短期（1-2年）、中期（3-5年）、和长期（10年）规划 按规划的层次可以分为总体规划和业务规划 3.人力资源规划的功能 ①企业战略规划的重要组成部分 ②实现人力资源管理职能的保证 ③企业管理的重要依据 ④确保企业对人力资源的需求 ⑤节省人工成本 ⑥调动员工积极性 4.人力资源规划的原则 ①战略性原则②系统性原则③服务性原则④人本性原则⑤动态性原则 5.人力资源规划的常用方法 关键成功因素法、战略集合转移法、企业系统规划法（企业战略因素，这个不常用，如果出选择选不是常用方法的就选这个） 6.人力资源规划的影响因素 地域因素、人口因素、经济因素、技术因素、法律因素 7.人力资源规划：是一种活动，它从战略的角度出发去探索和掌握人力资源系统的发展运动规律，并运用这些规律去规定和控制未来时期人力资源系统的运动状态。 8.人力资源规划的特点：动态性，系统性，超前性，独特性 第二章人力资源信息的收集和处理 1.人力资源信息的分类 ①按照人力资源信息的来源划分：部信息和外部信息 ②按人力资源信息的获取途径划分：原始信息和处理信息 ③按人力资源信息的功能划分：人，事，管理过程 2.人力资源指标体系 人力资源指标：描述各种人力资源现象在的质的规定性和外在的量度，通常用指标名称和指标数值表示。 人力资源指标体系的功能： ①描述功能②解释功能③评价功能④监测功能⑤预警功能 3.人力资源信息的来源：部：文档信源，数据库存信源 外部：权威机构信源，网络信源 4.人力资源信息收集的步骤 ①确定信息收集的要求和目的②确定信息收集的对象③拟定调查提纲，明确调查容④信息收
作业题答案 第二章单纯形法 3.两阶段法求解： 解：引入松弛变量x3，x4≥0，人工变量x5，x6≥0,得第一阶段模型： Min z= x5+x6 s.t. x1+2x2-x3+x5＝80 3x1+x2-x4+x6＝75 x1, x2, X3, X4X5, X6≥0 目标函数求minZ，根据min（-4，-3）=-4得x1为换入变量，θ=min{80/1,75/3}=25得到x6为换 min（-5/3，-1/3）=-5/3,得x2为换入变量，θ=min{55/(5/3),25/(1/3)}=33得到x5为换出变量。 所有Cj-Zj≥0，取得最优解，人工变量x5=x6=0，故有最优解，转入第二阶段： 目标函数变为 Min z= 4x1 +6x2
所有检验数非负，故已取得最优解（x1，x2，x3，x4）=（14，33，0，0），MinZ=4*14+6*33=254. 4、M法求解，并讨论 解：引入松弛变量x4和x5，x6，人工变量x7，得到线性规划标准形： max z= 10x1+15x2+12x3 -Mx7 s.t. 5x1+3x2+x3+x4=9 -5x1+6x2+15x3 +x5=15 2x1+x2+x3 -x6+x7= 5 x1, x2, x3x4x5x6X7≥0 构造初始单纯形表： Max(Cj-Zj)=（10+2M，15+M，12+M）=10+2M，选择x 做换入变量，根据最小比值法 1 则θ=min{9/5,5/2}=9/5,选择x4做换出变量，在（1，1）处进行基变换得： Max(Cj-Zj)=（10+3M/5）>0，选择x 做换入变量，根据最小比值法则 3 θ=min{(9/5)/(1/5),24/16,(7/5)/(3/5)}=3/2,选择x5做换出变量，在（2，3）处进行基变换得： 所有检验数≤0，所以已得最优解。注意到人工变量x7≠0，故没有可行解。
《运筹学》课程练习题 第一章 线性规划及单纯形法 1、教材43页——44页1.1题 2、教材44页1.4题 3、教材45页1.8题 4、教材46页1.13题 5、教材46页1.14题 6、补充：判断下述说法是否正确 ● LP 问题的可行域是凸集。 ● LP 问题的基本可行解对应可行域的顶点。 ● LP 问题的最优解一定是可行域的顶点,可行域的顶点也一定是最优解。 ● 若LP 问题有两个最优解,则它一定有无穷多个最优解. ● 求解LP 问题时,对取值无约束的自由变量，通常令 "-'=j j j x x x ,其中∶ ≥"' j j x x ,在用单纯形法求得的最优解中,不可能同时出现 "' j j x x . ● 当用两阶段法求解带有大M 的LP 模型时，若第一阶段的最优目标函数值为零， 则可断言原LP 模型一定有最优解。 7、补充：建立模型 （1）某采油区已建有n 个计量站B 1，B 2…B n ，各站目前尚未被利用的能力为b 1，b 2…b n （吨液量/日）。为适应油田开发的需要，规划在该油区打m 口调整井A 1，A 2…A m ，且这些井的位置已经确定。根据预测，调整井的产量分别为a 1，a 2…a m （吨液量/日）。考虑到原有计量站富余的能力，决定不另建新站，而用原有老站分工管辖调整井。按规划要求，每口井只能属于一个计量站。假定A i 到B j 的距离d ij 已知，试确定各调整井与计量站的关系，使新建集输管线总长度最短。 （2）靠近某河流有两个化工厂(见附图)，流经第一个工厂的河流流量是每天500万立方米；在两个工厂之间有一条流量为每天200万立方米的支流。第一个工厂每天排放工业污水2万立方米；第二个工厂每天排放工业污水1.4万立方米 。从第一个工厂排出的污水流到第二个
第一章 第一章 1. 建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。决策变量（Decision Variable）是决策问题待定的量值，取值一般为非负；约束条件（Constraint Conditions）是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数（Objective Function）是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。 2.（1）设立决策变量； （2）确定极值化的单一线性目标函数； （3）线性的约束条件：考虑到能力制约，保证能力需求量不能突破有效供给量； （4）非负约束。 3.（1）唯一最优解：只有一个最优点 （2）多重最优解：无穷多个最优解 （3）无界解：可行域无界，目标值无限增大 （4）没有可行解：线性规划问题的可行域是空集 无界解和没有可行解时，可能是建模时有错。 4. 线性规划的标准形式为：目标函数极大化，约束条件为等式，右端常数项bi≥0 , 决策变量满足非负性。 如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。 5. 可行解：满足约束条件AX =b,X≥0的解，称为可行解。 基可行解：满足非负性约束的基解，称为基可行解。 可行基：对应于基可行解的基，称为可行基。 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。 6. 计算步骤： 第一步，确定初始基可行解。 第二步，最优性检验与解的判别。 第三步，进行基变换。 第四步，进行函数迭代。 判断方式： 唯一最优解：所有非基变量的检验数为负数，即σj< 0 无穷多最优解：若所有非基变量的检验数σj≤ 0 ，且存在某个非基变量xNk 的检验数σk= 0 ，让其进基，目标函数的值仍然保持原值。如果同时存在最小θ值，说明有离基变量，则该问题在两个顶点上同时达到最优，为无穷多最优解。无界解：若某个非基变量xNk 的检验数σk> 0 ，但其对应的系数列向量P k' 中，每一个元素a ik' (i=1,2,3,…,m)均非正数，即有进基变量但找不到离基变量。
第二章 整数规划 §1 概论 1.1 定义 规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。 1.2 整数规划的分类 如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类： 1o 变量全限制为整数时，称纯（完全）整数规划。 2o 变量部分限制为整数的，称混合整数规划。 1.2 整数规划特点 （i ） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况： ①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 ②整数规划无可行解。 例1 原线性规划为 21m in x x z += 0,0, 5422121≥≥=+x x x x 其最优实数解为：4 5 min ,45,021===z x x 。 ③有可行解（当然就存在最优解），但最优解值变差。 例2 原线性规划为 21m in x x z += 0,0, 6422121≥≥=+x x x x 其最优实数解为：2 3 min ,23,021===z x x 。 若限制整数得：2m in ,1,121===z x x 。 （ii ） 整数规划最优解不能按照实数最优解简单取整而获得。 1.3 求解方法分类： （i ）分枝定界法—可求纯或混合整数线性规划。 （ii ）割平面法—可求纯或混合整数线性规划。 （iii ）隐枚举法—求解“0-1”整数规划： ①过滤隐枚举法； ②分枝隐枚举法。 （iv ）匈牙利法—解决指派问题（“0-1”规划特殊情形）。 （v ）蒙特卡洛法—求解各种类型规划。 下面将简要介绍常用的几种求解整数规划的方法。 §2 分枝定界法 对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，
第二章整数规划 （部分或全部）限制为整数时，称为整数规划。若在线性规划模型中， 则称为整数线性规划。 目前所流行的求解整数规划的方法， 往往只适 目前还没有一种方法能有效地求解一切整数规划。 1.2 整数规划的分类 如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类: 1。 变量全限制为整数时，称纯（完全）整数规划。 2。 变量部分限制为整数的，称混合整数规划。 1.2整数规划特点 （i ）原线性规划 有最优解， ① 原线性规划最优解全是整数， ② 整数规划无可行解。 例1原线性规划为 min § 2分枝定界法 对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系 统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子 集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题） ，这称 为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝， §1概论 1.1定义 规划中的变量 变量限制为整数， 用于整数 线性规划。 当自变量限制为整数后， 其整数规划解出现下述情况: 则整数规划最优解与线性规划最优解一致。 4X 2 5, X 1 c 5 . X 1 0,x 2 -,mi nz 4 ③有可行解（当然就存在最优解） 例2原线性规划为 min 2X 2x i 其最优实数解为: 0, X 2 0 5 O 4 ，但最优解值变差。 其最优实数解为: X 1 X i 6, X 2 0,X 2 X i 0, 3 . —,mi X 2 3 O 2 2 若限制整数得： （ii ）整数规划最优解不能按照实数最优解简单取整而获得。 1. 3 求解 方法分类： （i ）分枝定界法一可求纯或混合整数线性规划。 （ii ） 割平面法一可求纯或混合整数线性规划。 （iii ） 隐枚举法一求解“ 0-1 ”整数规划： ① 过滤隐枚举法； ② 分枝隐枚举法。 （iv ） 匈牙利法一解决指派问题（“ 0-1 ”规划特殊情形）。 （V ）蒙特卡洛法一求解各种类型规划。 下面将简要介绍常用的几种求解整数规划的方法。 X i 1,X 2 1,min z z X-I X 2