线性规划习题(6)

四、名词、简答题 1、对偶可行基：凡满足条件δ =C-CBB A≤0 的基 B 称为对偶可行基。 2、.对称的对偶问题：设原始线性规划问题为 maxZ=CX 称线性规划问题 minW=Yb s.t AX≤b X ≥0 s.t YA≥C Y≥0 为其对偶问题。又称它们为一对对称的对偶问题。

-1

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

六、已知线性规划问题

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

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

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

?

?

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

八、已知线性规划问题

(1) 写出其对偶问题 的最优解。

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

T

W*

= 16 第五章 线性规划的灵敏度分析

一、填空题 1、灵敏度分析研究的是线性规划模型的原始、最优解数据变化对产生的影响。 2、在线性规划的灵敏度分析中，我们主要用到的性质是_可行性，正则性。 3．在灵敏度分析中，某个非基变量的目标系数的改变，将引起该非基变量自身的检验数的变化。 4．如果某基变量的目标系数的变化范围超过其灵敏度分析容许的变化范围，则此基变量应出基。 5．约束常数 b；的变化，不会引起解的正则性的变化。 6．在某线性规划问题中，已知某资源的影子价格为 Y1，相应的约束常数 b1，在灵敏度容许变动范围内发生 Δ b1 的变化，则新的最优解对应的最优目标函数值是 Z*+yi△b (设原最优目标函数值为 Z?) 7．若某约束常数 bi 的变化超过其容许变动范围，为求得新的最优解，需在原最优单纯形表的基础上运用对 偶单纯形法求解。 8．已知线性规划问题，最优基为 B，目标系数为 CB，若新增变量 xt，目标系数为 ct，系数列向量为 Pt，则 － 当 Ct≤CBB 1Pt 时，xt 不能进入基底。 9．如果线性规划的原问题增加一个约束条件，相当于其对偶问题增加一个变量。 10、若某线性规划问题增加一个新的约束条件，在其最优单纯形表中将表现为增加一行，一列。

11．线性规划灵敏度分析应在最优单纯形表的基础上，分析系数变化对最优解产生的影响 12．在某生产规划问题的线性规划模型中，变量 xj 的目标系数 Cj 代表该变量所对应的产品的利润，则当某 一非基变量的目标系数发生增大变化时，其有可能进入基底。 二、单选题 1．若线性规划问题最优基中某个基变量的目标系数发生变化，则 C。 A．该基变量的检验数发生变化 B．其他基变量的检验数发生变化 C．所有非基变量的检验数发生变化 D．所有变量的检验数都发生变化 2．线性规划灵敏度分析的主要功能是分析线性规划参数变化对 D 的影响。 A．正则性 B．可行性 C．可行解 D．最优解 3．在线性规划的各项敏感性分析中，一定会引起最优目标函数值发生变化的是 B。 A．目标系数 cj 的变化 B．约束常数项 bi 变化 C．增加新的变量 D．增加新约束 4．在线性规划问题的各种灵敏度分析中，B_的变化不能引起最优解的正则性变化。 A．目标系数 B．约束常数 C．技术系数 D．增加新的变量 E．增加新的约束条件 5．对于标准型的线性规划问题，下列说法错误的是 C A．在新增变量的灵敏度分析中，若新变量可以进入基底，则目标函数将会得到进一步改善。