线性规划的对偶

第四章 线性规划的对偶理论

一、填空题

1．线性规划问题具有对偶性，即对于任何一个求最大值的线性规划问题，都有一个求最小值/极小值的

线性规划问题与之对应，反之亦然。

2．在一对对偶问题中，原问题的约束条件的右端常数是对偶问题的目标函数系数。 3．如果原问题的某个变量无约束，则对偶问题中对应的约束条件应为等式_。 4．对偶问题的对偶问题是原问题_。

5．若原问题可行，但目标函数无界，则对偶问题不可行。

6．若某种资源的影子价格等于k。在其他条件不变的情况下(假设原问题的最佳基不变)，当该种资源增加3个单位时。相应的目标函数值将增加3k 。

﹡－

7．线性规划问题的最优基为B，基变量的目标系数为CB，则其对偶问题的最优解Y= CBB1。

﹡﹡﹡﹡

8．若X和Y分别是线性规划的原问题和对偶问题的最优解，则有CX= Yb。 9．若X、Y分别是线性规划的原问题和对偶问题的可行解，则有CX≤Yb。

﹡﹡﹡

10．若X和Y分别是线性规划的原问题和对偶问题的最优解，则有CX=Y*b。

11．设线性规划的原问题为maxZ=CX，Ax≤b，X≥0，则其对偶问题为min=Yb YA≥c Y≥0_。 12．影子价格实际上是与原问题各约束条件相联系的对偶变量的数量表现。

13．线性规划的原问题的约束条件系数矩阵为A，则其对偶问题的约束条件系数矩阵为AT 。 14．在对偶单纯形法迭代中，若某bi<0，且所有的aij≥0(j=1，2，?n)，则原问题_无解。 二、单选题 1．线性规划原问题的目标函数为求极小值型，若其某个变量小于等于0，则其对偶问题约束条件为A形式。

A．“≥” B．“≤” C，“>” D．“=” 2．设X、Y分别是标准形式的原问题与对偶问题的可行解,则 C 。

3．对偶单纯形法的迭代是从_ A_开始的。

A．正则解 B．最优解 C．可行解 D．基本解

﹡

4．如果z。是某标准型线性规划问题的最优目标函数值，则其对偶问题的最优目标函数值wA。

﹡﹡ ﹡﹡ ﹡﹡ ﹡﹡

A．W=ZB．W≠ZC．W≤ZD．W≥Z 5．如果某种资源的影子价格大于其市场价格，则说明_ B

A．该资源过剩B．该资源稀缺 C．企业应尽快处理该资源D．企业应充分利用该资源，开僻新的生产途径 三、多选题

1．在一对对偶问题中，可能存在的情况是ABC。

A．一个问题有可行解，另一个问题无可行解 B．两个问题都有可行解

C．两个问题都无可行解 D．一个问题无界，另一个问题可行 2．下列说法错误的是B 。

A．任何线性规划问题都有一个与之对应的对偶问题B．对偶问题无可行解时，其原问题的目标函数无界。C．若原问题为maxZ=CX，AX≤b，X≥0，则对偶问题为minW=Yb，YA≥C，Y≥0。D．若原问题有可行解，但目标函数无界，其对偶问题无可行解。

3．如线性规划的原问题为求极大值型，则下列关于原问题与对偶问题的关系中正确的是BCDE。

A原问题的约束条件“≥”，对应的对偶变量“≥0” B原问题的约束条件为“=”，对应的对偶变量为自由变量 C．原问题的变量“≥0”，对应的对偶约束“≥” D．原问题的变量“≤O”对应的对偶约束“≤”E．原问题的变量无符号限制，对应的对偶约束“=” 4．一对互为对偶的问题存在最优解，则在其最优点处有BD

A．若某个变量取值为0，则对应的对偶约束为严格的不等式B．若某个变量取值为正，则相应的对偶约束必为等式C．若某个约束为等式，则相应的对偶变取值为正D．若某个约束为严格的不等式，则相应的对偶变量取值为0 E．若某个约束为等式，则相应的对偶变量取值为0 5．下列有关对偶单纯形法的说法正确的是ABCD。

A．在迭代过程中应先选出基变量，再选进基变量B．当迭代中得到的解满足原始可行性条件时，即得到最优解 C．初始单纯形表中填列的是一个正则解D．初始解不需要满足可行性 E．初始解必须是可行的。 6．根据对偶理论，在求解线性规划的原问题时，可以得到以下结论ACD。

A． 对偶问题的解B．市场上的稀缺情况 C．影子价格D．资源的购销决策E．资源的市场价格

7．在下列线性规划问题中，CE采用求其对偶问题的方法，单纯形迭代的步骤一般会减少。

四、名词、简答题

1、对偶可行基：凡满足条件δ=C-CBBA≤0的基B称为对偶可行基。 2、.对称的对偶问题：设原始线性规划问题为maxZ=CX s.t AX≤b X ≥0 称线性规划问题minW=Yb s.t YA≥C

Y≥0 为其对偶问题。又称它们为一对对称的对偶问题。 3、影子价格：对偶变量Yi表示与原问题的第i个约束条件相对应的资源的影子价格，在数量上表现为，当该约束条件的右端常数增加一个单位时（假设原问题的最优解不变），原问题目标函数最优值增加的数量。 4．影子价格在经济管理中的作用。（1）指出企业内部挖潜的方向；（2）为资源的购销决策提供依据；（3）分析现有产品价格变动时资源紧缺情况的影响；（4）分析资源节约所带来的收益；（5）决定某项新产品是否应投产。

5．线性规划对偶问题可以采用哪些方法求解？（1）用单纯形法解对偶问题；（2）由原问题的最优单纯形表得到；（3）由原问题的最优解利用互补松弛定理求得；（4）由Y*=CBB-1求得，其中B为原问题的最优基

6、一对对偶问题可能出现的情形：1.原问题和对偶问题都有最优解，且二者相等；2.一个问题具有无界解，则另一个问题具有无可行解；3.原问题和对偶问题都无可行解。 五、写出下列线性规划问题的对偶问题

1．minZ=2x1+2x2+4x3

-1

六、已知线性规划问题

应用对偶理论证明该问题最优解的目标函数值不大于25

七、已知线性规划问题 maxZ=2x1+x2+5x3+6x4

﹡

其对偶问题的最优解为Y=4，Y2=1，试应用对偶问题的性质求原问题的最优解。

﹡l

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

八、已知线性规划问题

(1) 写出其对偶问题 (2)已知原问题最优解为X﹡=(2，2，4，0)，试根据对偶理论，直接求出对偶问题

的最优解。

T

W* = 16

25/3