22线性规划的对偶定理 为了便于讨论,下面不妨总是假设 原问题:maxf(x)=CX对偶问题:ming(y)=Yb AX< b YA≥C s t X≥0 Y≥0 221弱对偶定理 定理对偶问题min)的任何可行解Y,其目标函数值总是 不小于原问题(max)任何可行解γ的目标函数值 证:由于X0,Y0分别为原问题和对偶问题的可行解故有 AX<b YA≥C X≥0 0 0 容易看出有Yb≥Y0AX0≥CX0.#9 2.2 线性规划的对偶定理 2.2.1 弱对偶定理 定理 对偶问题(min)的任何可行解Y 0 ，其目标函数值总是 不小于原问题(max)任何可行解X0的目标函数值 • 为了便于讨论，下面不妨总是假设      = X 0 AX b s t f x CX . . 原问题 : max ( )      = Y 0 Y A C s t g y Y b . . 对偶问题 : min ( ) Y b Y AX CX # Y 0 Y A C X 0 AX b X Y . : , , 0 0 0 0 0 0 0 0 0 0             容易看出有 证 由于 分别为原问题和对偶问题的可行解 故有