定義
矩陣形式
用矩陣形式表示,對稱形式的線性規劃問題的原問題為:
![弱對偶性](/img/a/867/wZwpmLwIDOwUDN4MjMxYjN1UTM1QDN5MjM5ADMwAjMwUzLzIzL1EzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
其對偶問題為:
![弱對偶性](/img/6/2f1/wZwpmL0UTM2cTNwczMxYjN1UTM1QDN5MjM5ADMwAjMwUzL3MzLxMzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
或表示為:
![弱對偶性](/img/f/1e9/wZwpmLyIDNyQTO4IzMxYjN1UTM1QDN5MjM5ADMwAjMwUzLyMzLxMzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
![弱對偶性](/img/d/248/wZwpmL4czMxQDOwITO5ADN0UTMyITNykTO0EDMwAjMwUzLykzLxEzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![弱對偶性](/img/b/280/wZwpmLyYTM2cjMwkDO0ATN0UTMyITNykTO0EDMwAjMwUzL5gzL1EzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![弱對偶性](/img/b/236/wZwpmL3ATMwkzN3kzMxYjN1UTM1QDN5MjM5ADMwAjMwUzL5MzL2QzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![弱對偶性](/img/f/cff/wZwpmLycTN5AjN2kzMxYjN1UTM1QDN5MjM5ADMwAjMwUzL5MzL0EzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
![弱對偶性](/img/6/da7/wZwpmLwczM3ATO1cjN1IDN0UTMyITNykTO0EDMwAjMwUzL3YzL0gzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
其中, 和 均是列向量, , ,上標 表示轉置 。
![弱對偶性](/img/1/03a/wZwpmL3EjMzQjN5MjM2EzM1UTM1QDN5MjM5ADMwAjMwUzLzIzLxAzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
![弱對偶性](/img/0/807/wZwpmL4UTO2IzNyYTMxYjN1UTM1QDN5MjM5ADMwAjMwUzL2EzLzgzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
若 是原問題的可行解, 其對偶問題的可行解,則恆有:
![弱對偶性](/img/2/b90/wZwpmL3MzN0cTM2gjMxYjN1UTM1QDN5MjM5ADMwAjMwUzL4IzL1UzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
如果原問題是求極小化問題上述結論的符號相反:
![弱對偶性](/img/8/106/wZwpmLyUjM3ETNygjMxYjN1UTM1QDN5MjM5ADMwAjMwUzL4IzL4QzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
標準形式
假定原問題是最大化問題即線性規劃問題(LP)的標準形式:
![弱對偶性](/img/8/988/wZwpmL4EzN1MDN2gjMxYjN1UTM1QDN5MjM5ADMwAjMwUzL4IzLxUzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
其對偶問題(DLP)如下式所示:
![弱對偶性](/img/8/988/wZwpmL4EzN1MDN2gjMxYjN1UTM1QDN5MjM5ADMwAjMwUzL4IzLxUzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![弱對偶性](/img/c/518/wZwpmL3MzNwEDO3gzMxYjN1UTM1QDN5MjM5ADMwAjMwUzL4MzL2MzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
若 是原問題的可行解,y=(j=1,2,···,m)是其對偶問題的可行解,則恆有:
![弱對偶性](/img/7/e70/wZwpmL4UTNykjM1YzMxYjN1UTM1QDN5MjM5ADMwAjMwUzL2MzL1IzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
定律推論
以下是根據 弱對偶性的推論:
原問題是極大化問題時,原問題任意可行的目標函式值是其對偶問題目標函式值的下界;反之對偶問題任一可行解的目標函式值是其原問題目標函式的上界。
原問題是極小化問題時,原問題任意可行的目標函式值是其對偶問題目標函式值的上界;反之對偶問題任一可行解的目標函式值是其原問題目標函式的下界。
如果原問題(有可行解且)目標函式值無界即有無界解,則其對偶問題無可行解;反之對偶問題(有可行解且)目標函式值無界,則其原問題無可行解。(可行解無界,就不能存在為其上下界的可行解。)
性質2的逆命題不成立,因為:當對偶問題無可行解時,其原問題或具有無界解或無可行解,反之亦然。
若原問題有可行解而對偶問題無可行解,則原問題目標函式無界;反之對偶問題有可行解而其對偶問題無可行解,對偶問題的目標函式無界。
1.原問題是極大化問題時,原問題任意可行的目標函式值是其對偶問題目標函式值的下界;反之對偶問題任一可行解的目標函式值是其原問題目標函式的上界。
2.原問題是極小化問題時,原問題任意可行的目標函式值是其對偶問題目標函式值的上界;反之對偶問題任一可行解的目標函式值是其原問題目標函式的下界。
3.如果原問題(有可行解且)目標函式值無界即有無界解,則其對偶問題無可行解;反之對偶問題(有可行解且)目標函式值無界,則其原問題無可行解。(可行解無界,就不能存在為其上下界的可行解。)
4.性質2的逆命題不成立,因為:當對偶問題無可行解時,其原問題或具有無界解或無可行解,反之亦然。
5.若原問題有可行解而對偶問題無可行解,則原問題目標函式無界;反之對偶問題有可行解而其對偶問題無可行解,對偶問題的目標函式無界。
推導過程
矩陣形式
![弱對偶性](/img/8/efe/wZwpmLycTM1YzN1gTMxYjN1UTM1QDN5MjM5ADMwAjMwUzL4EzLyYzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![弱對偶性](/img/b/f6d/wZwpmL2gzMxUDM4kTMxYjN1UTM1QDN5MjM5ADMwAjMwUzL5EzL2EzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![弱對偶性](/img/9/2b6/wZwpmLyQjNxYzM4YzMxYjN1UTM1QDN5MjM5ADMwAjMwUzL2MzL0UzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![弱對偶性](/img/f/c52/wZwpmL1UTOxcjM1QzMxYjN1UTM1QDN5MjM5ADMwAjMwUzL0MzL1EzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
由於原問題的任一可行解X必定滿足約束條件: ,在不等式兩邊同時右乘對偶問題可行解Y,有 ;且對偶問題的任一可行解Y必定滿足約束條件: ,在不等式兩邊同時左乘原問題可行解X,有 ,可以推導出它們的目標函式值有以下關係 :
![弱對偶性](/img/3/4d9/wZwpmLxMTO4YTMzgzMxYjN1UTM1QDN5MjM5ADMwAjMwUzL4MzLyQzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
(原問題的目標函式值) (對偶問題的目標函式值)
標準形式
![弱對偶性](/img/0/0fb/wZwpmLxYjN4UDNxczMxYjN1UTM1QDN5MjM5ADMwAjMwUzL3MzLwgzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
![弱對偶性](/img/c/72e/wZwpmL2YDO4QDNxczMxYjN1UTM1QDN5MjM5ADMwAjMwUzL3MzLyQzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
由於原問題的任一可行解滿足 ,對偶問題的任一可行解滿足
證:因為
![弱對偶性](/img/4/c90/wZwpmLygDOxkDN5EzMxYjN1UTM1QDN5MjM5ADMwAjMwUzLxMzL2gzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![弱對偶性](/img/4/0d9/wZwpmL1ITO0ATN2gTMxYjN1UTM1QDN5MjM5ADMwAjMwUzL4EzL0MzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![弱對偶性](/img/7/2c5/wZwpmL2czNwUzMwkTMxYjN1UTM1QDN5MjM5ADMwAjMwUzL5EzLxczLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
所以,