《运筹学》课后习题答案 第2章 对偶原理与灵敏度分析

一、选择题

1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

二、判断题

1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

三、写出下列线性规划问题的对偶问题

123

12312

3123123(1)2242352

373..465,,0

Min Z x x x x x x x x x s t x x x x x x =++++≥⎧⎪++≤⎪⎨++≤⎪⎪≥⎩ 对偶问题：123

12312

3123123()235232342..57640,,0

a MaxW y y y y y y y y y s t y y y y y y =++++≤⎧⎪++≤⎪⎨++≤⎪⎪≥≤⎩

123

1232313132(2)2433212

210..215,0,0

Max Z x x x x x x x x s t x x x x x =-+-+≤⎧⎪+≥⎪⎨

-=⎪⎪≥≤⎩ 对偶问题：123

1231

23123123()121015023204..2230,0,b MinW y y y y y y y y y s t y y y y y y free

=++++≥⎧⎪-+≥⎪⎨+-≥⎪⎪≥≤⎩

12312312312123(3)2323253..100,0,Max Z x x x x x x x x x s t x x x x x free

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

+=⎪⎪≥≤⎩ 对偶问题：123

123123123123()253102

21..3030,0,c MinW y y y y y y y y y s t y y y y y y free

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

-+⋅=⎪⎪≥≤⎩

123132312123(4)23332210..280,,0Min Z x x x x x x x s t x x x x free x =+-+≥⎧⎪+≤⎪⎨+=⎪⎪≤≥⎩ 对偶问题：123

123123123123()3108021

022..32030,0,d MaxW y y y y y y y y y s t y y y y y y free

=+++⋅+≥⎧⎪⋅++=⎪⎨

++⋅≤-⎪⎪≥≤⎩

四、应用对偶单纯形法求解下列线性规划问题

12121212

(1)24..75,0Min Z x x x x s t x x x x =++≥⎧⎪+≥⎨⎪≥⎩

标准型：

'12

12312412

24..75,0Max Z x x x x x s t x x x x x =----+=-⎧⎪--+=-⎨⎪≥⎩

X*=(23/13, 6/13, 0, 0)T , Z ’max=-29/13 原问题X*=(23/13, 6/13, 0, 0)T , Zmin=29/13.

12312312

3123123(2)42245363..5212,010,Min Z x x x x x x x x x s t x x x x x x =++++≥⎧⎪-

+≥

⎪⎨++≥⎪⎪≥⎩ 标准型： 123

123412351236123456'42245363..5212,,10,,,0Max Z x x x x x x x x x x x s t x x x x x x x x x x =------+=⎧⎪-+-+=-⎪⎨

----+=-⎪⎪≥⎩

237/23)T , Zmin=226/23.

3. 123123123

1232242352373..4650,1,2,3

j Max Z x x x x x x x x x s t x x x x j =---++≥⎧⎪++≤⎪⎨

++≤⎪⎪≥=⎩

解：

1231231231232242352373..4650,1,2,3

j Max Z x x x x x x x x x s t x x x x j =---++≥⎧⎪++≤⎪⎨

++≤⎪⎪≥=⎩

标准型：123

12341235

12362242352

373

..4650,1,2,3,4,5,6

j Max Z x x x x x x x x x x x s t x x x x x j =---++-=⎧⎪+++=⎪⎨

+++=⎪⎪≥=⎩

*max

(0,,0,0,,)3333

T X Z ==-

五、应用对偶理论证明如下线性规划问题有可行解，但无最优解

六、灵敏度分析题

1. 解：依题意知，*

811

(,

,0,0)99

T =X ，max

103Z =，1

51991299B -⎛⎫- ⎪= ⎪ ⎪- ⎪⎝⎭

，2115B ⎛⎫∴= ⎪⎝⎭

(1,2,0,0)=C ，(3,7)T =b ，3411

;33

σσ=-=-

（1）若目标函数122Z x x =+变为1235Z x x =+，则

511099(0,0)(3,5)120199⎛⎫- ⎪⎛⎫==- ⎪ ⎪ ⎪⎝⎭

- ⎪⎝⎭-1

N N B σC -C B N ＝107(,)99-- 因此，最优解不变，但最优值变为max 79Z =

。 （2）当(3,7)T =b 变为(8,11)T =b 时，'512989990121114999⎛⎫⎛⎫- ⎪

⎪⎛⎫===≥

⎪ ⎪ ⎪ ⎪ ⎪⎝⎭- ⎪ ⎪⎝⎭⎝⎭

-1

b B b 因此，最优解结构不变，数值变为*2914(

,,0,0)99T =X ，max 5719

93

Z ==。

（3）新产品C 3=1,3(1,3)T P =,则在系数矩阵中要增加一列，对应决策变量3x

1

333B c C B P σ-=-5111991(1,2)0123399⎛⎫- ⎪⎛⎫=-=-≤ ⎪ ⎪ ⎪⎝⎭

- ⎪⎝⎭

所以最优解和最优值不变，该产品不宜生产。

（4）若产品1的消耗系数由1(2,1)T P =变为1

(1,2)T

P =则 1

111B c C B P σ-=-511991(1,2)012299⎛⎫- ⎪⎛⎫=-=

⎪ ⎪ ⎪⎝⎭- ⎪⎝⎭

N N =--1

B σ

C C B N 51101199(0,0)(1,2)(,)12013399⎛⎫- ⎪⎛⎫=-=-- ⎪ ⎪

⎪⎝⎭

- ⎪⎝⎭ 故最优解改变，但最优值没变，产品结构无变化。

2. 解：设甲、乙两种产品的产量分别为1x 和2x 件。

原料A 消耗花费的钱：12(24)1x x +⨯ （元）。 原料B 消耗花费的钱：12(32)2x x +⨯ （元） 产品销售收益：121316x x +

扣除成本后的利润：1212121316(24)2(32)Z x x x x x x =+-+-⨯+

（1）利润最大化模型为：

12

1212125824160

.32180,0

Max Z x x x x s t x x x x =++≤⎧⎪

+≤⎨⎪≥⎩

解得：最优解*(50,15,0,0)T =X ，最优值max 370Z =（元）。

（2）从最优表中可知，原料A 的影子价格为*

13 1.75y σ=-=（7/4），原料B 的影子价格为*

240.5y σ=-=（1/2），显然原料A 更珍贵。

（3）若市场上有A 原料出售，企业应该购入以扩大生产。假设在保持最优解不

变的前提下，最多购入Q （kg ）。（请注意这里的逆矩阵先写第二行再第一行）

1

111604203118084Q -⎛⎫

- ⎪+⎛⎫==≥ ⎪ ⎪ ⎪⎝⎭- ⎪

⎝⎭B X B b

15004

31508Q Q ⎧

-≥⎪⎪⎨

⎪+≥⎪⎩

200Q ≤ 所以在保持最优解不变的前提下，最多只能再购入200kg 。

此时最优解为：*(0,90,0,0)T =X ，最优值max 720Z =（元）。可增加利润350=(720-370)元。

（4）若乙产品价格可达到20元／件，此时原线性规划模型中产品乙的价值系数变成C2＝12。

111042(0,0)(5,12)310184⎛⎫- ⎪⎛⎫==- ⎪ ⎪ ⎪⎝⎭- ⎪

⎝⎭-1

N N B σC -C B N ＝133(,)42-，40σ∴>， 选4x 进基，继续迭代，求出最优解和最优值。

此时最优解为：*(0,40,0,100)T =X ，最优值max 480Z =（元）。

（5）若新产品丙可投入开发，设其在模型中的价值系数为C3。

1

333B c C B P σ-=-113423(5,8)031484c ⎛⎫

- ⎪⎛⎫=-≥

⎪ ⎪ ⎪⎝⎭- ⎪⎝⎭

3297.254c ≥

= 同时，一单位丙的原料成本为3*1+4*2=11元，所以产品丙的价格至少应为7.25+11=18.25元。

七、研究讨论题

运筹学第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所示． 表1－23 产品 资源 A B C 资源限量 材料(kg) 1.5 1.2 4 2500 设备(台时) 3 1.6 1.2 1400 利润(元/件) 10 14 12 根据市场需求,预测三种产品最低月需求量分别是150、260和120,最高月需求是250、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－24 窗架所需材料规格及数量 型号A 型号B 每套窗架需要 材料 长度（m ） 数量(根) 长度(m) 数量(根) A 1：2 2 B 1：2.5 2 A 2：1.5 3 B 2：2 3 需要量（套） 300 400

运筹学作业2(清华版第二章部分习题)答案

运筹学作业2（第二章部分习题）答案 2．1 题 （P . 77） 写出下列线性规划问题的对偶问题： （1）123123123123123m ax 224..34223343500,z x x x s t x x x x x x x x x x x x =++? ? ++≥??++≤? ? ++≤? ≥≥??无约束，； 解：根据原—对偶关系表，可得原问题的对偶规划问题为： 123123123123123m ax 235..223424334,0,0w y y y s t y y y y y y y y y y y y =++??++≤??++≤? ?++=? ≥≤≤?? （2）111 1 m in ,1,,,1,,0,1,,;1,,m n ij ij i j n ij ij i j n ij ij j j ij z c x c x a i m c x b j n x i m j n ====?=? ? ? ==????==??≥==??∑∑∑∑ 解：根据原—对偶关系表，可得原问题的对偶规划问题为： 11m ax 1,,;1,,m n i i j j i j i j ij i w a u b v u v c i m j n u ==? =+???+≤? ?==? ??∑∑ j 无约束，v 无约束 2．2判断下列说法是否正确，为什么？ （1） 如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； 答：错。 因为：若线性规划的原问题存在可行解，且其对偶问题有可行解，则原问题和可行问题都将有最优解。但，现实中肯定有一些问题是无最优解的，故本题说法不对。

例如原问题 12 12212m ax 31..30,0z x x x x s t x x x =++≥??≤? ?≥≥?有可行解，但其对偶问题 12 11212m in 33..10,0w y y y s t y y y y =+≥??+ ≥??≤≥?无可行解。 （2） 如果线性规划的对偶问题无可行解，则原问题也一定无可行解； 答：错，如（1）中的例子。 （3） 在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或求极小，原问题可 行解的目标函数值一定不超过其对偶问题可行解的目标函数值。 答：错。正确说法是：在互为对偶的一对原问题与对偶问题中，求极大的问题可行解的目标函数值一定不超过求极小的问题可行解的目标函数值。 （4） 任何线性规划问题具有唯一的对偶问题。 答：正确。 2．5给出线性规划问题 123 123123123123m ax 221.. 22 0,0,0z x x x x x x x x x s t x x x x x x =+++-≤? ?-+=?? ++≥??≥≥≥? 写出其对偶问题；（2）利用对偶问题性质证明原问题目标函数值1z ≤ 解：（1）原问题的对偶问题为： 123 123123123123m in 22212.. 10,,0w y y y y y y y y y s t y y y y y y =++++≥? ?-+≤?? -++=? ?≥≤?无约束 （2）取()011T y =，既1230,1,0y y y ===，经验证，()011T y =是对偶问题的一个可行解，并且1w =。由对偶问题的性质可得1z w ≤= 2．9 用对偶单纯形法求解下列线性规划问题： （2）123 123123 123m in 524324..63510,,0z x x x x x x s t x x x x x x =++++≥??++≥??≥? ,

【优质】运筹学第三版课后习题答案-推荐word版 (13页)

本文部分内容来自网络整理，本司不为其真实性负责，如有异议或侵权请及时联系，本司将立即删除！ == 本文为word格式，下载后可方便编辑和修改！ == 运筹学第三版课后习题答案 篇一：运筹学第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.试建立该问题的数学模型,使每月利润最大． 【解】设x1、x2、x3分别为产品A、B、C的产量，则数学模型为 maxZ?10x1?14x2?12x3?1.5x1?1.2x2?4x3?2500?3x?1.6x?1.2x?1400 23?1 ? ?150?x1?250? ?260?x2?310?120?x3?130???x1,x2,x3?0 1.2 建筑公司需要用5m长的塑钢材料制作A、B两种型号的窗架．两种窗架所需材料规格 及数量如表1－24所示：

问怎样下料使得（1）用料最少；（2）余料最少．【解 设xj（j=1,2,…，10）为第j种方案使用原材料的根数，则（1）用料最少数学模型为 minZ??xj j?1 10 ?2x1?x2?x3?x4?800? ?x2?2x5?x6?x7?1200 ? ?x3?x6?2x8?x9?600?x?2x?2x?3x?900 7910 ?4??xj?0,j?1,2,?,10 （2）余料最少数学模型为 minZ?0.5x2?0.5x3?x4?x5?x6?x8?0.5x10?2x1?x2?x3?x4?800 ? ?x2?2x5?x6?x7?1200? ?x3?x6?2x8?x9?600?x?2x?2x?3x?900 7910 ?4??xj?0,j?1,2,?,10 1.3某企业需要制定1～6月份产品A的生产与销售计划。已知产品A每月底交货，市场需求没有限制，由于仓库容量有限，仓库最多库存产品A1000件，1月初仓库库存200件。1～6月份产品A的单件成本与售价如表1－25所示。 （2）当1月初库存量为零并且要求6月底需要库存200件时，模型如何变化。【解】设xj、yj（j＝1，2，?，6）分别为1～6月份的生产量和销售量，则数学模型为 maxZ??300x1?350y1?330x2?340y2?320x3?350y3?360x4? 420y4?360x5?410y5?300x6?340y6

运筹学：对偶理论与灵敏度分析习题与答案

一、填空题 1、对偶问题的对偶问题是（）。 正确答案：原问题 2、若X﹡和Y﹡分别是线性规划的原问题和对偶问题的最优解，则有CX﹡（）Y﹡b。 正确答案：= 3、若X、Y分别是线性规划的原问题和对偶问题的可行解，则有CX（）Yb。 正确答案：<= 4、若X﹡和Y﹡分别是线性规划的原问题和对偶问题的最优解，则有CX﹡（）Y*b。 正确答案：= 5、设线性规划的原问题为maxZ=CX，Ax≤b，X≥0，则其对偶问题为（）。 正确答案：min=Yb YA>=c Y>=0 6、影子价格实际上是与原问题各约束条件相联系的（）的数量表现。 正确答案：对偶变量 7、线性规划的原问题的约束条件系数矩阵为A，则其对偶问题的约束条件系数矩阵为（）。 正确答案：AT 8、在对偶单纯形法迭代中，若某bi<0，且所有的aij≥0(j=1，2，…

n)，则原问题（）。 正确答案：无解 二、选择题 1、线性规划原问题的目标函数为求极小值型，若其某个变量小于等于0，则其对偶问题约束条件为（）形式。 A. “≥” B. “≤” C. “>” D. “=” 正确答案：A 2、如果z*是某标准型线性规划问题的最优目标函数值，则其对偶问题的最优目标函数值w﹡满足（）。 A.W﹡=Z﹡ B.W﹡≠Z﹡ C.W﹡≤Z﹡ D.W﹡≥Z﹡ 正确答案：A 3、如果某种资源的影子价格大于其市场价格，则说明（）。 A.该资源过剩 B.该资源稀缺 C.企业应尽快处理该资源 D.企业应充分利用该资源，开辟新的生产途径

正确答案：B 4、线性规划原问题的目标函数为求极小值型，若其某个变量小于等于0，则其对偶问题约束条件为（）形式。 A.≥ B.≤ C. > D. = 正确答案：A 5、对偶单纯形法的迭代是从（）开始的。 A.正则解 B.最优解 C.可行解 D.可行解 正确答案：A 6、如果某种资源的影子价格大于其市场价格，则说明（）。 A.该资源过剩 B.该资源稀缺 C.企业应尽快处理该资源 D.企业应充分利用该资源，开辟新的生产途径 正确答案：B 7、线性规划灵敏度分析的主要功能是分析线性规划参数变化对（）的影响。

运筹学第四版课后答案

运筹学第四版课后答案《运筹学第四版课后答案》 第一章：线性规划基础 1.1 定义和性质 1.2 简单例子 1.3 代数表示法 1.4 简单例子 1.5 几何解释 1.6 凸集和凸函数 1.7 最优解的存在性 1.8 问题的变形 第二章：线性规划的几何解释 2.1 可行解集合 2.2 目标函数与等高线图 2.3 目标函数与等高线图（续） 2.4 从可行解的角度理解最优解 2.5 敏感性分析

2.6 邻域分析 2.7 图形方法 第三章：单纯形法 3.1 单纯形法的基本思想 3.2 人工变量法 3.3 人工变量法的例子 3.4 高级单纯形法 3.5 人工变量法的应用 第四章：对偶性 4.1 对偶问题的引入 4.2 对偶问题的定义 4.3 对偶性及其应用 4.4 敏感性分析的对偶方法4.5 例子 第五章：灵敏度分析 5.1 参数的变化对最优解的影响5.2 例子

5.3 例子（续） 5.4 增加既约费用 5.5 减少右端常数 第六章：网络优化问题 6.1 最小生成树问题 6.2 最短路径问题 6.3 最大流问题 6.4 最小费用流问题 第七章：整数规划 7.1 整数规划的引入 7.2 整数规划的一般形式7.3 整数规划的求解方法7.4 割平面算法 7.5 分支定界算法 第八章：动态规划和最优控制8.1 动态规划问题的引入8.2 状态转移方程

8.3 过程的描述 8.4 有限阶段情况的简化 8.5 资源分配问题 第九章：随机模型 9.1 随机规划问题的引入 9.2 随机变量的概率分布 9.3 期望值和方差的计算 9.4 随机规划问题的求解 9.5 例子 第十章：多目标规划 10.1 多目标规划问题的引入10.2 多目标规划问题的定义10.3 有效解集的概念 10.4 Pareto最优解的概念10.5 方法的具体实现 第十一章：饱和模型和逆问题11.1 饱和模型与逆问题的引入

运筹学习题答案(1)

第一章 线性规划及单纯形法 （作业） 1.4 分别用图解法和单纯型法求解下列线性规划问题，并对照指出单纯形表中的各基可行 解对应图解法中可行域的哪一顶点。 （1）Max z=2x 1+x 2 St.⎪⎩⎪ ⎨⎧≥≤+≤+0,242615532 12121x x x x x x 解：①图解法： 由作图知，目标函数等值线越往右上移动，目标函数越大，故c 点为对应的最优解，最优解 为直线⎩⎨⎧=+=+24 2615532121x x x x 的交点，解之得X=(15/4,3/4)T 。 Max z =33/4. ② 单纯形法： 将上述问题化成标准形式有： Max z=2x 1+x 2+0x 3+0x 4 St. ⎪⎩⎪ ⎨⎧≥≤++≤++0,,,242615535 421421321x x x x x x x x x x 其约束条件系数矩阵增广矩阵为：

P 1 P 2 P 3 P 4 ⎥⎦ ⎤⎢⎣⎡241026150153 P 3,P 4为单位矩阵，构成一个基，对应变量向，x 3,x 4为基变量，令非基变量x 1,x 2为零，找到 T 优解，代入目标函数得Max z=33/4. 1.7 分别用单纯形法中的大M 法和两阶段法求解下列线性规划问题，并指出属哪一类。 （3）Min z=4x 1+x 2 ⎪⎪⎩⎪⎪⎨ ⎧=≥=++=-+=+) 4,3,2,1(0426343 34213 2121j xj x x x x x x x x 解：这种情况化为标准形式： Max z ＇=-4x 1-x 2 ⎪⎪⎩ ⎪⎪⎨ ⎧=≥=++=-+=+)4,3,2,1(0426343 34213 2121j xj x x x x x x x x 添加人工变量y1,y2 Max z ＇=-4x 1-x 2+0x 3+0x 4-My 1-My 2

运筹学习题集（第二章）

运筹学习题集（第二章） 判断题 判断正误，如果错误请更正 第二章线形规划的对偶理论 1.原问题第i个约束是<=约束,则对偶变量yi>=0. 2.互为对偶问题,或则同时都有最优解,或则同时都无最优解. 3.原问题有多重解,对偶问题也有多重解. 4.对偶问题有可行解,原问题无可行解,则对偶问题具有无界解. 5.原问题无最优解,则对偶问题无可行解. 6.设X,Y分别为｛minZ=CX｜AX>=b,X>=0｝和｛maxw=Yb｜YA<=C,Y>=0｝的可行解,则有 (1)CX<=Yb; (2)CX是w的上界; (3)当X,Y为最优解,CX=Yb; (4)当CX=Yb 时,有YXs+YsX=0; (5)X为最优解且B是最优基时,则Y=C B B-1是最优解; (6)松弛变量Ys的检验数是λs,则X=-λs是基本解,若Ys是最优解, 则X=-λs是最优 解. 7.原问题与对偶问题都可行,则都有最优解. 8.原问题具有无界解,则对偶问题可行. 9.若X,Y是原问题与对偶问题的最优解.则X=Y. 10.若某种资源影子价格为0,则该资源一定有剩余. 11影子价格就是资源的价格. 12.原问题可行对偶问题不可行,可用对偶单纯形法计算. 13.对偶单纯形法比值失效说明原问题具有无界解. 14.对偶单纯形法是直接解对偶问题的一种解法. 15.减少一个约束,目标值不会比原来变差. 16.增加一个约束,目标值不会比原来变好.

17增加一个变量, 目标值不会比原来变差. 18.减少一个非基变量, 目标值不变. 19.当Cj(j=1,2,3,……，n)在允许的最大范围内同时变化时，最优解不变。 选择题 在下列各题中，从4个备选答案中选出一个或从5个备选答案中选出2~5个正确答案。 第二章线性规划的对偶理论 1.如果决策变量数列相等的两个线规划的最优解相同，则两个线性规划A约束条件相同 B目标函数相同C最优目标函数值相同D以上结论都不对 2.对偶单纯形法的最小比值规则是为了保证A使原问题保持可行B 使对偶问题保持可 行C逐步消除原问题不可行性D逐步消除对偶问题不可行性 3.互为对偶的两个线性规划问题的解存在关系A若最优解存在，则最优解相同B原问题 无可行解，则对偶问题也无可行解C对偶问题无可行解，原问题可能无可行解D一个问题无界，则另一个问题无可行解E一个问题无可行解，则另一个问题具有无界解4.已知规范形式原问题（max）的最优表中的检验数为（λ1，λ2，……λn），松弛变量 的检验数为（λn+1,λn+2,……λn+m）,则对偶问题的最优解为A—（λ1，λ2，…… λn）B （λ1，λ2，……λn）C —（λn+1,λn+2,……λn+m）D （λn+1,λn+2,…… λn+m） 5.原问题与对偶问题都有可行解，则A原问题有最优解，对偶问题可能没有最优解B原 问题与对偶问题可能都没有最优解C可能一个问题有最优解，另一个问题具有无界解D原问题与对偶问题都有最优解 计算题

运筹学_第2章_对偶理论习题

第二章线性规划的对偶理论 2.1 写出下列线性规划问题的对偶问题 max z=2x1+2x2－4x3 x1 + 3x2 + 3x3 ≤30 4x1 + 2x2 + 4x3≤80 x1、x2，x3≥0 解：其对偶问题为 min w=30y1+ 80y2 y1+ 4y2≥2 3y1 + 2y2 ≥2 3y1 + 4y2≥－4 y1、y2≥0 2.2 写出下列线性规划问题的对偶问题 min z=2x1+8x2－4x3 x1 + 3x2－3x3 ≥30 －x1 + 5x2 + 4x3 = 80 4x1 + 2x2－4x3≤50 x1≤0、x2≥0，x3无限制 解：其对偶问题为 max w=30y1+80 y2+50 y3 y1－y2 + 4 y3≥2 3y1+5y2 + 2y3≤8 －3y1 + 4y2－4y3 =－4 y1≥0，y2无限制，y3≤0 2.3已知线性规划问题 max z=x1+2x2+3x3+4x4 x1 + 2x2 + 2x3 +3x4≤20 2x1 + x2 + 3x3 +2x4≤20 x1、x2，x3，x4≥0 其对偶问题的最优解为y1*=6/5，y2*=1/5。试用互补松弛定理求该线性规划问题的最优解。 解：其对偶问题为

min w=20y1+ 20y2 y1 + 2y2≥1 （1） 2y1 + y2 ≥2 （2） 2y1 +3y2≥3 （3） 3y1 +2y2≥4 （4） y1、y2≥0 将y1*=6/5，y2*=1/5代入上述约束条件，得（1）、（2）为严格不等式；由互补松弛定理可以推得x1*=0，x2*=0。又因y1*>0，y2*>0，故原问题的两个约束条件应取等式，所以 2x3*+3x4* = 20 3x3* +2x4* = 20 解得x3* = x4* = 4。故原问题的最优解为 X*=（0，0，4，4）T 2.4用对偶单纯形法求解下列线性规划 min z=4x1+2x2+6x3 2x1 +4x2 +8x3 ≥24 4x1 + x2 + 4x3≥8 x1、x2，x3≥0 解将问题改写成如下形式 max（－z）=－4x1－2x2－6x3 －2x1－4x2 －8x3 + x4=－24 －4x1－x2－4x3+x5 =－8 x1、x2，x3，x4，x5≥0 显然，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正侧基。整个问题的计算过程列在表2—7中。

运筹学第2章答案

2.1某人根据医嘱，每天需补充A 、B 、C 三种营养，A 不少于80单位，B 不少于150单位，C 不少于180单位．此人准备每天从六种食物中摄取这三种营养成分．已知六种食物每百克的营养成分含量及食物价格如表2-22所示．（1）试建立此人在满足健康需要的基础上花费最少的数学模型；（2）假定有一个厂商计划生产一中药丸，售给此人服用，药丸中包含有A ，B ，C 三种营养成分．试为厂商制定一个药丸的合理价格，既使此人愿意购买，又使厂商能获得最大利益，建立数学模型． 表2-22 j ⎪⎪⎩⎪⎪ ⎨ ⎧≥≥++++≥+++++≥++++++++++=0 1801034217181501512253092480118401425132.03.09.08.04.05.0min 654321 54321654321654321654321x 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 Z 、、、、、 （2）设y i 为第i 种单位营养的价格，则数学模型为 1231231231231231 2312123m ax 801501801324180.525970.41430210.84025340.9812100.311150.2,,0 w y y y y y y y y y y y y y y y y y y y y y y y =++++≤⎧⎪ ++≤⎪ ⎪++≤⎪ ++≤⎨⎪ ++≤⎪⎪++≤⎪ ≥⎩ 2.2写出下列线性规划的对偶问题 （1）123 123 123123 m in 3536824 ,,0 x x x x x x x x x x x x =++-++≥⎧⎪+-≥⎨⎪≥⎩ 【解】12 12121212 m ax 84233561,0 w y y y y y y y y y y =+-+ ≤⎧⎪+ ≤⎪⎨-≤⎪⎪≥⎩

运筹学习题解答(chap2)(1)(1)

第二章 对偶问题与灵敏度分析 一、写出下列线性规划的对偶问题 1、P89，2。1(a ） 321422min x x x Z ++= s.t ⎪⎪⎩⎪⎪⎨⎧≥=++≤++≥++.,0,;534;332;2433213213 21321无约束 x x x x x x x x x x x x 解:原模型可化为 321422min x x x Z ++= s 。t ⎪⎪⎩⎪⎪ ⎨ ⎧≥=++≥≥++.,0,;534; 3-3--2-;24332 13 2 1 321321321无约束x x x y y y x x x x x x x x x 于是对偶模型为 321532max y y y W +-= s.t ⎪⎪⎩⎪⎪⎨⎧≥≤+-≤+-≤+-.,0,;4334;243;223213213 21321无约束 y y y y y y y y y y y y 2、P89,2。1(b) 321365max x x x Z ++= s 。t ⎪⎪⎩⎪⎪⎨⎧≤≥≤++≥-+-=++.0,0,;8374;35;5223213213 21321x x x x x x x x x x x x 无约束 解：令033≥-='x x 原模型可化为 3 21365max x x x Z '-+=

s 。t ⎪⎪⎩⎪⎪ ⎨⎧≥'≥≤'+≤'='+.0,0,;83-74;3--5-;52-2321 3 21 3213 21321x x x y y y x x x x x x x x x 无约束 于是对偶模型为 321835min y y y W +-= s.t ⎪⎪ ⎩⎪⎪⎨⎧≥-≥---≥+-=++.0,,;332; 6752; 54321321321321y y y y y y y y y y y y 无约束 或⎪⎪⎩⎪⎪⎨⎧≥≤++≥+-=++.0,,;332;6752;543213213 21321y y y y y y y y y y y y 无约束 二、灵敏度分析 1、P92， 2.11线性规划问题 213max x x Z += s 。t ⎪⎩⎪ ⎨⎧≥≤+≤+0,1025; 742 12121x x x x x x 最优单纯形表如下 试用灵敏度分析的方法，分析： （1） 目标函数中的系数21,c c 分别在什么范围内变化，最优解不变? （2） 约束条件右端常数项21,b b 分别在什么范围内变化，最优基保持不变？ 解：（1） 1c 的分析：要使得最优解不变,则需

《运筹学教程》第二章习题答案

《运筹学教程》第二章习题答案 1、（1）解：引入松弛变量x4≥0,x5≥0,化不等式为等式为： minz=2X1 +3X2+4X3 s.t. X1+3X2+2X3+X4=7 4X1+2X2+X5=9 X1,X2,X4,X5≥0 化自由变量为非负，令X3=X3′-X3〞，X3′，X3〞≥0 ： minz=2X1 +3X2+4X3′-4X3〞 s.t. X1+3X2+2 X3′-2 X3〞+X4=7 4X1+2X2+X5=9 X1,X2, X3′，X3〞，X4,X5 ≥0 (2)解：引入松弛变量x5≥0,剩余变量X6≥0，化不等式为等式为： maxz=X1 -5X2+4X3- X4 s.t. X1+2X3+X5=7 X2-2X4-X6=9 X1,X2，X4,X5 ，X6≥0 化自由变量为非负，令X3=X3′-X3〞，X3′，X3〞≥0 ： maxz=X1 -5X2+4X3′-4X3〞- X4 s.t. X1+2 X3′-2 X3〞+X5=7 X2-2X4-X6=9 X1,X2, X3′，X3〞，X4,X5 , X6≥0 化极大的目标函数为极小的目标函数：

minz=-X1+5X2-4X3′+4X3〞+X4 s.t. X1+2 X3′-2 X3〞+X5=7 X2-2X4-X6=9 X1,X2, X3′，X3〞，X4,X5 , X6≥0 2、(1)是不等式表示下图阴影区域，过阴影部分任意两点的直线仍在该区域内。 (2)不是不等式表示下图阴影区域，过阴影部分且通过曲线上部的直线上的点不完全在该区域内。

(3)不是 不等式表示下图阴影区域，过阴影部分且通过圆内部的直线上的点不完全在该区域内。 3、在以下问题中，指出一组基础变量，求出所有基础可行解以及最优解。 （1）123123123123m ax 2..2644,,0z x x x s t x x x x x x x x x =+-⎫ ⎪ ++≤⎪ ⎬+-≤⎪ ⎪≥⎭ 解：将上式化成标准形式，如下： 1231234123512345m in 2..2644,,,,0p x x x s t x x x x x x x x x x x x x =--+⎫⎪ +++=⎪ ⎬+-+=⎪ ⎪≥⎭ 从上式中可以得出系数矩阵为[]1 234 51 12101 4 1 1A P P P P P ⎡⎤==⎢ ⎥-⎣⎦ ， 取基础变量为45,x x ，令非基变量123,,x x x =0，解方程组123412352644 x x x x x x x x +++=+-+= 得基础可行解(1)(0,0,0,6,4)T x = 同理得基础解：(2)(0,6,0,0,20)T x =-，(3)(0,0,3,0,7)T x =，(4)(0,0,4,24,0)T x =-， (5) (0,1,0,5,0) T x =，(6)1420(0,,,0,0)99T x =，(7)(6,0,0,0,2)T x =-， (8) (4,0,0,2,0) T x =，(9)202( ,,0,0,0) 3 3T x =-， (10)142(,0, ,0,0) 3 3 T x =。 其中基础可行解为：(1)(0,0,0,6,4)T x =，(3)(0,0,3,0,7)T x =，(5)(0,1,0,5,0)T x =，

运筹学习题答案注释(第2章)

运筹学习题答案及注释 2.3 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如表2-32所示，求表中各括弧内未知数的值。 注释：由题中初始单纯形表及、最终单纯形表，我们可以看出：在初始单纯形表中，先选x 1进基，选x 5出基，做变换；然后再选x 2进基，选x 6出基，做变换，则得到最终单纯形表。 2.7 给出线性规划问题。 max 432142x x x x z +++= st. ⎪⎪⎪⎩⎪ ⎪⎪⎨⎧≥≤++≤++≤+≤++0 ,,,9 6628343213 2143221421x x x x x x x x x x x x x x x 要求：（1）写出其对偶问题；（2）已知原问题最优解为X*=（2，2，4，0），试根据对偶理论，直接求出对偶问题的最优解。 解：（1）其对偶问题为： min 43219668y y y y w +++=

st. ⎪⎪⎪⎩⎪ ⎪⎪⎨⎧≥≥+≥++≥+++≥++0 ,,,9 1432243213 14324321421y y y y y y y y y y y y y y y y （2）用单纯形法解原问题，将原问题化成标准形式如下： max 87654321000042x x x x x x x x z +++++++= st. ⎪⎪⎪⎩⎪ ⎪⎪⎨⎧≥=+++=+++=++=+++0 ,,,,,,,9 66283876543218 32174326215421x x x x x x x x x x x x x x x x x x x x x x x 因此，可得如下单纯形表： 因1≥0，所以选x 进基，因（10/3）/（5/3）≤3/1≤（8/3）/（1/3），故选x 出基，则得

运筹学习题答案

第一章习题 1.思考题 （1）微分学求极值的方法为什么不适用于线性规划的求解 （2）线性规划的标准形有哪些限制如何把一般的线性规划化为标准形式 （3）图解法主要步骤是什么从中可以看出线性规划最优解有那些特点 （4）什么是线性规划的可行解，基本解，基可行解引入基本解和基可行解有什么作用 （5）对于任意基可行解，为什么必须把目标函数用非基变量表示出来什么是检验数它有什么作用如何计算检验数 （6）确定换出变量的法则是什么违背这一法则，会发生什么问题{ （7）如何进行换基迭代运算 （8）大M法与两阶段法的要点是什么两者有什么共同点有什么区别 （9）松弛变量与人工变量有什么区别试从定义和处理方式两方面分析。 （10）如何判定线性规划有唯一最优解，无穷多最优解和无最优解为什么 2.建立下列问题的线性规划模型： （1）某厂生产A，B，C三种产品，每件产品消耗的原料和设备台时如表1-18所示：表1-18 另外，要求三种产品总产量不低于65件，A的产量不高于B的产量。试制定使总利润最大的模型。 （2）某公司打算利用具有下列成分（见表1-19）的合金配制一种新型合金100公斤，新合金含铅，锌，锡的比例为3：2：5。 ,

如何安排配方，使成本最低 （3）某医院每天各时间段至少需要配备护理人员数量见表1-20。 表1-20 初等数学的视察法，求出它的最优解 （4）某工地需要30套三角架，其结构尺寸如图1-6所示。仓库现有长6.5米的钢材。如何下料，使消耗的钢材最少 # ; 图1-6 3. 用图解法求下列线性规划的最优解： ⎪⎪⎩⎪⎪⎨ ⎧≥≤+-≥+≥++=0 ,425.134 1 2 64 min )1(21212 12121x x x x x x x x x x z ⎪⎪⎩⎪⎪⎨ ⎧≥≤+≥+-≤++=0 ,82 5 10 32 44 max )2(21212 12121x x x x x x x x x x z

运筹学规划习题答案

附录四：习题参考答案 第一章线性规划及单纯形法 1.1 （1）解： 第一，求可行解集合。令两个约束条件为等式，得到两条直线，在第一象限划出满足两个不等式的区域，其交集就是可行集或称为可行域，如图1-1所示，交集为（1/2, 0）。 第二，绘制目标函数图形。将目标函数的系数组成一个坐标点（6，4），过原点O作一条矢量指向点（6，4），矢量的长度不限，矢量的斜率保持4比6，再作一条与矢量垂直的直线，这条直线就是目标函数图形，目标函数图形的位置任意，如果通过原点则目标函数值Z=0，如图1-2所示。 第三，求最优解。图1-2的矢量方向是目标函数增加的方向或称梯度方向，在求最小值时将目标函数图形沿梯度方向的反方向平行移动，（在求最大值时将目标函数图形沿梯度方向平行移动）直到可行域的边界，停止移动，其交点对应的坐标就是最优解，如图1-3所示。最优解x=（1/2, 0）,目标函数的最小值Z=3。

附录四习题参考答案 （2）无可行解；[求解方法与（1）类似] （3）无界解； （4）无可行解； （5）无穷多最优解 z*=66 （6）唯一最优解 z*=92/3,x1=20/3,x2=3/8 1.2 （1）解：由题目可知，其系数矩阵为 ）即，，，，（54321P P P P P ⎥⎥⎥⎦ ⎤⎢⎢⎢⎣⎡1 0 0 2 30 1 0 2 00 0 1 0 1 因 =），，（321P P P ⎥⎥ ⎥⎦⎤ ⎢⎢⎢⎣⎡ 0 2 3 0 2 0 1 0 1线性独立，故有⎪⎩⎪⎨⎧-=+-==+521423118231224x x x x x x x 令非基变量0,54=x x 得⎪⎩⎪ ⎨⎧=+==+18 231224 21 231x x x x x → ⎪⎩⎪ ⎨⎧===264 3 21x x x 得到一个基可行解T x ），，，，（00262) 1(=，361=Z 。

运筹学(机械工业出版社)教材习题答案(第一章-第三章)

教材习题答案 部分有图形的答案附在各章PPT文档的后面，请留意。 第1章线性规划 第2章线性规划的对偶理论 第3章整数规划 第4章目标规划 第5章运输与指派问题 第6章网络模型 第7章网络计划 第8章动态规划 第9章排队论 第10章存储论 第11章决策论 第12章对策论 习题一 1.1 讨论下列问题： （1）在例1.1中，假定企业一周内工作5天，每天8小时，企业设备A有5台，利用率为0.8,设备B有7台，利用率为0.85,其它条件不变，数学模型怎样变化． （2）在例1.2中，如果设x j(j=1，2，…，7)为工作了5天后星期一到星期日开始休息的营业员，该模型如何变化． （3）在例1.3中，能否将约束条件改为等式；如果要求余料最少，数学模型如何变化；简述板材下料的思路． （4）在例1.4中，若允许含有少量杂质，但杂质含量不超过1％，模型如何变化． （5）在例1.6中，假定同种设备的加工时间均匀分配到各台设备上，要求一种设备每台每天的加工时间不超过另一种设备任一台加工时间1小时，模型如何变化． 1.2 工厂每月生产A、B、C三种产品,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1－22所示． 310和130.试建立该问题的数学模型,使每月利润最大． 【解】设x1、x2、x3分别为产品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.3 建筑公司需要用6m 长的塑钢材料制作A 、B 两种型号的窗架．两种窗架所需材料规格 及数量如表1－23所示： 【解】 设x j （j =1,2,…，14）为第j 种方案使用原材料的根数，则 （1）用料最少数学模型为 14 1 12342567891036891112132347910121314 min 2300322450 232400 23234600 0,1,2,,14 j j 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 x x x x x j ==⎧+++≥⎪ ++++++≥⎪⎪ ++++++≥⎨⎪++++++++≥⎪⎪≥=⎩∑ 用单纯形法求解得到两个基本最优解 X (1)=( 50 ,200 ,0 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=534 X (2)=( 0 ,200 ,100 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,150 ,0 ,0 );Z=534 （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 数学模型为： ,12 132323243434364635365612132434343546562324463612132446362335244656121324354656m in 52,22,23 3 344,510ij ij ij 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