【运筹学】对偶理论总结 ( 对称性质 | 弱对偶定理 | 最优性定理 | 强对偶性 | 互补松弛定理 ) ★★★

韩曙亮

发布于 2023-03-28 21:59:07

2.3K0

发布于 2023-03-28 21:59:07

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

文章目录

一、对偶问题的对称性质

参考博客 :

1、对称形式

1 . 对称形式特点 :

目标函数求最大值时 , 所有约束条件都是小于等于

\leq

符号 , 决策变量大于等于

;

目标函数求最小值时 , 所有约束条件都是大于等于

\geq

符号, 决策变量大于等于

;

2 . 原问题

的线性规划模型是 :

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

对称形式

要求 :

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

相关系数 :

目标函数系数是

约束方程系数是

约束方程常数是

3 . 对偶问题

的线性规划模型是 :

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

对偶问题

要求 :

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

相关系数 :

目标函数系数是

b^T

约束方程系数是

A^T

约束方程常数是

C^T

等价方法 ( 快速理解 ) :

生产 : 目标函数追求利润最大化 , 约束方程设备的使用时长受约束 , 小于等于某个时间值 ;
出租设备 : 目标函数追求租金最小化 , 约束方程设备产生的利润要大于等于生产的利润 , 不能亏钱 ;

2、对偶问题规律 ( 目标函数求最大值 )

对偶有以下规律 : 假设原问题

目标函数求最大值

maxZ

, 对偶问题

求最小值

minW

;

原问题

有

个约束条件 , 对应对偶问题

的

个约束变量 ;

原问题

有

个约束变量 , 对应对偶问题

的

个约束条件 ;

约束条件与约束变量的对应关系 ( 目标函数求最大值 ) : 这里特别注意 , 约束条件与约束变量大于小于符号是相反的 ;

如果原问题

中的约束条件是小于等于

\leq

不等式 , 那么对应的对偶问题

的约束变量就是大于等于

\geq 0

的 ;

如果原问题

中的约束条件是大于等于

\geq

不等式 , 那么对应的对偶问题

的约束变量就是小于等于

\leq 0

的 ;

如果原问题

中的约束条件是

等式 , 那么对应的对偶问题

的约束变量就是自由变量 , 即没有任何约束 ;

约束变量与约束条件的对应关系 ( 目标函数求最大值 ) : 这里特别注意 , 约束变量与约束条件大于小于符号是相同的 ;

如果原问题

中的约束变量就是大于等于

\geq 0

的 , 那么对应的对偶问题

的约束条件是大于等于

\geq

不等式 ;

如果原问题

中的约束变量就是小于等于

\leq 0

的 , 那么对应的对偶问题

的约束条件是小于等于

\leq

不等式 ;

如果原问题

中的约束变量就是自由变量 , 即没有任何约束 , 那么对应的对偶问题

的约束条件是

等式 ;

原问题 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 ≤
约束变量是自由变量 ( 没有约束 )	约束条件是等式

对偶问题

––目标函数求最大值

maxZ

目标函数求最小值

minW

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

个约束条件

个约束变量

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

\leq

约束变量是大于等于

\geq 0

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

\geq

约束变量是小于等于

\leq 0

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

\geq 0

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

\geq

约束变量是小于等于

\leq 0

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

\leq

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

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

约束条件与

约束变量符号相反 ,

约束变量与

约束条件符号相同 ;

补一张图 , 方便记忆 :

3、对偶问题实例

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

\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

, 可以将大于等于不等式转为小于等于不等式 ;

转换后的结果为 :

\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}

上图中的对偶问题线性规划 (

\rm DP

) 中的目标函数

y_3'

的系数应该是

, 这里在符号转换

y' = -y

时 , 将符合写错了 ;

二、弱对偶定理

参考博客 : 【运筹学】对偶理论 : 弱对偶性质 ( 弱对偶原理 | 弱对偶性 | 推论 1 | 推论 2 对偶问题的无界性 | 推论 3 )

弱对偶定理 :

假设

\rm X^0

和

\rm Y^0

分别是问题

\rm (P)

( 目标函数求最大值 ) 和问题

\rm (D)

( 目标函数求最小值 ) 的可行解 , 则必有

\rm CX^0 \leq Y^0 b

展开后为

\rm \sum_{j = 1}^n c_j x_j \leq \sum_{i = 1}^{m} y_i b_i

弱对偶定理推论 1 :

原问题任何一个可行解的目标函数值 , 都是其对偶问题目标函数值的下界 ;

反之 ,

对偶问题任何一个可行解的目标函数值 , 都是其原问题目标函数的上界 ;

弱对偶定理推论 2 : ( 对偶问题的无界性 )

在一对对偶问题

\rm (P)

和

\rm (D)

中 ,

如果其中一个线性规划问题可行 , 但是目标函数无界 , 则另外一个问题没有可行解 ;

如果其中一个线性规划问题不可行 , 其对偶问题不一定不可行 ;

弱对偶定理推论 3 :

在一对对偶问题

\rm (P)

和

\rm (D)

中 ,

如果其中一个线性规划问题可行 , 而另一个线性规划问题不可行 , 则该可行问题的目标函数是无界的;

三、最优性定理

最优性定理 :

如果

\rm X^0

是原问题的可行解 ,

\rm Y^0

是对偶问题的可行解 ,

并且两个可行解对应的目标函数值相等 , 即

\rm CX^0 = BY^0

, 即

\rm z = w

则

\rm X^0

是原问题的最优解 ,

\rm Y^0

是对偶问题的最优解 ;

两个互为对偶的线性规划问题 , 只要有一个有最优解 , 另一个也有最优解 ;

最优解首先是可行解 , 其次该可行解使目标函数达到最优 ( 最小值 / 最大值 ) ;

互为对偶的两个问题 :

原问题的目标函数求最大值 , 该值不断增大 , 处于一个界限值下方 ; 其最大值就是界限值 ;

对偶问题的目标函数求最小值 , 该值不断减小 , 处于一个界限值上方 ; 其最小值就是界限值 ;

当上述

\rm X^0

是原问题的可行解 ,

\rm Y^0

是对偶问题的可行解 ,

如果

\rm CX^0 = BY^0

, 则说明

\rm CX^0 = BY^0 = 界限值

, 当前的目标函数值就是界限值 ;

该界限值就是原问题目标函数的最大值 , 同时也是对偶问题目标函数的最小值 ;

四、强对偶性

强对偶性 : 如果原问题与对偶问题都有可行解 , 只要有一个问题有最优解 , 则两个问题都有最优解 , 二者的最优解的目标函数值相等 ;

五、互补松弛定理

1、定理内容

\rm X^0

和

\rm Y^0

分别是原问题

\rm P

问题和对偶问题

\rm D

的可行解 ,

这两个解各自都是对应线性规划问题的最优解

的充要条件是 :

\begin{cases} \rm Y^0 X_s = 0 \\\\ \rm Y_sX^0 = 0 \end{cases}

其中

\rm X_s , Y_s

是松弛变量或剩余变量 ;

2、示例 : 已知原问题最优解求对偶问题最优解

已知线性规划 :

\begin{array}{lcl} \rm maxZ = 3x_1 + 4x_2 + x_3 \\\\ \rm \begin{cases} \rm x_1 + 2x_2 + x_3 \leq 10 \\\\ \rm 2x_1 + 2x_2 + x_3 \leq 16 \\\\ \rm x_1,x_2, x_3 \geq 0 \end{cases}\end{array}

上述线性规划的最优解是

\rm X^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix}

, 求其对偶问题最优解 ;

3、方法一 : 单纯形法

方法一 : 写出上述线性规划的对偶问题 , 然后使用单纯形法求最优解 ,

首先写出对偶问题 , 然后转为标准形式 , 找单位阵作为基矩阵 , 然后得到基变量 , 假设非基变量为

求出基解 ,

在单纯形表中计算检验数 , 如果检验数都小于

就是最优解 , 如果检验数都大于

, 则不是最优解 ;

根据检验数确定出基变量 , 然后计算出入基变量 , 进行下一次迭代 ;

方程组同解变换, 构造单位阵 , 然后计算检验数 , 继续按照上述方法进行迭代 ;

该方法比较麻烦 ;

4、方法二 : 使用互补松弛定理公式一求解

方法二 : 利用互补松弛定理计算 ;

写出原问题的对偶问题 :

\begin{array}{lcl} \rm minW = 10y_1 + 16y_2 \\\\ \rm \begin{cases} \rm y_1 + 2y_2 \geq 3 \\\\ \rm 2y_1 + 2y_2 \geq 4 \\\\ \rm y_1 + y_2 \geq 1 \\\\ \rm y_1,y_2 \geq 0 \end{cases}\end{array}

给对偶问题的约束方程添加剩余变量 :

\begin{cases} \rm y_1 + 2y_2 - y_3 = 3 \\\\ \rm 2y_1 + 2y_2 - y_4 = 4 \\\\ \rm y_1 + y_2 - y_5 = 1 \\\\ \rm y_1,y_2, y_3 , y _4, y_5 \geq 0 \end{cases}

互补松弛定理 :

\rm X^0

和

\rm Y^0

分别是原问题

\rm P

问题和对偶问题

\rm D

的最优解 "

\Leftrightarrow

\begin{cases} \rm Y^0 X_s = 0 \\\\ \rm Y_sX^0 = 0 \end{cases}

其中

\rm X_s , Y_s

是松弛变量或剩余变量 ;

原问题

\rm P

线性规划最优解是

\rm X^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix}

对偶问题的剩余变量是

\rm Y_s= \begin{pmatrix} \quad \rm y_3 \quad \\\\ \quad \rm y_4 \quad \\\\ \quad \rm y_5 \quad \\ \end{pmatrix}

互补松弛定理中

\rm Y_sX^0 = 0

, 将上述

\rm X^0

和

\rm Y_s

代入上述式子得到 :

\rm Y_sX^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix} \times \begin{pmatrix} \quad \rm y_3 \quad \\\\ \quad \rm y_4 \quad \\\\ \quad \rm y_5 \quad \\ \end{pmatrix} = 6y_3 + 2y_4 + 0y_5 = 6y_3 + 2y_4 =0

已知

\rm y_3, y_4 \geq 0

, 上述

\rm 6y_3 + 2y_4 = 0

, 因此

\rm y_3 = 0 , y_4 = 0

;

将

\rm y_3 = 0 , y_4 = 0

代入到约束方程

\begin{cases} \rm y_1 + 2y_2 - y_3 = 3 \\\\ \rm 2y_1 + 2y_2 - y_4 = 4 \\\\ \rm y_1 + y_2 - y_5 = 1 \\\\ \rm y_1,y_2, y_3 , y _4, y_5 \geq 0 \end{cases}

中 ;

得到

\begin{cases} \rm y_1 + 2y_2 = 3 \\\\ \rm 2y_1 + 2y_2 = 4 \end{cases}

, 解上述方程 ,

① 变换 :

\begin{cases} \rm 2y_1 + 4y_2 = 6 \\\\ \rm 2y_1 + 2y_2 = 4 \end{cases}

② 求解 :

\begin{cases} \rm y_1 = 1 \\\\ \rm y_2 = 1 \end{cases}

上述求出的值就是最优解 , 即

\rm Y^0 = \begin{pmatrix} \quad \rm 1 \quad 1 \quad \end{pmatrix}

;

5、互补松弛定理示例分析

互补松弛定理 :

\rm X^0

和

\rm Y^0

分别是原问题

\rm P

问题和对偶问题

\rm D

的最优解 "

\Leftrightarrow

\begin{cases} \rm Y^0 X_s = 0 \\\\ \rm Y_sX^0 = 0 \end{cases}

其中

\rm X_s , Y_s

是松弛变量或剩余变量 ;

原问题

\rm P

线性规划最优解是

\rm X^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix}

对偶问题的剩余变量是

\rm Y_s= \begin{pmatrix} \quad \rm y_3 \quad \\\\ \quad \rm y_4 \quad \\\\ \quad \rm y_5 \quad \\ \end{pmatrix}

最优解中不等于

的 , 对应的剩余变量中对应的一定为

如果最优解中等于

, 那么剩余变量中的对应的值就不确定了 ;

6、互补松弛定理示例2

已知原问题最优解求对偶问题最优解 , 已知线性规划 :

\begin{array}{lcl} \rm minW= 2x_1 - x_2 + 2x_3 \\\\ \rm \begin{cases} \rm -x_1 + x_2 + x_3 = 4 \\\\ \rm -x_1 + x_2 - x_3 \leq 6 \\\\ \rm x_1 \leq 0 ,x_2 \geq 0 , x_3 无约束 \end{cases}\end{array}

上述线性规划的对偶问题的最优解是

\rm Y^0 = \begin{pmatrix} \quad \rm 0 \quad \rm -2 \quad \end{pmatrix}

, 求其原问题最优解 ;

互补松弛定理 :

\rm X^0

和

\rm Y^0

分别是原问题

\rm P

问题和对偶问题

\rm D

的最优解 "

\Leftrightarrow

\begin{cases} \rm Y^0 X_s = 0 \\\\ \rm Y_sX^0 = 0 \end{cases}

其中

\rm X_s , Y_s

是松弛变量或剩余变量 ;

分析 :

给出了对偶问题最优解

\rm Y^0 = \begin{pmatrix} \quad \rm 0 \quad \rm -2 \quad \end{pmatrix}

, 其互补松弛定理中对应原问题的松弛变量

\rm X_s =\begin{pmatrix} \quad \rm x_4 \quad \\\\ \quad \rm x_5 \quad \end{pmatrix}

;

根据公式有

\rm \begin{pmatrix} \quad \rm 0 \quad \rm -2 \quad \end{pmatrix} \times \begin{pmatrix} \quad \rm x_4 \quad \\\\ \quad \rm x_5 \quad \end{pmatrix} = 0

\rm 0 x_4 - 2x_5= 0

\rm - 2x_5= 0

原问题添加松弛变量 ,

\rm -x_1 + x_2 + x_3 = 4

已经是等式了 , 添加一个

\rm x_4

松弛变量 ,

\rm x_4 = 0

\rm -x_1 + x_2 - x_3 \leq 6

添加松弛变量

\rm x_5

, 由于对应的最优解不为

, 是

-2

, 其对应的松弛变量还是

, 即

x_5 = 0

;

原问题的最优解满足

\begin{cases} \rm -x_1 + x_2 + x_3 = 4 \\\\ \rm -x_1 + x_2 - x_3 = 6 \end{cases}

方程 , 该方程组

个等式 ,

个变量 , 如果再得到一个方程 , 就可以得到三个方程 ;

根据对偶理论中的 强对偶性 , 如果原问题与对偶问题都有可行解 , 只要有一个问题有最优解 , 则两个问题都有最优解 , 二者的最优解的目标函数值相等 ;

这里求一下对偶问题的目标函数值 , 对偶问题的目标函数与原问题的目标函数值相等 ;

对偶问题的目标函数是

\rm max Z = 4y_1 + 6y_2 = 4 \times 0 - 2 \times 6 = -12

;

因此原问题的目标函数值也是

, 得到式子

\rm minW= 2x_1 - x_2 + 2x_3 = -12

;

这里就得到了

个方程组 ,

个变量 , 求解下面的方程组 , 最终结果就是最优解 ;

\begin{cases} \rm -x_1 + x_2 + x_3 = 4 \ \ ① \\\\ \rm -x_1 + x_2 - x_3 = 6 \ \ ② \\\\ 2x_1 - x_2 + 2x_3 = -12 \ \ ③ \end{cases}

最终方程组的解是 :

\begin{cases} \rm x_1 = -5 \\\\ \rm x_2 = 0 \\\\ x_3 = -1 \end{cases}

最终的原方程的最优解是

\begin{pmatrix} \quad \rm -5 \quad 0 \quad \rm -1 \quad \end{pmatrix}

目标函数值是

-12

7、互补松弛定理求最优解思路

给定线性规划 , 给定一个问题的最优解 , 求另一个问题的最优解 ;

互补松弛定理 :

\rm X^0

和

\rm Y^0

分别是原问题

\rm P

问题和对偶问题

\rm D

的最优解 "

\Leftrightarrow

\begin{cases} \rm Y^0 X_s = 0 \\\\ \rm Y_sX^0 = 0 \end{cases}

其中

\rm X_s , Y_s

是松弛变量或剩余变量 ;

使用上述互补松弛定理 , 求出给定的最优解对应的对偶问题线性规划松弛变量的值 ;

将松弛变量代入到约束方程等式中 , 求解出的值就是线性规划问题的最优解 ;

还有一种方式 , 就是根据给定的最优解 , 求出本问题线性规划的松弛变量值 ,

根据本问题的松弛变量值求对应对偶问题的最优解 ;

六、原问题与对偶问题对应关系

原问题与对偶问题对应关系 :

如果原问题有最优解 , 对偶问题也有最优解 ;

如果原问题有无界解 , 对偶问题无可行解 ;

如果原问题无可行解 , 对偶问题无法判断 ;

上述是根据弱对偶定理总结的 ;

七、对偶理论的相关结论

1、对偶问题存在

任何线性规划问题 , 都有一个对应的对偶线性规划问题 ;

2、对偶问题转化

原问题

\rm P

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

;

\ \ \ \ \ \ \ \ \ \ \,

对偶问题

\rm D

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

原问题与对偶问题对应关系 :

原问题第

个约束条件是

\leq

约束 , 其对偶问题的第

个变量的符号不确定 , 可能大于等于

, 也可能小于等于

;

查看约束变量的符号与其另外一个对偶问题的约束方程的符号一致性 , 来确定对偶问题的约束方程符号 ;

约束方程符号 :

如果当前线性规划问题目标函数是求最大值 , 原问题就是上面的问题 , 其对偶问题 ( 下面的 ) 的约束方程符号是

\geq

, 因此对偶问题的约束方程符号与原问题变量符号一致 ;

如果当前线性规划问题目标函数是求最小值 , 原问题就是下面的问题 , 其对偶问题 ( 上面的 ) 的约束方程符号是

\leq

, 因此对偶问题的约束方程符号与原问题变量符号相反 ;

变量符号 :

如果当前线性规划问题目标函数是求最大值 , 原问题就是上面的问题 , 其对偶问题 ( 下面的 ) 的约束方程符号是

\geq

, 因此对偶问题的变量符号与原问题约束方程符号符号相反 ;

如果当前线性规划问题目标函数是求最大值 , 原问题就是上面的问题 , 其对偶问题 ( 下面的 ) 的约束方程符号是

\geq

, 因此对偶问题的变量符号与原问题约束方程符号符号一致 ;

3、对偶问题的解

① 互为对偶的两个问题 , 或者同时都有最优解 , 或者同时都没有最优解 ;

② 对偶问题有可行解 , 原问题不一定有可行解 , 因为对偶问题的可行解可能是无界解 , 原问题可能无可行解 ;

③ 原问题有多重解 , 对偶问题可能有多重解 , 也可能有唯一解 ; 多重解是有无穷多最优解 ;

④ 对偶问题有可行解 , 原问题无可行解 , 则对偶问题有无界解 ; 一对问题中 , 一个有可行解 , 一个无可行解 , 则有可行解的是无界解 ;

⑤ 原问题没有最优解 , 对偶问题无法判断 ; 没有最优解有两种情况 , 一种是无界解 , 一种是无可行解 ; 如果原问题有无界解 , 则对偶问题无可行解 ; 如果原问题无可行解 , 则对偶问题无可行解 ;

⑥ 如果对偶问题没有可行解 , 对偶问题无法判断 , 无界解或无可行解两种情况都有可能 ;

⑦ 如果原问题与对偶问题都有可行解 , 则都有最优解 ;

如果原问题有最优解 , 对偶问题也有最优解 ;

如果原问题有无界解 , 对偶问题无可行解 ;

如果原问题无可行解 , 对偶问题无法判断 ;

4、互补松弛定理

如果

\rm X^0

和

\rm Y^0

分别是原问题与对偶问题的最优解 , 则

\rm Y^0 X_s = Y_sX^0 = 0

;

\rm X^0

和

\rm Y^0

分别是原问题

\rm P

问题和对偶问题

\rm D

的最优解 "

\Leftrightarrow

\begin{cases} \rm Y^0 X_s = 0 \\\\ \rm Y_sX^0 = 0 \end{cases}

其中

\rm X_s , Y_s

是松弛变量或剩余变量 ;

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

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

变量

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

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

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