当前位置：文档之家 › 第二章 整数规划+答案

第二章 整数规划+答案

  • 格式：pdf
  • 大小：202.21 KB
  • 文档页数：8

下载文档原格式

  / 8

合集下载

运筹学第二章习题答案

运筹学第二章习题答案

运筹学第二章习题答案运筹学是一门应用数学学科，旨在通过数学模型和定量方法来解决实际问题。

在运筹学的学习中，习题是必不可少的一部分，通过解答习题可以加深对知识的理解和应用。

本文将针对运筹学第二章的习题进行解答，希望能够帮助读者更好地掌握运筹学的知识。

第一题：线性规划问题的基本要素包括目标函数、约束条件和决策变量。

请问线性规划问题的目标函数通常是什么形式？为什么？答：线性规划问题的目标函数通常是线性函数的形式。

这是因为线性函数具有简单的数学性质，容易求解和分析。

此外，线性函数的图像为直线，可以通过直观的图形方法来理解问题的解。

第二题：什么是单纯形法？请简要描述单纯形法的基本思想和步骤。

答：单纯形法是一种求解线性规划问题的常用方法。

其基本思想是通过不断地移动到更优解的顶点，直到找到最优解。

单纯形法的步骤如下：1. 初始解的选择：选择一个可行解作为初始解。

初始解可以通过图形方法或其他启发式算法得到。

2. 进行迭代：通过计算目标函数的改进方向来确定下一步移动的方向。

如果目标函数不能再改进，则停止迭代，当前解即为最优解。

3. 顶点的移动：通过改变决策变量的值，将当前解移动到相邻的顶点。

移动的方向和距离由迭代步骤中计算得到。

4. 检验最优性：对移动后的顶点进行最优性检验，判断是否达到最优解。

如果达到最优解，则停止迭代，当前解即为最优解；否则，返回第2步。

第三题：什么是整数规划问题？请举一个实际应用的例子，并说明为什么需要使用整数规划方法来解决。

答：整数规划问题是线性规划问题的一种扩展形式，要求决策变量的取值为整数。

整数规划问题通常用于需要离散决策的场景，如生产调度、资源分配等。

举个例子，假设某公司有多个项目需要进行投资，每个项目的投资金额和预期收益已知。

公司希望选择一些项目进行投资，使得总投资金额不超过公司的可用资金，并最大化预期收益。

由于项目的投资金额和收益都是整数，这就是一个整数规划问题。

使用整数规划方法来解决这个问题的原因是，如果将决策变量的取值限制为整数，可以更好地符合实际情况。

整数规划问题的求解

整数规划问题的求解

max Z 4 x1 3 x 2 1.2 x1 0.8 x 2 10 2 x1 2.5 x 2 25 LP 21 : x1 4，x 2 6 x1 , x 2 0
C o 3 4
x1
分支定界法
x2
A
Page 16
由 于Z 21 Z 1， 选 择 LP 21进 行 分 枝 ， 增 加 约 束 x1 4及x1 5， 得 线 性 规 划 LP 211 及LP 212 ：
10
A
x2 7不可行
max Z 4 x1 3 x 2 1.2 x1 0.8 x 2 10 2 x1 2.5 x 2 25 LP 22 : x1 4，x 2 7 x1 , x 2 0
B 6 LP1
LP21
LP21:X=(4.33,6),Z21=35.33
整数规划问题的求解
整数规划问题的求解方法： 分支定界法和割平面法
Page 1
匈牙利法（指派问题）
分支定界法
分支定界法的解题步骤：
Page 2
1）求整数规划的松弛问题最优解； 若松弛问题的最优解满足整数要求，得到整数规划的最优解,否则转下 一步； 2）分支与定界： 任意选一个非整数解的变量xi，在松弛问题中加上约束： xi≤[xi] 和 xi≥[xi]+1 组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题 是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目 标值是分枝问题的下界。 检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数 值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若 还存在非整数解并且目标值大于(max)整数解的目标值，需要继续分枝， 再检查，直到得到最优解。
运筹学03_整数规划2

运筹学03_整数规划2


二、固定成本问题
高压容器公司制造小、中、大三种尺寸的金属容器，所用资 源为金属板、劳动力和机器设备，制造一个容器所需的各种 资源的数量如下表所示。每种容器售出一只所得的利润分别 为 4万元、5万元、6万元，可使用的金属板有500吨，劳动 力有300人月，机器有100台月，此外不管每种容器制造的数 量是多少，都要支付一笔固定的费用：小号是l00万元，中 号为 150 万元，大号为200万元。现在要制定一个生产计划， 使获得的利润为最大。
投资额 利润
A1 100 36
A2 A3 120 150 40 50
A4 80 22
A5 70 20
A6 90 30
A7 80 25
A8 140 48
A9 160 58
A10 180 61
解：设：0--1变量 xi = 1 (Ai 点被选用）或 0 (Ai 点 没被选用）。 这样我们可建立如下的数学模型：
例(p90)
求下列问题：
Max Z=3x1- 2x2 + 5x3
s.t. x1+2x2 - x3 2
x1+4x2 + x3 4 x1 + x2 xj 0或1 3 4x2 + x3 6
(1)
(2) (3) (4) (5)
解： 容易看出(1,0,0)满足约束条件， 对应Z=3，对Max Z来说，希望Z 3,所 以增加约束条件： Z=3x1- 2x2 + 5x3 3 (0)
当y=1时,(1)(3)无差别,(4)式显然成立; 当y=0时,(2)(4)无差别,(3)式显然成立。 以上方法可以处理绝对值形式的约束 f(x) 此时
a (a>0)
f(x)
a
运筹学课后答案2

运筹学课后答案2

运筹学（第2版）习题答案2第1章 线性规划 P36~40第2章 线性规划的对偶理论 P68~69 第3章 整数规划 P82~84 第4章 目标规划 P98~100 第5章 运输与指派问题 P134~136 第6章 网络模型 P164~165 第7章 网络计划 P185~187 第8章 动态规划 P208~210 第9章 排队论 P239~240 第10章 存储论 P269~270 第11章 决策论 Pp297－298 第12章 博弈论 P325~326 全书360页由于大小限制，此文档只显示第6章到第12章，第1章至第5章见《运筹学课后答案1》习题六6.1如图6－42所示，建立求最小部分树的0－1整数规划数学模型。

【解】边[i ，j ]的长度记为c ij ，设⎩⎨⎧=否则包含在最小部分树内边0],[1j i x ij数学模型为：,12132323243434364635365612132434343546562324463612132446362335244656121324354656m in 52,22,233344,510ij ijij i j ij Z c 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 x x x x x ==++≤++≤++≤++≤+++≤+++≤+++≤++++≤++++≤+++++≤=∑或,[,]i j ⎧⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎩所有边6.2如图6－43所示，建立求v 1到v 6的最短路问题的0－1整数规划数学模型。

图6－42【解】弧(i ，j )的长度记为c ij ，设⎩⎨⎧=否则包含在最短路径中弧0),(1j i x ij数学模型为：,1213122324251323343524344546253545564656m in 100,00110,(,)ijiji jij Z cx x x x x x x x x x x x x x x x x x x x x x i j =⎧+=⎪---=⎪⎪+--=⎪⎪+--=⎨⎪++-=⎪⎪+=⎪=⎪⎩∑或所有弧 6.3如图6－43所示，建立求v 1到v 6的最大流问题的线性规划数学模型。

5.4整数规划2

5.4整数规划2


整数规划——卫星信号传输问题
x=[0 5 0 1 0 0 6 1 3 4 0 0 6 0 9 0 7 0 0 0 0 0]’ s=10
模式和传输量为：
Mathematical Experiments
30
整数规划——数独问题
Mathematical Experiments
发源于欧洲的 数学大师欧拉 之手； 在日本广泛流 传； 近年来在全世 界流行。
Mathematical Experiments
决策变量为ri,i=1,2,…,24，表示在第i种传输模式下的传输量。 记双随机矩阵为D，所有的四阶置换矩阵Pi,i=1,2,…,24。
r1P1 r2 P2 ... r24 P24 D
得到线性规划模型：
min
s.t.
ri i
r1 P1 r2 P2 ... r24 P24 D ri 为非负整数
i 1 33
x(i U , j V , k ) 1,U ,V {0, 3, 6}
i 1 j 1
x(i, j, k ) {0,1}, i 1, , 9, j 1, , 9, k 1, , 9
整数规划——数独问题
部分代码：
B = [1,2,2; 1,5,3; 1,8,4; 2,1,6; 2,9,3; 3,3,4; 3,7,5; 4,4,8; 4,6,6; 5,1,8; 5,5,1; 5,9,6; 6,4,7; 6,6,5; 7,3,7; 7,7,6; 8,1,4; 8,9,8; 9,2,3; 9,5,4; 9,8,2]; figure;hold on;axis off;axis equal rectangle('Position',[0 0 9 9],'LineWidth',3,'Clipping','off') rectangle('Position',[3,0,3,9],'LineWidth',2) rectangle('Position',[0,3,9,3],'LineWidth',2) rectangle('Position',[0,1,9,1],'LineWidth',1) rectangle('Position',[0,4,9,1],'LineWidth',1) rectangle('Position',[0,7,9,1],'LineWidth',1) rectangle('Position',[1,0,1,9],'LineWidth',1) rectangle('Position',[4,0,1,9],'LineWidth',1) rectangle('Position',[7,0,1,9],'LineWidth',1) for ii = 1:size(B,1)
整数规划习题解答 ppt课件

整数规划习题解答 ppt课件


15
14
练习
第四步：增加独立零元素
0 3 0 11 8
0
1
7
7
3
1 3 0 11 8
0
0
6
6
2
0 2 3 2 1
0
0
5
0
4
0 2 3 4 0
0 1 2 1 0
1
0
5
0
4
1 2 3 4 0
解矩阵为
0 0 1 0 0
0
1
0
0
0
X* 1 0 0 0 0
0 0 0 1 0
0 0 0 0 1
以 x 4 ,x 5 ,x 6 为 基 变 量 ， B (p 4 ,p 5 ,p 6 ) E 为 初 始 可 行 基 ， 运 用 单 纯 性 法 求 解
（增加了人工变量x4）
5
练习
（2）不增加人工变量，通过对约束方程组进行行变换得到 初始可行基
max z x2 2 x3
x1 2 x2 x3
6
练习
cj
0
1
-2
0
0
CB
XB
b
x1
x2
x3
x4
x5
0
x1 13/2 1
0
0 -1/2 5/2
1
x2
5/2
0
1
0 -1/2 3/2
-2
x3 1/2
0
0
1 -1/2 1/2
-z
-3/2 0
0
0 -1/2 -1/2
7
练习
伴随规划问题的最优解不是整数解，构造割平面（由 最终表中任意一个不取整数值得基变量所对应的约束方程 进行构造，不妨选x3）
第02章 整数规划

第02章 整数规划


必须为 1；当 x j = 0 时只有 y j 为 0 时才有意义，所以（4）式完全可以代替（3）式。
3.2 0 −1型整数规划解法之一（过滤隐枚举法） 解 0 −1型整数规划最容易想到的方法，和一般整数规划的情形一样，就是穷举法，
即检查变量取值为 0 或 1 的每一种组合，比较目标函数值以求得最优解，这就需要检查
5x1 + 4x2 ≤ 24 或 7x1 + 3x2 ≤ 45 。 为了统一在一个问题中，引入 0 − 1 变量 y ，则上述约束条件可改写为：
⎪⎨⎧57xx11
+ +
4x2 3x2
≤ ≤
24 45
+ +
yM (1 −
y)M
⎪⎩ y = 0或1
其中 M 是充分大的数。
约束条件
可改写为
x1 = 0 或 500 ≤ x1 ≤ 800
x2
=
3 2
, min
z
=
3 2
。
若限制整数得： x1 = 1, x2 = 1, min z = 2 。
（ii） 整数规划最优解不能按照实数最优解简单取整而获得。
1.3 求解方法分类：
（i）分枝定界法—可求纯或混合整数线性规划。
（ii）割平面法—可求纯或混合整数线性规划。
（iii）隐枚举法—求解“0-1”整数规划：
第二章 整数规划
§1 概论
1.1 定义
规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，
变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适
用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。
1.2 整数规划的分类
《管理运筹学》第二版)课后习题参考答案

《管理运筹学》第二版)课后习题参考答案

《管理运筹学》（第二版）课后习题参考答案第1章 线性规划（复习思考题）1．什么是线性规划？线性规划的三要素是什么？答：线性规划（Linear Programming ，LP ）是运筹学中最成熟的一个分支，并且是应用最广泛的一个运筹学分支。

线性规划属于规划论中的静态规划，是一种重要的优化工具，能够解决有限资源的最佳分配问题。

建立线性规划问题要具备三要素：决策变量、约束条件、目标函数。

决策变量是决策问题待定的量值，取值一般为非负；约束条件是指决策变量取值时受到的各种资源条件的限制，保障决策方案的可行性；目标函数是决策者希望实现的目标，为决策变量的线性函数表达式，有的目标要实现极大值，有的则要求极小值。

2．求解线性规划问题时可能出现几种结果，哪种结果说明建模时有错误？ 答：（1）唯一最优解：只有一个最优点； （2）多重最优解：无穷多个最优解； （3）无界解：可行域无界，目标值无限增大； （4）没有可行解：线性规划问题的可行域是空集。

当无界解和没有可行解时，可能是建模时有错。

3．什么是线性规划的标准型？松弛变量和剩余变量的管理含义是什么？答：线性规划的标准型是：目标函数极大化，约束条件为等式，右端常数项0≥i b ，决策变量满足非负性。

如果加入的这个非负变量取值为非零的话，则说明该约束限定没有约束力，对企业来说不是紧缺资源，所以称为松弛变量；剩余变量取值为非零的话，则说明“≥”型约束的左边取值大于右边规划值，出现剩余量。

4．试述线性规划问题的可行解、基础解、基可行解、最优解的概念及其相互关系。

答：可行解：满足约束条件0≥=X b AX ，的解，称为可行解。

基可行解：满足非负性约束的基解，称为基可行解。

可行基：对应于基可行解的基，称为可行基。

最优解：使目标函数最优的可行解，称为最优解。

最优基：最优解对应的基矩阵，称为最优基。

它们的相互关系如右图所示：5．用表格单纯形法求解如下线性规划。

s .t . ⎪⎩⎪⎨⎧≥≤++≤++0,,86238321321321x x x x x x x x x解：标准化 32124max x x x Z ++=s .t . ⎪⎩⎪⎨⎧≥=+++=+++0,,,,862385432153214321x x x x x x x x x x x x x 列出单纯形表故最优解为T X )6,0,2,0,0(*=，即2,0,0321===x x x ，此时最优值为4*)(=X Z ．6．表1—15中给出了求极大化问题的单纯形表，问表中d c c a a ,,,,2121为何值及变量属于哪一类型时有：（1）表中解为唯一最优解；（2）表中解为无穷多最优解之一；（3）下一步迭代将以1x 代替基变量5x ；（4）该线性规划问题具有无界解；（5）该线性规划问题无可行解。

《运筹学》习题与答案

《运筹学》习题与答案

《运筹学》习题与答案（解答仅供参考）一、名词解释1. 线性规划：线性规划是运筹学的一个重要分支，它主要研究在一系列线性约束条件下，如何使某个线性目标函数达到最大值或最小值的问题。

2. 动态规划：动态规划是一种解决多阶段决策问题的优化方法，通过把原问题分解为相互联系的子问题来求解，对每一个子问题只解一次，并将其结果保存起来以备后续使用，避免了重复计算。

3. 整数规划：整数规划是在线性规划的基础上，要求决策变量取值为整数的一种优化模型，用于解决实际问题中决策变量只能取整数值的情形。

4. 马尔可夫决策过程：马尔可夫决策过程是一种随机环境下的决策模型，其中系统的状态转移具有无后效性（即下一状态的概率分布仅与当前状态有关），通过对每个状态采取不同的策略（行动）以最大化期望收益。

5. 最小费用流问题：最小费用流问题是指在网络流模型中，每条边都有一个容量限制和单位流量的成本，寻找满足所有节点流量平衡的同时使得总成本最小的流方案。

二、填空题1. 运筹学的主要研究对象是系统最优化问题，其核心在于寻求在各种（约束条件）下实现（目标函数）最优的方法。

2. 在运输问题中，供需平衡指的是每个（供应地）的供应量之和等于每个（需求地）的需求量之和。

3. 博弈论中的纳什均衡是指在一个博弈过程中，对于各个参与者来说，当其他所有人都不改变策略时，没有人有动机改变自己的策略，此时的策略组合构成了一个（纳什均衡）。

4. 在网络计划技术中，关键路径是指从开始节点到结束节点的所有路径中，具有最长（总工期）的路径。

5. 对于一个非负矩阵A，如果存在一个非负矩阵B，使得AB=BA=A，则称A为（幂等矩阵）。

三、单项选择题1. 下列哪项不是线性规划的标准形式所具备的特点？（D）A. 目标函数是线性的B. 约束条件是线性的C. 决策变量非负D. 变量系数可以为复数2. 当线性规划问题的一个基解满足所有非基变量的检验数都非正时，那么该基解（C）。

A. 不是可行解B. 是唯一最优解C. 是局部最优解D. 不一定是可行解3. 下列哪种情况适合用动态规划法求解？（B）A. 问题无重叠子问题B. 问题具有最优子结构C. 问题不能分解为多个独立子问题D. 子问题之间不存在关联性4. 在运输问题中，如果某条路线的运输量已经达到了其最大运输能力，我们称这条路线处于（A）状态。

运筹学12-整数规划II-11

运筹学12-整数规划II-11

xi=
1 当Ai 点被选用时 0 当Ai 点未被选用时
Max Z=∑ci xi ∑bi xi≤B x1+ x2 +x3≤2 x4+ x5≥ 1 x6+ x7≥ 1
xi=0或1（i=1,2,…n）
School of Business ECUST
“或”约束
两种货物甲和乙，可以选择用车运或者用船运
甲
乙 托运限
制
车运体积 5 4
24
船运体积 7 3
45
重量 2 5
13
利润 20 10
问：应选择何种运输方式，两种货物各托运多少箱可以使 利润最大？
School of Business ECUST
解：设甲运x1箱，乙运x2箱 运货有车运和船运两种方式，用车运时的体积限制条件：
5x1+4x224
[1]
如用船运时关于体积的限制条件为
隐枚举法：不同于穷举法，只检查变量取值组 合的一部分就能找到问题的最优解。解题关键 是寻找可行解，产生过滤条件。
过滤条件：目标函数值优于计算过的可行解目 标函数值。
School of Business ECUST
maxZ=3X1 -2X2+5X3
X1+ 2X2 - X3 ≤2 ①
X1 + 4X2 +X3 ≤4 ②
其中M是个充分大的正数。
School of Business ECUST
产品 资源
Ⅰ
Ⅱ
Ⅲ 资源量
A
2
4
8
500
B
2
3
4
300
C
1
2
3
100
单件可变费用
4
运筹学整数规划课后答案吉林大学

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

运筹学整数规划课后答案吉林大学一、单项选择题1、以下说法正确的选项是（）。

A.分枝定界法在处理整数规划问题时，借用线性规划单纯形法的基本思想，在求相应的线性模型解的同时，逐步加入对各变量的整数要求限制，从而把原整数规划问题通过分枝迭代求出最优解B.用割平面法求解整数规划问题，构造的割平面有可能切去一些不属于最优解的整数解C.用分枝定界法求解一个极大化的整数规划时，当得到多于一个可行解时，通常可任取其中一个作为下界，再进行比拟剪枝D.整数规划问题最优值优于其相应的线性规划问题的最优值正确答案：A2、整数规划的最优解中，决策变量满足（）。

A.决策变量不是整数B.没有要求C.决策变量至少有一个是整数D.决策变量必须都是整数正确答案：D3、以下（）可以求解指派问题。

A.梯度法B.牛顿法C.单纯形法D.匈牙利法正确答案：D4、整数规划中，通过增加线性约束条件将原规划可行域进行切割，切割后的可行域的整数解正好是原规划的最优解的方法是（)。

A.隐枚举法B.0-1规划法C.分支定界法D.割平面法正确答案：D5、标准指派问题(m人，m件事)的规划模型中，有()个决策变量。

A渚B不对m*mB.mD.2m正确答案：B二、判断题1、匈牙利法可以直接求解极大化的指派问题。

()正确答案：x2、整数规划的可行解集合是离散型集合。

（）正确答案：V3、用分支定界法求一个极大化的整数规划时，任何一个可行解的目标函数值是该问题的目标函数值的下界。

（）正确答案：V4、用分支定界法求一个极大化的整数规划时，当得到多于一个可行解时，通常可以任取一个作为下界值，在进行比拟和剪枝。

（）正确答案：X5、用割平面求纯整数规划时，要求包括松弛变量在内的全部变量都取整数。

（）正确答案：V。

运筹学教材习题答案

方案三：在三年投资人应在第二年年初投资，两年结算一次，收益率是60％，这种投资最多不超过1.5万元；
方案四：在三年投资人应在第三年年初投资，一年结算一次，年收益率是30％，这种投资最多不超过1万元．
投资人应采用怎样的投资决策使三年的总收益最大，建立数学模型.
【解】是设xij为第i年投入第j项目的资金数，变量表如下
1.5某投资人现有下列四种投资机会,三年每年年初都有3万元（不计利息）可供投资：
方案一：在三年投资人应在每年年初投资，一年结算一次，年收益率是20％，下一年可继续将本息投入获利；
方案二：在三年投资人应在第一年年初投资，两年结算一次，收益率是50％，下一年可继续将本息投入获利，这种投资最多不超过2万元；
项目2
项目3
0
400
800
900
1
600
800
500
2
900
800
200
3
100
700
600
净现值
450
700
500
【解】以1％为单位，计算累计投资比例和可用累计投资额，见表（2）。
表（2）
年份
每种活动单位资源使用量（每个百分点投资的累计数）
项目1
项目2
项目3
累计可用资金(万元)
0
40
80
90
2500
3/4
C(j)-Z(j)
0
0
-0.375
-0.875
11.25
对应的顶点：
基可行解
可行域的顶点
X(1)=（0，0，2，12）、
X(2)=（0，2，0，6，）、
X(3)=（ 、
（0，0）
（0，2）

运筹学参考资料

运筹学参考资料一、单项选择题(本大题共0 0 分，共60 小题，每小题0 分)1. 割平面法若达不到整数要求条件，则针对某个变量( )。

C. 增加一个割平面2. 整数规划模型在其( )基础上附加了决策变量为整数的约束条件。

C. 松弛问题3. 整数规划模型在其松弛问题基础上附加了( )的约束条件。

B. 决策变量为整数4. 如果产出量与投入量(近似)存在线性关系，则可以写成投入产出的( ) D. 线性函数5. 分枝定界法不会增加( )的个数。

A. 决策变量6. 割平面法每切割压缩一次都要再增加( )。

B. 切割约束式7. 关于分配问题，叙述错误的是() 。

B. 任务书>08. 线性规划问题的特点是( )D. 约束条件限制为实际的资源投入量9. 运筹学的应用另一方面是由于电子计算机的发展，保证其( )能快速准确得到结果。

D. 反馈10. 纯整数或混整数规划问题的求解方法没有( )。

D. 避圈法11. 下列_____ 不是线性规划标准型的特征B. 决策变量无符号限制12. 以下不属于图解法步骤的是( )A. 建立目标函数13. 决策变量的一组数据代表一个( )D. 解决方案14. 整数规划的松弛问题指()A. 去掉决策变量取整约束形成的线性规划问题15. 资源数大于任务数的目标最小化分派问题需要( )。

C. 增加任务数至等于资源数，并赋M(无限大)值16. 关于线性规划标准型的特征，哪一项不正确_________B. 约束条件全为线性等式17. 动态规划的构成要素不包括( )。

D. 阶段和阶段静态参数18. 决策变量表示一种( )C. 活动19. 下列结论错误的是( )。

D. 一个图中一定存在圈.20. 下列图形所包含的区域不是凸集的是_________C. 圆环21. 动态规划的特点不含有( )。

D. 最优结果唯一22. 运筹学有助于人们在市场经济条件下的（）。

C. 资源合理配置23. 使目标函数增加最快的方向是____________ 。

运筹学第二版3.2 整数规划的求解

max Z c j x j ,
j 1 n
与它对应的线性规划问题即松弛问题 （B）为：
max Z c j x j ,
j 1 n
n aij x j bi (i 1,2,, m), j 1 x j 0且是整数( j 1,2,...n).
n aij x j bi (i 1,2,, m), j 1 x j 0( j 1,2,..., n).
xi
j m 1
j m 1
n
b
n
ij x j
bi 0 , 称为割平面的来源行．
[b
f
n
ij ] x j
[bi 0 ] f i 0
j m 1
f
n
ij x j .
为了使x i（i=1,2，…，m）是整数，上式右端必须是整式． 又注意到 f ij 0, x j 0
（2.25，3.75）
B2
B1
( B1 )
max Z 5 x1 8 x2 , x1 x2 6, 5 x1 9 x2 45, x2 3, x1 , x2 0.
( B2 )
max Z 5 x1 8 x2 , x1 x2 6, 5 x1 9 x2 45, x2 4, x1 , x2 0.
解 （1）设（A）的松弛问题为（B0），不考虑整数约束， 利用单纯形法求解（B0），其可行解域如图1所示，解得最 优解为： x 1=2.25，x 2=3.75，且Z0=41.25． ．
（2.25，3.75）
图1
图2


因x 1，x 2都是小数，可任选一个进行分枝．今选 x 2=3.75，对问题（B0）分别增加约束条件： x 2[3.75]=3 和 x 2[3.75]+1=4, 将（B0）分解成为两个子问题（B1）和（B2）．

最优化方法第二章整数规划


将这两个约束条件分别加入问题( IP ) ，形成两个子问题 ( IP1)和( IP2 ) ，再解这两个子问题的松弛问题( LP1)和( LP2) 。
16
（1）先不考虑整数约束，解(IP)的松弛问题(LP)： （2）定界： （3）分枝： （4）修改上、下界：按照以下两点规则进行。 ①在各分枝问题中，找出目标函数值最小者作为新的下 界； ②从已符合整数条件的分枝中，找出目标函数值最小者 作为新的上界。 （5）比较与剪枝 ： 各分枝的目标函数值中，若有大于 z 者，则剪掉此枝，表 明此子问题已经探清，不必再分枝了;否则继续分枝。
现在只要求出（LP1）和（LP2）的最优解即可。
20
⑵
先求（LP1）,如图所示。 x2 此时B 在点取得最优解。 A B C
⑴
x1 1, x2 3, z (1) 16
找到整数解，问题已探明， 此枝停止计算。 同理求（LP2） ,如图所示。
3
⑶
1 1 3 x1
在C 点取得最优解。
即 x1 2, x2 10 / 3,
bn
设： xij 表示从工厂运往销地的运量(i=1.2…m、 j=1.2…n), 1 在Ai 建厂 又设 Yi＝ （i=1.2…m） 0 不在Ai 建厂 模型：
m inZ cij xij f i yi
i 1 m
n x ij a i yi ( i 1.2 m ) j 1 m x ij b j (j 1.2n ) i 1 x ij 0, yi 0 或 1 (i 1.2m、j 1.2n )
零件 方 个数 式 零件
B1
Bn
零 件 毛坯数
m i nZ x j
j 1

整数规划2


6 3 7
为便于计算，常列出表格配合上述作图过程同时进行， 为便于计算，常列出表格配合上述作图过程同时进行，见下表
由上表知问题的最优解 即 ，代入原问题目标函数中，有max z = 4 代入原问题目标函数中，
某公司准备在五种畅销的货物中采购100万元的货物， 某公司准备在五种畅销的货物中采购100万元的货物， 100万元的货物 采购各种货物所需的金额和购进后所能获得的利润如下表所示。 采购各种货物所需的金额和购进后所能获得的利润如下表所示。 应采购哪几种货物才能使总获利最大。 应采购哪几种货物才能使总获利最大。
式中Kj 是同产量无关的生产准备费用。目标是使所有产品的总 是同产量无关的生产准备费用。 生产费用和为最小。 生产费用和为最小。 为表达生产费用函数， 为表达生产费用函数，需有一个逻辑变量yj ， =0时 0时 当xj =0时，yj =0 ；当xj > 0时，yj =1 。 为此引进一个特殊的约束条件： 为此引进一个特殊的约束条件： 将生产费用函数表达为： 将生产费用函数表达为：
引进人工变量yi ,设
运送货物到各个销售点的总费用为: 则从仓库i 运送货物到各个销售点的总费用为:
引进一个特殊的约束条件： 引进一个特殊的约束条件： 来说， 上式对具体的i 来说，当 个仓库被租用， 即第i 个仓库被租用，其费用为 当 可能为0 时，yi可能为0或1。 只能为1, 时，yi只能为1,
人 工作 1 2 3 4 人 工作 1 2 3 4 5 甲 乙 丙 丁 戊
10 5 15 20 甲
2 10 5 15 乙
3 15 14 13 丙
15 2 7 6 丁
9 4 15 8 戊
10 5 15 20 M
三．逻辑变量与数学模型

整数规划解法


31
问
题
2 5 (0) 8 11 (0) 5 4 2 3 (0) 0 0 11 4 5
只能对三个零元素进行标定（代表独立的零 元素只有三个），后续如何操作？
32
非直观法-步骤3（第一种情形）


(3) 重复(1)、(2)两个步骤，可能出现三种 情况： ① 效率矩阵每行都有一个打( )号的零元 素，很显然，按上述步骤得到的打( )号 的零元素都位于不同行不同列，只要令 对应打( )号零元素对应的决策变量xij=1 就找到了问题的最优解；


如何让效率矩阵中产生零元素； 如何让产生的零元素位于不同行和不同列。
17

（2）零元素的产生方法： 匈牙利法的基本定理1

如果从分配问题效率矩阵[aij]的每一行元 素中分别减去(或加上)一个常数ui (被称 为该行的位势)，从每一列分别减去(或 加上)一个常数vj (称为该列的位势)，得 到一个新的效率矩阵[bij]，若其中
33
第一种情形
甲
任务一
任务二 任务三 任务四
乙
丙
丁 x11=1，x22=1， x33=1，x44=1。
2 3 (0) 1 1 (0) 3 4 1 2 (0) 5 8 2 (0) 3
任务一→甲；二 →乙；三→丙； 四→丁
34
非直观法-4（第二种情形）

② 打( )号的零元素个数小于m，但未被划去的 零元素之间存在闭回路（全以0为拐点），这 时可顺着闭回路的走向，对每个间隔的零元素打 一( )号，然后对所有打( )号的零元素，或所在 行，或所在列画一条直线（一般会出现多种方 案）。如：
人
从人的 角度看 从任务 角度看
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

故最优解为：X
0010
1 0
0 1
0 0
0 0
，最优值为 14。
0001
6103 0211 1030 5300
5、在今后三年内有五项工程考虑施工，每项工程的期望收入和年度费用（千元）如表所示。假定 每一项已批准的工程要在三年内完成，目标是要选出使总收入达到最大的那些工程。
工程
第1年
费用（千元） 第2年
2 3 14 s. t. 4 2 18
, 0 且为整数
B：X=（3.25,2.5）z=14.75
x2<=3
x2>=4
B1：X=（3,2.67）z=14.33
B2：X=（4,1）z=14
x2<=2
x2>=3
B11：X=（3,2）z=13
B12：X=（2.5,3）z=13.5
所以，最优解为：X=（4,1），最优值为 14。
人
A
B
C
D
E
甲
25
29
31
42
37
乙
39
38
26
20
33
丙
34
27
28
40
32
丁
24
42
36
23
45
解：（1）由于任务数多于人数，所以需要一名假想的人，设为戊。因为工作 E 必须完成，故设戊完
成 E 的时间为 M，其余的假象为 0，建立如下的效率矩阵。
任务
人
A
B
C
D
E
甲
25
29
31
42
37
乙
39
38
解：变换目标函数 max Z=16‐（2 3 5 6 ）
Z值 x1
组合解 x2 x3 x4
是否满足约束条件 ①② ③
16 0 0 0 0 ×
14 1 0 0 0 √ ×
13 0 1 0 0 ×
11 0 0 1 0 ×
11 1 1 0 0 √ ×
10 0 0 0 1 ×
9
1010√ √ √
故，最优解为：（1,0,1,0），此时目标函数值为 7。
1 x1
1
0
0
-1
1 x2
0
1
0
1
0 s1
0
0
1
1
0 s2
0
0
0
0
σj
0
0
0
0
1 x1
1
0
0
-1
1 x2
0
1
0
1
0 x3
0
0
1
1
0 s2
0
0
0
0
σj
0
0
0
0
故，最优解为：X=（0,4），最优值为 4。
0
s1 1 -4/5 -6/5 -4/5 -1/5 0 0 0 1 0
0
s2 0 0 0 1 0 5/4 -1 -3/2 -5/4 -1/4
6
45
3
=> (X=(3,3),Z=39)
0
对 1 进行分支 1.1 max z 5 8 0 0 +0 +0
59 s. t.
,,,
6
45 4 => (无解) 2
0
1.2 max z 5
59 s. t.
,,,
8 0 0 +0 +0
6
45 4 => (X=(1,4.44),Z=40.5) 1
0
对 1.2 进行分支
2、用割平面法求解下列整数规划问题：
（1）max z 4 3
6 4 30
s. t.
2 10
, 0 且为整数
解：松弛问题为 max z 4 3 0 0
64
30
s. t.
2
10
,,, 0
Cj
4
3
0
0
进基 x1
CB XB
x1
x2
x3
x4
b
出基 x3
min{30/6,10/1}
0 x3
6
4
1
0
30
0 x4
（0,0,0） ×
（0,1,1） ×
（0,0,1） ×
（1,0,1） ×
（0,1,0） ×
（1,1,0） ×
（1,0,0） √ √ √ √ √ 6 （1,1,1） ×
故，最优解为：（1,0,1），此时目标函数值为 6。
（2）min z 2 3 5 6
623 35 s. t. 2
56
64 3
0 或 1（j 1,2,3,4）
1 3 0 11 8 00662 01210 10502 12340
故最优解为：X
00100 01000 1 0 0 0 0 ，最优值为 34。 00010 00001
9437
（2）
4 5
6 4
5 7
6 5
7523
9437
解：
4 5
6 4
5 7
6 5
7523
6104 0212 1031 5301
6103 0211 1030 5300
故最优解为X 为 131h。
01000 00010 0 0 0 0 1 ，即甲——B，乙——C 和 D，丙——E，丁——A，最少使用时间 10000 00100
1.2.1 max z 5
59 s. t.
,,,
8 0 0 +0 +0 6 45
5 => (X=(0,5),Z=40) 1
0
1.2.2 max z 5
80 6
0 +0 +0
59 s. t.
,,,
45 4 => (X=(1,4),Z=37) 1
0
所以，最优解为 X=（0,5），最优值为 40。
（2）max z 3 2
0
1/4
- 1/2
0
2 1/2
3 x2
0
1
- 1/8
3/4
0
3 3/4
0 s1
0
0
-1
-2
1
-2
σj
0
0
- 5/8 - 1/4
0
Cj
4
3
0
0
CB XB
x1
x2
x3
x4
0 s1
b
4 x1
1
0
1/2
0
- 1/4
3
3 x2
0
1
- 1/2
0
3/8
3
0 x4
0
0
1/2
1
- 1/2
1
σj
0
0
- 1/2
0
- 1/8
6、分配甲、乙、丙、丁 4 个人去完成 A、B、C、D、E 五项任务。每个人完成各项任务的时间如表 所示。由于任务数多于人数，故考虑： （1）任务 E 必须完成，其他 4 项工作中可任选 3 项完成； （2）其中有一人完成两项，其他每人完成一项。 试分别确定最优分配方案，使完成任务的总时间最少。
任务
是否可行解
否 否 否 否 否 否 是
4、用匈牙利法求解下列最小化指派问题：
4 8 7 15 12 7 9 17 14 10 （1） 6 9 12 8 7 6 7 14 6 10 6 9 12 10 6
解：
4 8 7 15 12 4 7 9 17 14 10 7 6 9 12 8 7 6 6 7 14 6 10 6 6 9 12 10 6 6
第3年
收入
1
5
1
8
20
2
4
7
10
40
3
3
9
2
20
4
7
4
1
15
5
8
6
10
30
可用基金最大数
25
25
25
解：这个问题表示为 0‐1 规划问题如下： max 20 40 20 15 30
5 4 3 7 8 25 7 9 4 6 25
8 10 2 1 10 25
0 或 1 j 1,2,3,4,5
最优解为 X=（1,1,1,1,0），最优值为 95。
s. t. 5
9 ,,,
58
0
0
b
x1
x2
x3
x4
1 0 2 1/4 - 1/4 2 1/4
0 1 -1 1/4 1/4 3 3/4
0 0 -1 1/4 - 3/4 41.25
8 0 0 +0
6 4 45 => (X=(1.8,4),Z=41)
0
2、max z 5
s. t. 5
9 ,,,
8 0 0 +0
0 4 5 17 7 19 18 5 0 8 7 0 0 13 0 1 19 12 0 17 47507
0 4 5 18 7 18 17 4 0 7 7 0 0 14 0 0 18 11 0 16 36406
0 0 1 18 3 18 13 0 0 3 11 0 0 18 0 0 14 7 0 12 32002
b
1 16/5 4/5 -4/5
0 4 2 1
3、用隐枚举法求解下列 0‐1 规划问题： （1）max z 4 3 2
253 5
4 s. t.
33 1
0 或 1（j 1,2,3）
解：通过观察找到一个可行解（1,0,1），此时目标函数值为 6；添加约束条件 4 3 2 6◎
解
◎①②③④Z