整数规划问题。
姓名：王旭。
学号：07081071
整数规划(integer programming)
一类要求问题中的全部或一部分变量为整数的数学规划。
一般认为非线性的整数规划可分成线性部分和整数部分，因此常常把整数规划作为线性规划的特殊部分。**性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求解答必须是整数。例如，所求解是机器的台数，工作的人数或装货的车数等。
为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。
整数规划的一种特殊情形是01规划，它的变数仅限于0或1。
关键词：整数规划纯整数规划混合整数规划 01规划。
目录。第一章整数规划
1.1整数规划的定义及应用
1.2起源于发展
1.3 整数规划的种类
1.4 整数规划的特征。
第二章整数规划的一些求解方法
2.1匈牙利法（指派问题）
2.2分支定界法
2.3割平面法
第三章综述
参考文献 线性规划问题的最优解可能是分数或小数，但对于某些问题，常要求解必须是整数(称为整数解)。例如，所求解是机器的台数、完成工作的人数或装货的车数等。我们称这样的问题为整数线性规划(integer linear programming)，简称ilp
整数线性规划的一般形式：
整数规划与组合最优化从广泛的意义上说，两者的领域是一致的，都是在有限个可供选择的方案中，寻找满足一定标准的最好方案。有许多典型的问题反映整数规划的广泛背景。因此整数规划的应用范围也是极其广泛的。
它不仅在工业和工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。
例如：某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表：问两种货物各托运多少箱，可使利润为最大？
建立线性规划模型为：
maxz= 20x1 +10x2
5x1 +4x2 ≤24
2x1 +5 x2 ≤13
x1 ≥0, x2 ≥0
利用单纯形法求得最优解为：
x1＝4.8，x2＝0，maxz＝96
1）四舍五入：
x1＝5，x2＝0，z＝100
但破坏了体积限制条件，因而不是可行解。
2）舍小数：
x1＝4，x2＝0，z＝80
是可行解，但不是最优解，因 x1＝4，x2＝1，z＝90也是可行解。
因此，对于一个线性规划问题，若要求某些决策变量的取值为整数，这样的规划问题称为整数规划。如：上班人数问题，厂址选择问题，集装箱运输问题等。
我们称这样的问题为整数线性规划(integer linear programming)，简称ilp。
整数规划是从2023年由戈莫里提出割平面法之后形成独立分支的 ，30多年来发展出很多方法解决各种问题。解整数规划最典型的做法是逐步生成一个相关的问题，称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更易于求解的松弛问题（衍生问题称为松弛问题的源问题）。
通过松弛问题的解来确定它的源问题的归宿，即源问题应被舍弃，还是再生成一个或多个它本身的衍生问题来替代它。随即 ，再选择一个尚未被舍弃的或替代的原问题的衍生问题，重复以上步骤直至不再剩有未解决的衍生问题为止。目前比较成功又流行的方法是分枝定界法和割平面法，它们都是在上述框架下形成的。
1.3整数线性规划问题的种类。
纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划。
0-1型整数线性规划：决策变量只能取值0或1的整数线性规划。
混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。
1.4整数规划问题解的特征。
最优点不一定在顶点处取到。
最优解不一定是松弛问题最优解的邻近整数解。
整数可行解远多余于顶点，枚举法不可取。
可行解是其松弛问题的可行解，反之不一定，但如果松弛。
问题的最优解还满足整数约束条件，是整数规划的最优解。
现实中，经常遇到这样的问题，几个人恰好从事几项任务，由于每人专长不同，效率不同，那么如何分配任务使效率最大或所消耗时间最小。如：
一、指派问题的数学模型。
则问题的数学模型为：
二、模型的特征及解的结构。
从模型的结构上看，指派问题既是一类特殊的运输问题，又是一类特殊的0-1规划问题，能否按照运输问题等方法求解呢？
模型任一可行解的结构（解矩阵）可描述为：
解矩阵的特征使得该模型若按运输问题的方法求解，基变量的个数为9个，因而是一个高度退化的运输问题。
指派问题的解法——匈牙利法。
匈牙利法的核心是匈牙利数学家 提出了关于零元素的重要定理：效益矩阵中独立零元素的个数等于能覆盖所有零元素的最少直线数。
匈牙利法的步骤：
㈠、变换效益矩阵，使每行每列都有零元素。
根据价值系数的特征，对效益矩阵中的每行（列）减去该行（列）的最小元素，使每行每列至少有一个零元素存在。
关键在于零元素的位置，特别是处于不同行不同列的零元素——独立零元素。
如果独立零元素的个数等于n，则已得到最优解。
、进行试分配。
试分配的过程就是找独立零元素的过程。
从具有零元素最少的行（列）开始，圈出一个零元素并划去同行同列的其他零元素，依次进行下去。
、作能覆盖零元素的最少直线。
①对没有圈0的行打“√”号；
②对打“√”号的行上有零元素的列打“√”号；
③对打“√”号的列上圈0的行打“√”号；
④重复②、③直到打不出 “√号为止；
⑤对没有打“√”号的行画横线，对打“√”号的列画竖线。
、效益矩阵的变换。
①在未被直线覆盖的元素中找出最小元素；
②对未画直线的行的各元素都减去最小元素；
③对画直线的列的各元素都加上最小元素。
五)、注意的几个问题。
1.效益矩阵的变换规则（找出最小元素）
①未被直线覆盖的元素都减去最小元素；
②竖单线覆盖的元素不变；
③交叉线（双线）覆盖的元素加上最小元素。
2.对于求极大化问题如何处理。
1）效益矩阵变成负的，再进行处理。
2）用bij=m-cij进行效益矩阵转换（m为足够大正数）
3.行列不等情形的处理。
增加相应的行列，其效益值根据具体情况而定。
一、基本思想和算法依据。
基本思想是：先求出相应的线性规划最优解，若此解不符合整数条件，那么其目标函数的值就是整数规划问题最优值的上界，而任意满足整数条件的可行解的目标函数值将是其下界（定界），然后将相应的线性规划问题进行分枝，分别求解后续的分枝问题。如果后续分枝问题的最优值小于上述下界， 则剪掉此枝； 如果后续某一分枝问题的最优解满足整数条件，且其最优值大于上述下界，则用其取代上述下界，继续考虑其它分枝，直到最终求得最优的整数解。
算法的依据在于：“整数规划的最优解不会优于相应的线性规划问题的最优解”。具体说就是，对极大化问题，与整数规划问题相应的线性规划问题的目标函数值，是该整数规划问题目标函数的上界；任何满足整数条件的可行解的目标函数值将是其下界。
二、具体步骤（以例子说明）
解： 第一步：先不考虑整数约束条件，求解相应的线性规划问题，得最优解和最优值如下。
x1=4.81, x2=1.82, z=356
此解不满足整数解条件。定出整数规划问题目标函数的上下界。上界为 z=356；用观察法可知x1=0，x2=0是可行解，从而其整数规划问题目标函数的下界应为0，即。
0 z* 356
第二步：分枝与定界过程。
将其中一个非整数变量的解，比如x1, 进行分枝，即。
x1 4.81 =4, x1 4.81 =5
并分别加入lp问题的约束条件中， 得两个子lp规划问题lp-1, lp-2, 分别求解此两个子线性规划问题， 其最优解分别是。
lp-1: x1=4, x2=2.1, z1=349
lp-2: x1=5, x2=1.57, z2=341
没有得到全部决策变量均是整数的解。再次定出上下界。
0 z* 349
继续对问题lp-1，lp-2进行分枝。先对目标函数值大的子问题进行分枝，即分别将。
x2 2.1 =2, x2 2.1 =3
加入到约束条件中去， 得子问题lp-3, lp-4, 分别求解得。
lp-3: x1=4, x2=2, z3=340 （是整数解，定下界）
lp-4: x1=1.42, x2=3, z4=327（剪掉）
问题lp-3的所有解均是整数解， 而问题lp-4还有非整数解， 但由于 z3>z4, 对lp-4分枝已没有必要，剪掉。
上下界为340 z* 349
在对问题lp-2进行分枝， x2 1.57 =1， x2 1.57 =2, 得子问题lp-5, lp-6, 求解得。
lp-5: x1=5.44, x2=1, z5=308 (下界340, 剪掉)
运筹学作业
运筹学关于库存的分析。主讲 秦舟 200900709071 摘要 关键词编辑 梁海琳 200900709074 模型制作 软件求解 欧迅 200900709077 秦舟 200900709071 理论综述与结果分析 林建佳 200900709069 秦普满 200900709067 参考文献与结论 ...
运筹学作业
习题1.1 1.决策变量 四种产品每月的产量。x1表示产品a每月的产量，x2表示产品b每月的产量，x3表示产品c每月的产量，x4表示产品d每月的产量。2.目标函数 设总利润为z,则z 200x1 250x2 300x3 400x4 3.约束条件 x1 x2 2x3 2x4 600 x2 x3 3x4...
运筹学作业
西安理工大学实验报告。第页 共页 课程实验日期年月日。专业班号组别交报告日期 年月日。姓名学号报告退发 订正 重做 同组者教师审批签字 实验报告格式。一 预习准备 实验目的和要求 实验仪器和设备等 二 实验过程 实验步骤和实验数据记录等 三 实验总结 实验数据处理和实验结果讨论等。实验名称。一 实验...