文章目录
一、对偶问题的对称形式
1 . 对称形式特点 :
- 目标函数求最大值时 , 所有约束条件都是 小于等于
\leq 符号 , 决策变量大于等于
0 ;
- 目标函数求最小值时 , 所有约束条件都是 大于等于
\geq 符号, 决策变量大于等于
0 ;
2 . 原问题
P 的线性规划模型是 :
\begin{array}{lcl} maxZ = C X \\\\ s.t\begin{cases} AX \leq b \\\\ X \geq 0 \end{cases}\end{array}对称形式
P 要求 :
相关系数 :
CAb3 . 对偶问题
D 的线性规划模型是 :
\begin{array}{lcl} minW = b^T Y \\\\ s.t\begin{cases} A^TY \geq C^T \\\\ Y \geq 0 \end{cases}\end{array}对偶问题
D 要求 :
相关系数 :
b^TA^TC^T二、对偶问题实例
写出如下线性规划对偶问题 :
\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}将上述线性规划转为 对称形式 :
- 目标函数最大值 : 对称形式目标函数求最大值 , 上述线性规划符合该条件 , 不用进行修改 ;
- 约束方程小于等于不等式 : 对称形式的约束方程都是小于等于不等式 , 方程
1 和方程
3 都是大于等于不等式 , 不符合要求 ; 将不等式左右两边都乘以
-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}对称形式 的 目标函数的系数 为
C = \begin{pmatrix} & 2 & -3 & 4 & \end{pmatrix} , 约束方程的系数 为
A = \begin{pmatrix} &-2 & -3 & 5 & \\ &3 & 1 & 7 & \\ &1 & -4 & -6 & \\ \end{pmatrix} , 约束方程常数
b = \begin{pmatrix} &-2 &\\ &3 & \\ &-5 & \\ \end{pmatrix} ;
对偶问题 的 目标函数系数 为
b^T = \begin{pmatrix} & -2 & 3 & -5 & \end{pmatrix} , 约束方程的系数 为
A^T = \begin{pmatrix} &-2 & 3 & 1 & \\ &-3 & 1 & -4 & \\ &5 & 7 & -6 & \\ \end{pmatrix} , 约束方程常数
C^T = \begin{pmatrix} & 2 &\\ &-3 & \\ &4 & \\ \end{pmatrix} ;
线性规划形式 :
- 对称形式 : 求目标函数最大值 , 约束方程是求小于等于不等式 ;
- 对偶问题 : 求目标函数求最小值 , 约束方程都是大于等于不等式 ;
根据上述分析 , 写出对偶形式 :
\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}原问题 与 对偶问题线性规划分析 :
上述对偶问题线性规划 , 与原问题线性规划 , 明显不互为转置矩阵 ;
原问题线性规划系数为
\begin{pmatrix} &2 & 3 & -5 & \\ &3 & 1 & 7 & \\ &-1 & 4 & 6 & \\ \end{pmatrix} , 对偶问题线性规划系数为
\begin{pmatrix} &-2 & 3 & 1 & \\ &-3 & 1 & -4 & \\ &5 & 7 & -6 & \\ \end{pmatrix} , 原问题的转置矩阵应该是
\begin{pmatrix} &2 & 3 & -1 & \\ &3 & 1 & 4 & \\ &-5 & 7 & 6 & \\ \end{pmatrix} ,
y_1 , y_3 系数的正负号与原问题的转置矩阵值的符号相反 ;
令
y_1' = -y_1 ,
y_3' = -y_3 , 则得到如下线性规划 :
\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}三、对偶问题规律 ( 目标函数求最大值 )
对偶有以下规律 : 假设原问题
LP 目标函数求最大值
maxZ , 对偶问题
DP 求最小值
minW ;
LP 有
m 个约束条件 , 对应对偶问题
DP 的
m 个 约束变量 ;
LP 有
n 个约束变量 , 对应对偶问题
DP 的
n 个 约束条件 ;
约束条件与约束变量的对应关系 ( 目标函数求最大值 ) : 这里特别注意 , 约束条件与约束变量 大于小于符号是相反的 ;
LP 中的约束条件是小于等于
\leq 不等式 , 那么对应的 对偶问题
DP 的约束变量就是大于等于
\geq 0 的 ;
LP 中的约束条件是大于等于
\geq 不等式 , 那么对应的 对偶问题
DP 的约束变量就是小于等于
\leq 0 的 ;
LP 中的约束条件是
= 等式 , 那么对应的 对偶问题
DP 的约束变量就是自由变量 , 即没有任何约束 ;
约束变量与约束条件的对应关系 ( 目标函数求最大值 ) : 这里特别注意 , 约束变量与约束条件 大于小于符号是相同的 ;
LP 中的 约束变量就是大于等于
\geq 0 的 , 那么对应的 对偶问题
DP 的 约束条件是大于等于
\geq 不等式 ;
LP 中的 约束变量就是小于等于
\leq 0 的 , 那么对应的 对偶问题
DP 的 约束条件是小于等于
\leq 不等式 ;
LP 中的 约束变量就是自由变量 , 即没有任何约束 , 那么对应的 对偶问题
DP 的 约束条件是
= 等式 ;
| |
---|
| |
目标函数求最大值
m
a
x
Z
maxZ
maxZ | 目标函数求最小值
m
i
n
W
minW
minW |
| |
| |
| |
| |
| |
| |
| |
| 约束变量是大于等于
≥
0
\geq 0
≥0 的 |
| 约束变量是小于等于
≤
0
\leq 0
≤0 的 |
| |
| |
约束变量是大于等于
≥
0
\geq 0
≥0 的 | |
约束变量是小于等于
≤
0
\leq 0
≤0 的 | |
| |
LP对偶问题
DP––目标函数求最大值
maxZ目标函数求最小值
minW––约束条件常数项目标函数系数目标函数系数约束条件常数项––
m 个约束条件
n 个约束变量
n 个约束变量
m 个约束条件––约束条件是小于等于不等式
\leq约束变量是大于等于
\geq 0 的约束条件是大于等于不等式
\geq约束变量是小于等于
\leq 0 的约束条件是等式约束变量是自由变量 ( 没有约束 )––约束变量是大于等于
\geq 0 的约束条件是大于等于不等式
\geq约束变量是小于等于
\leq 0 的约束条件是小于等于不等式
\leq约束变量是自由变量 ( 没有约束 )约束条件是等式
记住一条 : 目标函数求最大值 ,
LP 约束条件与
DP 约束变量符号相反 ,
LP 约束变量 与
DP 约束条件符号相同 ;
补一张图 , 方便记忆 :