判断题判断正误，如果错误请更正第二章线形规划的对偶理论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=CB-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 原问题与对偶问题都有最优解计算题线性规划问题和对偶问题对于如下的线性规划问题min z = 3x1 + 2x2+x3. x1 + x2+ x3 ≤ 15 (1)2x1 - x2+ x3≥ 9 (2)-x1 + 2x2+2x3≤ 8 (3)x1 x2x3 ≥ 01、写出题目中线性规划问题的对偶问题；2、分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）；解答：1、写出题目中线性规划问题的对偶问题；解：max w = 15y1 + 9y2 + 8y3. y1 + 2y2- y3 ≤ 3 (1)y1 - y2+ 2y3≤ 2 (2)y1 + y2+ 2y3≤ 1 (3)y1≤0、 y2 ≥0、y3 ≤02、分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）；解：先将原问题化成以下形式，则有mi n z = 3x1 + 2x2 + x3. x1 + x2+ x3+ x4= 15 (1)-2x1 + x2- x3+ x5= -9 (2)-x1 + 2x2+2x3+x6= 8 (3)x1 x2x3x4x5x6 ≥ 0原始问题的最优解为（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对于以下线性规划问题max z = -x1 - 2x2. -2x1 + 3x2≤ 12 (1)-3x1 + x2≤ 6 (2)x1 + 3x2≥ 3 (3)x1≤ 0， x2≥ 01、写出标准化的线性规划问题；2、用单纯形表求出这个线性规划问题的最优解和最优的目标函数值；3、写出这个（极大化）线性规划问题的对偶问题；4、求出对偶问题的最优解和最优解的目标函数值；5、第（2）个约束右端常数b2=6在什么范围内变化，最优解保持不变。
解答：1、写出标准化的线性规划问题:令x1*=- x1max z = x1*- 2x2. 2x1* + 3x2+ x3= 12 (1)3x1* + x2+ x4= 6 (2)-x1* + 3x2-x5= 3 (3)x1* x2x3x4x5≥ 02、（6分）用单纯形表求出这个线性规划问题的最优解和最优的目标函数值此时最优解为（X1、X2、X3、X4 X5）=（-3/2，3/2，9/2，0，0）maxz=-3/2 3、写出这个（极大化）线性规划问题的对偶问题；min w = 12y1 + 6y2+ 3y3. -2y1 - 3y2+ y3 ≤ -1 (1)3y1 + y2+ 3 y3≥ -2 (2)y1≥0、 y2 ≥0、y3 ≤04、求出对偶问题的最优解和最优解的目标函数值；此时最优解为（y1、y2、y3、y4 y5）=（0，1/10,-7/10，0，0）minw =-3/2 5、则有1≤b2≤11，最优解不变。
已知LP 问题：max z = x 1 + 2x 2 +3x 3 + 4x 4. x 1 + 2x 2 + 2x 3 + 3x 4 ≤ 20 (1) 2x 1 + x 2 + 3x 3 + 2x 4 ≤ 20 (2) x 1 、 x 2 、 x 3 、 x 4 ≥ 0的最优解为（0，0，4，4）T ，最优值为Z=28。
请用互补松弛定理计算其对偶问题的最优解。
解答：首先写出此LP 问题的对偶问题为：min w = 20y 1 + 20y 2. y 1 + 2y 2 ≥ 1 (1)2y 1 + y 2 ≥ 2 (2)2y 1 + 3y 2 ≥ 3 (3)3y 1 + 2y 2 ≥ 4 (4)y 1 、 y 2 、 ≥ 0将上述对偶问题的化成标准型，取松弛变量分别为v 1 、v 2、、 v 3 、v 4，则有min w = 20y 1 + 20y 2. y 1 + 2y 2 - v 1 = 1 (5)2y 1 + y 2 - v 2 = 2 (6)2y 1 + 3y 2 - v 3 = 3 (7)3y 1 + 2y 2 - v 4 = 4 (8)y 1 、 y 2 、 ≥ 0利用互补松弛定理可知：x 3 = 4 > 0 ,又有 x 3 v 3 = 0 ， 所以有 v 3 = 0 代入(7)式 x 4 = 4 > 0，又有 x 4 v 4= 0 ， 所以有 v 4 = 0 代入(8)式，则有2y 1 + 3y 2 = 3 (9)3y 1 + 2y 2 = 4 (10)从中可计算出y 1 = 6/5 、 y 2 = 1/5，则 w* =28一个工厂用四种原料生产三种产品，生产每种产品要消耗的各种原料数量（表中“—”表示相应的产品不需要这种原料）、各种产品的利润以及各种原料的限量如下表所示。
1、写出原料限制条件下利润最大化的线性规划模型；2、写出以上问题的对偶问题；3、已知利润最大的线性规划问题的最优解是产品A生产120件，产品B不生产，产品C生产52件，用互补松弛关系求四种原料的影子价格。
解答：一个工厂用四种原料生产三种产品，生产每种产品要消耗的各种原料数量（表中“—”表示相应的产品不需要这种原料）、各种产品的利润以及各种原料的限量如下表所示。
1.写出原料限制条件下利润最大化的线性规划模型；max z = 120x1 + 180x2+210x3. 12x1 + 8x2+10x3 ≤ 2400 (1)6x1 + 10x2+15x3 ≤ 1500 (2)15x1 + 18x2≤ 1800 (3)20x2 + 22x3≤ 2000 (4)x1≥ 0， x2≥ 0 x3≥ 0 2.写出以上问题的对偶问题；min w = 2400y 1 + 1500 y 2 +1800 y 3 +2000 y 4. 12y 1 + 6y 2 + 15y 3 ≥ 120 (1)8y 1 + 10y 2 + 18 y 3 + 20 y 4 ≥ 180 (2) 10y 1 + 15y 2 +22y 4 ≥ 210 (3) y 1≥ 0， y 2 ≥ 0 y 3 ≥ 0 y 4 ≥ 03. 已知利润最大的线性规划问题的最优解是产品A 生产120件，产品B 不生产，产品C 生产52件，用互补松弛关系求四种原料的影子价格。
max z = 120x 1 + 180 x 2 +210 x 3. 12x 1 + 8x 2 +10 x 3 +x 4 = 2400 (1) 6x 1 + 10x 2 +15 x 3 + x5 = 1500 (2) 15x 1 + 18x 2 + x 6 = 1800 (3) 20x 2 + 22x 3 + x 7 = 2000 (4) x 1≥0， x 2 ≥0 x 3 ≥0 x 4 ≥0 x 5 ≥0 x 6 ≥0 x 7 ≥0 x 4 =440 x 5 =0 x 6 =0 x 7 =856min w = 2400y 1 + 1500 y 2 +1800 y 3 +2000 y 4. 12y 1 + 6y 2 + 15y 3 - y 5 = 120 (1) 8y 1 + 10y 2 + 18 y 3 + 20 y 4 - y 6 = 180 (2) 10y 1 + 15y 2 +22y 4 - y 7 = 210 (3) y 1≥ 0， y 2 ≥0 y 3 ≥0 y 4 ≥0 y 5 ≥0 y 6 ≥0 y 7 ≥0由互补松弛关系可知，x 1 x 3 x 4 x 7≥0，得到y 5= y 7= y 1= y 4=06y 2 + 15y 3 = 12010y 2 + 18 y 3 - y 6 = 180 15y 2 = 210解得y 2=14 y 3= y 6= 原材料甲的影子价格为：0万元/吨 原材料乙的影子价格为：14万元/吨 原材料丙的影子价格为：万元/吨原材料丁的影子价格为：0万元/吨。