128499-管理运筹学-第⼆章线性规划-习题
11（2），12,14,18 习题
2-1 判断下列说法是否正确：
（1） 任何线性规划问题存在并具有惟⼀的对偶问题； T （2） 对偶问题的对偶问题⼀定是原问题；T
（3） 根据对偶问题的性质，当原问题为⽆界解时，其对偶问题⽆可⾏解，反之，
当对偶问题⽆可⾏解时，其原问题具有⽆界解；F
（4） 若线性规划的原问题有⽆穷多最优解，则其对偶问题也⼀定具有⽆穷多最优
解；
（5） 若线性规划问题中的b i ，c j 值同时发⽣变化，反映到最终单纯形表中，不会出
现原问题与对偶问题均为⾮可⾏解的情况； （6） 应⽤对偶单纯形法计算时，若单纯形表中某⼀基变量x i <0，⼜x i 所在⾏的元素全
部⼤于或等于零，则可以判断其对偶问题具有⽆界解。 （7） 若某种资源的影⼦价格等于k ，在其他条件不变的情况下，当该种资源增加5个单位时，相应的⽬标函数值将增⼤5k ；
（8） 已知y i 为线性规划的对偶问题的最优解，若y i >0，说明在最优⽣产计划中第i 种资源已经完全耗尽；若y i =0，说明在最优⽣产计划中的第i 种资源⼀定有剩余。
2-2将下述线性规划问题化成标准形式。
≥≥-++-≤+-+-=-+-+-+-=⽆约束
43
214321432143214321,0,,232142224.5243max )1(x x x x x x x x x x x x x x x x st x x x x z
2-3分别⽤图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基
可⾏解对应图解法中可⾏()≥≤≤-+-=++-+-=⽆约束321
3213213
21,0,06
24
.322min 2x x x x x x x x x st x x x z 域的哪⼀顶点。
()
≥≤+≤++=0,8259
43.510max 12
1212121x x x x x x st x x z ()
≥≤+≤++=0,242615
１
第二章线性规划
教学目的和要求：
目的：使学生具备线性规划的基本知识以及应用线性规划的基本能力。
要求：理解线性规划概念，标准型，解的概念，基本定理；掌握单纯形法，人工变量法，了解图解法。
重点：线性规划标准型，解的概念，单纯形法，人工变量法。
难点：线性规划基本定理，单纯形法。
教学方法：讲授法，习题法。
学时分配：12学时
作业安排：见教材P38.
线性规划是运筹学的一个重要分支。1939年苏联科学家康托罗维奇提出了生产组织和计划中的线性规划模型。1947年美国学者丹捷格(George B.Dantzig)提出了求解一般线性规划问题的方法。此后，线性规划理论日趋成熟，应用也日益广泛和深入。
第一节线性规划问题
一、问题的提出
在企业的生产经营活动中经常会面临这样两类问题：一是如何合理地利用有限的人力、物力、财力等资源，取得最佳的经济效果；二是在取得一定的经济效果的前提下，如何合理安排使用人力、物力、财力等资源，使花费的成本最低。
例1.生产计划问题 某工厂利用甲、乙、丙、丁四种设备生产A、B、C三种产品，具体数据如下表所示。 A、B、C单位产品的利润分别是4.5、5、7(百元)。问如何安排生产计划，才能使所获总利润最大？
解：设产品A、B、C产量分别为X1,X2,X3件,Z表示利润，要求总利润最大，即求Z=4.5X1+5X2+7X3的最大值，故记作极大化Z=4.5X1+5X2+7X3，另外对甲、乙、丙、丁设备需满足2X1+2X2+4X3≦800，X1+2X2+3X3≦650，4X1+2X2+3X3≦850，2X1+4X2+2X3≦700；同时产量应非负，故Xj≧0 (j=1,2,3)；
以上问题可用数学模型表示为：
极大化Z=4.5X1+5X2+7X3
满足 2X1+2X2+4X3≦800
X1+2X2+3X3≦650
4X1+2X2+3X3≦850
第二章 线性规划的对偶问题
４７ 习题二2.1 写出下列线性规划问题的对偶问题
(1) max z ＝10x1＋ x2＋2x3 (2) max z ＝2x1＋ x2＋3x3＋ x4
st. x1＋ x2＋2 x3≤10 st. x1＋ x2＋ x3 ＋ x4 ≤5
4x1＋ x2＋ x3≤20 2x1－ x2＋3x3 ＝－4
xj ≥0 （j＝1,2,3） x1 － x3＋ x4≥1
x1，x3≥0，x2，x4无约束
(3) min z ＝3x1＋2 x2－3x3＋4x4 (4) min z ＝－5 x1－6x2－7x3
st. x1－2x2＋3x3＋4x4≤3 st. －x1＋5x2－3x3 ≥15
x2＋3x3＋4x4≥－5 －5x1－6x2＋10x3 ≤20
2x1－3x2－7x3 －4x4＝2＝ x1－ x2－ x3＝－5
x1≥0，x4≤0，x2，，x3 无约束 x1≤0， x2≥0，x3 无约束
2.2 已知线性规划问题max z＝CX，AX=b，X≥0。分别说明发生下列情况时，其对偶问题的解的变化：
（1）问题的第k个约束条件乘上常数λ（λ≠0）；
（2）将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上；
（3）目标函数改变为max z＝λCX（λ≠0）；
（4）模型中全部x1用31'x代换。
2.3 已知线性规划问题 min z＝8x1＋6x2＋3x3＋6x4
st. x1＋2x2 ＋ x4≥3
3x1＋ x2＋ x3＋ x4≥6
x3 ＋ x4＝2
x1 ＋ x3 ≥2
xj≥0（j＝1,2,3,4）
(1) 写出其对偶问题；
第二章 线性规划的对偶理论
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。故原问题的最优解为
