每个线性规划问题都有一个与之对应的对偶问题。
简单考虑如下的生产分配问题
我们有下面的对偶问题：
该问题的任意一个可行解对应的目标函数值都不小于原问题的目标函数值，但是两个问题的最优目标函数值（有限）相同。
一般而言：
1、每个对偶变量对应原问题的一个约束条件
2、原问题是等式约束则对偶变量无不等式约束（非负约束）
3、原问题是不等式约束则对偶变量有不等式约束
4、原问题变量和对偶问题约束条件同样具有如上规律
任何原问题和对偶问题之间都存在下述相互关系：
弱对偶性：原对偶问题任何可行解的目标值都是另一问题最优目标值的界（推论：原对偶问题目标值相等的一对可行解是各自的最优解）
强对偶性：原对偶问题只要有一个有最优解，另一个就有最优解，并且最优目标值相等
互为对偶的线性规划问题解之间关系有如下四种：
原问题与对偶问题之间存在互补松弛性：
一般形式的线性规划互补松弛定理：
经济学中有所谓影子价格的概念：如果增加某些
约束条件的数值，原问题的最优目标值应该增加，增加单位约束使得原问题最优值的增加量为该约束条件的影子价格。影子价格可以由对偶线性规划问题清楚地描述：
对偶单纯形法：
当线性规划问题中地某个约束条件或价值变量中含有参数时，原问题称之为参数线性规划，它有如下的处理方法：
1）固定λ的数值解线性规划问题
2）确定保持当前最优基不变的λ的区间
3）确定λ在上述区间附近的最优基，回2）
如以下问题：
在实际问题中，许多变量以及它们的约束条件往往是离散的，或者说限定在整数域上，这便引入了整数线性规划的概念。
具体而言，整数线性规划包含纯整数线性规划（所有变量是整数变量）、混合整数线性规划（同时包含整数和非整数变量）、0-1型整数线性规划（变量等于0或1）
去除整数规划的整数约束后的问题称为其松弛问题。一般情况，原问题的解并不一定是其松弛问题的最优解附近的整数解，例如：
通常的解决办法是在松弛问题的基础上出发，不断地引入整数的约束条件，从而求出整数规划的解。
第四章整数规划
第三节分支定界法第一节整数规划的数学模型及解的特点
第四节0-1型整数规划
第五节指派问题第二节解纯整数规划的割平面法
整数规划的数学模型及解的特点
一、整数规划数学模型的一般形式
要求一部分或全部决策变量必须取整数值的规划问题称
为整数规划( integer programming，简记IP )。
不考虑整数条件，由余下的目标函数和约束条件构成的
规划问题称为该整数规划问题的松弛问题(slack problem)。
若松弛问题是一个线性规划，则称该整数规划问题为整
数线性规划( integer liner programming )。
本章仅讨论整数线性规划。
n
jjjxcz1min)max(或
中部分或全部取整数jjn
jijij
xnjxmibxa
),,1(0),,1(),(
1
n
jjjxcz1min)max(或
),,1(0),,1(),(
1njxmibxa
jn
jijij
松弛问题为
1. 纯整数线性规划(pure integer liner programming )：
2. 混合整数线性规划(mixed integer liner programming)：
3. 0-1型整数线性规划( zero-one integer liner programming)：指全部决策变量都必须取整数值的整数线性规划。有时，
也称为全整数规划。
指决策变量中有一部分必须取整数值，另一部分可以不
取整数值的整数线性规划。
指决策变量只能取值0 或1 的整数线性规划。
例：某服务部门各时段（每2小时为一时段）需要服务员人
数见表，按规定服务员连续工作8小时（即四个时段）为一
班。现在要求安排服务员的工作时间，使服务部门服务员总数最少。
时段12345678
服务员最少数目10891113853设在第j 时段开始上班的服务员人数为xj。由于在第j 时段开始上班的服务员将在第（j+3）时段结束时下班，故服务员的数量只需要考虑x1，x2，x3，x4，x5。
第一章
1. 运筹学的主要分支包括（ ）答案:非线性规划;整数规划;图论;线性规划;目标规划
2. 运筹学是应用系统的、科学的、数学分析的方法，通过建模、检验和求解数学模型而获得最优决策的科学。答案:对
3. 运筹学是用数学方法研究各种系统中最优化问题的科学，它主要用数学模型来求得合理运用现有条件的最优方案，为决策者提供科学决策的依据。答案:对
4. 运筹学着重以管理、经济活动方面的问题及解决这些问题的原理和方法作为研究对象。答案:对
5. 制定决策是运筹学应用的核心，而（ ）则是运筹学方法的精髓。答案:建立模型
6. 运筹学可用（ ）来进行概括。答案:寻优科学
7. 运筹学的简称是（ ）。答案:OR
8. 下列哪一项不是运筹学的特点（ ）。答案:主观的
9. 下列哪一项不是运筹学的研究步骤（ ）。答案:实施模型
10. 运筹学模型是以（ ）模型为其主要形式。答案:数学
第二章
1. 线性规划问题的一般模型中不能出现等式约束。答案:错
2. 用图解法求最优解时，只需求出可行域顶点对应的目标值，通过比较大小，就能找出最优解。答案:对
3. 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。答案:对
4. 单纯形法计算中，如不按最小比值原则选取换出变量,则在下一个解中至少有一个基变量的值为负。答案:对
5. 单纯形法的迭代运算过程是从一个可行解转换到目标函数值更大的另一个可行解。答案:错
6. 检验数λj表示非基变量xj增加一个单位时目标函数值的改变量。答案:对
7. 利用单纯形法求解线性规划问题的过程中，所有基变量的检验数必为零。答案:对
8. 若某个bk≤0, 化为标准形式时原不等式( )。答案:两边同乘负1
9. 将线性规划问题转化为标准形式时，下列说法不正确的是：答案:若约束条件为＝，则要增加一个人工变量
10. 标准形式的线性规划问题，其可行解（ ）是基本可行解，最优解一定是可行解。答案:不一定
一、单选题
1、下列说法正确的是（ ）。
A.分枝定界法在处理整数规划问题时，借用线性规划单纯形法的基本思想，在求相应的线性模型解的同时，逐步加入对各变量的整数要求限制，从而把原整数规划问题通过分枝迭代求出最优解
B.用割平面法求解整数规划问题，构造的割平面有可能切去一些不属于最优解的整数解
C.用分枝定界法求解一个极大化的整数规划时，当得到多于一个可行解时，通常可任取其中一个作为下界，再进行比较剪枝
D.整数规划问题最优值优于其相应的线性规划问题的最优值
正确答案：A
2、整数规划的最优解中，决策变量满足（ ）。
A.决策变量不是整数
B.没有要求
C.决策变量至少有一个是整数
D.决策变量必须都是整数
正确答案：D
3、下列（ ）可以求解指派问题。
A.梯度法
B.牛顿法
C.单纯形法
D.匈牙利法 正确答案：D
4、整数规划中，通过增加线性约束条件将原规划可行域进行切割，切割后的可行域的整数解正好是原规划的最优解的方法是（ ）。
A.隐枚举法
B.0-1规划法
C.分支定界法
D.割平面法
正确答案：D
5、标准指派问题（m人，m件事）的规划模型中，有（ ）个决策变量。
A.都不对
B. m*m
C. m
D.2m
正确答案：B
二、判断题
1、匈牙利法可以直接求解极大化的指派问题。（ ）
正确答案：×
2、整数规划的可行解集合是离散型集合。（ ）
正确答案：√
3、用分支定界法求一个极大化的整数规划时，任何一个可行解的目标函数值是该问题的目标函数值的下界。（ ） 正确答案：√
4、用分支定界法求一个极大化的整数规划时，当得到多于一个可行解时，通常可以任取一个作为下界值，在进行比较和剪枝。（ ）
正确答案：×
5、用割平面求纯整数规划时，要求包括松弛变量在内的全部变量都取整数。（ ）
正确答案：√
