【运筹学】对偶理论 : 对称形式 ( 对称形式 | 对偶模型转化实例 | 对偶问题规律分析 )

文章目录

• 一、对偶问题的对称形式
• 二、对偶问题实例
• 三、对偶问题规律

一、对偶问题的对称形式

---

1 . 对称形式特点 :

• 目标函数求最大值时 , 所有约束条件都是 小于等于 $\leq$≤ 符号 , 决策变量大于等于 $0$0 ;
• 目标函数求最小值时 , 所有约束条件都是 大于等于 $\geq$≥ 符号, 决策变量大于等于 $0$0 ;

2 . 原问题 $P$P 的线性规划模型是 :

$\begin{array}{lcl} maxZ = C X \\\\ s.t\begin{cases} AX \leq b \\\\ X \geq 0 \end{cases}\end{array}$maxZ=CXs.t⎩⎪⎨⎪⎧​AX≤bX≥0​​

对称形式 $P$P 要求 :

• 目标函数求最大值
• 约束方程是 小于等于 不等式

相关系数 :

• 目标函数系数是 $C$C
• 约束方程系数是 $A$A
• 约束方程常数是 $b$b

3 . 对偶问题 $D$D 的线性规划模型是 :

$\begin{array}{lcl} minW = b^T Y \\\\ s.t\begin{cases} A^TY \geq C^T \\\\ Y \geq 0 \end{cases}\end{array}$minW=bTYs.t⎩⎪⎨⎪⎧​ATY≥CTY≥0​​

对偶问题 $D$D 要求 :

• 求最小值
• 约束方程时 大于等于 不等式

相关系数 :

• 目标函数系数是 $b^T$bT
• 约束方程系数是 $A^T$AT
• 约束方程常数是 $C^T$CT

二、对偶问题实例

---

写出如下线性规划对偶问题 :

$\begin{array}{lcl} maxZ = 2x_1 - 3x_2 + 4x_3 \\\\ s.t\begin{cases} 2 x_1 + 3x_2 - 5x_3 \geq 2 \\\\ 3x_1 + x_2 + 7x_3 \leq 3 \\\\ -x_1 + 4x_2 + 6x_3 \geq 5 \\\\ x_j \geq 0 \quad ( j = 1, 2, 3 ) \end{cases}\end{array}$maxZ=2x1​−3x2​+4x3​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​2x1​+3x2​−5x3​≥23x1​+x2​+7x3​≤3−x1​+4x2​+6x3​≥5xj​≥0(j=1,2,3)​​

将上述线性规划转为 对称形式 :

• 目标函数最大值 : 对称形式目标函数求最大值 , 上述线性规划符合该条件 , 不用进行修改 ;

• 约束方程小于等于不等式 : 对称形式的约束方程都是小于等于不等式 , 方程 $1$1 和方程 $3$3 都是大于等于不等式 , 不符合要求 ; 将不等式左右两边都乘以 $-1$−1 , 可以将大于等于不等式转为小于等于不等式 ;

转换后的结果为 :

$\begin{array}{lcl} maxZ = 2x_1 - 3x_2 + 4x_3 \\\\ s.t\begin{cases} -2 x_1 - 3x_2 + 5x_3 \leq -2 \\\\ 3x_1 + x_2 + 7x_3 \leq 3 \\\\ x_1 - 4x_2 - 6x_3 \leq -5 \\\\ x_j \geq 0 \quad ( j = 1, 2, 3 ) \end{cases}\end{array}$maxZ=2x1​−3x2​+4x3​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​−2x1​−3x2​+5x3​≤−23x1​+x2​+7x3​≤3x1​−4x2​−6x3​≤−5xj​≥0(j=1,2,3)​​

对称形式 的 目标函数的系数 为 $C = \begin{pmatrix} & 2 & -3 & 4 & \end{pmatrix}$C=(​2​−3​4​​) , 约束方程的系数 为 $A = \begin{pmatrix} &-2 & -3 & 5 & \\ &3 & 1 & 7 & \\ &1 & -4 & -6 & \\ \end{pmatrix}$A=⎝⎛​​−231​−31−4​57−6​​⎠⎞​ , 约束方程常数 $b = \begin{pmatrix} &-2 &\\ &3 & \\ &-5 & \\ \end{pmatrix}$b=⎝⎛​​−23−5​​⎠⎞​ ;

对偶问题 的 目标函数系数 为 $b^T = \begin{pmatrix} & -2 & 3 & -5 & \end{pmatrix}$bT=(​−2​3​−5​​) , 约束方程的系数 为 $A^T = \begin{pmatrix} &-2 & 3 & 1 & \\ &-3 & 1 & -4 & \\ &5 & 7 & -6 & \\ \end{pmatrix}$AT=⎝⎛​​−2−35​317​1−4−6​​⎠⎞​ , 约束方程常数 $C^T = \begin{pmatrix} & 2 &\\ &-3 & \\ &4 & \\ \end{pmatrix}$CT=⎝⎛​​2−34​​⎠⎞​ ;

线性规划形式 :

• 对称形式 : 求目标函数最大值 , 约束方程是求小于等于不等式 ;

• 对偶问题 : 求目标函数求最小值 , 约束方程都是大于等于不等式 ;

根据上述分析 , 写出对偶形式 :

$\begin{array}{lcl} minW = -2y_1 + 3y_2 - 5y_3 \\\\ s.t\begin{cases} -2y_1 + 3y_2 + y_3 \geq 2 \\\\ -3y_1 + y_2 - 4y_3 \geq -3 \\\\ 5y_1 + 7y_2 - 6y_3 \geq -4 \\\\ y_j \geq 0 \quad ( j = 1, 2, 3 ) \end{cases}\end{array}$minW=−2y1​+3y2​−5y3​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​−2y1​+3y2​+y3​≥2−3y1​+y2​−4y3​≥−35y1​+7y2​−6y3​≥−4yj​≥0(j=1,2,3)​​

原问题 与 对偶问题线性规划分析 :

上述对偶问题线性规划 , 与原问题线性规划 , 明显不互为转置矩阵 ;

原问题线性规划系数为 $\begin{pmatrix} &2 & 3 & -5 & \\ &3 & 1 & 7 & \\ &-1 & 4 & 6 & \\ \end{pmatrix}$⎝⎛​​23−1​314​−576​​⎠⎞​ , 对偶问题线性规划系数为 $\begin{pmatrix} &-2 & 3 & 1 & \\ &-3 & 1 & -4 & \\ &5 & 7 & -6 & \\ \end{pmatrix}$⎝⎛​​−2−35​317​1−4−6​​⎠⎞​ , 原问题的转置矩阵应该是 $\begin{pmatrix} &2 & 3 & -1 & \\ &3 & 1 & 4 & \\ &-5 & 7 & 6 & \\ \end{pmatrix}$⎝⎛​​23−5​317​−146​​⎠⎞​ , $y_1 , y_3$y1​,y3​ 系数的正负号与原问题的转置矩阵值的符号相反 ;

令 $y_1' = -y_1$y1′​=−y1​ , $y_3' = -y_3$y3′​=−y3​ , 则得到如下线性规划 :

$\begin{array}{lcl} minW = 2y_1' + 3y_2 - 5y_3' \\\\ s.t\begin{cases} 2y_1 + 3y_2 - y_3' \geq 2 \\\\ 3y_1 + y_2 + 4y_3' \geq -3 \\\\ -5y_1 + 7y_2 + 6y_3' \geq -4 \\\\ y_1' \leq 0 , y_2 \geq 0 , y_3' \leq 0 \end{cases}\end{array}$minW=2y1′​+3y2​−5y3′​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​2y1​+3y2​−y3′​≥23y1​+y2​+4y3′​≥−3−5y1​+7y2​+6y3′​≥−4y1′​≤0,y2​≥0,y3′​≤0​​

三、对偶问题规律

---

对偶有以下规律 : 假设原问题 $LP$LP 目标函数求最大值 $maxZ$maxZ , 对偶问题 $DP$DP 求最小值 $minW$minW ;

• 原问题 $LP$LP 有 $m$m 个约束条件 , 对应对偶问题 $DP$DP 的 $m$m 个 约束变量 ;
• 原问题 $LP$LP 有 $n$n 个约束变量 , 对应对偶问题 $DP$DP 的 $n$n 个 约束条件 ;

约束条件与约束变量的对应关系 :

• 如果原问题 $LP$LP 中的约束条件是小于等于 $\leq$≤ 不等式 , 那么对应的 对偶问题 $DP$DP 的约束变量就是大于等于 $\geq 0$≥0 的 ;
• 如果原问题 $LP$LP 中的约束条件是大于等于 $\geq$≥ 不等式 , 那么对应的 对偶问题 $DP$DP 的约束变量就是小于等于 $\leq 0$≤0 的 ;
• 如果原问题 $LP$LP 中的约束条件是 $=$= 等式 , 那么对应的 对偶问题 $DP$DP 的约束变量就是*变量 , 即没有任何约束 ;

约束变量与约束条件的对应关系 :

• 如果原问题 $LP$LP 中的 约束变量就是大于等于 $\geq 0$≥0 的 , 那么对应的 对偶问题 $DP$DP 的 约束条件是小于等于 $\leq$≤ 不等式 ;
• 如果原问题 $LP$LP 中的 约束变量就是小于等于 $\leq 0$≤0 的 , 那么对应的 对偶问题 $DP$DP 的 约束条件是大于等于 $\geq$≥ 不等式 ;
• 如果原问题 $LP$LP 中的 约束变量就是*变量 , 即没有任何约束 , 那么对应的 对偶问题 $DP$DP 的 约束条件是 $=$= 等式 ;

原问题 $LP$LP	对偶问题 $DP$DP
求最大值 $maxZ$maxZ	求最小值 $minW$minW
$m$m 个约束条件	$m$m 个约束变量
$n$n 个约束变量	$m$m 个约束条件
约束条件是小于等于不等式	约束变量是大于等于 $0$0 的
约束条件是大于等于不等式	约束变量是小于等于 $0$0 的
约束条件是等式	约束变量是*变量 ( 没有约束 )
约束变量是大于等于 $0$0 的	约束条件是小于等于不等式
约束变量是小于等于 $0$0 的	约束条件是大于等于不等式
约束变量是*变量 ( 没有约束 )	约束条件是等式

记住一条 : 目标函数求最大值 , 约束条件小于等于不等式 , 对偶问题的对应变量就是大于等于 $0$0 的 ;

补一张图 , 方便记忆 :