判 断 题
判断正误，如果错误请更正 1. 2. 3. 4. 5. 6.
第二章 线形规划的对偶理论
原问题第i个约束是<=约束,则对偶变量yi>=0.
互为对偶问题,或则同时都有最优解,或则同时都无最优解. 原问题有多重解,对偶问题也有多重解.
对偶问题有可行解,原问题无可行解,则对偶问题具有无界解. 原问题无最优解,则对偶问题无可行解.
设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=CBB-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，……
1
λ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.1 对于如下的线性规划问题
min z = 3x1 + 2x2 +x3
s.t. x1 + x2 + x3 15 (1) 2x1 - x2 + x3 9 (2) -x1 + 2x2 +2x3 8 (3) x1 x2 x3 0
1、写出题目中线性规划问题的对偶问题；
2、分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）； 解答：1、写出题目中线性规划问题的对偶问题；
解：max w = 15y1 + 9y2 + 8y3
s.t. y1 + 2y2 - y3 3 (1) y1 - y2 + 2y3 2 (2) y1 + y2 + 2y3 1 (3) y1 0、 y2 0、y3 0
2、分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）； 解：先将原问题化成以下形式，则有
min z = 3x1 + 2x2 + x3
s.t. x1 + x2 + x3 + x4 = 15 (1) -2x1 + x2 - x3 + x5 = -9 (2) -x1 + 2x2 +2x3 +x6 = 8 (3) x1 x2 x3 x4 x5 x6 0 X1 X2 X3 X4 X5 X6 右端 z -3 -2 -1 0 0 0 X4 1 1 1 1 0 0 15 X5 -2 1 [-1] 0 1 0 -9 X6 -1 2 2 0 0 1 8 X1 X2 X3 X4 X5 X6 右端 z -1 -3 0 0 -1 0 9 X4 -1 2 0 1 1 0 6 X3 2 -1 1 0 -1 0 9 X6 [-5] 4 0 0 2 1 -10 X1 X2 X3 X4 X5 X6 右端
2
z X4 X3 X1 0 0 0 1 -19/5 6/5 3/5 -4/5 0 0 1 0 0 1 0 0 -7/5 3/5 -1/5 -2/5 -1/5 -1/5 2/5 -1/5 11 8 5 2 原始问题的最优解为（X1 X2 X3 X4 X5 X6）=（2，0，5，8，0，0），minz=11 对偶问题的最优解为（y1 y2 y3 y4 y5 y6）=（0，7/5，-1/5，0，19/5，0），maxw=11
2.2 对于以下线性规划问题
max z = -x1 - 2x2
s.t. -2x1 + 3x2 12 (1) -3x1 + x2 6 (2) x1 + 3x2 3 (3) x1 0， x2 0
1、写出标准化的线性规划问题；
2、用单纯形表求出这个线性规划问题的最优解和最优的目标函数值； 3、 写出这个（极大化）线性规划问题的对偶问题； 4、 求出对偶问题的最优解和最优解的目标函数值；
5、 第（2）个约束右端常数b2=6在什么范围内变化，最优解保持不变。 解答：1、写出标准化的线性规划问题:令x*
1=- x1
max z = x*
1 - 2x2
s.t. 2x*1 + 3x2 + x3 = 12 (1) 3x*1 + x2 + x4 = 6 (2) -x*1 + 3x2 -x5 = 3 (3) x*1 x2 x3 x4 x5 0
2、（6分）用单纯形表求出这个线性规划问题的最优解和最优的目标函数值
x*1 X2 X3 X4 X5 R 右端 Z’ 1-M 3M-2 0 0 -M 0 3M X3 2 3 1 0 0 0 12 X4 3 1 0 1 0 0 6 R -1 [3] 0 0 -1 1 3 x*1 X2 X3 X4 X5 R 右端 Z’ 1/3 0 0 0 -2/3 2/3-M 2 X3 3 0 1 0 1 -1 9 X4 [10/3] 0 0 1 1/3 -1/3 5 X2 -1/3 1 0 0 -1/3 1/3 1 x*1 X2 X3 X4 X5 R 右端 Z’ 0 0 0 -1/10 -7/10 21/30-M 3/2 X3 0 0 1 -9/10 9/2 X*1 1 0 0 3/10 1/10 -1/10 3/2 X2 0 1 0 1/10 3/2 此时最优解为（X1、X2、X3、X4 X5）=（-3/2，3/2，9/2，0，0）maxz=-3/2 3、写出这个（极大化）线性规划问题的对偶问题；
min w = 12y1 + 6y2 + 3y3
s.t. -2y1 - 3y2 + y3 -1 (1) 3y1 + y2 + 3 y3 -2 (2)
3
y1 0、 y2 0、y3 0
4、求出对偶问题的最优解和最优解的目标函数值；
此时最优解为（y1、y2、y3、y4 y5）=（0，1/10,-7/10，0，0）minw =-3/2 5、则有1b211，最优解不变。
2.3 已知LP问题：
max z = x1 + 2x2 +3x3 + 4x4
s.t. x1 + 2x2 + 2x3 + 3x4 20 (1) 2x1 + x2 + 3x3 + 2x4 20 (2) x1 、 x2 、 x3 、 x4 0
的最优解为（0，0，4，4）T，最优值为Z=28。请用互补松弛定理计算其对偶问题的最优解。
解答：首先写出此LP问题的对偶问题为：
min w = 20y1 + 20y2
s.t. y1 + 2y2 1 (1)
2y1 + y2 2 (2)
2y1 + 3y2 3 (3)
3y1 + 2y2 4 (4)
y1 、 y2 、 0
将上述对偶问题的化成标准型，取松弛变量分别为v1 、v2、、 v3 、v4，则有
min w = 20y1 + 20y2
s.t. y1 + 2y2 - v1 = 1 (5)
2y1 + y2 - v2 = 2 (6)
2y1 + 3y2 - v3 = 3 (7)
3y1 + 2y2 - v4 = 4 (8)
y1 、 y2 、 0
利用互补松弛定理可知：
x3 = 4 > 0 ,又有 x3 v3 = 0 ， 所以有 v3 = 0 代入(7)式
x4 = 4 > 0，又有 x4 v4= 0 ， 所以有 v4 = 0 代入(8)式，则有
2y1 + 3y2 = 3 (9)
3y1 + 2y2 = 4 (10) 从中可计算出y1 = 6/5 、 y2 = 1/5，则 w* =28
2.4 一个工厂用四种原料生产三种产品，生产每种产品要消耗的各种原料
数量（表中“—”表示相应的产品不需要这种原料）、各种产品的利润以及各 种原料的限量如下表所示。
1、 写出原料条件下利润最大化的线性规划模型； 2、 写出以上问题的对偶问题；
3、 已知利润最大的线性规划问题的最优解是产品A生产120件，产品B不生
产，产品C生产52件，用互补松弛关系求四种原料的影子价格。
原料消耗 （吨/件） 原料甲 原料乙 原料丙 原料丁
产品 A 12 6 15 —— 产品 B 8 10 18 20 产品 C 10 15 —— 22 原料限量 （吨） 2400 1500 1800 2000 4
产品利润 （万元/件） 120 180 210 解答：一个工厂用四种原料生产三种产品，生产每种产品要消耗的各种原料
数量（表中“—”表示相应的产品不需要这种原料）、各种产品的利润以及各 种原料的限量如下表所示。
1. 写出原料条件下利润最大化的线性规划模型；
max z = 120x1 + 180 x2 +210 x3
s.t. 12x1 + 8x2 +10 x3 2400 (1) 6x1 + 10x2 +15 x3 1500 (2) 15x1 + 18x2 1800 (3) 20x2 + 22x3 2000 (4) x1 0， x2 0 x3 0
2. 写出以上问题的对偶问题；
min w = 2400y1 + 1500 y2 +1800 y3 +2000 y4
s.t. 12y1 + 6y2 + 15y3 120 (1)
8y1 + 10y2 + 18 y3 + 20 y4 180 (2) 10y1 + 15y2 +22y4 210 (3) y1 0， y2 0 y3 0 y4 0
3. 已知利润最大的线性规划问题的最优解是产品A生产120件，产品B不生
产，产品C生产52件，用互补松弛关系求四种原料的影子价格。 max z = 120x1 + 180 x2 +210 x3
s.t. 12x1 + 8x2 +10 x3 +x4 = 2400 (1) 6x1 + 10x2 +15 x3 + x5 = 1500 (2) 15x1 + 18x2 + x6 = 1800 (3) 20x2 + 22x3 + x7 = 2000 (4) x10， x2 0 x3 0 x4 0 x5 0 x6 0 x7 0 x4 =440 x5 =0 x6 =0 x7 =856
min w = 2400y1 + 1500 y2 +1800 y3 +2000 y4
s.t. 12y1 + 6y2 + 15y3 - y5 = 120 (1) 8y1 + 10y2 + 18 y3 + 20 y4 - y6 = 180 (2) 10y1 + 15y2 +22y4 - y7 = 210 (3) y1 0， y2 0 y3 0 y4 0 y5 0 y6 0 y7 0 由互补松弛关系可知，x1 x3 x4 x70，得到y5= y7= y1= y4=0
6y2 + 15y3 = 120
10y2 + 18 y3 - y6 = 180 15y2 = 210
解得y2=14 y3= 2.4 y6=3.2
原材料甲的影子价格为：0万元/吨 原材料乙的影子价格为：14万元/吨 原材料丙的影子价格为：2.4万元/吨
原材料丁的影子价格为：0万元/吨
5
