A-A+

在LP与DP中若一个有最优解则另一个也有最优解且二者的目标函数最优值相等．若其中一个问

2022-08-12 13:52:07 问答库阅读 196 次

问题详情

在LP与DP中，若一个有最优解，则另一个也有最优解，且二者的目标函数最优值相等．若其中一个问题的目标函数无界，则另一个问题无可行解．

参考答案

若LP有最优解，则可用单纯形法求得最优基可行解，设为x⁽⁰⁾，对应基阵设为B．由定理，u⁽⁰⁾=C_BB^-1是DP的最优解，并且
cx⁽⁰⁾=C_Bx_B⁽⁰⁾=C_BB^-1b=u⁽⁰⁾b．
若DP有最优解，由于任何线性规划问题都可化为标准形式和对偶关系的相互性，可知LP也必有最优解，且二者最优值相等．