下载文档原格式
一、单选题1、下列说法正确的是（）。
A.分枝定界法在处理整数规划问题时，借用线性规划单纯形法的基本思想，在求相应的线性模型解的同时，逐步加入对各变量的整数要求限制，从而把原整数规划问题通过分枝迭代求出最优解B.用割平面法求解整数规划问题，构造的割平面有可能切去一些不属于最优解的整数解C.用分枝定界法求解一个极大化的整数规划时，当得到多于一个可行解时，通常可任取其中一个作为下界，再进行比较剪枝D.整数规划问题最优值优于其相应的线性规划问题的最优值正确答案：A2、整数规划的最优解中，决策变量满足（）。
A.决策变量不是整数B.没有要求C.决策变量至少有一个是整数D.决策变量必须都是整数正确答案：D3、下列（）可以求解指派问题。
A.梯度法B.牛顿法C.单纯形法D.匈牙利法4、整数规划中，通过增加线性约束条件将原规划可行域进行切割，切割后的可行域的整数解正好是原规划的最优解的方法是（）。
A.隐枚举法B.0-1规划法C.分支定界法D.割平面法正确答案：D5、标准指派问题（m人，m件事）的规划模型中，有（）个决策变量。
A.都不对B. m*mC. mD.2m正确答案：B二、判断题1、匈牙利法可以直接求解极大化的指派问题。
（）正确答案：×2、整数规划的可行解集合是离散型集合。
（）正确答案：√3、用分支定界法求一个极大化的整数规划时，任何一个可行解的目标函数值是该问题的目标函数值的下界。
（）4、用分支定界法求一个极大化的整数规划时，当得到多于一个可行解时，通常可以任取一个作为下界值，在进行比较和剪枝。
（）正确答案：×5、用割平面求纯整数规划时，要求包括松弛变量在内的全部变量都取整数。
（）正确答案：√。
运筹学整数规划运筹学是研究在资源有限的条件下，如何进行决策和优化的一门学科。
整数规划是运筹学中的一个重要分支，它解决的是决策变量必须为整数的问题。
整数规划在实际问题中具有广泛的应用，如生产计划、设备配置、选址问题等。
整数规划问题的数学模型可以表示为：max/min c^T xs.t. Ax ≤ bx ≥ 0x ∈ Z其中，c是目标函数的系数矩阵，x是决策变量的向量，A是约束条件的系数矩阵，b是约束条件的向量，Z表示整数集合。
整数规划问题与线性规划问题相似，但整数规划问题的约束条件多了一个整数限制，使得问题的解空间变得更为复杂。
由于整数规划问题的NP-hard性质，求解整数规划问题是一项困难的任务。
求解整数规划问题的常用方法有分支定界法、割平面法和启发式算法等。
分支定界法是一种穷举搜索的方法，它通过将整数规划问题不断分割成更小的子问题，从而逐步搜索解空间，直到找到最优解。
分支定界法对于规模较小的问题比较有效，但对于大规模复杂问题，效率较低。
割平面法是一种通过添加新的约束条件来减少解空间的方法。
它利用线性松弛问题（将整数约束条件放宽为线性约束条件）的解来构造有效的割平面，从而逐步缩小解空间，找到最优解。
割平面法通常比分支定界法更有效，但对于某些问题，可能需要添加大量的割平面才能收敛到最优解。
启发式算法是一种基于经验和启发式搜索的方法。
它通过设置初始解、搜索策略和邻域搜索等步骤，来快速找到近似最优解。
常见的启发式算法有遗传算法、模拟退火算法和禁忌搜索算法等。
启发式算法虽然不能保证找到全局最优解，但能够在可接受的时间内找到较优解。
综上所述，整数规划作为运筹学中的重要分支，解决的是决策变量必须为整数的问题。
整数规划问题具有广泛的应用，但由于其NP-hard性质，求解过程较为困难。
常用的求解方法包括分支定界法、割平面法和启发式算法等。
这些方法各有优劣，根据具体问题的特点选择合适的方法进行求解。
运筹学中的整数规划问题分析运筹学是运用数学和定量分析方法，通过对系统的建模和优化，来解决实际问题的学科。
其中整数规划是运筹学中的一个重要分支，它在许多实际情况中得到广泛应用。
本文将对整数规划问题进行分析，并探讨其解决方法与应用领域。
一、整数规划问题定义及特点整数规划是一类线性规划问题的扩展，其目标函数和约束条件中的变量取值限定为整数。
通常，整数规划问题可以形式化表示为：Max/Min Z = c₁x₁ + c₂x₂ + ... + cₙxₙs.t.a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂...aₙ₁x₁ + a₂₂x₂ + ... + aₙₙxₙ ≤ bₙx₁, x₂, ..., xₙ ∈ Z其中，Z为目标函数值，x₁, x₂, ..., xₙ为待求解的整数变量，c₁, c₂, ..., cₙ为目标函数的系数，aᵢₙ为约束条件的系数，b₁, b₂, ..., bₙ为约束条件的右端常数。
整数规划问题的特点在于整数约束条件的引入，使其解空间变得有限，增加了问题的复杂性。
与线性规划问题相比，整数规划问题更接近实际情况，能够更准确地描述和解决很多实际问题。
二、整数规划问题的解决方法解决整数规划问题的方法主要有以下几种：穷举法、剪枝法、分支定界法、动态规划法等。
具体使用哪种方法需要根据问题的规模和特点来确定。
1. 穷举法是最简单直观的方法，通过枚举搜索整数解空间中的每一个可能解来寻找最优解。
然而，由于整数解空间往往非常大，这种方法在实际问题中往往是不可行的。
2. 剪枝法是一种通过对解空间进行剪枝操作，减少搜索空间的方法。
通过合理选择剪枝条件，可以避免对明显无解的解空间进行搜索，从而提高求解效率。
3. 分支定界法是一种将整数规划问题不断分解为子问题，并对子问题进行界定的方法。
通过不断缩小问题规模，并计算上下界确定最优解的位置，可以有效地求解整数规划问题。
第５章整数规划（割平面法）求解整数规划问题：Max Z=3x1+2x22x1+3x2≤144x1+2x2≤18x1,x2≥0，且为整数解：首先，将原问题的数学模型标准化，这里标准化有两层含义：（1）将不等式转化为等式约束，（2）将整数规划中所有非整数系数全部转化为整数，以便于构造切割平面。
从而有：Max Z=3x1+2x22x1+3x2+x3=142x1+x2+x4=9x1,x2≥0，且为整数利用单纯形法求解，得到最优单纯形表，见表1：表1最优解为：x1=13/4, x2=5/2, Z=59/4根据上表，写出非整数规划的约束方程，如：x2+1/2x3-1/2x4=5/2 (1)将该方程中所有变量的系数及右端常数项均改写成“整数与非负真分数之和”的形式，即：(1+0)x2+(0+1/2)x3+(-1+1/2)x4=2+1/2把整数及带有整数系数的变量移到方程左边，分数及带有分数系数的变量称到方程右边，得：x2 - x4-2 =1/2-(1/2x3+1/2x4) (2)由于原数学模型已经“标准化”，因此，在整数最优解中，x2和x4也必须取整数值，所以(2)式左端必为整数或零，因而其右端也必须是整数。
又因为x3,x4 0，所以必有：1/2-(1/2x3+1/2x4)<1由于(2)式右端必为整数，于是有：1/2-(1/2x3+1/2x4)≤0 (3)或x3+x4≥1 (4)这就是考虑整数约束的一个割平面约束方程，它是用非基变量表示的，如果用基变量来表示割平面约束方程，则有：2x1+2x2≤11 (5)从图1中可以看出，(5)式所表示的割平面约束仅割去线性规划可行域中不包含整数可行解的部分区域，使点E(3.5，2)成为可行域的一个极点。
图1在(3)式中加入松弛变量x5，得：-1/2x3-1/2x4+x5=-1/2 (6)将(6)式增添到问题的约束条件中，得到新的整数规划问题：Max Z=3x1+2x22x1+3x2+x3=142x1+x2+x4=9-1/2x3-1/2x4+x5=-1/2x i≥0，且为整数，i=1,2,…,5该问题的求解可以在表1中加入(6)式，然后运用对偶单纯形法求出最优解。
每个线性规划问题都有一个与之对应的对偶问题。
简单考虑如下的生产分配问题我们有下面的对偶问题：该问题的任意一个可行解对应的目标函数值都不小于原问题的目标函数值，但是两个问题的最优目标函数值（有限）相同。
一般而言：1、每个对偶变量对应原问题的一个约束条件2、原问题是等式约束则对偶变量无不等式约束（非负约束）3、原问题是不等式约束则对偶变量有不等式约束4、原问题变量和对偶问题约束条件同样具有如上规律任何原问题和对偶问题之间都存在下述相互关系：弱对偶性：原对偶问题任何可行解的目标值都是另一问题最优目标值的界（推论：原对偶问题目标值相等的一对可行解是各自的最优解）强对偶性：原对偶问题只要有一个有最优解，另一个就有最优解，并且最优目标值相等互为对偶的线性规划问题解之间关系有如下四种：原问题与对偶问题之间存在互补松弛性：一般形式的线性规划互补松弛定理：经济学中有所谓影子价格的概念：如果增加某些约束条件的数值，原问题的最优目标值应该增加，增加单位约束使得原问题最优值的增加量为该约束条件的影子价格。
影子价格可以由对偶线性规划问题清楚地描述：对偶单纯形法：当线性规划问题中地某个约束条件或价值变量中含有参数时，原问题称之为参数线性规划，它有如下的处理方法：1）固定λ的数值解线性规划问题2）确定保持当前最优基不变的λ的区间3）确定λ在上述区间附近的最优基，回2）如以下问题：在实际问题中，许多变量以及它们的约束条件往往是离散的，或者说限定在整数域上，这便引入了整数线性规划的概念。
具体而言，整数线性规划包含纯整数线性规划（所有变量是整数变量）、混合整数线性规划（同时包含整数和非整数变量）、0-1型整数线性规划（变量等于0或1）去除整数规划的整数约束后的问题称为其松弛问题。
一般情况，原问题的解并不一定是其松弛问题的最优解附近的整数解，例如：通常的解决办法是在松弛问题的基础上出发，不断地引入整数的约束条件，从而求出整数规划的解。
