-
2020-12-30 19:57:12
一、弱对偶性质
弱对偶定理 :
假设 X 0 \rm X^0 X0 和 Y 0 \rm Y^0 Y0 分别是 问题 ( P ) \rm (P) (P) ( 目标函数求最大值 ) 和 问题 ( D ) \rm (D) (D) ( 目标函数求最小值 ) 的 可行解 , 则必有 C X 0 ≤ Y 0 b \rm CX^0 \leq Y^0 b CX0≤Y0b ,
展开后为 ∑ j = 1 n c j x j ≤ ∑ i = 1 m y i b i \rm \sum_{j = 1}^n c_j x_j \leq \sum_{i = 1}^{m} y_i b_i ∑j=1ncjxj≤∑i=1myibi
二、弱对偶定理分析
弱对偶定理分析 :
问题 ( P ) \rm (P) (P) 与 问题 ( D ) \rm (D) (D) 互为对偶 , 其中
问题 ( P ) \rm (P) (P) 是 原问题 , 目标函数求 最大值 ,
问题 ( D ) \rm (D) (D) 是 对偶问题 , 目标函数求 最小值 ;
C X 0 \rm CX^0 CX0 是 原问题 ( P ) \rm (P) (P) 目标函数 代入 X 0 \rm X^0 X0 可行解之后的值 ; 计算出一个具体的数值 ;
Y 0 b \rm Y^0b Y0b 是 对偶问题 ( D ) \rm (D) (D) 目标函数 代入 Y 0 \rm Y^0 Y0 可行解之后的值 ; 计算出一个具体的数值 ;
只要互为对偶的两个问题都有可行解 , 目标函数求最大值的 C X 0 \rm CX^0 CX0 值 ( 原问题 ) , 一定小于等于 , 目标函数求最小值的 Y 0 b \rm Y^0b Y0b 值 ( 对偶问题 ) ;
如果互为对偶的两个问题都有可行解 , 原问题求最大值 , 对偶问题求最小值 ,
求最大值的原问题一定都 在某个界限值之下 ,
求最小值的对偶问题一定都 在某个界限之上 ,
上述描述中的 界限值是同一个界限值 ;
三、弱对偶定理推论 1
弱对偶定理推论 1 :
原问题 任何一个 可行解 的目标函数值 , 都是其对偶问题 目标函数值的下界 ;
反之 ,
对偶问题 任何一个 可行解 的目标函数值 , 都是其原问题 目标函数的上界 ;
问题 ( P ) \rm (P) (P) 与 问题 ( D ) \rm (D) (D) 互为对偶 , 其中
问题 ( P ) \rm (P) (P) 是 原问题 , 目标函数求 最大值 ,
问题 ( D ) \rm (D) (D) 是 对偶问题 , 目标函数求 最小值 ;
C X 0 \rm CX^0 CX0 是 原问题 ( P ) \rm (P) (P) 目标函数 代入 X 0 \rm X^0 X0 可行解之后的值 , 该值是其对偶问题目标函数值的下界 ;
Y 0 b \rm Y^0b Y0b 是 对偶问题 ( D ) \rm (D) (D) 目标函数 代入 Y 0 \rm Y^0 Y0 可行解之后的值 , 该值是其原问题目标函数值的上界 ;
四、弱对偶定理推论 2 对偶问题的无界性
弱对偶定理推论 2 : ( 对偶问题的无界性 )
在一对 对偶问题 ( P ) \rm (P) (P) 和 ( D ) \rm (D) (D) 中 ,
如果其中 一个线性规划问题可行 , 但是 目标函数无界 , 则 另外一个问题没有可行解 ;
如果其中 一个线性规划问题不可行 , 其 对偶问题不一定不可行 ;
弱对偶定理推论 2 ( 对偶问题的无界性 ) 解析 :
如果目标函数求最小值的问题无界 , 则 取值一直可以减小 , 此时不存在一个界限值 ,
因此其对偶问题 一定没有可行解 ;
只要该问题有可行解 , 将可行解代入目标函数 , 即可获得一个 界限值 ;
这个界限值一定是另外对应对偶问题的可行解 ;
如果目标函数求最大值的问题无界 , 则 取值一直可以增大 , 此时不存在一个界限值 ,
因此其对偶问题 一定没有可行解 ;
只要该问题有可行解 , 将可行解代入目标函数 , 即可获得一个 界限值 ;
这个界限值一定是另外对应对偶问题的可行解 ;
一个线性规划是不可行的 , 其对偶问题不一定不可行 ;
一个线性规划不可行 , 其对偶问题可能有如下情况 :
-
①
有最优解( 不会成立 ) , 根据最优性定理 , 一个有最优解 , 另一个也有最优解 ; -
② 无界解
-
③ 无可行解
原问题 与 对偶问题 ,
一个无界 , 另一个肯定不可行 ;
一个不可行 , 另一个不一定可行 , 有两种情况 ① 无界解 ② 无可行解 ;
五、弱对偶定理推论 3
弱对偶定理推论 3 :
在一对 对偶问题 ( P ) \rm (P) (P) 和 ( D ) \rm (D) (D) 中 ,
如果其中 一个线性规划问题可行 , 而 另一个线性规划问题不可行 , 则 该可行问题的目标函数是无界的;
更多相关内容 -
-
基于matlab的yalmip+cplex的IEEE33的SOCP原对偶问题
2021-12-05 19:37:37文件夹1是最基本的原对偶问题,只有包含支路潮流约束 文件夹2是包含储能的原对偶问题,去除了储能的时间耦合约束,使用我自己的方法进行推导,虽然复杂但是可以解决问题,理解了我的这个做法,也就掌握了对偶的使用... -
基于Matlab的对偶问题最优解探讨.pdf
2021-06-27 12:17:50基于Matlab的对偶问题最优解探讨.pdf -
单纯形算法及对偶的python实现
2020-12-21 05:04:16将线性规划问题转化为标准型,求minz转化为求max-z 以下图为例 初始化 import numpy as np class Simplex(object): #构造函数(初始化函数) def __init__(self,z,B,bound): self.X_count=len(z) #变量个数 ... -
对偶理论 : 对称理论示例 ( 对称理论 | 标准的原问题对偶问题 | 原问题目标函数求最小值示例 | 求对偶技巧 ...
2020-12-31 22:47:27一、对称理论、 二、对偶理论示例、 三、对偶理论示例 2、 四、求对偶技巧 ★★、
一、对称理论
参考 【运筹学】对偶理论 : 对称形式 ( 对称形式 | 对偶模型转化实例 | 对偶问题规律分析 ) 写出原问题线性规划的对偶问题线性规划 ,
原问题的线性规划模型 : 注意原问题的线性规划 目标函数求最大值 , 约束方程都是 小于等于不等式 ;
m a x Z = C X s . t { A X ≤ b X ≥ 0 \begin{array}{lcl} \rm maxZ = C X \\\\ \rm s.t\begin{cases} \rm AX \leq b \\\\ \rm X \geq 0 \end{cases}\end{array} maxZ=CXs.t⎩⎪⎨⎪⎧AX≤bX≥0
如果原问题是求最大值 , 约束方程有大于等于不等式 , 需要在这些大于等于不等式 左右两边乘以 − 1 \rm -1 −1 , 将 大于等于不等式 转为 小于等于不等式 ;
如果进行了上述操作 , 则最终求出对偶问题后 , 系数矩阵肯定不互为转置矩阵 , 还要进行一次代换 , 令 y ′ = − y \rm y' = -y y′=−y 吗使用 − y ′ = y \rm -y' = y −y′=y 替换对偶问题中的变量 ;
对偶问题的线性规划模型 : 对偶问题 目标函数求最小值 , 约束方程都是 大于等于不等式 ;
m i n W = b T Y s . t { A T Y ≥ C T Y ≥ 0 \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} minW=bTYs.t⎩⎪⎨⎪⎧ATY≥CTY≥0
矩阵转置 : 第 1 1 1 列变第 1 1 1 行 , ⋯ \cdots ⋯ , 第 n \rm n n 列变第 n \rm n n 行 ;
二、对偶理论示例
对偶示例 : 给出如下线性规划 ,
m a x Z = 2 x 1 + x 2 s . t { x 1 − 2 x 2 ≤ 8 x 1 , x 2 ≥ 0 \begin{array}{lcl} \rm maxZ = 2 x_1 + x_2 \\\\ \rm s.t\begin{cases} \rm x_1 - 2x_2 \leq 8 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array} maxZ=2x1+x2s.t⎩⎪⎨⎪⎧x1−2x2≤8x1,x2≥0
上述线性规划原问题 ① 目标函数求最大值 ② 约束方程是小于等于不等式 , ③ 约束变量大于等于 0 0 0 , 符合标准 ;
写出其对偶问题 :
( 1 ) 目标函数求最小 , 且目标函数的系数是原方程的约束方程常数 ;
m i n Z = 8 y 1 \rm minZ = 8y_1 minZ=8y1
( 2 ) 约束条件 :
对偶问题约束方程系数 : 约束方程矩阵是 ( 1 − 2 ) \begin{pmatrix} &1 & -2 & \\ \end{pmatrix} (1−2) 的转置矩阵 ( 1 − 2 ) \begin{pmatrix} &1 & \\ &-2 & \\ \end{pmatrix} (1−2) ;
对偶问题变量个数 : 约束方程的变量个数是矩阵的列数 , 这里只有 1 1 1 列 , 则只有 1 1 1 个变量 y 1 \rm y_1 y1 ;
约束方程中间符号 : 约束条件的符号是由 原问题 变量符号决定 ( 都是 ≥ 0 \geq 0 ≥0 ) , 因此对偶问题的约束方程符号也是 ≥ \geq ≥ ;
约束方程右侧常数 : 是原问题目标函数的系数转置 , 分别是 2 , 1 2 , 1 2,1 ;
变量符号 : 对偶问题变量符号与原问题约束方程符号相反 ; 原问题约束方程是小于等于符号 , 对偶问题的变量是大于等于 0 0 0 的 ;
最终的对偶问题是 :
m i n W = 8 y 1 s . t { y 1 ≥ 2 − 2 y 1 ≥ 1 y 1 ≥ 0 \begin{array}{lcl} \rm minW = 8y_1 \\\\ \rm s.t\begin{cases} \rm y_1 \geq 2 \\\\ \rm -2y_1 \geq 1 \\\\ \rm y_1 \geq 0 \end{cases}\end{array} minW=8y1s.t⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧y1≥2−2y1≥1y1≥0
三、对偶理论示例 2
如果给出的原问题目标函数是求最小值 :
m i n Z = 2 x 1 + x 2 s . t { x 1 − 2 x 2 ≤ 8 x 1 , x 2 ≥ 0 \begin{array}{lcl} \rm minZ = 2 x_1 + x_2 \\\\ \rm s.t\begin{cases} \rm x_1 - 2x_2 \leq 8 \\\\ \rm x_1, x_2 \geq 0 \end{cases}\end{array} minZ=2x1+x2s.t⎩⎪⎨⎪⎧x1−2x2≤8x1,x2≥0
上述线性规划的对偶问题的目标函数是求最大值 ;
参考下图列表 :
写出其对偶问题 ( 上述表格中的右侧 ) :
( 1 ) 目标函数求最大 , 且目标函数的系数是原方程的约束方程常数 ;
m i n W = 8 y 1 \rm minW = 8y_1 minW=8y1
( 2 ) 约束条件 :
对偶问题约束方程系数 : 约束方程矩阵是 ( 1 − 2 ) \begin{pmatrix} &1 & -2 & \\ \end{pmatrix} (1−2) 的转置矩阵 ( 1 − 2 ) \begin{pmatrix} &1 & \\ &-2 & \\ \end{pmatrix} (1−2) ;
对偶问题变量个数 : 约束方程的变量个数是矩阵的列数 , 这里只有 1 1 1 列 , 则只有 1 1 1 个变量 y 1 \rm y_1 y1 ;
约束方程中间符号 : 约束条件的符号是由 原问题 变量符号决定 ( 都是 ≥ 0 \geq 0 ≥0 ) , 这里如果目标函数求最小值时原问题 , 其对偶问题约束方程符号 与 原问题变量符号相反 , 因此对偶问题的约束方程符号也是 ≤ \leq ≤ ;
约束方程右侧常数 : 是原问题目标函数的系数转置 , 分别是 2 , 1 2 , 1 2,1 ;
变量符号 : 对偶问题变量符号与原问题约束方程符号相同 ; 原问题约束方程是小于等于符号 , 对偶问题的变量是小于等于 0 0 0 的 ;
最终的对偶问题是 :
m a x Z = 8 y 1 s . t { y 1 ≤ 2 − 2 y 1 ≤ 1 y 1 ≤ 0 \begin{array}{lcl} \rm maxZ = 8y_1 \\\\ \rm s.t\begin{cases} \rm y_1 \leq 2 \\\\ \rm -2y_1 \leq 1 \\\\ \rm y_1 \leq 0 \end{cases}\end{array} maxZ=8y1s.t⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧y1≤2−2y1≤1y1≤0
四、求对偶技巧 ★★
写出对偶定理的标准对称形式 ★ : 记住下面的标准形式
原问题 :
m a x Z = C X s . t { A X ≤ b X ≥ 0 \begin{array}{lcl} \rm maxZ = C X \\\\ \rm s.t\begin{cases} \rm AX \leq b \\\\ \rm X \geq 0 \end{cases}\end{array} maxZ=CXs.t⎩⎪⎨⎪⎧AX≤bX≥0
对偶问题 :
m i n W = b T Y s . t { A T Y ≥ C T Y ≥ 0 \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} minW=bTYs.t⎩⎪⎨⎪⎧ATY≥CTY≥0
查看 约束变量的符号 与 其另外一个对偶问题的 约束方程的符号 一致性 , 来确定对偶问题的约束方程符号 ;
约束方程符号 :
如果当前线性规划问题 目标函数是求最大值 , 原问题就是上面的问题 , 其对偶问题 ( 下面的 ) 的约束方程符号是 ≥ \geq ≥ , 因此 对偶问题的约束方程符号 与 原问题变量 符号一致 ;
如果当前线性规划问题 目标函数是求最小值 , 原问题就是下面的问题 , 其对偶问题 ( 上面的 ) 的约束方程符号是 ≤ \leq ≤ , 因此 对偶问题的约束方程符号 与 原问题变量 符号相反 ;
变量符号 :
如果当前线性规划问题 目标函数是求最大值 , 原问题就是上面的问题 , 其对偶问题 ( 下面的 ) 的约束方程符号是 ≥ \geq ≥ , 因此 对偶问题的变量符号 与 原问题约束方程符号 符号相反 ;
如果当前线性规划问题 目标函数是求最大值 , 原问题就是上面的问题 , 其对偶问题 ( 下面的 ) 的约束方程符号是 ≥ \geq ≥ , 因此 对偶问题的变量符号 与 原问题约束方程符号 符号一致 ;
-
SDPSlover_大规模SDP求解器(原始对偶内点法)
2021-09-11 06:32:06大规模SDP求解器,基于SDPT3实现文档,全部MATLAB实现,没有底层c语言库 -
【运筹学】对偶理论 : 互补松弛定理应用 ( 原问题与对偶问题标准形式 | 已知原问题最优解求对偶问题最优解 ...
2021-01-02 13:48:53一、原问题与对偶问题标准形式、 ...三、已知原问题最优解求对偶问题最优解、 四、使用单纯形法求解、 五、使用互补松弛定理公式一求解、 六、使用互补松弛定理公式二求解 ( 无效方法 )、 七、总结
一、原问题与对偶问题标准形式
原问题 P \rm P P : m a x Z = C X s . t { A X ≤ b X ≥ 0 \begin{array}{lcl} \rm maxZ = C X \\\\ \rm s.t\begin{cases} \rm AX \leq b \\\\ \rm X \geq 0 \end{cases}\end{array} maxZ=CXs.t⎩⎪⎨⎪⎧AX≤bX≥0 ; \ \ \ \ \ \ \ \ \ \ \, 对偶问题 D \rm D D : m i n W = b T Y s . t { A T Y ≥ C T Y ≥ 0 \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} minW=bTYs.t⎩⎪⎨⎪⎧ATY≥CTY≥0
等价方法 :
- 生产 : 目标函数追求 利润最大化 , 约束方程设备的使用时长受约束 , 小于等于 某个时间值 ;
- 出租设备 : 目标函数追求 租金最小化 , 约束方程设备产生的利润要 大于等于 生产的利润 , 不能亏钱 ;
二、互补松弛定理
X 0 \rm X^0 X0 和 Y 0 \rm Y^0 Y0 分别是 原问题 P \rm P P 问题 和 对偶问题 D \rm D D 的 可行解 ,
这两个解各自都是对应 线性规划问题 的 最优解
的 充要条件是 : { Y 0 X s = 0 Y s X 0 = 0 \begin{cases} \rm Y^0 X_s = 0 \\\\ \rm Y_sX^0 = 0 \end{cases} ⎩⎪⎨⎪⎧Y0Xs=0YsX0=0
其中 X s , Y s \rm X_s , Y_s Xs,Ys 是 松弛变量 或 剩余变量 ;
三、已知原问题最优解求对偶问题最优解
已知线性规划 :
m a x Z = 3 x 1 + 4 x 2 + x 3 { x 1 + 2 x 2 + x 3 ≤ 10 2 x 1 + 2 x 2 + x 3 ≤ 16 x 1 , x 2 , x 3 ≥ 0 \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} maxZ=3x1+4x2+x3⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧x1+2x2+x3≤102x1+2x2+x3≤16x1,x2,x3≥0
上述线性规划的最优解是 X 0 = ( 6 2 0 ) \rm X^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix} X0=(620) , 求其对偶问题最优解 ;
四、使用单纯形法求解
方法一 : 写出上述线性规划的对偶问题 , 然后使用单纯形法求最优解 ,
首先写出 对偶问题 , 然后转为 标准形式 , 找 单位阵 作为基矩阵 , 然后得到基变量 , 假设非基变量为 0 0 0 求出 基解 ,
在单纯形表中计算 检验数 , 如果 检验数都小于 0 0 0 就是最优解 , 如果检验数都大于 0 0 0 , 则不是最优解 ;
根据检验数确定 出基变量 , 然后计算出 入基变量 , 进行下一次迭代 ;
方程组 同解变换, 构造单位阵 , 然后计算检验数 , 继续按照上述方法进行迭代 ;
该方法比较麻烦 ;
五、使用互补松弛定理公式一求解
方法二 : 利用 互补松弛定理 计算 ;
写出原问题的对偶问题 :
m i n W = 10 y 1 + 16 y 2 { y 1 + 2 y 2 ≥ 3 2 y 1 + 2 y 2 ≥ 4 y 1 + y 2 ≥ 1 y 1 , y 2 ≥ 0 \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} minW=10y1+16y2⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧y1+2y2≥32y1+2y2≥4y1+y2≥1y1,y2≥0
给对偶问题的约束方程添加剩余变量 :
{ y 1 + 2 y 2 − y 3 = 3 2 y 1 + 2 y 2 − y 4 = 4 y 1 + y 2 − y 5 = 1 y 1 , y 2 , y 3 , y 4 , y 5 ≥ 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} ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧y1+2y2−y3=32y1+2y2−y4=4y1+y2−y5=1y1,y2,y3,y4,y5≥0
互补松弛定理 :
" X 0 \rm X^0 X0 和 Y 0 \rm Y^0 Y0 分别是 原问题 P \rm P P 问题 和 对偶问题 D \rm D D 的 最优解 " ⇔ \Leftrightarrow ⇔ { Y 0 X s = 0 Y s X 0 = 0 \begin{cases} \rm Y^0 X_s = 0 \\\\ \rm Y_sX^0 = 0 \end{cases} ⎩⎪⎨⎪⎧Y0Xs=0YsX0=0
其中 X s , Y s \rm X_s , Y_s Xs,Ys 是 松弛变量 或 剩余变量 ;
原问题 P \rm P P 线性规划最优解是 X 0 = ( 6 2 0 ) \rm X^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix} X0=(620) ,
对偶问题的剩余变量是 Y s = ( y 3 y 4 y 5 ) \rm Y_s= \begin{pmatrix} \quad \rm y_3 \quad \\\\ \quad \rm y_4 \quad \\\\ \quad \rm y_5 \quad \\ \end{pmatrix} Ys=⎝⎜⎜⎜⎜⎛y3y4y5⎠⎟⎟⎟⎟⎞
互补松弛定理中 Y s X 0 = 0 \rm Y_sX^0 = 0 YsX0=0 , 将上述 X 0 \rm X^0 X0 和 Y s \rm Y_s Ys 代入上述式子得到 :
Y s X 0 = ( 6 2 0 ) × ( y 3 y 4 y 5 ) = 6 y 3 + 2 y 4 + 0 y 5 = 6 y 3 + 2 y 4 = 0 \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 YsX0=(620)×⎝⎜⎜⎜⎜⎛y3y4y5⎠⎟⎟⎟⎟⎞=6y3+2y4+0y5=6y3+2y4=0
已知 y 3 , y 4 ≥ 0 \rm y_3, y_4 \geq 0 y3,y4≥0 , 上述 6 y 3 + 2 y 4 = 0 \rm 6y_3 + 2y_4 = 0 6y3+2y4=0 , 因此 y 3 = 0 , y 4 = 0 \rm y_3 = 0 , y_4 = 0 y3=0,y4=0 ;
将 y 3 = 0 , y 4 = 0 \rm y_3 = 0 , y_4 = 0 y3=0,y4=0 代入到约束方程 { y 1 + 2 y 2 − y 3 = 3 2 y 1 + 2 y 2 − y 4 = 4 y 1 + y 2 − y 5 = 1 y 1 , y 2 , y 3 , y 4 , y 5 ≥ 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} ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧y1+2y2−y3=32y1+2y2−y4=4y1+y2−y5=1y1,y2,y3,y4,y5≥0 中 ;
得到 { y 1 + 2 y 2 = 3 2 y 1 + 2 y 2 = 4 \begin{cases} \rm y_1 + 2y_2 = 3 \\\\ \rm 2y_1 + 2y_2 = 4 \end{cases} ⎩⎪⎨⎪⎧y1+2y2=32y1+2y2=4 , 解上述方程 ,
① 变换 : { 2 y 1 + 4 y 2 = 6 2 y 1 + 2 y 2 = 4 \begin{cases} \rm 2y_1 + 4y_2 = 6 \\\\ \rm 2y_1 + 2y_2 = 4 \end{cases} ⎩⎪⎨⎪⎧2y1+4y2=62y1+2y2=4
② 求解 : { y 1 = 1 y 2 = 1 \begin{cases} \rm y_1 = 1 \\\\ \rm y_2 = 1 \end{cases} ⎩⎪⎨⎪⎧y1=1y2=1
上述求出的值就是最优解 , 即 Y 0 = ( 1 1 ) \rm Y^0 = \begin{pmatrix} \quad \rm 1 \quad 1 \quad \end{pmatrix} Y0=(11) ;
六、使用互补松弛定理公式二求解 ( 无效方法 )
方法三 : 利用 互补松弛定理 计算 ;
互补松弛定理 :
" X 0 \rm X^0 X0 和 Y 0 \rm Y^0 Y0 分别是 原问题 P \rm P P 问题 和 对偶问题 D \rm D D 的 最优解 " ⇔ \Leftrightarrow ⇔ { Y 0 X s = 0 Y s X 0 = 0 \begin{cases} \rm Y^0 X_s = 0 \\\\ \rm Y_sX^0 = 0 \end{cases} ⎩⎪⎨⎪⎧Y0Xs=0YsX0=0
其中 X s , Y s \rm X_s , Y_s Xs,Ys 是 松弛变量 或 剩余变量 ;
上面 " 五、使用互补松弛定理公式一求解 " 小节 使用的是 Y s X 0 = 0 \rm Y_sX^0 = 0 YsX0=0 公式进行求解 , 在本小节中使用 Y 0 X s = 0 \rm Y^0 X_s = 0 Y0Xs=0 公式进行求解 ;
原问题 P \rm P P 线性规划最优解是 X 0 = ( 6 2 0 ) \rm X^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix} X0=(620) , 将该最优解代入原问题的约束条件中 , 求出原问题的约束变量 X s \rm X_s Xs ;
原问题 :
m a x Z = 3 x 1 + 4 x 2 + x 3 { x 1 + 2 x 2 + x 3 ≤ 10 2 x 1 + 2 x 2 + x 3 ≤ 16 x 1 , x 2 , x 3 ≥ 0 \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} maxZ=3x1+4x2+x3⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧x1+2x2+x3≤102x1+2x2+x3≤16x1,x2,x3≥0
原问题添加松弛变量后 :
m a x Z = 3 x 1 + 4 x 2 + x 3 { x 1 + 2 x 2 + x 3 + x 4 = 10 2 x 1 + 2 x 2 + x 3 + x 5 = 16 x 1 , x 2 , x 3 , x 4 , x 5 ≥ 0 \begin{array}{lcl} \rm maxZ = 3x_1 + 4x_2 + x_3 \\\\ \rm \begin{cases} \rm x_1 + 2x_2 + x_3 + x_4 = 10 \\\\ \rm 2x_1 + 2x_2 + x_3 + x_5 =16 \\\\ \rm x_1,x_2, x_3, x_4 , x_5 \geq 0 \end{cases}\end{array} maxZ=3x1+4x2+x3⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧x1+2x2+x3+x4=102x1+2x2+x3+x5=16x1,x2,x3,x4,x5≥0
将最优解 X 0 = ( 6 2 0 ) \rm X^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix} X0=(620) 代入原问题 :
{ 6 + 2 × 2 + 0 + x 4 = 10 2 × 6 + 2 × 2 + 0 + x 5 = 16 \begin{cases} \rm 6 + 2\times 2 + 0 + x_4 = 10 \\\\ \rm 2 \times 6 + 2 \times 2 + 0 + x_5 = 16 \end{cases} ⎩⎪⎨⎪⎧6+2×2+0+x4=102×6+2×2+0+x5=16
得到 : { x 4 = 0 x 5 = 10 \begin{cases} \rm x_4 = 0 \\\\ \rm x_5 = 10 \end{cases} ⎩⎪⎨⎪⎧x4=0x5=10
X s = ( 0 0 ) \rm X_s = \begin{pmatrix} \quad \rm 0 \quad \\\\ \quad \rm 0 \quad \end{pmatrix} Xs=⎝⎛00⎠⎞
这个信息是无用的 , 根据这个 X s \rm X_s Xs 乘以任意的 Y 0 \rm Y^0 Y0 值都是 0 0 0 , 求不出对偶问题的最优解 ;
七、总结
互补松弛定理 :
" X 0 \rm X^0 X0 和 Y 0 \rm Y^0 Y0 分别是 原问题 P \rm P P 问题 和 对偶问题 D \rm D D 的 最优解 " ⇔ \Leftrightarrow ⇔ { Y 0 X s = 0 Y s X 0 = 0 \begin{cases} \rm Y^0 X_s = 0 \\\\ \rm Y_sX^0 = 0 \end{cases} ⎩⎪⎨⎪⎧Y0Xs=0YsX0=0
其中 X s , Y s \rm X_s , Y_s Xs,Ys 是 松弛变量 或 剩余变量 ;
原问题 P \rm P P 线性规划最优解是 X 0 = ( 6 2 0 ) \rm X^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix} X0=(620) ,
对偶问题的剩余变量是 Y s = ( y 3 y 4 y 5 ) \rm Y_s= \begin{pmatrix} \quad \rm y_3 \quad \\\\ \quad \rm y_4 \quad \\\\ \quad \rm y_5 \quad \\ \end{pmatrix} Ys=⎝⎜⎜⎜⎜⎛y3y4y5⎠⎟⎟⎟⎟⎞
最优解中不等于 0 0 0 的 , 对应的剩余变量中对应的一定为 0 0 0 ,
如果最优解中等于 0 0 0 , 那么剩余变量中的对应的值就不确定了 ;
-
对偶锥
2018-10-30 19:30:08若 KKK 为一个锥,那么它的对偶锥的定义为: K∗={y∣xTy≥0 for all x∈K}K^\ast=\{y\mid x^Ty\geq 0 \text{ for all } x\in K\}K∗=...若 K K K 为一个锥,那么它的对偶锥的定义为:
K ∗ = { y ∣ x ⋅ y ≥ 0 for all x ∈ K } K^\ast=\{y\mid x\cdot y\geq 0 \text{ for all } x\in K\} K∗={y∣x⋅y≥0 for all x∈K}上式中的点表示内积。(两个矩阵的内积等于他们乘积的迹)
在几何意义上,对偶锥上的一条线 y y y 一定属于 K K K 其中一个支撑超平面的法线。例如下图
上图中的红色区域就是 C C C 的对偶锥。几个实例
- 子空间(线性子空间)
V
V
V 的对偶锥是它的正交补.
V ∗ = V ⊥ = { y ∣ y T v = 0 } V^\ast=V^{\perp}=\{y\mid y^Tv=0\} V∗=V⊥={y∣yTv=0}
利用了一个性质:若 x ∈ V x\in V x∈V,则 − x ∈ V -x\in V −x∈V. - 非负象限的对偶锥是它自身.
- 半正定矩阵的对偶锥是它自身.
- 范式锥的对偶锥是它的对偶范式锥.
- 子空间(线性子空间)
V
V
V 的对偶锥是它的正交补.
-
【运筹学】对偶理论 : 总结 ( 对偶理论 | 原问题与对偶问题对应关系 | 对偶理论的相关结论 ) ★★★
2021-01-02 16:37:54一、对偶理论 、 1、对称性定理 、 2、弱对偶定理 、 3、最优性定理 、 4、强对偶性 、 5、互补松弛定理 、 二、原问题与对偶问题对应关系 、 二、对偶理论的相关结论 、 1、对偶问题存在 、 2、对偶问题... -
AI-统计学习(10)-拉格朗日对偶性-求极值必备
2019-11-12 13:15:28为了数学方便,引入的是拉格朗日乘子和对偶性。在求解极值的其实就是关注d*(最优值) C(约束) p*(最优概率)。如果不想看推导,可直接看总结的红字即可。 1.拉格朗日对偶性及其推导 2.定理 2.1定理1 d* ... -
发一个求解二次规划的原始对偶法的MATLAB程序-QPhild.m
2019-08-14 06:47:09该算法对于中小规模的二次规划问题求解效果非常好,对于不可行解可退而求其次,求出该问题的次优解,算法方便好用! 标准凸最优化问题: y=1/2*X'*H*X X'f subject to A_cons*X; 函数f=QPhild ... -
拉格朗日对偶问题
2022-04-06 21:45:48拉格朗日乘数法、拉格朗日对偶问题的原理,拉格朗日对偶问题的充分条件和必要条件 -
线性规划对偶问题
2021-04-28 23:49:31线性规划对偶问题线性规划及单纯形法〇. 前言一. 对偶问题的提出二. 对称形式下对偶问题的一般形式三. 非对称形式的原-对偶问题关系四. 对偶问题的基本性质五. 对偶问题的单纯形法描述六. 影子价格七. 利用... -
【运筹学】对偶理论 : 互补松弛定理应用 2 ( 互补松弛定理求最优解思路 ) ★★
2021-01-02 14:34:11一、原问题与对偶问题标准形式、 二、互补松弛定理、 三、已知原问题最优解求对偶问题最优解、 四、互补松弛定理求最优解思路 -
【运筹学】对偶理论 : 对称形式 ( 对称形式 | 对偶模型转化实例 | 对偶问题规律分析 )
2020-07-31 22:41:06一、对偶问题的对称形式、 二、对偶问题实例、 三、对偶问题规律 -
感知机对偶算法
2021-10-21 22:16:41知识源于——《统计学习方法(第二版)》李航 感知机(perception)一种二分类的线性分类...正样本点是x1=(3,3)T, x2=(4,3)T,负样本点x3=(1,1)T,用感知机学习对偶形式求感知机模型。 二,实验内容 三,实验步... -
主从博弈下层KKT条件 强对偶处理双线性.zip
2021-10-08 19:47:47主从博弈的尝试 另外发现YALMIP的kkt命令能很方便的把下层问题转化为KKT系统 复刻论文 [1]魏韡, 陈玥, 刘锋, 梅生伟, 田芳, 张星. 基于主从博弈的智能小区电动汽车充电管理及代理商定价策略, 电网技术, 2015, 39(4... -
强对偶性、弱对偶性以及KKT条件的证明(对偶问题的几何证明)
2020-08-02 13:58:09本文主要探讨优化问题中强、弱对偶性以及KKT条件的证明。 -
MOOC运筹学不挂科笔记 求对偶问题的最优解
2021-05-09 14:55:44 -
【运筹学】对偶理论 : 最优性定理、强对偶性
2020-12-30 23:02:57一、最优性定理、 二、强对偶性 -
凸集之对偶锥和对偶广义不等式
2021-06-24 16:46:55凸集之对偶锥和对偶广义不等式 1.对偶锥(Dual cones) 设K是一个圆锥体。集合 被称为K的对偶锥。正如顾名思义的,K∗是一个锥,并且总是凸的,即使原始的锥K不是凸的。 几何上,y∈K∗当且仅当−y是在原点处支持K... -
【运筹学】对偶理论 : 对偶性质 ( 对称性质 | 对称性质推导 )
2020-08-03 00:42:58原问题 LPLPLP 对偶问题 DPDPDP – – 目标函数求最大值 maxZmaxZmaxZ 目标函数求最小值 minWminWminW – – 约束条件常数项 目标函数系数 目标函数系数 约束条件常数项 – – mmm 个约束条件 nnn 个约束变量 nnn 个... -
对偶空间
2019-04-03 09:59:51摘自知乎两个比较能够理解的回答 一、 作者:Hua Xiao ...“对偶空间”是“线性空间”,它里面的元素是“线性映射”。 仅仅是这句话就足以让许多人一头雾水了。为了理解它,我们先说说“集合... -
线性规划——对偶问题的对偶问题
2018-10-25 11:37:37线性规划的对偶问题的对偶问题是原问题 -
为什么对偶问题一定是凸优化问题?
2020-10-14 17:34:28\lambda, \nu)=f(x)+\sum^m_{i=1}\lambda_ig_i(x)+\sum^p_{j=1}\nu_j h_j(x)minx,λ,νL(x,λ,ν)=f(x)+i=1∑mλigi(x)+j=1∑pνjhj(x)再求一次对偶问题 maxλ,νminxL(x,λ,ν) s.t. λ≥0max_{\... -
最优化——对偶问题的性质(弱对偶性,强对偶性),对偶问题形式的书写(对偶规则)
2020-12-10 16:15:35对偶性质 弱对偶性 原对偶问题任何可行解的目标值都是另一问题最优目标值的界。(推论:原对 偶问题目标值相等的一对可行解是各自的最优解) 强对偶性 原对偶问题只要有一个有最优解,另一个就有最优解,并且最优... -
对偶范数
2018-10-27 16:49:212范数的对偶范数是 2范数,1范数的对偶范数是 ∞范数,∞范数的对偶范数是 1范数,对偶范数的对偶范数是原范数。 -
【运筹学】对偶理论与的对偶问题最优解算法
2020-06-13 11:32:351.3将对偶问题化为标准型,求出对偶问题的松弛变量是否为0 1.4解对偶问题标准化后的约束方程组,求出对偶问题的最优解 2.原问题的最优单纯形表已经求出 对偶问题的最优解中,基变量的值为原问题最优单纯... -
【运筹学】对偶理论总结 ( 对称性质 | 弱对偶定理 | 最优性定理 | 强对偶性 | 互补松弛定理 ) ★★★
2021-03-08 22:57:17对偶理论总结 ( 对称性质 | 弱对偶定理 | 最优性定理 | 强对偶性 | 互补松弛定理 )