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

韩曙亮

发布于 2023-03-28 16:32:26

8820

发布于 2023-03-28 16:32:26

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

一、对偶问题的对称形式

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

要求 :

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

相关系数 :

目标函数系数是

C

约束方程系数是

A

约束方程常数是

b

3 . 对偶问题

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^T

约束方程系数是

A^T

约束方程常数是

C^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

的约束条件是

=

等式 ;

原问题 L P LP LP	对偶问题 D P DP DP
–	–
目标函数求最大值 m a x Z maxZ maxZ	目标函数求最小值 m i n W minW minW
–	–
约束条件常数项	目标函数系数
目标函数系数	约束条件常数项
–	–
m m m 个约束条件	n n n 个约束变量
n n n 个约束变量	m m m 个约束条件
–	–
约束条件是小于等于不等式 ≤ \leq ≤	约束变量是大于等于 ≥ 0 \geq 0 ≥0 的
约束条件是大于等于不等式 ≥ \geq ≥	约束变量是小于等于 ≤ 0 \leq 0 ≤0 的
约束条件是等式	约束变量是自由变量 ( 没有约束 )
–	–
约束变量是大于等于 ≥ 0 \geq 0 ≥0 的	约束条件是大于等于不等式 ≥ \geq ≥
约束变量是小于等于 ≤ 0 \leq 0 ≤0 的	约束条件是小于等于不等式 ≤ \leq ≤
约束变量是自由变量 ( 没有约束 )	约束条件是等式

LP

对偶问题

DP

––目标函数求最大值

maxZ

目标函数求最小值

minW

––约束条件常数项目标函数系数目标函数系数约束条件常数项––

m

个约束条件

n

个约束变量

n

个约束变量

m

个约束条件––约束条件是小于等于不等式

\leq

约束变量是大于等于

\geq 0

的约束条件是大于等于不等式

\geq

约束变量是小于等于

\leq 0

的约束条件是等式约束变量是自由变量 ( 没有约束 )––约束变量是大于等于

\geq 0

的约束条件是大于等于不等式

\geq

约束变量是小于等于

\leq 0

的约束条件是小于等于不等式

\leq

约束变量是自由变量 ( 没有约束 )约束条件是等式

记住一条 : 目标函数求最大值 ,

LP

约束条件与

DP

约束变量符号相反 ,

LP

约束变量与

DP

约束条件符号相同 ;

补一张图 , 方便记忆 :

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-07-31，如有侵权请联系 cloudcommunity@tencent.com 删除

dp

变量

函数

模型

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度