作业帮对偶理论的弱对偶定理是什么
来源：学生作业帮助网 编辑：作业帮 时间：2024/04/30 09:44:20
对偶理论的弱对偶定理是什么
对偶理论的弱对偶定理是什么
对偶理论的弱对偶定理是什么
基本定理 原始问题和对偶问题的标准形式如下：
原始问题 对偶问题
max z=cx min w=yb
s.t. Ax≤b s.t. yA≥c
x≥0 y≥0
式中max表示求极大值,min表示求极小值,s.t.表示“约束条件为”；z为原始问题的目标函数,w为对偶问题的目标函数；x为原始问题的决策变量列向量（n×1）,y为对偶问题的决策变量行向量(1×m);A为原始问题的系数矩阵(m×n),b为原始问题的右端常数列向量（m×1）,c为原始问题的目标函数系数行向量（1×n）.在原始问题与对偶问题之间存在着一系列深刻的关系,业已得到严格数学证明的有如下一些定理.
弱对偶定理 若上述原始问题和对偶问题分别有可行解x0和y0,则cx0≥y0b.这个定理表明极大化问题任一可行解的目标函数值总是不大于它的对偶问题的任一可行解的目标函数值.
强对偶定理 若上述原始问题和对偶问题都可行,则它们分别有最优解x*和y*,且cx*=y*b.