对偶性定理: 定理2.3原线性规划(P)与其对偶规划(D)存 在以下对应关系: (1)(P)有最优解的充要条件是(D)有最优解 (2)若X*和Y分别是(P)和(D)的可行解, 则X和Y分别是(P)和(D)的最优解的充 要条件是: CX=Y*b
定理2.3 原线性规划（P）与其对偶规划（D）存 在以下对应关系： （1）（P）有最优解的充要条件是（D）有最优解 （2）若X*和Y*分别是（P）和（D）的可行解， 则X*和Y*分别是（P）和（D）的最优解的充 要条件是： CX*=Y*b 三、对偶性定理：
设原问题(P)为标准型 则其对偶问题(D)为 max 2=CX mIn s=yb .t AX= b stYA≥C X≥0 Y无符号限制 (1)(P)有最优解的充要条件是(D)有最优解 证明必要性:若(P)有最优解xB为最优基心 有CN-CB_N≤0, C-CBBA=CB, CN)-CBB(B,M) (CB, CN)CB, CBB N) (0,Cx-CBBN)≤0, 即CBA≥C,取Y=CB-1,则有YA≥C 即Y=CB是(D)的一个可行解 由定理22的推论2知:(D)有最优解 充分性:由定理2.1知,(P)与(D)互为对偶, 充分性同理证明
证明：必要性：若（P）有最优解X0 ， C CB B A −1 − , 1 CB B A C 即 − 1 0 − 取Y = CB B , , 则有Y0 A C 即Y0 = CB B −1 是（D）的一个可行解 由定理2.2的推论2知：（D）有最优解 充分性：由定理2.1知，（P）与（D）互为对偶， 充分性同理证明0, 1 − − 有CN CB B N ( , ) ( , ) 1 CB CN CB B B N − = − ( , ) ( , ) 1 CB CN CB CB B N − = − (0, ) 1 CN CB B N − = − 0, （1）（P）有最优解的充要条件是（D）有最优解 B为最优基 0 . max = = X st AX b z CX 设原问题（P）为标准型 无符号限制 则其对偶问题 为 Y st YA C S Yb D = . min ( )