【运筹学】对偶理论 : 对偶性质 ( 对称性质 | 对称性质推导 )

韩曙亮

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

7940

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

文章目录

一、对称性质

对称性定理 :

原问题 (

LP

) 的对偶是对偶问题 (

DP

)

对偶问题 (

DP

) 的对偶是原问题 (

LP

)

原问题和对偶问题互为对偶 ;

对偶问题是对称的

原问题

LP

:

\begin{array}{lcl} maxZ = C X \\\\ s.t\begin{cases} AX \leq b \\\\ X \geq 0 \end{cases}\end{array}

对偶问题

DP

:

\begin{array}{lcl} minW = b^T Y \\\\ s.t\begin{cases} A^TY \geq C^T \\\\ Y \geq 0 \end{cases}\end{array}

二、对称性质推导

将上述对偶问题

DP

转为求最大值 ;

\begin{array}{lcl} minW = b^T Y \\\\ s.t\begin{cases} A^TY \geq C^T \\\\ Y \geq 0 \end{cases}\end{array}

转换过程 :

目标函数转为取最大值 : 转换后的结果如下 , 就是相当于在目标函数的左右两端乘以

-1

;

\begin{array}{lcl} maxZ = -b^T Y \\\\ s.t\begin{cases} A^TY \geq C^T \\\\ Y \geq 0 \end{cases}\end{array}

根据下面表格中的对偶问题写法 , 写出上述线性规划的对偶问题 :
- 目标函数由最大值转为最小值 ( 目标函数求最大值前提 ) :
min W = CX
LP
约束条件与
DP
约束变量符号相反 ( 目标函数求最大值前提 ) : 上述线性规划问题的约束条件是大于等于不等式 , 那么对应的约束变量小于等于
0
; 约束变量
X \leq 0
LP
约束变量与
DP
约束条件符号相同 ( 目标函数求最大值前提 ) : 上述线性规划问题的约束变量大于等于
0
, 那么对应的约束条件也是大于等于不等式 ; 约束条件是
AX \geq -b
- 最终得到的线性规划为 :

\begin{array}{lcl} min W = CX \\\\ s.t\begin{cases} AX \geq -b \\\\ X \leq 0 \end{cases}\end{array}

原问题 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

约束条件符号相同 ;

对如下线性规划作代换 :

\begin{array}{lcl} min W = CX \\\\ s.t\begin{cases} AX \geq -b \\\\ X \leq 0 \end{cases}\end{array}

代换内容 : 引入变量

X' = -X

, 使用

-X'

替换上述线性规划中的

X

;

目标函数 : 代换后为

minW = -CX'

, 此时两边乘以

-1

即可得到

maxZ = CX'

;

约束方程 : 代换后为

-AX' \geq -b

, 左右两边乘以

-1

即可得到

AX' \leq b

;

约束变量 : 代换后为

-X' \leq 0

, 左右变量乘以

-1

即可得到

X' \geq 0

最终代换结果为 :

\begin{array}{lcl} maxZ = CX' \\\\ s.t\begin{cases} AX' \leq b \\\\ X' \geq 0 \end{cases}\end{array}

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

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

dp

变量

表格

函数