运筹学08整数规划

实验报告课程名称：___ 运筹学 ____ 项目名称：整数规划问题_ 姓名：__专业：、班级：1班学号：同组成员：_ __1注：1、实验准备部分包括实验环境准备和实验所需知识点准备。

2、若是单人单组实验，同组成员填无。

例4.5设某部队为了完成某项特殊任务，需要昼夜24小时不间断值班，但每天不同时段所需要的人数不同，具体情况如表4-4所示。

假设值班人员分别在各时间段开时上班，并连续工作8h。

现在的问题是该部队要完成这项任务至少需要配备多少名班人员？解：根据题意，假设用i x（i=1,2,3,4,5,6）分别表示第i个班次开始上班的人数，每个人都要连续值班8h，于是根据问题的要求可归结为如下的整数规划模型：目标函数：iixz61min=∑=约束条件：⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=≥）且为整数（6...1,0x30>=x6+x520>=x5+x450>=x4+x360>=x3+x270>=x2+x160>=x6+x1iimodel:sets:num/1,2,3,4,5,6/:b,x;endsetsdata:b=60,70,60,50,20,30;enddata[obj]min=@sum(num(i):x(i));x(1)+x(6)>=60;x(1)+x(2)>=70;x(2)+x(3)>=60;x(3)+x(4)>=50;2注：实验过程记录要包含实验目的、实验原理、实验步骤，页码不够可自行添加。

解：目标函数：y3*2000-y2*2000-y1*5000-x3*200)-(300+x2*30)-(40+x1*280)-(400=z max约束条件：⎪⎪⎩⎪⎪⎨⎧y3*300<=x3*2y2*300<=x2*0.5y1*300<=x1*32000<=x3*4+x2+x1*5 model :sets :num/1,2,3/:x,y;endsets[obj]max =(400-280)*x(1)+(40-30)*x(2)+(300-200)*x(3)-5000*y(1)-2000*y(2)-2000*y(3);5*x(1)+x(2)+4*x(3)<=2000;3*x(1)<=300*y(1);0.5*x(2)<=300*y(2);2*x(3)<=300*y(3);@for (num(i):x(i)>=0;@bin (y(i)););end实验报告成绩（百分制）__________ 实验指导教师签字：__________。

运筹学与优化中的整数规划与线性规划对比分析运筹学与优化是一门研究如何利用数学方法来优化决策的学科。

在运筹学与优化领域中，整数规划和线性规划是两种常用的数学模型。

本文将对整数规划和线性规划进行比较和分析，探讨它们在应用中的异同点以及各自的优势和劣势。

首先，我们来看整数规划。

整数规划是一种求解含有整数变量的优化问题的数学方法。

在整数规划中，决策变量必须取整数值，这导致整数规划比线性规划要更加复杂。

整数规划可以用来解决很多实际问题，例如生产调度问题、资源分配问题和路线选择问题等。

整数规划的一个重要应用领域是物流运输问题。

在物流运输中，有时需要决定在某一段时间内应该购买多少辆卡车，以满足快速变化的运输需求。

这个问题可以被建模为一个整数规划问题，目标是最小化成本或最大化利润。

与整数规划相比，线性规划是一种在决策变量可以取任意实数值的情况下求解优化问题的方法。

线性规划在运筹学与优化中被广泛应用。

线性规划的求解方法相对较为简单，可以通过线性规划软件来求解。

线性规划常被用来解决资源分配问题、产品混合问题和生产计划问题等。

一个典型的线性规划问题是生产计划问题，其中目标是最大化产量或最小化生产成本，同时满足一系列约束条件，例如原料和人力资源的限制。

整数规划和线性规划在应用中有一些明显的异同点。

首先，整数规划相对于线性规划来说更加复杂，因为整数规划需要考虑决策变量取整数值的限制。

这使得整数规划的问题规模更大，求解难度更高。

其次，整数规划可以更好地描述某些实际问题，例如一些离散决策问题，而线性规划更适用于某些具有连续决策变量的问题。

此外，整数规划常常需要更长的计算时间来求解，而线性规划则可以在较短的时间内得到结果。

尽管整数规划和线性规划在应用中有一些区别，它们也有一些共同之处。

首先，整数规划和线性规划都是数学模型，通过最大化或最小化某个特定的目标函数来进行决策。

其次，整数规划和线性规划都可以通过数学方法来求解。

虽然整数规划的求解方法相对复杂一些，但仍然可以被有效地求解出来。

求解整数规划的方法整数规划是一种最优化问题，其解决方案限制了决策变量必须取整数值。

整数规划的应用非常广泛，涉及到许多实际问题，如制造业生产调度、物流优化、资源分配等。

在本文中，我们将介绍几种常用的整数规划方法。

一、分支定界法分支定界法是一种常用的整数规划求解方法，它通过不断将解空间分割为子问题并求解这些子问题，最终找到整数规划的最优解。

具体步骤如下：1. 初始时，将整数规划问题转化为一个线性规划问题，并求解线性规划问题的松弛解。

2. 如果松弛解满足整数约束条件，则找到一个整数解，更新当前最优解。

3. 如果松弛解不满足整数约束条件，则选择一个变量将其分割为两个子问题，并分别求解这两个子问题。

4. 对每个子问题，递归地应用上述步骤，直到找到一个整数解或者确定当前子问题的上界小于当前最优解。

5. 最终，得到整数规划的最优解。

分支定界法的优点是能够保证找到最优解，但其缺点是计算复杂度较高，特别是在问题规模较大时，会导致计算时间过长。

二、整数规划的近似算法当整数规划问题规模较大时，找到精确解的计算复杂度可能变得非常高，此时可以考虑使用近似算法来求解。

近似算法的思想是通过放松整数约束条件，将整数规划问题转化为一个线性规划问题，并对线性规划问题进行求解。

然后，根据线性规划问题的解，对整数规划问题进行修正，得到整数规划问题的一个近似解。

三、割平面法割平面法是一种常用的整数规划求解方法，它通过添加一系列线性不等式（割平面）来逐步减小可行解空间，最终找到整数规划的最优解。

具体步骤如下：1. 初始时，将整数规划问题转化为一个线性规划问题，并求解线性规划问题的松弛解。

2. 如果松弛解满足整数约束条件，则找到一个整数解，更新当前最优解。

3. 如果松弛解不满足整数约束条件，则根据当前松弛解所对应的目标函数值，添加一系列线性不等式（割平面）来限制可行解空间。

4. 对添加了割平面约束的线性规划问题，继续求解，并更新最优解。

5. 重复以上步骤，直到找到一个整数解或者确定当前问题的上界小于当前最优解。

第二章整数规划§1 概论定义规划中的变量（部分或全部）限制为整数时，称为整数规划。

若在线性规划模型中，变量限制为整数，则称为整数线性规划。

目前所流行的求解整数规划的方法，往往只适用于整数线性规划。

目前还没有一种方法能有效地求解一切整数规划。

1.2 整数规划的分类如不加特殊说明，一般指整数线性规划。

对于整数线性规划模型大致可分为两类：1o 变量全限制为整数时，称纯（完全）整数规划。

2o 变量部分限制为整数的，称混合整数规划。

1.2 整数规划特点（i）原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。

②整数规划无可行解。

例1 原线性规划为 其最优实数解为：45min ,45,021===z x x 。

③有可行解（当然就存在最优解），但最优解值变差。

例2 原线性规划为 其最优实数解为：23min ,23,021===z x x 。

若限制整数得：2m in ,1,121===z x x 。

（ii ） 整数规划最优解不能按照实数最优解简单取整而获得。

求解方法分类：（i ）分枝定界法—可求纯或混合整数线性规划。

（ii ）割平面法—可求纯或混合整数线性规划。

（iii ）隐枚举法—求解“0-1”整数规划：①过滤隐枚举法；②分枝隐枚举法。

（iv）匈牙利法—解决指派问题（“0-1”规划特殊情形）。

（v）蒙特卡洛法—求解各种类型规划。

下面将简要介绍常用的几种求解整数规划的方法。

§2 分枝定界法对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。

通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。

在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。

《运筹学》上机实验报告三(整数线性规划)实验名称：利用Gomory割平面法编程求解整数规划问题；利用分枝定界法编程求解整数规划问题实验目的：1. 学会软件lindo/lingo的安装及基本的操作；2. 对实际问题进行数学建模，并学会用数学软件Matlab或运筹软件Lindo/Lingo 对问题进行求解。

实验内容：1．用lindo/lingo 计算（学会输入、查看、运行、结果分析）max z = 20x1 + 10x25x1 + 4x2 ≤ 242x1 + 5x2 ≤ 13x1,x2 ≥ 0x1,x2取整数2．(指派问题)现在有A 、B、C、D、E五种任务，要交给甲、乙、丙、丁、戊去完成，每人完成一种任务，每个人完成每种任务所需要的时间如下表。

问应该如何安排个人完成哪项任务可使总的花费的时间最少？(建立数学模型，用数学软件求解该问题，写出结果并对运行结果加以说明)A B C D E任务人甲127979乙89666丙717121412丁15146610戊41071063.选址问题某跨国公司准备在某国建三个加工厂，现有8个城市供选择，每个城市需要的投资分别为1200万美元、1400万美元、800万美元、900万美元、1000万美元、1050万美元、950万美元、150万美元，但投资总额不能超过3400万美元，形成生产能力分别为100万台、120万台、80万台、85万台、95万台、100万台、90万台、130万台，由于需求的原因，要求：城市1和城市3最多选1个，城市3、城市4、城市5最多选两个，城市6和城市7最少选1个，问选择哪些城市建厂，才能使总的生产能力最大？(建立数学模型，用数学软件求解该问题，写出结果并对运行结果加以说明)整数变量定义LinDo一般整数变量:GIN <Variable>0-1整数变量: INT <Variable>LinGo一般整数变量: @GIN( variable_name);0-1整数变量：@BIN( variable_name);例如（1）Lindo运算程序max 3 x1+5 x2+4 x3subject to2 x1+3 x2<=15002 x2+4 x3<=8003 x1+2 x2 +5 x3<=2000endgin x1gin x3（2） max z = 3x1 - 2x2 + 5x3x1 + 2x2 - x3 ≤ 2x1 + 4x2 + x3 ≤ 4x1 + x2 ≤ 34x2 + x3 < 6x1,x2,x3 = 0或1lingo程序：max =3*x1 – 2*x2 + 5*x3;x1 + 2*x2 - x3 <= 2;x1 + 4*x2 + x3 <= 4;x1 + x2 <= 3 ; 4*x2 + x3< 6; @bin(x1);@bin(x2);@bin(x3);。