线性规划原问题与对偶问题

男娘i 2021-09-25 02:00 506阅读 0赞

### 文章目录 ###

*  1. 对偶问题
 *  2. 原问题和对偶问题的对应关系
 *  3. 举例
 *  参考

# 1. 对偶问题 #

任一线性规划问题都存在另一与之伴随的线性规划问题，它们组成一对互为对偶的线性规划问题。

线性规划的对偶问题与原问题互为对偶，线性规划的原问题与对偶问题地位具有对称关系。

# 2. 原问题和对偶问题的对应关系 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70]

# 3. 举例 #

原问题：  
 max ⁡ z = c x s.t.  \{ A x ≤ b x ≥ 0 \\max z = \\bm\{cx\} \\\\ \\text\{s.t. \} \\left\\lbrace \\begin\{array\}\{ll\} \\bm\{Ax\} \\leq \\bm\{b\} \\\\ \\bm\{x\} \\geq 0 \\\\ \\end\{array\} \\right. maxz=cxs.t. \{ Ax≤bx≥0

对偶问题：  
 min ⁡ w = y b s.t.  \{ y A ≥ c y ≥ 0 \\min w = \\bm\{yb\} \\\\ \\text\{s.t. \} \\left\\lbrace \\begin\{array\}\{ll\} \\bm\{yA\} \\geq \\bm\{c\} \\\\ \\bm\{y\} \\geq 0 \\\\ \\end\{array\} \\right. minw=ybs.t. \{ yA≥cy≥0

--------------------

原问题：  
 max ⁡ z = 3 x 1 + 5 x 2 s.t.  \{ x 1 ≤ 4 , 2 x 2 ≤ 12 3 x 1 + 2 x 2 ≤ 18 x 1 ≥ 0 , x 2 ≥ 0 \\max z = 3x\_1 + 5x\_2 \\\\ \\text\{s.t. \} \\left\\lbrace \\begin\{array\}\{ll\} x\_1 \\leq 4, \\\\ 2x\_2 \\leq 12 \\\\ 3x\_1 + 2x\_2 \\leq 18 \\\\ x\_1 \\geq 0, x\_2 \\geq 0 \\\\ \\end\{array\} \\right. maxz=3x1\+5x2s.t. ⎩⎪⎪⎨⎪⎪⎧x1≤4,2x2≤123x1\+2x2≤18x1≥0,x2≥0  
其中，约束方程系数矩阵  A \\bm\{A\} A，约束方程常数矩阵  b \\bm\{b\} b，目标方程系数矩阵  c \\bm\{c\} c，变量  x \\bm\{x\} x

A = \[ 1 0 0 2 3 2 \] , b = \[ 4 12 18 \] , c = \[ 3 5 \] , x = \[ x 1 x 2 \] \\bm\{A\} = \\begin\{bmatrix\} 1 & 0 \\\\ 0 & 2 \\\\ 3 & 2 \\\\ \\end\{bmatrix\}, \\bm\{b\} = \\begin\{bmatrix\} 4 \\\\ 12 \\\\ 18 \\\\ \\end\{bmatrix\}, \\bm\{c\} = \\begin\{bmatrix\} 3 & 5 \\end\{bmatrix\}, \\bm\{x\} = \\begin\{bmatrix\} x\_1 \\\\ x\_2 \\\\ \\end\{bmatrix\} A=⎣⎡103022⎦⎤,b=⎣⎡41218⎦⎤,c=\[35\],x=\[x1x2\]

对偶问题：  
 y = \[ y 1 y 2 y 3 \] , \\bm\{y\} = \\begin\{bmatrix\} y\_1 & y\_2 & y\_3 \\\\ \\end\{bmatrix\}, y=\[y1y2y3\],

min ⁡ w = 4 y 1 + 12 y 2 + 18 y 3 s.t.  \{ y 1 + 3 y 3 ≥ 3 , 2 y 2 + 2 y 3 ≥ 5 y 1 ≥ 0 , y 2 ≥ 0 , y 3 ≥ 0 \\min w = 4y\_1 + 12y\_2 + 18y\_3 \\\\ \\text\{s.t. \} \\left\\lbrace \\begin\{array\}\{ll\} y\_1 + 3y\_3 \\geq 3, \\\\ 2y\_2 + 2y\_3 \\geq 5 \\\\ y\_1 \\geq 0, y\_2 \\geq 0, y\_3 \\geq 0 \\\\ \\end\{array\} \\right. minw=4y1\+12y2\+18y3s.t. ⎩⎨⎧y1\+3y3≥3,2y2\+2y3≥5y1≥0,y2≥0,y3≥0

# 参考 #

1.  《运筹学》 第四版 徐玖平，胡知能 编著

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70]: /images/20210923/9a7fd206b4d74f478de6d4626e396ff9.png