《运筹学》第三章线性规划对偶理论与灵敏度分析习题及答案.doc

运筹学第三章习题答案详细运筹学是一门研究如何有效地做出决策的学科，它运用数学和逻辑的方法来解决实际问题。

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

本文将详细解答运筹学第三章的习题，帮助读者更好地掌握该章节的内容。

第一题是关于线性规划的基本概念和性质的。

线性规划是运筹学中的重要分支，它的目标是在一组约束条件下，找到使目标函数最大或最小的变量值。

这个问题可以用一个线性规划模型来描述，其中包括决策变量、目标函数和约束条件。

在解答这个问题时，我们需要先确定决策变量、目标函数和约束条件，然后使用线性规划的方法求解最优解。

具体的计算过程可以通过线性规划的算法来完成。

第二题是关于线性规划的图解法的。

线性规划的图解法是一种直观的解法，它通过绘制变量的可行域和目标函数的等高线图来求解最优解。

在解答这个问题时，我们需要先将约束条件转化为直线或者曲线的形式，然后绘制出这些直线或曲线，并确定它们的交点。

最后，我们需要在可行域内找到使目标函数取得最大或最小值的点，这个点就是线性规划的最优解。

第三题是关于整数规划的应用的。

整数规划是线性规划的一种特殊形式，它要求决策变量取整数值。

在解答这个问题时，我们需要先确定整数规划的模型，包括决策变量、目标函数和约束条件。

然后，我们可以使用整数规划的算法来求解最优解。

在实际应用中，整数规划可以用来解决很多实际问题，比如生产计划、运输调度等。

第四题是关于线性规划的灵敏度分析的。

灵敏度分析是线性规划中的一种重要技术，它用来分析目标函数系数、约束条件右端常数和决策变量上下界的变化对最优解的影响。

在解答这个问题时，我们需要计算目标函数系数、约束条件右端常数和决策变量上下界的变化对最优解的影响程度，并进行相应的调整。

通过灵敏度分析，我们可以了解到线性规划模型对参数变化的敏感性，从而做出更加准确的决策。

第五题是关于线性规划的对偶问题的。

线性规划的对偶问题是线性规划的一个重要概念，它可以用来求解原始问题的最优解。

《运筹学教程》第三章习题答案1.影子价格是根据资源在生产中作出的贡献而做的估价。

它是一种边际价格，其值相当于在资源得到最有效利用的生产条件下，资源每变化一个单位时目标函数的增量变化。

又称效率价格。

影子价格是指社会处于某种最优状态下，能够反映社会劳动消耗、资源稀缺程度和最终产品需求状况的价格，是社会对货物真实价值的度量。

只有在完善的市场条件下才会出现，然而这种完善的市场条件是不存在的，因此现成的影子价格也是不存在的。

市场价格是物品和服务在市场上销售的实际价格，是由供求关系决定的。

2.证明：当原问题约束条件右端变为b i′时，原问题变为： maxz=∑C i X js.t. ∑a ij X i≤b i′(i=1,2,3,……,m)X j≥0 (j=1,2,3,……,n)对偶问题为： minp=∑b i′y is.t. ∑a ij y i≥C iy i≥0(i=1,2,3,……,m) (j=1,2,3,……,n) 设，当b i变为b i′原问题有最优解（X1′X2′X3′……X n-1′X n′）时，对偶问题的最优解为（y1′y2′y3′……y n-1′y n′）,则有：又因为当原问题有最优解时，对偶问题也有最优解，且相等，则有：所以3（1）.minp=6y1 + 2y2s.t. -y1+2y2≥-33y1+3y2≥4y1,y2≥0(2)解：令X2=X2′-X2〞，X4= X4′-X4〞，X2′，X2〞，X4′，X4〞≥0 ，原式化为：maxz=2X1 +2X2′-2X2〞-5X3 +2X4′-2X4〞s.t. 2X1 -X2′+X2〞+3X3 +3X4′-3X4〞≤-5-2X1 +X2′-X2〞-3X3 -3X4′+3X4〞≤5-6X1 -5X2′+5X2〞+X3 -5X4′+5X4〞≤-610X1 -9X2′+9X2〞+6X3 +4X4′-4X4〞≤12X1, X2′，X2〞，X3, X4′，X4〞≥0则对偶规划为：.minp= -5y1′+ 5y1〞-6y2 + 12y3s.t. 2y1′-2y1〞-6y2 + 10y3≥2-y1′+y1〞-5y2 -9y3≥2y1′-y1〞+5y2 + 9y3≥-23y1′-3y1〞+y2 + 6y3≥-53y1′-3y1〞-5y2 + 4y3≥2-3y1′+3y1〞+5y2 -4y3≥-2即：minp= -5y1′+ 5y1〞-6y2 + 12y3s.t. 2y1′-2y1〞-6y2 + 10y3≥2-y1′+y1〞-5y2 -9y3=23y1′-3y1〞+y2 + 6y3≥-53y1′-3y1〞+5y2 + 4y3=2令 y1〞- y1′= y1，得：minp= 5y1 -6y2 + 12y3s.t. -2y1-6y2 + 10y3≥2y1-5y2 -9y3=2-3y1+y2 + 6y3≥-5-3y1-5y2 + 4y3=24、试用对偶理论讨论下列原问题与他们的对偶问题是否有最优解。

第二章 线性规划的对偶理论与灵敏度分析习题1. 写出下列线性规划问题的对偶问题。

(1)⎪⎪⎩⎪⎪⎨⎧≥=++≤++≥++++=无约束321321321321321,0,534332243422min x x x x x x x x x x x x x x x z (2) ⎪⎪⎩⎪⎪⎨⎧≤≥≤++≥-+-=++++=0,0,837435522365max 321321321321321x x x x x x x x x x x x x x x z 无约束(3)⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧==≥=====∑∑∑∑====),,1;,,1(0),,1(),,1(min 1111n j m i x n j b x m i a x x c z ij mi j ij nj i ij mi ijnj ij (4)⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=≥++==<=<=∑∑∑===),,,,1(0),,2,1(),,1(min 1211111n n j x m m m i b x a m m i b x a x c z j n j i j ij nj i j ij nj jj 无约束 2. 判断下列说法是否正确，为什么?(1)如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； (2)如果线性规划的对偶问题无可行解，则原问题也一定无可行解； ( 3)在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值；(4)任何线性规划问题具有唯一的对偶问题。

3. 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表所示，求表中各括弧内未知数的值。

⎪⎩⎪⎨⎧=≥-≤+-+-≥++++++=)4,,1(0322326532min 432143214321 j x x x x x x x x x x x x x z j(1)写出其对偶问题；(2)用图解法求解对偶问题；(3)利用(2)的结果及根据对偶问题性质写出原问题最优解。

一、填空题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>=06、影子价格实际上是与原问题各约束条件相联系的（）的数量表现。

正确答案：对偶变量7、线性规划的原问题的约束条件系数矩阵为A，则其对偶问题的约束条件系数矩阵为（）。

正确答案：AT8、在对偶单纯形法迭代中，若某bi<0，且所有的aij≥0(j=1，2，…n)，则原问题（）。

正确答案：无解二、选择题1、线性规划原问题的目标函数为求极小值型，若其某个变量小于等于0，则其对偶问题约束条件为（）形式。

A. “≥”B. “≤”C. “>”D. “=”正确答案：A2、如果z*是某标准型线性规划问题的最优目标函数值，则其对偶问题的最优目标函数值w﹡满足（）。

A.W﹡=Z﹡B.W﹡≠Z﹡C.W﹡≤Z﹡D.W﹡≥Z﹡正确答案：A3、如果某种资源的影子价格大于其市场价格，则说明（）。

A.该资源过剩B.该资源稀缺C.企业应尽快处理该资源D.企业应充分利用该资源，开辟新的生产途径正确答案：B4、线性规划原问题的目标函数为求极小值型，若其某个变量小于等于0，则其对偶问题约束条件为（）形式。

A.≥B.≤C. >D. =正确答案：A5、对偶单纯形法的迭代是从（）开始的。

A.正则解B.最优解C.可行解D.可行解正确答案：A6、如果某种资源的影子价格大于其市场价格，则说明（）。

A.该资源过剩B.该资源稀缺C.企业应尽快处理该资源D.企业应充分利用该资源，开辟新的生产途径正确答案：B7、线性规划灵敏度分析的主要功能是分析线性规划参数变化对（）的影响。

精品文档第三章 线性规划的对偶理论及灵敏度分析主要内容：1、对偶问题及其性质； 2、对偶单纯形法；3、灵敏度分析。

重点与难点：对偶问题与原问题的对应关系，对偶问题的基本性质，对偶单纯形法的求解步骤，灵敏度分析的方法。

要 求：理解线性规划对偶问题的性质，熟练掌握对偶单纯形法的求解步骤和灵敏度分析的方法和技巧，能够用这些数学方法解决实际问题。

§1 对偶问题的对称形式一、对偶问题引例，某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需要的设备台时及A 、B 两种原材料的消耗，该工厂每生产一件产品甲可获利2元，每生产一件产品乙可获利3元，问应如何安排计划才能使该工厂获利最多？解：设1x 、2x 分别为甲、乙两种产品的产量则目标函数2132m ax x x z +=约束条件 ⎪⎪⎩⎪⎪⎨⎧≥≤≤≤+0,12416482212121x x x x x x(1)假设该工厂决定不再生产甲、乙产品，而将其出租或出售。

这时要考虑每种资源的定价问题，设321,,y y y 分别为出租单位设备台时的租金和出让单位原材料A 、B 的附加额。

作一比较：若用一个单位台时和4个单位原材料A 生产一件产品甲，可获利2元，那么生产每件产品甲的设备台时和原材料出租和出让的收入应不低于生产一件甲产品的利润。

即：2421≥+y y同理，将生产每件乙产品的设备台时和原材料出租和出让的收入应不低于生产一件乙产品的利润。

即：精品文档34231≥+y y将工厂所有设备台时和资源都出租和出让，其收入为32112168y y y ++=ω对工厂来说，ω越大越好；但对接受者来说，支付的愈少愈好，所以工厂只能在满足≥所有产品的利润前提下，使其总收入尽可能小，才能实现其愿望。

为此，得到如下模型：32112168m in y y y ++=ω⎪⎩⎪⎨⎧=≥≥+≥+3,2,1,0342243121j y y y y y j(2)我们就称(2)为模型(1)的对偶问题。

对偶理论及灵敏度分析习题1. 什么是对偶理论？对偶理论是线性规划中的一种方法，它是将一个线性规划问题转化为另一个等价的线性规划问题。

这个等价问题被称为原问题的对偶问题，原问题和对偶问题之间存在着一种对偶关系。

2. 什么是灵敏度分析？灵敏度分析是一种方法，用于评估一个线性规划问题的解对输入数据的变化的敏感程度。

它涉及到对线性规划问题的目标函数系数、约束条件常数、以及右手边向量的变化进行分析，以确定线性规划问题在输入数据变化下的解的变化情况。

3. 对偶问题和原问题之间有什么关系？对偶问题和原问题之间存在着一种对偶关系，即两个问题中的变量和约束条件互相对应。

对原问题的对偶问题的目标函数系数就是原问题的约束条件系数，而对原问题的每个变量的约束条件对应着对偶问题的每个变量的目标函数系数。

4. 什么是原问题？原问题是一个线性规划问题，它包括在一组约束条件下最大化或最小化一个线性目标函数的问题。

原问题通常表示为标准形式或规范形式。

5. 什么是对偶问题？对偶问题是一个等价的线性规划问题，它与原问题共享相同的约束条件，但目标函数和约束条件的系数经过了转换。

对偶问题可以用来评估原问题的最优解并提供其他信息，如原问题的灵敏度分析和可行性分析。

6. 什么是灵敏度分析中的“影响范围”？灵敏度分析中的“影响范围”指输入参数发生变化时，该变化对解决方案的影响的程度范围。

影响范围可以用来确定哪些输入参数对问题的解决非常敏感，以及如何调整这些参数以最大程度地减少对解决方案的影响。

7. 在灵敏度分析中，什么是“松弛变量”的作用？在灵敏度分析中，“松弛变量”用于评估一个约束条件的“松弛度”，即约束条件与等式相差多少。

这个信息可以用来确定输入参数值的变化可以多少，以使某个约束条件的松弛度保持不变。

8. 什么是敏感性分析？敏感性分析是一种评估线性规划问题解决方案的稳定性的方法。

它涉及到对输入参数的变化进行分析，以确定对线性规划问题最优解的影响程度。

《运筹学》第三章线性规划对偶理论与灵敏度分析习题及答案一、填空题1. 在线性规划问题中，若原问题存在最优解，则其对偶问题也一定存在最优解，这是线性规划的基本性质之一，称为______。

答案：对偶性2. 在线性规划问题中，若原问题与对偶问题均存在可行解，则它们均有______。

答案：最优解3. 对于线性规划问题，若原问题约束条件系数矩阵为A，目标函数系数向量为c，则其对偶问题的目标函数系数向量是______。

答案：c的转置（c^T）二、选择题1. 线性规划的原问题与对偶问题之间的关系是：A. 原问题的最优解和对偶问题的最优解相同B. 原问题的最优解是对偶问题的最优解的负数C. 原问题的最优解与对偶问题的最优解互为对偶D. 原问题的最优解和对偶问题的最优解没有关系答案：C2. 在线性规划中，若原问题不可行，则其对应的对偶问题：A. 可行B. 不可行C. 无界D. 无法确定答案：B三、判断题1. 线性规划的原问题和对偶问题具有相同的可行解。

（）答案：错误2. 若线性规划的原问题存在唯一最优解，则其对偶问题也一定存在唯一最优解。

（）答案：正确四、计算题1. 已知线性规划问题：max z = 3x1 + 2x2s.t.x1 + 2x2 ≤ 42x1 + x2 ≤ 5x1, x2 ≥ 0求该问题的对偶问题，并求解原问题和对偶问题的最优解。

答案：对偶问题为：min w = 4y1 + 5y2s.t.y1 + 2y2 ≥ 32y1 + y2 ≥ 2y1, y2 ≥ 0原问题和对偶问题的最优解如下：原问题最优解：x1 = 2, x2 = 1，最大利润z = 8对偶问题最优解：y1 = 2, y2 = 1，最小成本w = 82. 某工厂生产甲、乙两种产品，生产一件甲产品需要2小时的机器时间和3小时的工人劳动时间，生产一件乙产品需要1小时的机器时间和1小时的工人劳动时间。

工厂每周最多能使用12小时的机器时间和9小时的工人劳动时间。