1 . 对称形式特点 :

2 . 原问题 P P P 的线性规划模型是 :

m a x Z = C X s . t { A X ≤ b X ≥ 0 \begin{array}{lcl} maxZ = C X \\\\ s.t\begin{cases} AX \leq b \\\\ X \geq 0 \end{cases}\end{array} maxZ=CXs.t⎩⎪⎨⎪⎧​AX≤bX≥0​​

对称形式 P P P 要求 :

相关系数 :

3 . 对偶问题 D D D 的线性规划模型是 :

m i n W = b T Y s . t { A T Y ≥ C T Y ≥ 0 \begin{array}{lcl} minW = b^T Y \\\\ s.t\begin{cases} A^TY \geq C^T \\\\ Y \geq 0 \end{cases}\end{array} minW=bTYs.t⎩⎪⎨⎪⎧​ATY≥CTY≥0​​

对偶问题 D D D 要求 :

相关系数 :

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

m a x Z = 2 x 1 − 3 x 2 + 4 x 3 s . t { 2 x 1 + 3 x 2 − 5 x 3 ≥ 2 3 x 1 + x 2 + 7 x 3 ≤ 3 − x 1 + 4 x 2 + 6 x 3 ≥ 5 x j ≥ 0 ( j = 1 , 2 , 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} maxZ=2x1​−3x2​+4x3​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​2x1​+3x2​−5x3​≥23x1​+x2​+7x3​≤3−x1​+4x2​+6x3​≥5xj​≥0(j=1,2,3)​​

将上述线性规划转为 对称形式 :

目标函数最大值 : 对称形式目标函数求最大值 , 上述线性规划符合该条件 , 不用进行修改 ;

约束方程小于等于不等式 : 对称形式的约束方程都是小于等于不等式 , 方程 1 1 1 和方程 3 3 3 都是大于等于不等式 , 不符合要求 ; 将不等式左右两边都乘以 − 1 -1 −1 , 可以将大于等于不等式转为小于等于不等式 ;

转换后的结果为 :

m a x Z = 2 x 1 − 3 x 2 + 4 x 3 s . t { − 2 x 1 − 3 x 2 + 5 x 3 ≤ − 2 3 x 1 + x 2 + 7 x 3 ≤ 3 x 1 − 4 x 2 − 6 x 3 ≤ − 5 x j ≥ 0 ( j = 1 , 2 , 3 ) \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} maxZ=2x1​−3x2​+4x3​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​−2x1​−3x2​+5x3​≤−23x1​+x2​+7x3​≤3x1​−4x2​−6x3​≤−5xj​≥0(j=1,2,3)​​

对称形式 的 目标函数的系数 为 C = ( 2 − 3 4 ) C = \begin{pmatrix} & 2 & -3 & 4 & \end{pmatrix} C=(​2​−3​4​​) , 约束方程的系数 为 A = ( − 2 − 3 5 3 1 7 1 − 4 − 6 ) A = \begin{pmatrix} &-2 & -3 & 5 & \\ &3 & 1 & 7 & \\ &1 & -4 & -6 & \\ \end{pmatrix} A=⎝⎛​​−231​−31−4​57−6​​⎠⎞​ , 约束方程常数 b = ( − 2 3 − 5 ) b = \begin{pmatrix} &-2 &\\ &3 & \\ &-5 & \\ \end{pmatrix} b=⎝⎛​​−23−5​​⎠⎞​ ;

对偶问题 的 目标函数系数 为 b T = ( − 2 3 − 5 ) b^T = \begin{pmatrix} & -2 & 3 & -5 & \end{pmatrix} bT=(​−2​3​−5​​) , 约束方程的系数 为 A T = ( − 2 3 1 − 3 1 − 4 5 7 − 6 ) A^T = \begin{pmatrix} &-2 & 3 & 1 & \\ &-3 & 1 & -4 & \\ &5 & 7 & -6 & \\ \end{pmatrix} AT=⎝⎛​​−2−35​317​1−4−6​​⎠⎞​ , 约束方程常数 C T = ( 2 − 3 4 ) C^T = \begin{pmatrix} & 2 &\\ &-3 & \\ &4 & \\ \end{pmatrix} CT=⎝⎛​​2−34​​⎠⎞​ ;

线性规划形式 :

对称形式 : 求目标函数最大值 , 约束方程是求小于等于不等式 ;

对偶问题 : 求目标函数求最小值 , 约束方程都是大于等于不等式 ;

根据上述分析 , 写出对偶形式 :

m i n W = − 2 y 1 + 3 y 2 − 5 y 3 s . t { − 2 y 1 + 3 y 2 + y 3 ≥ 2 − 3 y 1 + y 2 − 4 y 3 ≥ − 3 5 y 1 + 7 y 2 − 6 y 3 ≥ 4 y j ≥ 0 ( j = 1 , 2 , 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_j \geq 0 \quad ( j = 1, 2, 3 ) \end{cases}\end{array} minW=−2y1​+3y2​−5y3​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​−2y1​+3y2​+y3​≥2−3y1​+y2​−4y3​≥−35y1​+7y2​−6y3​≥4yj​≥0(j=1,2,3)​​

原问题 与 对偶问题线性规划分析 :

上述对偶问题线性规划 , 与原问题线性规划 , 明显不互为转置矩阵 ;

原问题线性规划系数为 ( 2 3 − 5 3 1 7 − 1 4 6 ) \begin{pmatrix} &2 & 3 & -5 & \\ &3 & 1 & 7 & \\ &-1 & 4 & 6 & \\ \end{pmatrix} ⎝⎛​​23−1​314​−576​​⎠⎞​ , 对偶问题线性规划系数为 ( − 2 3 1 − 3 1 − 4 5 7 − 6 ) \begin{pmatrix} &-2 & 3 & 1 & \\ &-3 & 1 & -4 & \\ &5 & 7 & -6 & \\ \end{pmatrix} ⎝⎛​​−2−35​317​1−4−6​​⎠⎞​ , 原问题的转置矩阵应该是 ( 2 3 − 1 3 1 4 − 5 7 6 ) \begin{pmatrix} &2 & 3 & -1 & \\ &3 & 1 & 4 & \\ &-5 & 7 & 6 & \\ \end{pmatrix} ⎝⎛​​23−5​317​−146​​⎠⎞​ , y 1 , y 3 y_1 , y_3 y1​,y3​ 系数的正负号与原问题的转置矩阵值的符号相反 ;

令 y 1 ′ = − y 1 y_1' = -y_1 y1′​=−y1​ , y 3 ′ = − y 3 y_3' = -y_3 y3′​=−y3​ , 则得到如下线性规划 :

m i n W = 2 y 1 ′ + 3 y 2 − 5 y 3 ′ s . t { 2 y 1 ′ + 3 y 2 − y 3 ′ ≥ 2 3 y 1 ′ + y 2 + 4 y 3 ′ ≥ − 3 − 5 y 1 ′ + 7 y 2 + 6 y 3 ′ ≥ 4 y 1 ′ ≤ 0 , y 2 ≥ 0 , y 3 ′ ≤ 0 \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} minW=2y1′​+3y2​−5y3′​s.t⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​2y1′​+3y2​−y3′​≥23y1′​+y2​+4y3′​≥−3−5y1′​+7y2​+6y3′​≥4y1′​≤0,y2​≥0,y3′​≤0​​

对偶有以下规律 : 假设原问题 L P LP LP 目标函数求最大值 m a x Z maxZ maxZ , 对偶问题 D P DP DP 求最小值 m i n W minW minW ;

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

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

记住一条 : 目标函数求最大值 , L P LP LP 约束条件与 D P DP DP 约束变量符号相反 , L P LP LP 约束变量 与 D P DP DP 约束条件符号相同 ;

补一张图 , 方便记忆 :