运筹学___整数规划习题

第四章 整数规划

4.1 某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料A 、材料B ，有关数据如下，问这两种设备各生产多少使工厂利润最大？（只建模不求解）

解：设生产甲、乙这两种设备的数量分别为x 1、x 2，由于是设备台数，则其变量都要求为整数，建立模型如下：

2123max x x z +=

⎪⎪⎩⎪⎪

⎨

⎧≥≤+≤+为整数

21212121,0,5

.45.01432x x x x x x x x

4.2 2197max x x z +=

⎪⎩⎪⎨⎧≥≤+≤+-且为整数

0,35

763.212121x x x x x x t s 割平面法求解。（下表为最优表）

线性规划的最优解为：

63max ,0,2/7,2/94321=====z x x x x

由最终表中得：

2

7221227432=++

x x x ④

将系数和常数项分解成整数和非负真分式之和，上式化为；

2

1

3221227432+=++

x x x 移项后得：

①②③④

①

②③

即：

2

1221227212212274343-≤--→≥+x x x x 只要把增加的约束条件加到B 问题的最优单纯形表中。

表4－3

表4－4

由x 1行得：

7

32

7171541=

-+

x x x 将系数和常数项分解成整数和非负真分数之和：

74476715541+=+-+

x x x x 得到新的约束条件： 74

767154-≤--x x

7

47671654-=+--x x x 在的最优单纯形表中加上此约束，用对偶单纯形法求解：

则最优解为3,421==x x ，最优目标函数值为z =55。

4.3 max z ＝4x 1＋3x 2＋2x 3

⎪⎪⎩

⎪⎪

⎨

⎧=≥+≥++≤+-10,,13

344352.32132

321321或x x x x x x x x x x x t s 隐枚举法 解：（1）先用试探的方法找出一个初始可行解，如x 1＝x 2＝0，x 3＝1。满足约束条件，选其作为初始可行解，目标函数z 0＝2。

（2）附加过滤条件

以目标函数0z z ≥作为过滤约束：

2234321≥++x x x

原模型变为：

max z ＝4x 1＋3x 2＋2x 3

⎪⎪⎪⎩⎪

⎪⎪

⎨⎧=≥++≥+≥++≤+-1

0,,22341

3344

352321321

32321321或x x x x x x x x x x x x x x 求解过程如表所示。

所以该0－1规划最优解为9,1**

3*2*1====z x x x 。

4.4 某公司拟在市东、西、南三区中建立门市部，有7个点A i （i ＝1，2，…，7）可供选择，要求满足以下条件：

（1）在东区，在A 1，A 2，A 3三个点中至多选两个； （2）在西区，A 4，A 5两个点中至少选一个； （3）在南区，A 6，A 7两个点为互斥点。 （4）选A 2点必选A 5点。

若A i 点投资为b i 万元，每年可获利润为c i 万元，投资总额为B 万元，试建立利润最大化的0－1规划模型。

解：设决策变量为

7,,2,1,

0,1 =⎩⎨

⎧=i A A x i i i 点未被选用

当点被选用当

建立0－1规划模型如下：

①②③④

i

i i x c x c x c x c z ∑==

+++=7

1

772211max

⎪

⎪⎪⎪⎩⎪

⎪⎪⎪⎨⎧==≤-=+≥+≤++≤⋅∑

=7

,,2,1,1001

1

2.5276

543217

1

i x x x x x x x x x x B x b t s i i i i ，或 4.5 某城市消防队布点问题。该城市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15 分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见表4－9，请帮助该市制定一个布点最少的计划。

i 6,,2,1,

0,1 =⎩⎨

⎧=i i i x i 不设消防站

表示在地区设消防站表示在地区

目标函数为

min z ＝x 1＋x 2＋x 3＋x 4＋x 5＋x 6

本问题的约束方程是要保证每个地区都有一个消防站在15分钟行程内。如地区1，由表4－9可知，在地区1及地区2内设消防站都能达到此要求，即

x 1＋x 2≥1

因此本问题的数学模型为：

min z ＝x 1＋x 2＋x 3＋x 4＋x 5＋x 6

x 1＋x 2 ≥1 x 1＋x 2 ＋x 6≥1 x 3＋x 4 ≥1 x 3＋x 4＋x 5 ≥1 x 4＋x 5＋x 6 ≥1 x 2 ＋x 5＋x 6 ≥1 x i ＝1或0 （i ＝1， (6)

4.7 一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等，每种物品的重量及重要性系数见表4－10所示，能携带的最大重量为25 kg ，试选择该队员所应携带的物品。

表4－10 s.t

解：引入0－1变量x i

⎩⎨

⎧=i

i

i x x x 不携带物品携带物品01 （i ＝1，…，7） 则0－1规划模型为：

max z ＝20x 1＋15x 2＋16x 3＋14x 4＋8x 5＋14x 6＋9x 7 s.t. 5x 1＋5x 2＋2x 3＋5x 4＋10x 5＋2x 6＋3x 7≤25

x i ＝0或1，i ＝1，0，…，7

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

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

4、整数规划中，通过增加线性约束条件将原规划可行域进行切割，切割后的可行域的整数解正好是原规划的最优解的方法是（）。 A.隐枚举法 B.0-1规划法 C.分支定界法 D.割平面法 正确答案：D 5、标准指派问题（m人，m件事）的规划模型中，有（）个决策变量。 A.都不对 B. m*m C. m D.2m 正确答案：B 二、判断题 1、匈牙利法可以直接求解极大化的指派问题。（） 正确答案：× 2、整数规划的可行解集合是离散型集合。（） 正确答案：√ 3、用分支定界法求一个极大化的整数规划时，任何一个可行解的目标函数值是该问题的目标函数值的下界。（）

4、用分支定界法求一个极大化的整数规划时，当得到多于一个可行解时，通常可以任取一个作为下界值，在进行比较和剪枝。（）正确答案：× 5、用割平面求纯整数规划时，要求包括松弛变量在内的全部变量都取整数。（） 正确答案：√

运筹学练习题

运筹学练习题 一、 填空题 1. 运输问题中，当总供应量小于总需求量时，求解时需虚设一个 点，此 点的供应量(或需求量)应为 。 2．线性规划中，任何基对应的决策变量称为 。整数规划 (是或不是)线性规划。 3．用单纯法求解目标函数是最大化的线性规划问题时，(0) 12(,,,,0,,0)T m X b b b =L L 为一 基本可行解，有一个检验数0m k σ+>，并且对,1,2,,0.i m k i m +=≤L ，有 a 其中,i m k a +是其m k x +的系数向量，那么该线性规划问题具有 解，若所有的检验数非正，且存在某个非基变量的检验数为零，则线性规划问题有 解。 4．在用图论解决问题时，常用 表示研究的对象，对象之间的关系用 表示。 5．在双代号网络图中，虚工作只表示相邻工作之间的 ，不占用 。 6．用对偶单纯型法求解线性规划问题时，得到了检验数为(1/2,2,4,0,0),λ=--- 则对偶问题的最优解为 ，假若此原问题为无界解，则其对偶问 题 可行解（存在或不存在）。 7．在资源受限制时，时间与资源优化的方法之一，是先将有限的资源从 活动调往 活动，以便均衡地使用资源 8. 决策分析的基本原则为 ，系统原则， , 信息对称、准全原则. 9 在一个工厂中，有一个厂址选择的决策，这属于 ，生产品合格标准选择属于 。 10. 决策的一般过程为目标确定， ， ，方案选优，决策。 11. 在决策中，人们只知道可能的情况是什么，但不知道各情况出现的可能性大小，有一个实力相对来说很小的企业，它应该采取 原则。如果知道了各情况的可能性，这属于 。 12 在决策中， ， ，损益函数是决策的三要素。

运筹学整数规划例题

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

整数规划习题

第五章 整数规划习题 5.1 考虑下列数学模型 )()(m in 2211x f x f z += 且满足约束条件 （1）或101≥x ，或102≥x ； （2）下列各不等式至少有一个成立： ??? ??≥+≥+≥+15 215152212121x x x x x x （3）021=-x x 或5或10 （4）01≥x ，02≥x 其中 )(11x f =?? ?=>+0,0 0,520111x x x 如如 =)(2 2x f ?? ?=>+0,00,612222x x x 如如 将此问题归结为混合整数规划的模型。 解：2211612510m in x y x y z +++= ? ? ?????????????? ????=≥≥=+++++-+-=-≤++-≥+-≥+-≥+?--≥?-≥?≤?≤），，＝（或，）（）（）（；）（11.110;00)4(1 11105503215215152)1(1010102111 1098711109872165462152142132312211i y x x y y y y y y y y y y x x y y y M y x x M y x x M y x x M y x M y x M y x M y x i 5.2 试将下述非线性的0-1规划问题转换成线性的0-1规划问题 3 3 3221max x x x x z -+= ?? ?==≤++-） ，（或3,2,110332321j x x x x j

解：令=y ???==否则，当,01132x x 故有y x x =32，又21x ，3 1x 分别与1x ，3x 等价，因此题中模型可转换为 31m ax x y x z -+= ? ???? ?? ??-+≤+≤≤≤++-变量均为10,,,1 3 323213 23 2321y x x x y x x x y x y x x x 5.3 某科学实验卫星拟从下列仪器装置中选若干件装上。有关数据资料见表5-1 要求：（1）装入卫星的仪器装置总体积不超过V ，总质量不超过W ；（2）A 1与A 3中最多安装一件；（3）A 2与A 4中至少安装一件；（4）A 5同A 6或者都安上，或者都不安。总的目的是装上取的仪器装置使该科学卫星发挥最大的实验价值。试建立这个问题的数学模型。 解： j j j x c z ∑==6 1 max ??? ?? ?????????????==≥+≤+≤≤∑∑==否则 仪器安装,0,111 654231 6 1 6 1j j j j j j j j A x x x x x x x W x w V x v 5.4 某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用最小。若10个井位的代号为s 1 ，s 2,…s 10,相应的钻探费用为c 1 ，c 2,…,c 10,并且井位选择上要满足下列限制条件：

运筹学第3版熊伟编著习题答案

运筹学（第3版）习题答案 第1章线性规划 P36 第2章线性规划的对偶理论 P74 第3章整数规划 P88 第4章目标规划 P105 第5章运输与指派问题P142 第6章网络模型 P173 第7章网络计划 P195 第8章动态规划 P218 第9章排队论 P248 第10章存储论P277 第11章决策论P304 第12章 多属性决策品P343 第13章博弈论P371 全书420页 第1章 线性规划 1.1工厂每月生产A 、B 、C 三种产品 ,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1－23所示． 310和130.试建立该问题的数学模型,使每月利润最大． 【解】设x 1、x 2、x 3分别为产品A 、B 、C 的产量，则数学模型为 1231231 23123123max 1014121.5 1.2425003 1.6 1.21400 150250260310120130,,0 Z x x x x x x x x x x x x x x x =++++≤??++≤??≤≤?? ≤≤??≤≤?≥?? 1.2建筑公司需要用5m 长的塑钢材料制作A 、B 两种型号的窗架．两种窗架所需材料规格 及数量如表1－24所示：

问怎样下料使得（1）用料最少；（2）余料最少． 【解 设x j （j =1,2,…，10）为第j 种方案使用原材料的根数，则 （1）用料最少数学模型为 10 1 12342567368947910 min 2800212002600223900 0,1,2,,10 j j j Z x x x x x x x x x x x x x x x x x x j ==?+++≥? +++≥?? +++≥??+++≥??≥=?∑L （2）余料最少数学模型为 2345681012342567368947910 min 0.50.50.52800 212002********* 0,1,2,,10 j Z x x x x x x x x x x x x x x x x x x x x x x x x j =++++++?+++≥? +++≥?? +++≥??+++≥??≥=?L 1.3某企业需要制定1～6月份产品A 的生产与销售计划。已知产品A 每月底交货，市场需求没有限制，由于仓库容量有限，仓库最多库存产品A1000件，1月初仓库库存200件。1～6月份产品A 的单件成本与售价如表1－25所示。 （2）当1月初库存量为零并且要求6月底需要库存200件时，模型如何变化。 【解】设x j 、y j （j ＝1，2，…，6）分别为1～6月份的生产量和销售量，则数学模型为

运筹学第五章 整数规划

第五章 整数规划 主要内容：1、分枝定界法； 2、割平面法； 3、0－1型整数规划； 4、指派问题。 重点与难点：分枝定界法和割平面法的原理、求解方法，0－1型规划模型的建立及求解步骤，用匈牙利法求解指派问题的方法和技巧。 要 求：理解本章内容，熟练掌握求解整数规划的方法和步骤，能够运用这些方法解决实际问题。 §1 问题的提出 要求变量取为整数的线性规划问题，称为整数规则问题（简称IP ）。如果所有的变量都要求为（非负）整数，称之为纯整数规划或全整数规划；如果仅一部分变量要求为整数，称为混合整数规划。 例1 求解下列整数规划问题 211020max x x z += ????? ? ?≥≤+≤+为整数2 1212121,0,13522445x x x x x x x x 如果不考虑整数约束，就是一个线性规划问题（称这样的问题为原问题相应的线性规划问题），很容易求得最优解为： 96max ,0,8.421===z x x 。

50 用图解法将结果表示于图中画“+”号的点都是可行的整数解，为满足要求，将等值线向原点方向移动，当第一次 遇到“+”号点（ 1,421==x x ）时得最优解为1,421==x x ，最优值为z=90。 由上例可看出，用枚举法是容易想到的，但常常得到最优解比较困难，尤其是遇到变量的取值更多时，就更困难了。下面介绍几种常用解法。 §2 分枝定界法 分枝定界法可用于解纯整数或混合的整数规划问题。基本思路：设有最大化的整数规划问题A ，与之相应的线性 规划问题B ，从解B 开始，若其最优解不符合A 的整数条件，那么B 的最优值必是A 的最优值 * z 的上界，记为 z ； 而A 的任意可行解的目标函数值是* z 的一个下界 z ，采取将B 的可行域分枝的方法，逐步减少z 和增大z ，最 终求得* z 。现举例说明： 例2 求解A 219040max x x z += ?????? ?≥≤+≤+为整数 21212121,0 ,7020756 79x x x x x x x x 解：先不考虑条件⑤，即解相应的线性规划B （①--④），得最优解=1x 4.81, =2x 1.82, =0z 356（见下 图）。 ① ② ③ ④ ⑤

运筹学习题

1. 考虑下面的线性规划问题： max z=2x1+3x2； 约束条件：x1+2x2≤6， 5x1+3x2≤15， x1，x2≥0． (1) 画出其可行域． (2) 当z=6时，画出等值线2x1+3x2=6． (3) 用图解法求出其最优解以及最优目标函数值． 2. 用图解法求解下列线性规划问题，并指出哪个问题具有惟一最优解、无穷多最优解、无界解或无可行解．(1) min f=6x1+4x2； 约束条件：2x1+x2≥1， 3x1+4x2≥3， x1，x2≥0． (2) max z=4x1+8x2； 约束条件：2x1+2x2≤10， -x1+x2≥8， x1,x2≥0． (3) max z=3x1-2x2； 约束条件：x1+x2≤1， 2x1+2x2≥4， x1，x2≥0． (4) max z=3x1+9x2； 约束条件：x1+3x2≤22， -x1+x2≤4， x2≤6， 2x1-5x2≤0， x1，x2≥0 3. 将下述线性规划问题化成标准形式： (1) max f=3x1+2x2； 约束条件：9x1+2x2≤30， 3x1+2x2≤13， 2x1+2x2≤9， x1，x2≥0． (2) min f=4x1+6x2； 约束条件：3x1-x2≥6， x1+2x2≤10， 7x1-6x2=4， x1，x2≥0． (3) min f=-x1-2x2； 约束条件：3x1+5x2≤70, -2x1-5x2=50， -3x1+2x2≥30， x1≤0，-∞≤x2≤∞．

(提示：可以令x′1=-x1，这样可得x′1≥0．同样可以令x′2-x″2=x2，其中x′2，x″2≥0．可见当x′2≥x″2时，x2≥0；当x′2≤x″2时，x2≤0，即-∞≤x2≤∞．这样原线性规划问题可以化为含有决策变量x′1，x′2，x″2的线性规划问题，这里决策变量x′1，x′2，x″2≥0．) 4. 考虑下面的线性规划问题： min f=11x1+8x2； 约束条件：10x1+2x2≥20， 3x1+3x2≥18， 4x1+9x2≥36， x1，x2≥0． (1) 用图解法求解． (2) 写出此线性规划问题的标准形式． (3) 求出此线性规划问题的三个剩余变量的值． 5. 考虑下面的线性规划问题： max f=2x1+3x2； 约束条件：x1+x2≤10， 2x1+x2≥4， x1+3x2≤24， 2x1+x2≤16， x1，x2≥0． (1) 用图解法求解． (2) 假定c2值不变，求出使其最优解不变的c1值的变化范围． (3) 假定c1值不变，求出使其最优解不变的c2值的变化范围． (4) 当c1值从2变为4，c2值不变时，求出新的最优解． (5) 当c1值不变，c2值从3变为1时，求出新的最优解． (6) 当c1值从2变为25，c2值从3变为25时，其最优解是否变化?为什么? 6. 某公司正在制造两种产品，产品Ⅰ和产品Ⅱ，每天的产量分别为30个和120个，利润分别为500元/个和400元/个．公司负责制造的副总经理希望了解是否可以通过改变这两种产品的数量而提高公司的利润．公司各个车间的加工能力和制造单位产品所需的加工工时如表2-4（25页）所示． (1) 假设生产的全部产品都能销售出去，用图解法确定最优产品组合，即确定使得总利润最大的产品Ⅰ和产品Ⅱ的每天的产量． (2) 在(1)所求得的最优产品组合中，在四个车间中哪些车间的能力还有剩余?剩余多少?这在线性规划中称为剩余变量还是松弛变量? (3) 四个车间加工能力的对偶价格各为多少?即四个车间的加工能力分别增加一个加工时数时能给公司带来多少额外的利润? (4) 当产品Ⅰ的利润不变时，产品Ⅱ的利润在什么范围内变化，此最优解不变?当产品Ⅱ的利润不变时，产品Ⅰ的利润在什么范围内变化，此最优解不变? (5) 当产品Ⅰ的利润从500元/个降为450元/个，而产品Ⅱ的利润从400元/个增加为430元/个时，原来的最优产品组合是否还是最优产品组合?如有变化，新的最优产品组合是什么?

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

第六章整数规划 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个店的费用情况如下表：

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

一、判断题 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

运筹学-第4章--整数规划习题

第四章 整数规划 ４.1 某工厂生产甲、乙两种设备,已知生产这两种设备需要消耗材料A 、材料B,有关数据如下,问这两种设备各生产多少使工厂利润最大？(只建模不求解） 解:设生产甲、乙这两种设备的数量分别为x １、x 2,由于是设备台数,则其变量都要求为整数,建立模型如下: 2123max x x z += ⎪⎪⎩⎪⎪ ⎨ ⎧≥≤+≤+为整数 21212121,0,5 .45.01432x x x x x x x x ４．2 2197max x x z += ⎪⎩⎪ ⎨⎧≥≤+≤+-且为整数 0,35 76 3.212121x x x x x x t s 割平面法求解。(下表为最优表） 线性规划的最优解为： 63max ,0,2/7,2/94321=====z x x x x 由最终表中得: 2 7221227432=++ x x x ﻩ④ 将系数和常数项分解成整数和非负真分式之和，上式化为； 2 132********+=++x x x 移项后得: ①②③④ ①②③

即： 2 1221227212212274343-≤--→≥+x x x x 只要把增加的约束条件加到B 问题的最优单纯形表中。 表4-4 由ｘ1行得: 7 32 7171541= -+ x x x 将系数和常数项分解成整数和非负真分数之和: 74476715541+=+-+x x x x 得到新的约束条件： 74 767154-≤--x x 7 47671654-=+--x x x 在的最优单纯形表中加上此约束，用对偶单纯形法求解： 则最优解为3,421 ==x x ，最优目标函数值为z *=55。 4．3 m ａx z =４ｘ1+３x 2+2x ３

运筹学习题解答(chap4 整数规划与分配问题)

第四章 整数规划与分配问题 一、建立下列问题的数学模型 1、P143, 4.1 利用0－1变量对下列各题分别表示成一般线性约束条件 (a) 221≤+x x 或53221≥+x x ； (b) x 取值0,3,5,7中的一个； (c) 变量x 或等于0，或50≥； (d) 若21≤x ，则12≥x ，否则42≤x ； (e) 以下四个约束条件中至少满足两个： 6225433121≥+≥≤≤+x x x x x x ，，，。 解：(a) 设 ⎩⎨ ⎧=否则。 ，个条件起作用； 第1 i ,0y i （i=1,2）,M 为任意大正数。 则有 ⎪⎩⎪ ⎨⎧=+≥++≤+1 y y My -5x 3x 2My 2x x 21 221121 (b) 设⎩⎨ ⎧=≠=i x i x y i , 1, 0，7,5,3,0=i ，则原条件可表示为 ⎩⎨⎧=++++++=175307530 7 530y y y y y y y y x (c) 设⎩⎨ ⎧≥==50 , 10, 0x x y ，则原条件可表示为 ⎪⎩⎪ ⎨⎧≥--≥≤0)1(50x M y x yM x (d)⎩⎨ ⎧=否则。 ，组条件起作用； 第1i , 0y i （i=1,2）,M 为任意大正数。 则有

⎪⎪⎪⎩⎪ ⎪⎪⎨⎧=++≤->-≥+≤. 1, 4,2,1,2212 2211211y y My x My x My x My x (e)设⎩⎨ ⎧=个条件不成立 第个条件成立 第i , 1i , 0y i ，4,3,2,1i =，则原条件可表示为： ⎪⎪⎪⎩⎪ ⎪⎪⎨⎧≤+++-≥+-≥+≤+≤+2 y y y y M y 6x x M y 2x M y 2x M y 5x x 43214 433321121 2、P143, 4.2 某钻井队要从以下10个可供选择的井位确定5个钻井探油，目的是使得总的钻探费用最小。若10个井位代号为101S ,...,S ，相应的钻探费用为 101C ,...,C ，并且井位的选择要满足下列条件： （1）或选择1S 和7S ，或选择8S ； （2）选择了3S 或4S 就不能选择5S ，反过来也一样； （3）在10962S ,S ,S ,S 中最多只能选两个。 请建立该问题的数学模型。 解：设⎩⎨⎧=个井位未被选择 第，个井位被选择 第i i x i 0,1，则 目标函数是：10102211......MIN x c x c x c Z +++= 约束条件： 10 (21105) 2 1115 1 876554538171，，，型变量，是=-=≤+++≤+≤+=+=∑=i x x x x x x x x x x x x x x i i i

整数规划

若某钻井队要从以下10个可供选择的井位中确定5个钻井探油。使总的钻探费用为最小。若10个井位的代号为S 1,S 2．…，S 10相应的钻探费用为C 1 ,C 2 ,… C 10，并且井位选择要满足下列限制条件： (1)在s 1，s 2，S 4中至多只能选择两个； （2）在S 5，s 6中至少选择一个；（3）在s 3，s 6，S 7，S 8中至少选择两个。 试建立这个问题的整数规划模型 解：设x j （j=1,…,10）为钻井队在第i 个井位探油 minZ=j j j x c ∑=10 1 背包问题：一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量合重要性系数如表所示。设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。 序号 1 2 3 4 5 6 7 物品 食品 氧气 冰镐 绳索 帐篷 照相器材 通信设备 重量/Kg 5 5 2 6 12 2 4 重要性系数 20 15 18 14 8 4 10 解：引入0—1变量x i , x i =1表示应携带物品i ，,x i =0表示不应携带物品I ⎩⎨ ⎧==≤++++++++++++=7 ,...,2,1,1025 4212625510481418152076543217654321i x x x x x x x x x x x x x x x naxz i 或 集合覆盖和布点问题 某市消防队布点问题。该市共有6个区，每个区都可以建消防站，市政府希望设

置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15min 内赶到现场。据实地测定，各区之间消防车行驶的时间见表，请制定一个布点最少的计划。 解：引入0—1变量x i , x i =1表示在该区设消防站，,x i =0表示不设 ⎪⎪⎪⎪⎩ ⎪⎪⎪⎪⎨⎧=≥++≥++≥++≥+≥++≥++++++=0 11 11 111min 6 5 2 654 543 436 2 12 1654321或i x x x x x x x x x x x x x x x x x x x x x x x z 解得： X*=(0,1,0,1,0,0)’ Z*=2 某公司现有5个项目被列入投资计划，各项目的投资额和期望的投资收益如下表所示：

南开大学2021年9月《运筹学》作业考核试题及答案参考7

南开大学2021年9月《运筹学》作业考核试题及答案参考 1. 用Excel中的“规划求解”模块可以求解大规模整数规划问题。( ) A.正确 B.错误 参考答案：B 2. 企业价格决策目标是获得最大的( )。 企业价格决策目标是获得最大的( )。 A.销售额 B.总利润 C.市场占有率 D.知名度 参考答案：B 3. 家庭中的存储储备品，工厂储备原材料，商店存储商品等都是存储问题。( ) A.正确 B.错误 参考答案：A 4. 割集中弧的容量之和称为割量。( ) A.错误 B.正确 参考答案：B 5. 线性规划问题有可行解，则( ) A.必有基可行解 B.必有唯一最优解 C.无基可行解 D.无唯一最优解 参考答案：A

6. 在电子表格模型中，有关函数VARP表述正确的是( )。 A、用来求解基于给定样本的总体方差 B、用来求解两个变量的协方差 C、用来求解两个数组矩阵的乘积 D、以上说法均不正确 参考答案：A 7. 数学规划的研究方向，包括线性规划、非线性规划、对偶规划、几何规划、整数规划、动态规划及多目标规划等。( ) A.正确 B.错误 参考答案：A 8. 线性规划的可行域无界则具有无界解。( ) T.对 F.错 参考答案：F 9. 网络分析包括最小支撑树问题、最短路问题、最大流问题，以及网络计划评审与优化问题等。( ) A.正确 B.错误 参考答案：A 10. 在市场经济环境下，当资源的市场价格低于影子价格时，可以购进该资源。( ) A.正确 B.错误 参考答案：A 11. 线性规划问题求解结果中可行域无解与目标函数的目标值不收敛是一回事。( )

T、对 F、错 参考答案：T 12. 下列关于非线性规划问题的叙述正确的是( ) A.目标函数中有一个是决策变量的非线性函数 B.约束条件中有一个是决策变量的非线性函数 C.目标函数是决策变量的线性函数，而约束条件中有一个是决策变量的线性函数 D.以上说法均不正确 参考答案：AB 13. 在纯市场经济条件下，买进资源的条件是( ) A.资源的市场价格低于影子价格 B.资源的市场价格高于影子价格 C.资源的市场价格等于影子价格 D.选项A正确，BC不正确 参考答案：AD 14. 无圈的图称为树图，简称树。( ) A.正确 B.错误 参考答案：B 15. 典型的无概率决策准则，不包括( )。 A.乐观准则 B.折中准则 C.等可能准则 D.最大后悔值准则 参考答案：D 16. 关于带收发点的容量网络中从发点到收点的一条增广路，以下叙述( )不正确。

整数规划例题

〈运筹学〉补充例题 例题 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.４随着企业改革的不断深化，该企业的经理的管理思想产生了变化，由原来的追求销售额变为注重销售利润，因此，要考虑资源的成本。工厂的各种产品所需要的机时、人

128501-管理运筹学-习题-03-整数规划

习题 3-1某厂拟在A 、B 、C 、D 、E 五个城市中建立若干个配送中心，各处设配送中心都需要资金、人力、设备等，而这样的需求量及能提供的利润各处不同，有些点可能亏本，但却能得到贷款和人力等资源。设数据已知，由下表所示。厂方应作出何种最优选址方案能使总利润最大。请建立该问题的数学模型。 3-2用分支定界法求解下列整数规划问题 ⎪⎩⎪⎨⎧≥≥+≤+⎪⎩⎪⎨⎧≥≥+≤+-+=+=且为整数且为整数）（）（0,5427230,50 21010m 2min 12121212 12121212 1x x x x x x x x x x x x x x z ax x x z 3-3用割平面法求解下列整数规划问题 ⎪⎩⎪⎨⎧≥≤+≤+⎪⎩⎪⎨⎧≥≥+≥++=+=且为整数且为整数）（）（0,102920,10 29232m 232min 1212121212121212 1x x x x x x x x x x x x x x z ax x x z 3-4用隐枚举法求解下列0-1规划问题 ⎪⎪⎪⎩⎪⎪⎪⎨⎧=≤+≤+≤++≤-++-=1 ,0,,16 2444233max 32122 323213213 21x x x x x x x x x x x x x x x x z

3-5安排4个人做4项不同的工作，每个人完成工作所需要的时间如下表所示， （1）应如何指派，可使总的时间最少？ （2）如果表中的数据为创造的效益，应如何指派，使总效益最大？ （3）如果在表中增加一个人（一行），完成A、B、C、D工作的时间分别为16、17、20、21天，这时应如何指派，使总时间最少？ 3-6对每题结论进行判断，如果结论错误请改正。 （1）整数规划的最优解是先求相应的线性规划的最优解然后取整得到。 （2）求最大值整数规划问题的目标函数值是各分支函数值的上界。 （3）求最小值整数规划问题的目标函数值是各分支函数值的上界。 （4）整数规划的可行解集合是离散型集合。 （5）0一1规划的变量有n个，则有2n个可行解。 （6）割平面约束是将可行域中一部分非整数解切割掉。 （7）指派问题的数学模型属于混合整数规划模型。 （8）在指派问题的效率表的某行加上一个非零数最优解不变。 （9）在指派问题的效率表的某行乘以一个大于零的数最优解不变。

运筹学习题库

运筹学习题库 一、线性规划 1．某工厂生产甲、乙、丙三种产品，单位产品所需工时分别为2、3、1个工时；单位产品所需原材料分别为3、1、5公斤；单位产品利润分别为2元、3元、5元。工厂每天可利用的工时为12个，可供应的原材料为15公斤。 1）试确定使总利润为最大的日生产计划和最大利润。 2）若由于原材料涨价，使得产品丙的单位利润比原来减少了2元，问原来的最优生产计划变否？若不变，说明为什么；若变，请求出新的最优生产计划和最优利润。 3）在保持现行最优基不变的情况下，若要增加一种资源量，应首先考虑增加哪种资源？ 为什么？单位资源增量所支付的费用是多少才合算？为什么？ 2．给出一线性规划问题如下： max z = 3x1 + x2 x1 + x2≤4 －x1 + x2≤2 6x1 + 2x2≤18 x１，x2≥0 试用对偶理论判断该问题是否存在以x１、x2和x3为基变量的最优解？ 3．用单纯形法求解某个目标函数为max，约束为≤形式，x4、x5为松弛变量的线性规划问题的最终表如下： 试用改进单纯形法原理求该问题的数学模型。 4．给出一个线性规划问题如下： max z = x1 +2 x2 +3 x3 x1 + 2x2 + 3x3≤8 4x1+ 5x3≤12 x1，x2 ，x3 ≥0 已知其对偶问题的最优解为Y* = (1，0 )，试用对偶理论求上述问题的最优解和最优值。5．试用大M法求下述线性规划问题的最优解和最优值（不能用图解法）：

max z = 3x 1 – 3 x 2 x 1 + x 2 ≥1 2x 1 + 3x 2 ≤6 x 1，x 2 ≥0 6．已知一线性规划问题如下： max z = 5x 1 + 2 x 2 + 4 x 3 3 x 1 + x 2 + 2 x 3 ≤ 4 6 x 1 + 3 x 2 + 5 x 3 ≤ 10 x 1，x 2，x 3 ≥ 0 试用松紧定理判断X = ( 0，0，2 )T 是否是该问题的最优解，若不是，说明为什么；若是， 请求出相应的目标函数值。 7．试用单纯形法或对偶单纯形法求解线性规划问题（不能用图解法）： min z = x 1 + x 2 x 1 + 2x 2 ≥ 2 x 1 – x 2 ≥ –1 x 1，x 2 ≥ 0 二、运 输 问 题 1．已知某运输问题如下（单位：百元/吨）： 求：1）使总运费最小的调运方案和最小运费。 2）该问题是否有多个最优调运方案？若没有，说明为什么； 若有，请再求出一个最优调运方案来。 2．已知某运输问题如下（单位：百元/吨）：

最新最全整数规划习题(完整版)

第五章整数规划习题 5.1考虑以下数学模型 min z = fi(Xi) + f2 (x2) 且满意约束条件 (1) 或 ,或X2 河0： (2) 以下各不等式至少有一个成立： 2x〔+ x2 *5 + X2 >15 x〔+2x2 215 (3) Xi -X2 =0或 5 或10 (4) 为No , X2 2 0 其中 20 + 5xi,如>0 fi(xO= 10 ，如=° 12 + 6x2,如>0 f2(X2)= .0 ，如=0 将此问题归结为混合整数规划的模型； minz = 1°y〔* 5xi 十12y2 -6x2 （0）xi V yi ,M; x2 y2• M （1）% >10- y3

X2 己10 —（1 — y3）• M （2）X1 +x A5- y4M 2 Xi +X2 2 15- y5M X1 + 2x2 2 15 - yeM 第 +y5 + y6 < 2 （3）x1 _X2 =0y7 -5y8+5y9 -10y w+ 11yn 工y8 + y9 + Yw + y” = 1 （4）xi >0，x2 - 0; yi = 0或 5.2试将下述非线性的0-1规划问题转换成线性的0-1规划问题 _ 2 + 3 max z - % x2 x3 - x3

一 2xi + 3x2 + X3 <3 Xj = 0或 1, = 1,2,3) ，当=Xs = 1 X 2 2 3 又X 〔，Xi 分别与X 、X3等价，因此题中模型可转换为 max z = % + y - X3 —2xi + 3x2 X3 — 3 y WX2 "X3 X2 * X3 V y F 一Xi ，X2，X3，y 均为 一1 变 5.3某科学试验卫星拟从以下仪器装置中选如干件装上； 有关数据资料见表5-1 表5-1 要求：(1)装入卫星的仪器装置总体积不超过 V,总质量不超过 W (2) A 与A 中最多安装一件；(3)氏与4中至少安装一件；(4) As 同玲或者都安上，或者都 担心；总的目的是装上取的仪器装置使该科学卫星发挥最大的试验价值； 试建立 这个问题的数学模型； 解： 6 max z = Z CjXj j = '6 三 VjXj -V jT 解：令y = 故有 x 2x3 =y,

运筹学习题及解答(熊义杰版)

《运筹学》习题及其解答 目录 《运筹学》习题及其解答 (1) 第一章 线性规划 ........................................................................................................... 1 第二章 对偶规划及灵敏度分析 ........................................................................................... 12 第三章 运输问题 ................................................................................................................... 17 第四章 整数规划 ................................................................................................................... 22 第五章 动态规划 ................................................................................................................... 27 第六章 图与网络分析 .. (34) 第一章 线性规划 1.1将下列线性规划模型转化为标准型： （1）2164.x x Z Min += （2）212.x x Z Min --= ⎪⎪⎩⎪⎪⎨ ⎧≥=-≤+≥-0,46710263. .21212 121x x x x x x x x t S ⎪⎪⎩ ⎪⎪⎨ ⎧≤≥+-=--≤+03023505270 53..1212 121x x x x x x x t S 【解】（1）—2164)(x x Z Max --=- ⎪⎪⎩⎪⎪⎨ ⎧≥=-=++=--0 ,,,4671026 3. .2121212 21121s s x x x x s x x s x x t S （2）—v u y Z Max 22)(1+--=- ⎪⎪⎩ ⎪⎪⎨ ⎧≥=-+=+-=+-+-0,,302235055270553. .111 11v u y v u y v u y s v u y t S 1.2 用图解法解下列线性规划问题：