文章目錄

• 最優化—對偶原理與對偶單純形法
• • 線性規劃的對偶原理
  • 原問題為何與對偶問題等價
  • • 前提1
    • 前提2
    • 證明等價性

最優化—對偶原理與對偶單純形法

線性規劃的對偶原理

對于標準線性規劃問題：
$$\begin{array}{c}\max c_1{x}_1+c_2{x}_2+?+c_n{x}_n\\ \text{?s.t.?}{P}_1{x}_1+P_2{x}_2+?+P_n{x}_n=b\\ x_j\ge 0,?1\le j\le n\end{array}$$
$C=(c_1,...,c_n{)}^T,P_j=(p_{1j},...,p_{mj}),b=(b_1,...,b_m{)}^T,X=(x_1,...,x_m{)}^T,P=(P_1,...,P_n)$
定義：標準線性規劃問題(最大規劃)的對偶問題
$$\begin{array}{l}\text{原}問題對偶問題\\ \max {\sum }_{j=1}^n{c}_j{x}_j\\ \text{?s.t.?}{\sum }_{j=1}^n{P}_j{x}_j=b?\min b^{T}Y\\ x_j\ge 0,?1\le j\le ns.t.P_j^{T}Y\ge c_j,?1\le j\le n\end{array}$$
簡化為：
$$\begin{array}{l}max{C}^{T}X\min b^{T}Y\\ \text{?s.t.?}PX=b?\text{?s.t.?}{P}^{T}Y\ge C\\ X\ge 0\end{array}$$

原問題為何與對偶問題等價

首先確定以下前提

前提1

? 假設一個基陣$B=\left(P_{j(1)},P_{j(2)},?,P_{j(m)}\right)$使得原問題得到最優解，對應$C_B=\left(c_{j(1)},c_{j(2)},?,c_{j(m)}\right)$

? 則檢驗數${\sigma }_j=c_j?C_B^T{B}^{?1}{P}_j\le 0,?1\le j\le n$

? 若原問題有最優解，并設$Y^T=C_B^T{B}^{?1}$，則$Y^T{P}_j\ge c_j,?1\le j\le n$，其中$Y=(y_1,...y_m)$。

前提2

設 $\hat{X}={\left({\hat{x}}_1,?,{\hat{x}}_n\right)}^T$ 是原問題的任意一個可行解，滿足
$$P_1{\hat{x}}_1+P_2{\hat{x}}_2+?+P_n{\hat{x}}_n=b,{\hat{x}}_j\ge 0,?1\le j\le n$$
對任何滿足不等式約束 $Y^T{P}_j\ge c_j,?1\le j\le n$ 的 $Y,$ 有
$$Y^{T}b=Y^T\sum _{j=1}^n{P}_j{\hat{x}}_j=\sum _{j=1}^n{Y}^T{P}_j{\hat{x}}_j\ge \sum _{j=1}^n{c}_j{\hat{x}}_j=C^T\hat{X}$$
這說明對偶問題的任何可行的目標函數值不會小于原問題的任何可行解的目標函數值：$Y^{T}b\ge C^{T}X$

證明等價性

? 對于對偶問題 :
$$\begin{array}{l}\min Y^{T}b\\ \text{?s.t.?}{Y}^T{P}_j\ge c_j,?1\le j\le n\end{array}$$
? ①當 $B$ 是原問題的最優基陣時,根據前提1紅字 $Y_B^T=C_B^T{B}^{?1}$ 是上述問題的可行解，其目標函數值與原問題的最優目標函數值相同。
$$Y_B^{T}b=C_B^T{B}^{?1}b=C_B^T\left(B^{?1}b\right)=C_B^T{X}_B$$
? 其中 $X_B$ 是 $B$ 決定的最優的基本可行解的基分量$=(x_{j(1)},...,x_{j(m)})$

? PS：根據①呢，我們知道了：對于一個原問題的最優狀態，對偶問題中一定有一個對應的Y，使得對偶問題的目標函數值等于原問題的最優目標函數值。

下面我們就來看看這個對應的Y是否就是對偶問題的最優解?

? ②由前提2知：對于任何滿足不等式約束 $Y^T{P}_j\ge c_j,?1\le j\le n$ 的 $Y,$ 有
$$Y^{T}b\ge C_B^T{X}_B$$
? 又由于① $Y_B^{T}b=C_B^T{X}_B$得：
$$Y^{T}b\ge C_B^T{X}_B=Y_B^{T}b$$
? ③綜上所述：對于任何滿足不等式約束 $Y^T{P}_j\ge c_j,?1\le j\le n$ 的 $Y,$ 都有$Y^{T}b\ge Y_B^{T}b$，所以對偶問題的最優解就是$Y_B^T$。

? 所以求解上面線性規劃問題能夠找到原問題的最優基陣

總結

以上是生活随笔為你收集整理的最优化——分析线性规划的对偶问题的等价性的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。