精华内容
下载资源
问答
  • 【运筹学】对偶理论 : 弱对偶性质 ( 弱对偶原理 | 弱对偶性 | 推论 1 | 推论 2 对偶问题的无界性 | 推论 3 ...
    千次阅读
    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 CX0Y0b ,

    展开后为 ∑ 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=1ncjxji=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) 中 ,

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

    更多相关内容
  • 文件夹1是最基本的原对偶问题,只有包含支路潮流约束 文件夹2是包含储能的原对偶问题,去除了储能的时间耦合约束,使用我自己的方法进行推导,虽然复杂但是可以解决问题,理解了我的这个做法,也就掌握了对偶的使用...
  • 基于Matlab的对偶问题最优解探讨.pdf
  • 将线性规划问题转化为标准型,minz转化为max-z 以下图为例 初始化 import numpy as np class Simplex(object): #构造函数(初始化函数) def __init__(self,z,B,bound): self.X_count=len(z) #变量个数 ...
  • 一、对称理论、 二、对偶理论示例、 三、对偶理论示例 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.tAXbX0

    如果原问题是求最大值 , 约束方程有大于等于不等式 , 需要在这些大于等于不等式 左右两边乘以 − 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.tATYCTY0


    矩阵转置 : 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.tx12x28x1,x20

    上述线性规划原问题 ① 目标函数求最大值 ② 约束方程是小于等于不等式 , ③ 约束变量大于等于 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} (12) 的转置矩阵 ( 1 − 2 ) \begin{pmatrix} &1 & \\ &-2 & \\ \end{pmatrix} (12) ;

    对偶问题变量个数 : 约束方程的变量个数是矩阵的列数 , 这里只有 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.ty122y11y10





    三、对偶理论示例 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.tx12x28x1,x20


    上述线性规划的对偶问题的目标函数是求最大值 ;

    参考下图列表 :

    在这里插入图片描述


    写出其对偶问题 ( 上述表格中的右侧 ) :

    ( 1 ) 目标函数求最大 , 且目标函数的系数是原方程的约束方程常数 ;

    m i n W = 8 y 1 \rm minW = 8y_1 minW=8y1


    ( 2 ) 约束条件 :

    对偶问题约束方程系数 : 约束方程矩阵是 ( 1 − 2 ) \begin{pmatrix} &1 & -2 & \\ \end{pmatrix} (12) 的转置矩阵 ( 1 − 2 ) \begin{pmatrix} &1 & \\ &-2 & \\ \end{pmatrix} (12) ;

    对偶问题变量个数 : 约束方程的变量个数是矩阵的列数 , 这里只有 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.ty122y11y10





    四、求对偶技巧 ★★



    写出对偶定理的标准对称形式 ★ : 记住下面的标准形式

    原问题 :

    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.tAXbX0

    对偶问题 :

    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.tATYCTY0



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


    约束方程符号 :

    如果当前线性规划问题 目标函数是求最大值 , 原问题就是上面的问题 , 其对偶问题 ( 下面的 ) 的约束方程符号是 ≥ \geq , 因此 对偶问题的约束方程符号原问题变量 符号一致 ;

    如果当前线性规划问题 目标函数是求最小值 , 原问题就是下面的问题 , 其对偶问题 ( 上面的 ) 的约束方程符号是 ≤ \leq , 因此 对偶问题的约束方程符号原问题变量 符号相反 ;


    变量符号 :

    如果当前线性规划问题 目标函数是求最大值 , 原问题就是上面的问题 , 其对偶问题 ( 下面的 ) 的约束方程符号是 ≥ \geq , 因此 对偶问题的变量符号原问题约束方程符号 符号相反 ;

    如果当前线性规划问题 目标函数是求最大值 , 原问题就是上面的问题 , 其对偶问题 ( 下面的 ) 的约束方程符号是 ≥ \geq , 因此 对偶问题的变量符号原问题约束方程符号 符号一致 ;

    展开全文
  • 大规模SDP求解器,基于SDPT3实现文档,全部MATLAB实现,没有底层c语言库
  • 一、原问题与对偶问题标准形式、 ...三、已知原问题最优解求对偶问题最优解、 四、使用单纯形法求解、 五、使用互补松弛定理公式一求解、 六、使用互补松弛定理公式二求解 ( 无效方法 )、 七、总结





    一、原问题与对偶问题标准形式



    原问题 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.tAXbX0 ;              \ \ \ \ \ \ \ \ \ \ \,            对偶问题 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.tATYCTY0


    等价方法 :

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




    二、互补松弛定理



    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+x3x1+2x2+x3102x1+2x2+x316x1,x2,x30

    上述线性规划的最优解是 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+16y2y1+2y232y1+2y24y1+y21y1,y20


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

    { 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+2y2y3=32y1+2y2y4=4y1+y2y5=1y1,y2,y3,y4,y50



    互补松弛定理 :

    " 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,y40 , 上述 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+2y2y3=32y1+2y2y4=4y1+y2y5=1y1,y2,y3,y4,y50 中 ;

    得到 { 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+x3x1+2x2+x3102x1+2x2+x316x1,x2,x30

    原问题添加松弛变量后 :

    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+x3x1+2x2+x3+x4=102x1+2x2+x3+x5=16x1,x2,x3,x4,x50

    将最优解 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={yxy0 for all xK}

    上式中的点表示内积。(两个矩阵的内积等于他们乘积的迹)

    在几何意义上,对偶锥上的一条线 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={yyTv=0}
      利用了一个性质:若 x ∈ V x\in V xV,则 − x ∈ V -x\in V xV.
    • 非负象限的对偶锥是它自身.
    • 半正定矩阵的对偶锥是它自身.
    • 范式锥的对偶锥是它的对偶范式锥.
    展开全文
  • 一、对偶理论 、 1、对称性定理 、 2、弱对偶定理 、 3、最优性定理 、 4、强对偶性 、 5、互补松弛定理 、 二、原问题与对偶问题对应关系 、 二、对偶理论的相关结论 、 1、对偶问题存在 、 2、对偶问题...
  • 为了数学方便,引入的是拉格朗日乘子和对偶性。在求解极值的其实就是关注d*(最优值) C(约束) p*(最优概率)。如果不想看推导,可直接看总结的红字即可。 1.拉格朗日对偶性及其推导 2.定理 2.1定理1 d* ...
  • 该算法对于中小规模的二次规划问题求解效果非常好,对于不可行解可退而其次,出该问题的次优解,算法方便好用! 标准凸最优化问题:  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
    线性规划对偶问题线性规划及单纯形法〇. 前言一. 对偶问题的提出二. 对称形式下对偶问题的一般形式三. 非对称形式的原-对偶问题关系四. 对偶问题的基本性质五. 对偶问题的单纯形法描述六. 影子价格七. 利用...
  • 一、原问题与对偶问题标准形式、 二、互补松弛定理、 三、已知原问题最优解求对偶问题最优解、 四、互补松弛定理最优解思路
  • 一、对偶问题的对称形式、 二、对偶问题实例、 三、对偶问题规律
  • 感知机对偶算法

    2021-10-21 22:16:41
    知识源于——《统计学习方法(第二版)》李航 感知机(perception)一种二分类的线性分类...正样本点是x1=(3,3)T, x2=(4,3)T,负样本点x3=(1,1)T,用感知机学习对偶形式感知机模型。 二,实验内容 三,实验步...
  • 主从博弈的尝试 另外发现YALMIP的kkt命令能很方便的把下层问题转化为KKT系统 复刻论文 [1]魏韡, 陈玥, 刘锋, 梅生伟, 田芳, 张星. 基于主从博弈的智能小区电动汽车充电管理及代理商定价策略, 电网技术, 2015, 39(4...
  • 本文主要探讨优化问题中强、弱对偶性以及KKT条件的证明。
  • 一、最优性定理、 二、强对偶
  • 凸集之对偶锥和对偶广义不等式 1.对偶锥(Dual cones) 设K是一个圆锥体。集合 被称为K的对偶锥。正如顾名思义的,K∗是一个锥,并且总是凸的,即使原始的锥K不是凸的。 几何上,y∈K∗当且仅当−y是在原点处支持K...
  • 原问题 LPLPLP 对偶问题 DPDPDP – – 目标函数最大值 maxZmaxZmaxZ 目标函数最小值 minWminWminW – – 约束条件常数项 目标函数系数 目标函数系数 约束条件常数项 – – mmm 个约束条件 nnn 个约束变量 nnn 个...
  • 对偶空间

    千次阅读 2019-04-03 09:59:51
    摘自知乎两个比较能够理解的回答 一、 作者:Hua Xiao ...“对偶空间”是“线性空间”,它里面的元素是“线性映射”。 仅仅是这句话就足以让许多人一头雾水了。为了理解它,我们先说说“集合...
  • 线性规划——对偶问题的对偶问题

    千次阅读 2018-10-25 11:37:37
    线性规划的对偶问题的对偶问题是原问题
  • \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​λi​gi​(x)+j=1∑p​νj​hj​(x)再一次对偶问题 maxλ,νminxL(x,λ,ν) s.t. λ≥0max_{\...
  • 对偶性质 弱对偶性 原对偶问题任何可行解的目标值都是另一问题最优目标值的界。(推论:原对 偶问题目标值相等的一对可行解是各自的最优解) 强对偶性 原对偶问题只要有一个有最优解,另一个就有最优解,并且最优...
  • 对偶范数

    万次阅读 多人点赞 2018-10-27 16:49:21
    2范数的对偶范数是 2范数,1范数的对偶范数是 ∞范数,∞范数的对偶范数是 1范数,对偶范数的对偶范数是原范数。
  • 1.3将对偶问题化为标准型,对偶问题的松弛变量是否为0 1.4解对偶问题标准化后的约束方程组,对偶问题的最优解 2.原问题的最优单纯形表已经对偶问题的最优解中,基变量的值为原问题最优单纯...
  • 对偶理论总结 ( 对称性质 | 弱对偶定理 | 最优性定理 | 强对偶性 | 互补松弛定理 )

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,807
精华内容 5,522
关键字:

对偶是怎么求