运筹学实验6整数规划

实验六、用EXCEL 求解整数规划

用单纯形法求解线性规划问题，最优解可能是整数，也可能不是整数，但在很多实际问题中，要求全部或部分变量的取值必须是整数，如所求的解是安排上班的人数，按某个方案裁剪钢材的根数，生产设备的台数等等。对于整数解的线性规划问题，不是用四舍五入或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决，如分枝定界法和割平面算法。这些算法比单纯形法更为复杂，因此，一般的学习者要想掌握整数规划的数学算法有一定的困难。然而事实上，由于Excel 的[工具][规划求解]可以求解整数规划问题，所以，对于一个真正有志于运用运筹学方法解决生产经营中问题的管理者来说，算法将不是障碍因素。

一、实验目的

1、 掌握如何建立整数线性规划模型，特别是0～1逻辑变量在模型中的应用。

2、 掌握用Excel 求解整数线性规划模型的方法。

3、 掌握如何借助于Excel 对整数线性规划模型进行灵敏度分析，以判断各种可能

的变化对最优方案产生的影响。 4、 读懂Excel 求解整数线性规划问题输出的运算结果报告和敏感性报告。 二、 实验内容

1、 整数规划问题模型

该问题来自于《运筹学基础及应用》（第四版）胡运权主编P126习题4.13,题目如下: 需生产2000件某种产品，该种产品可利用A 、B 、C 、D 设备中的任意一种加工，已知每种设备的生产准备结束费用、生产该产品时的单件成本以及每种设备限定的最大加工数量（件）如表1所示，问企业应该如何安排设备生产该产品才能使得总的生产成本最少，试建立该问题的数学模型并求解。

该产品可以利用四种不同的设备加工，由于采用不同的设备加工需要支付不同的准备结束费用，而如果不采用某种设备加工，是不需要支付使用该设备的准备结束费用的，所以必须借助于逻辑变量来鉴定准备结束费用的支付。

再设

，种设备加工的产品数量

为利用第设;4,3,2,1=j j x j

⎪⎩⎪⎨

⎧=>=）种设备生产（即，若不使用第

）种设备生产（即若使用第000,1j j i x j x j y 4,3,2,1=j

则问题的整数规划模型为：

43214321281624207008009801000min x x x x y y y y z +++++++=

⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨

⎧==≥≤≤≤≤=+++4

,3,2,110,01600120010009002000..4

43322114321

j y x y x y x y x y x x x x x t s j j

，或

2、 [工具][规划求解]命令求解

下面我们用Excel 中的[工具][规划求解]对该问题进行求解。由于[工具][规划求解]命令我们在求解线性规划和目标规划问题时已经用过，本实验的重点在于逻辑变量的应用。另外，为了使得结果看上去更加直观，我们将会运用If 函数来表达逻辑变量的真实涵义。

第一，表格设置与公式说明

根据本问题的规模和条件，拟设置如表1中A1︰K8所示形式：

表1

⑴输入原始数据和公式：区域B2︰I6为各变量在约束条件中的系数，B7︰I7为各变量在目标函数中的系数，K2︰K6为约束条件右边常数项。B8︰I8为各决策变更的初始值，我们全部令其为0。

⑵输入公式：在J2︰J6输入约束条件左边的公式，输入方式为：调用SUMPRODUCT 函数，首先在单元格J2中输入“=SUMPRODUCT(B2:I2,B$8:I$8)”,单元格J3︰J6的公式只要用填充柄进行自动填充即可。在单元格J7中输入目标函数公式，即“=SUMPRODUCT(B7:I7,B$8:I$8)”，输入方式也是用填充柄自动填充。

第二，求解

选择菜单[工具][规划求解]，出现[规划求解参数]对话框，在对话框中输入如图1所示的内容，在这里应该注意的是，在“约束（U ）”对话框中输入了“$F$8:$I$8=二进制”，这是因为$F$8:$I$8代表决策变量4321,,,y y y y ，而4321,,,y y y y 为逻辑变量，即这四个变量的值只能取0或1。点击该对话框中的[选项（O ）]，选择[采用线性模型]，然后按[确定]，重新回到[规划求解参数]对话框，点击该对话框中的[求解（S ）]，最后的计算结果如表2所示。

图1

第三，结果分析 各变量的值如下：

.0,1,0,1,0,1200,0,80043214321========y y y y x x x x

目标函数：Z=37000

表2

以上结果表明，应该用设备A 和C 加工该产品，其中用设备A 加工的数量为800件，用设备C 加工的数量为1200件；与此对应的是0,1,0,14321====y y y y 。意思是：未用设备B 和D 加工产品，因此用这两种设备生产产品的准备结束费就不用投入了。

第四，用if 函数来表达逻辑变量取0和1的涵义 为了更直观地判断输出结果的意思，我们还可以调用EXCEL 中的if 函数来表达逻辑变量取0和1的涵义。方法如下：在表1中再加上一行，即第9行，在单元格F9中输入“=IF(F8=1,"使用","不使用")”，然后用填充柄填充单元格G9:I9。这样在第9行的单元格F9:I9，将显示逻辑变量0,1,0,14321====y y y y 的涵义，结果如表3所示。

表3

三、 课外练习 1、利用Excel 对教材中的例题进行求解，并与教材中用图解法或分枝定界法求得的结果相比较，以判断计算是否正确。

2、试着对教材中的习题进行建模，并利用Excel 求解，然后阐述计算结果的经济涵义。

3、练习使用if 函数。 四、 实验要求

1、 课前预习，写出实验提纲；

2、 能建立常见的整数规划模型（纯整数规划、混合整数规划和0-1整数规划），并用Excel 进行求解；

3、 能读懂Excel 输出的结果报告，了解结果的经济学含义，以将计算结果用于指导企业经营实践；

4、

根据实验目的和实验内容写出实验报告。

运筹学整数规划

运筹学整数规划 运筹学是研究在资源有限的条件下，如何进行决策和优化的一门学科。整数规划是运筹学中的一个重要分支，它解决的是决策变量必须为整数的问题。整数规划在实际问题中具有广泛的应用，如生产计划、设备配置、选址问题等。 整数规划问题的数学模型可以表示为： max/min c^T x s.t. Ax ≤ b x ≥ 0 x ∈ Z 其中，c是目标函数的系数矩阵，x是决策变量的向量，A是 约束条件的系数矩阵，b是约束条件的向量，Z表示整数集合。 整数规划问题与线性规划问题相似，但整数规划问题的约束条件多了一个整数限制，使得问题的解空间变得更为复杂。由于整数规划问题的NP-hard性质，求解整数规划问题是一项困难 的任务。 求解整数规划问题的常用方法有分支定界法、割平面法和启发式算法等。 分支定界法是一种穷举搜索的方法，它通过将整数规划问题不断分割成更小的子问题，从而逐步搜索解空间，直到找到最优解。分支定界法对于规模较小的问题比较有效，但对于大规模复杂问题，效率较低。

割平面法是一种通过添加新的约束条件来减少解空间的方法。它利用线性松弛问题（将整数约束条件放宽为线性约束条件）的解来构造有效的割平面，从而逐步缩小解空间，找到最优解。割平面法通常比分支定界法更有效，但对于某些问题，可能需要添加大量的割平面才能收敛到最优解。 启发式算法是一种基于经验和启发式搜索的方法。它通过设置初始解、搜索策略和邻域搜索等步骤，来快速找到近似最优解。常见的启发式算法有遗传算法、模拟退火算法和禁忌搜索算法等。启发式算法虽然不能保证找到全局最优解，但能够在可接受的时间内找到较优解。 综上所述，整数规划作为运筹学中的重要分支，解决的是决策变量必须为整数的问题。整数规划问题具有广泛的应用，但由于其NP-hard性质，求解过程较为困难。常用的求解方法包括 分支定界法、割平面法和启发式算法等。这些方法各有优劣，根据具体问题的特点选择合适的方法进行求解。

运筹学中整数规划问题的近似算法

运筹学中整数规划问题的近似算法运筹学是一门研究如何在有限资源下做最优决策的学科，其中整数规划是其中一种重要的决策方法。整数规划问题是指在线性规划问题的基础上，对决策变量的取值加以限定，限定为整数值。 整数规划问题在实际应用中非常常见，例如优化生产计划、物流配送、资源分配等。然而，整数规划问题的解空间通常是离散的，由于整数规划问题的NP难解性质，寻找准确解的效率很低，因此近似算法成为解决整数规划问题的重要手段。 一、近似算法的概念 近似算法是指在可接受的误差范围内，通过有效的计算方法得到问题的近似最优解。在整数规划问题中，近似算法主要通过松弛约束条件、局部搜索等方法寻找问题的近似解。 二、近似算法的分类 近似算法可以根据问题的特性和解决方法的不同进行分类，下面介绍几种常见的近似算法。 1. 线性松弛算法（Linear Relaxation） 线性松弛算法是整数规划问题中常用的近似算法之一。该算法的基本思想是将整数规划问题的整数约束放宽为实数约束，得到一个线性规划问题。然后通过求解线性规划问题的松弛解，并将松弛解的整数部分作为整数规划问题的一个近似解。

2. 近似局部搜索算法（Approximate Local Search） 近似局部搜索算法通过在整数规划问题的解空间中进行局部搜索， 通过一系列的改进和优化策略来逐步提高解的质量。该算法在每一步 都根据某种准则选择当前最优解，并通过局部搜索来寻找局部最优解。然后，通过重复进行局部搜索和改进操作，逐渐向全局最优解靠近。 3. 启发式算法（Heuristic Algorithm） 启发式算法是一种基于经验和直觉的算法，通过在可行解空间中搜 索一组近似解，并根据某种评价准则选择最优解。在解决整数规划问 题时，启发式算法通过寻找有效的近似解，来替代寻找准确解，从而 节省计算资源和时间。 三、近似算法的应用案例 近似算法在实际问题中有广泛的应用，下面以物流配送问题为例， 介绍近似算法的应用。 假设某物流公司需要将一批货物从仓库分配到多个客户，其中仓库 和客户的位置已知，货物的需求和供应量也已知。目标是找到一种最 优的配送方案，使得总配送距离最短。 针对这个问题，可以使用整数规划模型进行建模，并通过近似算法 来寻找最优解。其中线性松弛算法可以将整数规划问题转化为线性规 划问题，通过求解线性规划问题得到最短配送距离，即为近似最优解。 另外，近似局部搜索算法和启发式算法也可以在该问题中应用。近 似局部搜索算法通过多次局部搜索来逐渐改进配送方案，从而得到接

运筹学中的线性规划与整数规划

运筹学中的线性规划与整数规划在运筹学中，线性规划和整数规划是两个常用且重要的数学模型。它们被广泛应用于资源分配、生产调度、物流管理等问题的决策过程中。本文将介绍线性规划和整数规划的基本概念、数学模型以及求解方法。 一、线性规划 线性规划是一种通过线性关系来描述问题的数学模型。它的目标是在给定的约束条件下，找到使目标函数达到最优的决策变量取值。线性规划模型一般可以表示为如下形式： 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ₙ ≥ 0 其中，Z表示目标函数值，c₁, c₂, ..., cₙ表示目标函数的系数，x₁, x₂, ..., xₙ为决策变量，a₁₁, a₁₂, ..., aₙₙ为约束条件的系数，b₁, b₂, ..., bₙ为约束条件的右侧常数。 线性规划的求解方法主要有两类：图形法和单纯形法。图形法适用于二维问题，通过绘制目标函数和约束条件在坐标系中的图形，找到

交点来确定最优解。而单纯形法适用于多维问题，通过迭代计算，逐 步接近最优解。 二、整数规划 整数规划是线性规划的一种特殊情况，它要求决策变量的取值必须为整数。整数规划模型可以表示为如下形式： 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表示目标函数值，c₁, c₂, ..., cₙ表示目标函数的系数，x₁, x₂, ..., xₙ为整数决策变量，a₁₁, a₁₂, ..., aₙₙ为约束条件的系数，b₁, b₂, ..., bₙ为约束条件的右侧常数。 由于整数规划中决策变量的取值范围更为限制，整数规划的求解更加困难。常用的整数规划求解方法有分支定界法、割平面法和整数规 划启发式算法等。 三、线性规划与整数规划的应用 线性规划和整数规划在实际应用中有着广泛的应用。以下列举几个常见的应用领域：

运筹学实验6整数规划

实验六、用EXCEL 求解整数规划 用单纯形法求解线性规划问题，最优解可能是整数，也可能不是整数，但在很多实际问题中，要求全部或部分变量的取值必须是整数，如所求的解是安排上班的人数，按某个方案裁剪钢材的根数，生产设备的台数等等。对于整数解的线性规划问题，不是用四舍五入或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决，如分枝定界法和割平面算法。这些算法比单纯形法更为复杂，因此，一般的学习者要想掌握整数规划的数学算法有一定的困难。然而事实上，由于Excel 的[工具][规划求解]可以求解整数规划问题，所以，对于一个真正有志于运用运筹学方法解决生产经营中问题的管理者来说，算法将不是障碍因素。 一、实验目的 1、 掌握如何建立整数线性规划模型，特别是0～1逻辑变量在模型中的应用。 2、 掌握用Excel 求解整数线性规划模型的方法。 3、 掌握如何借助于Excel 对整数线性规划模型进行灵敏度分析，以判断各种可能 的变化对最优方案产生的影响。 4、 读懂Excel 求解整数线性规划问题输出的运算结果报告和敏感性报告。 二、 实验内容 1、 整数规划问题模型 该问题来自于《运筹学基础及应用》（第四版）胡运权主编P126习题4.13,题目如下: 需生产2000件某种产品，该种产品可利用A 、B 、C 、D 设备中的任意一种加工，已知每种设备的生产准备结束费用、生产该产品时的单件成本以及每种设备限定的最大加工数量（件）如表1所示，问企业应该如何安排设备生产该产品才能使得总的生产成本最少，试建立该问题的数学模型并求解。 该产品可以利用四种不同的设备加工，由于采用不同的设备加工需要支付不同的准备结束费用，而如果不采用某种设备加工，是不需要支付使用该设备的准备结束费用的，所以必须借助于逻辑变量来鉴定准备结束费用的支付。 再设 ，种设备加工的产品数量 为利用第设;4,3,2,1=j j x j ⎪⎩⎪⎨ ⎧=>=）种设备生产（即，若不使用第 ）种设备生产（即若使用第000,1j j i x j x j y 4,3,2,1=j 则问题的整数规划模型为： 43214321281624207008009801000min x x x x y y y y z +++++++= ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨ ⎧==≥≤≤≤≤=+++4 ,3,2,110,01600120010009002000..4 43322114321 j y x y x y x y x y x x x x x t s j j ，或

运筹学 第4章 整数规划

第四章整数规划 整数规划（Integer Programming）主要是指整数线性规划。一个线性规划问题，如果要求部分决策变量为整数，则构成一个整数规划问题，在项目投资、人员分配等方面有着广泛的应用。 整数规划是近二、三十年发展起来的数学规划的一个重要分支，根据整数规划中变量为整数条件的不同，整数规划可以分为三大类：所有变量都要求为整数的称为纯整数规划（Pure Integer Programming）或称全整数规划（All integer Programming）；仅有一部分变量要求为整数的称为混合整数规划（Mixed Integer Programming）；有的变量限制其取值只能为0或1，这类特殊的整数规划称为0－1规划。 本章主要讨论整数规划的分枝定界法、割平面法、0－1规划及指派问题。 第一节整数规划问题及其数学模型 一、问题的提出 在线性规划模型中，得到的最优解往往是分数或小数，但在有些实际问题中要求有的解必须是整数，如机器设备的台数、人员的数量等，这就在原来线性规划模型的基础上产生了一个新的约束，即要求变量中某些或全部为整数，这样的线性规划称为整数规划（Integer Programming）简称IP，是规划论中的一个分枝。 整数规划是一类特殊的线性规划，为了满足整数解的条件，初看起来，只要对相应线性规划的非整数解四舍五入取整就可以了。当然在变量取值很大时，用上述方法得到的解与最优解差别不大，当变量取值较小时，得到的解与实际最优解差别较大，当变量较多时，如n＝10个，则整数组合有210＝1024个，而且整数解不一定在这些组合当中。先来看下面的例子。 例4.1某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料A、材料B，有关数据如下，问这两种设备各生产多少使工厂利润最大？ 表4－1 12 量都要求为整数，建立模型如下：

运筹学中的线性规划和整数规划

运筹学中的线性规划和整数规划运筹学是一门涉及决策分析、优化、模型构建和仿真等知识领域的学科，应用广泛，如供应链管理、交通规划、制造业生产、金融投资等方面。其中，线性规划和整数规划是运筹学中最为基础和重要的优化技术，被广泛应用于各个领域。 一、线性规划 线性规划是一种在一组线性约束条件下，求解线性目标函数极值问题的数学方法。在生产、运输、选址等问题中，线性规划都有着重要的应用。其数学模型可以表示为： $\max c^Tx$ $s.t. Ax \leq b,x\geq 0$ 其中$c$为目标函数的向量，$x$为决策变量向量，$A$为约束矩阵，$b$为约束向量，$c^Tx$表示目标函数的值，$\leq$表示小于等于。

如果目标函数和约束都是线性的，则可以通过线性规划的求解 方法来确定决策变量的最优值。线性规划的求解方法一般分为单 纯形法和内点法两种方法。 单纯性法是线性规划中最为常用的方法，通过对角线交替调整，逐步从可行解中寻找最优解，收敛速度较快，但是存在不稳定的 情况。 内点法是近年来发展起来的用于求解大规模线性规划问题的数 值方法，其核心思想是迭代求解一系列线性方程组，每次保持解 在可行域内部，直到找到最优解为止。这种方法对大规模问题求 解能力强，使用较多。 二、整数规划 整数规划是线性规划的升级版，它要求决策变量必须取整数值。整数规划在很多实际问题中都有着重要的应用，比如很多生产过 程中需要将生产数量取整数，物流路径问题需要选取整数条路径等。

与线性规划不同的是，整数规划是NP难问题，没有一种有效的算法能够完全解决所有的整数规划问题。因此，通常需要采用分支定界、割平面等方法来求解。 分支定界是一种常用的整数规划求解方法。它通过将整数规划问题分为多个子问题，依次求解这些子问题并优化当前最优解，以逐步逼近最优解。割平面法则是在分支定界方法的基础上加入约束条件，使得求解过程更加严格化，最终得到更好的结果。 总的来说，运筹学中线性规划和整数规划是不可或缺的优化工具，我们可以通过理论和实践加深对它们的理解。未来，在更加复杂的实际应用场景下，这两种技术也将不断发展和创新，为各种决策分析和优化问题提供更加高效和精确的解决方案。

运筹学整数规划课后答案吉林大学

运筹学整数规划课后答案吉林大学 一、单项选择题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 B.mD.2m 正确答案：B二、判断题 1、匈牙利法可以直接求解极大化的指派问题。()正确答案：x 2、整数规划的可行解集合是离散型集合。（）正确答案：V 3、用分支定界法求一个极大化的整数规划时，任何一个可行解的目标函数值是该问题的目标函数值的下界。（）正确答案：V 4、用分支定界法求一个极大化的整数规划时，当得到多于一个可行解时，通常可以任取一个作为下界值，在进行比拟和剪枝。（） 正确答案：X 5、用割平面求纯整数规划时，要求包括松弛变量在内的 全部变量都取整数。（）正确答案：V

运筹学：目标规划、整数规划习题与答案

一、判断题 1、正偏差变量大于等于零，负偏差变量小于等于零。（） 正确答案：× 2、系统约束中最多含有一个正或负的偏差变量。（） 正确答案：× 3、目标约束一定是等式约束。（） 正确答案：√ 4、一对正负偏差变量至少一个大于零。（） 正确答案：× 5、一对正负偏差变量至少一个等于零。（） 正确答案：√ 6、要求不超过目标值的目标函数是minZ= d+。（） 正确答案：√ 7、超出目标的差值称为正偏差。（） 正确答案：√ 8、未到达目标的差值称为负偏差。（） 正确答案：√ 二、填空题 1. 用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的（）。 正确答案：下界 2.在分枝定界法中，若选Xr=4／3进行分支，则构造的约束条件应为

（）。 正确答案：X1<=1，X1>=2 3. 已知整数规划问题P0，其相应的松驰问题记为P0’，若问题P0’无可行解，则问题P0（）。 正确答案：无可行解 4.在0 - 1整数规划中变量的取值可能是（）。 正确答案：0或1 5. 对于一个有n项任务需要有n个人去完成的分配问题，其解中取值为1的变量数为（）个。 正确答案：n 三、选择题 1. 整数规划问题中，变量的取值可能是（）。 A.整数 B.0或1 C.大于零的非整数 D.以上三种都可能 正确答案：D 2.在下列整数规划问题中，分枝定界法和割平面法都可以采用的是（）。 A.纯整数规划 B.混合整数规划 C.0—1规划

D.线性规划 正确答案：A 3.下列方法中用于求解分配问题的是（）。 A.单纯形表 B.分枝定界法 C.表上作业法 D.匈牙利法 正确答案：D

运筹学整数规划模型

运筹学整数规划模型 5.某企业利用一种设备生产某种试件。该设备可以在高，低两种不同的负荷下进行生产。在高负荷下生产的试件产量是投入生产设备数量的10倍，设备年完好率为75%；低负荷下生产的试件产量是投入生产设备数量的8倍，设备年完好率为90%。现在企业有完好的设备200台，试制定一个5年计划，确定每年投入投入高，低两种负荷下生产的设备数量，使5年内试件的总产量达到最大。 整数规划模型 设立第i年资金投入高负荷下生产的较完整的设备数量为xi，生产的试件数量为 10xi；第i年资金投入高负荷下生产的较完整的设备数量为yi，生产的试件数量为8yi。模型为： maxz?10?xi?8?yi i?1i?155x1?y1?200 s.t.?0.75xi?+?0.9yi?-xi?1-yi?1=0 xi,yi?0且为整数，（i=1,2,3,4,5） lingo程序为： max=10*(x1+x2+x3+x4+x5)+8*(y1+y2+y3+y4+y5); x1+y1=200; z1=@floor(0.75*x1);u1=@floor(0.9*y1);z1+u1-x2-y2=0; z2=@floor(0.75*x2);u2=@floor(0.9*y2);z2+u2-x3-y3=0; z3=@floor(0.75*x3);u3=@floor(0.9*y3);z3+u3-x4-y4=0; z4=@floor(0.75*x4);u4=@floor(0.9*y4);z4+u4-x5- y5=0;@gin(x1);@gin(x2);@gin(x3);@gin(x4);@gin(x5);@gin(y1);@gin(y2);@gin(y3);@ gin(y4);@gin(y5); lingo解结果为： objectivevalue:6362.000variablevalue x1200.0000x21.000000x30.000000x4119.0000x589.00000y10.000000y2149.0000y3134.00 00y41.000000y50.000000

运筹学期三次实验

1. 实验目的和要求 理解整数问题模型的基本思想，模型的建立方法及使用运筹学软件对整数规划问题进行求解。 2. 实验前准备 复习教材第八章相关内容。 3. 实验条件 每名同学使用一台计算机。小组同学相邻，方便讨论。 4. 实验内容 (1) 练习教材第八章例4-例8中的一个例子，使用运筹学软件求解模 型，分析输出数据。 (2) 选择教师指定的实际问题，进行分析、建模和用软件求解（实验 报告内容）。 问题1：求解下面的整数规划问题 s.t.⎪⎪⎪⎩⎪ ⎪⎪⎨⎧≥≤≤+-≤-≤++-++=为整数213211321323213 21,,0,,1723113413233max x x x x x x x x x x x x x x x x x Z (1)打开管理运筹学软件，如图:

(2)在主菜单中选择整数规划模型，如图： （c）此题选“混合整数规划问题”进入求解界面，如图：

（d）在点击“新建”按钮以后，按要求输入相应的值，如图： （e）单击解决，结果如图： 问题2：求解下面整数规划问题 某游泳队教练需选派一组运动员去参加4×200混合接力赛，候选运动

员有甲、乙、丙、丁、戊五位，他们游仰泳、蛙泳、蝶泳、自由泳的成绩，根据统计资料算得平均值（以秒计）如下表：问：教练应选派哪四位运动员，各游什么泳姿，才能使总的成绩最好? (a)打开管理运筹学软件，如图: (b)首先在主菜单中选择整数规划模型，在屏幕上就会出整数规划页面，如图：

（c）此题选“指派问题”进入求解界面，如图：

（d）在点击“新建”按钮以后，按要求输入相应的值，如图: （e）当输入完毕后，请点击“解决”按钮，运输问题的结果，如图： 问题3：求解下面整数规划问题： 某地区在今后三年内有四种投资机会： 第一种：三年内每年年初投资，年底可获利润20%，并将本金收回； 第二种：第一年年初投资，第二年年底可获利润50%，并将本金收回，但该项目投资不得超过2万元； 第三种：第二年年初投资，第三年年底收回本金，并获利润60%，但该项投资不得超过1.5万元； 第四种：第三年年初投资，于该年年底收回本金，且获利40%，但该

整数规划例题

〈运筹学〉补充例题 例题 1.1 某工厂可以生产产品A和产品B两种产品。生产单位产品A和B所需要的机时、人工工时的数量以及可利用资源总量由下表给出。这两种产品在市场上是畅销产品。该工厂经理要制订季度的生产计划，其目标是使工厂的销售额最大。 产品A 产品B 资源总量 机器（时） 6 8 120 人工（时） 10 5 100 产品售价（元） 800 300 MAX 800X1 +300X2 ST 6X1 +8X2 <= 120 10X1 +5X2 <= 100 X1, X2 >=0 例题 1.2该工厂根据产品A和产品B的销售和竞争对手的策略，调整了两种产品的售价。产品A和B的价格调整为600元和400元。假设其它条件不变，请你帮助该工厂经理制订季度的生产计划，其目标仍然是使工厂的销售额最大。 X 600X1 +400X2 ST 6X1 +8X2 <= 120 10X1 +5X2 <= 100 X1, X2 >=0 例题 1.3由于某些原因，该工厂面临产品原料供应的问题。因此，工厂要全面考虑各种产品所需要的机时、人工工时、原材料的资源数量及可用资源的总量、产品的售价等因素。有关信息在下表中给出。 产品A 产品B 资源总量 机器（时） 6 8 120 人工（时） 10 5 100 原材料(公斤) 11 8 130 产品售价（元） 600 400 MAX 600X1 +400X2 ST 6X1 +8X2 <= 120 10X1 +5X2 <= 100 11X1 +8X2 <= 130 X1, X2 >=0 例题 1.４随着企业改革的不断深化，该企业的经理的管理思想产生了变化，由原来的追求销售额变为注重销售利润，因此，要考虑资源的成本。工厂的各种产品所需要的机时、人

熊伟编《运筹学》习题六详细解答

习题六 6.1如图6－39所示，建立求最小部分树的0－1整数规划数学模型。 【解】边[i ，j ]的长度记为c ij ，设 ⎩⎨ ⎧=否则 包含在最小部分树内 边0],[1j i x ij 数学模型为： ⎪⎪ ⎪⎪⎪⎩ ⎪ ⎪⎪⎪⎪⎨⎧=≤+++≤+++≤+++≤+++≤+++≤++≤++≤++≤++≤++==∑],[,013,33 ,33 ,22,22 ,25min 562615125626352336 26131256463534 34241312362623563635463634342423231312 ,j i x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x c Z ij j i ij ij ij 所有边或 6.2如图6－40所示，建立求v 1到v 6的最短路问题的0－1整数规划数学模型。 【解】弧(i ，j )的长度记为c ij ，设 ⎩⎨ ⎧=否则 包含在最短路径中 弧0),(1j i x ij 数学模型为： ⎪⎪⎩ ⎪⎪⎨ ⎧==+=+++=++=+++==+=∑),(,011,,,1min 5646564535254645342435342313 25 2423121312,j i x x x x x x x x x x x x x x x x x x x x x x c Z ij j i ij ij 所有弧或 6.3如图6－40所示，建立求v 1到v 6的最大流问题的线性规划数学模型。 【解】 设x ij 为弧（i ,j ）的流量，数学模型为 ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨ ⎧≤≤=+++=++=+++=+=++=) ,(,0min 564535254645342435 34231325242312 5646131213 12j i c x x x x x x x x x x x x x x x x x x x x x x x Z ij ij 所有弧 6.4求图6－41的最小部分树。图6-41（a ）用破圈法,图6-41（b ）用加边法。 图6－39 图6－40

第六章 运筹学 整数规划案例

第六章整数规划 6.1 用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域(在图上用“×”标出)。 1、 max z=3x1+2x2 S.T. 2x1+3x2≤12 2x1+x2≤9 x1、x2≥0 解： 2、 min f=10x1+9x2 S.T. 5x1+3x2≥45 x1≥8 x2≤10 x1、x2≥0

6.2 求解下列整数规划问题 1、 min f=4x1+3x2+2x3 S.T. 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 S.T. -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 S.T. 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 6.3 一餐饮企业准备在全市范围内扩展业务，将从已拟定的14个点中确定8个点建立分店，由于地理位置、环境条件不同，建每个分店所用的费用将有所不同，现拟定的14个店的费用情况如下表：

运筹学整数规划例题

练习 4.9 连续投资问题 某公司现有资金10万元, 拟在今后五年考虑用于下列项目的投资: 项目A:从第一年到第四年每年年初需要投资, 并于次年收回本利115%,但要求第一年投资最低金额为4 万元, 第二. 三. 四年不限. 项目B:第三年初需要投资, 到第五年末能收回本利128%,但规定最低投资金额为3万元,最高金额为 5 万元. 项目C:第二年初需要投资, 到第五年末能收回本利140%,但规定其投资金额或为2万元,或为 4 万元, 或为 6 万元, 或为8 万元. 项目D:五年每年年初都可购买公债,于当年末归还, 并获利6%,此项目投资金额不限. 试问该公司应图和确定这些项目的每年投资金额, 使到第五年末拥有最大的资金收益. (1)x 为项目各年月初投入向量。 (2)x ij 为i 种项目j 年的月初的投入 (3)向量c中的元素cij为i 年末j种项目收回本例的百分比 (4)矩阵A中元素aij为约束条件中每个变量xij的系数。 (5)Z为第5年末能拥有的资金本利最大总额。因此目标函数为 max Z 1.15 x4 A 1.28 x3B 1.40x2C 1.06 x5 D 束条件应是每年年初的投资额应等于该投资者年初所拥有的资金 第 1 年年初该投资者拥有10 万元资金, 故有 x1A x1D 100000 . 第 2 年年初该投资者手中拥有资金只有 1 6% x1D , 故有 x2A x2C x2D 1.06 x1D . 第3 年年初该投资者拥有资金为从D 项目收回的本金: 1.06x2D , 及从项目 A 中第 1 年投资收回的本金: 1.15x1A , 故有

运筹学上机实验指导书

运筹学上机实验指导书 重庆交通大学管理学院

目录 绪论 运筹学上机实验软件简介 第一章运筹学上机实验指导 §1.1 中小型线性规划模型的计算机求解 §1.2 大型线性规划模型的编程计算机求解 §1.3线性规划的灵敏度分析 §1.4运输问题数学模型的计算机求解 §1.5目标规划数学模型的计算机求解 §1.6整数规划数学模型的计算机求解 §1.7 指派问题的计算机求解 §1.8最短路问题的计算机求解 §1.9最大流问题的计算机求解 第二章LINGO软件基础及应用 §2.1 原始集(primitive set)和派生集(derived set)与集的定义 §2.2 LINGO中的函数与目标函数和约束条件的表示 §2.3 LINGO中的数据 §2.4 LINDO简介

第三章运筹学上机实验及要求 实验一.中小型线性规划模型的求解与Lingo软件的初步使用实验二.中小型运输问题数学模型的Lingo软件求解。 实验三.大型线性规划模型的编程求解。 实验四.运输问题数学模型的Lingo编程求解。 实验五.分支定界法上机实验 实验六.整数规划、0-1规划和指派问题的计算机求解 实验七：最短路问题的计算机求解 实验八:最大流问题的计算机求解 实验九:运筹学综合实验

绪论 运筹学是研究资源最优规划和使用的数量化的管理科学，它是广泛利用现有的科学技术和计算机技术，特别是应用数学方法和数学模型，研究和解决生产、经营和经济管理活动中的各种优化决策问题。 运筹学通常是从实际问题出发，根据决策问题的特征，建立适当的数学模型，研究和分析模型的性质和特点，设计解决模型的方法或算法来解决实际问题，是一门应用性很强的科学技术。运筹学的思想、内容和研究方法广泛应用于工程管理、工商企业管理、物流和供应链管理、交通运输规划与管理等各行各业，也是现代管理科学和经济学等许多学科研究的重要基础。 在解决生产、经营和管理活动中的实际决策问题时，一般都是建立变量多、约束多的大型复杂的运筹学模型，通常都只能通过计算机软件才能求解，因此，学习运筹学的计算机求解和进行上机实验，就是运筹学教学的重要组成部分。 现在求解各类运筹学模型的软件多种，主要有Microexcel，Matlab，LINDO，LINGO，WinQSB和英国运筹学软件Dash-Xpress。Microexcel主要利用规划求解来解线性规划模型，WinQSB功能比较齐全，但是主要适合解决规模较小的运筹学模型，英国运筹学软件Dash-Xpress现在在中国的使用率不高，Matlab是通过矩阵的方法解决线性规划，对非线性规划和其它运筹学模型特别是大规模的模型的输入不太方便，。而LINGO和LINDO是使用最广泛的运筹学专业软件，前者功能强大，能解决几乎所有的运筹学优化模型，后者主要功能是线性规划模型的求解。在LINGO中模型的输入和编程都比较方便，可解决大规模的运筹学模型。因此，本课程的教学就是以LINGO为主，适当补充Excel和LINDO作为运筹学上机软件，后者的优势主要在于能获得最优单纯形表以进行更全面地灵敏度分析。 LINGO是用来求解线性和非线性优化问题的简易工具。LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果。 LINGO全称是Linear INteractive and General Optimizer的缩写---交互式的线性和通用优化求解器。它是一套设计用来帮助您快速,方便和有效的构建和求解线性,非线性,和整数最优化模型的功能全面的工具.包括功能强大的建模语言,建立和编辑问题的全功能环境,读取和写入Excel和数据库的功能,和一系列完全内置的求解程序. 运行环境：Win9x/NT/2000/XP/2003/Vista/Win7 软件类别：国外软件/工具软件/计算工具 软件语言：英文 LINGO 是使建立和求解线性、非线性和整数最佳化模型更快更简单更有效率的综合工具。LINGO 提供强大的语言和快速的求解引擎来阐述和求解最佳化模型。LINGO具有如下的优势： 1．简单的模型表示 LINGO 可以将线性、非线性和整数问题迅速得予以公式表示，并且容易阅读、了解和修改。LINGO的建模语言允许您使用汇总和下标变量以一种易懂的直观的方式来表达模型，非常类似您在使用纸和笔。模型更加容易构建，更容易