OP의 희망에 따라 위의 주석에서 링크 된 math.SE 답변이 있습니다.

---

예제 문제에서 듀얼이 어디에서 나오는지 이야기하는 것이 좋습니다. 이 작업에는 다소 시간이 걸리지 만 듀얼이 우리가 끝났을 때 그렇게 신비하게 보이지 않을 것입니다.

다음과 같이 근본적인 문제가 있다고 가정하십시오.

$$Primal =\begin{Bmatrix} \max \ \ \ \ 5x_1 - 6x_2 \\ \ \ \ s.t. \ \ \ \ 2x_1 -x_2 = 1\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_1 +3x_2 \leq9\\ \ \ \ \ x_1 \geq 0\\ \end{Bmatrix}$$

---

이제, 최적의 최적 값에 대한 상한을 찾는 방법으로 기본의 구속 조건을 사용한다고 가정합니다. 우리는 다중 제에 의해 구속하면 에 의해 제 2 구속 1 과 함께 추가 우리 얻을 9 ( 2 X 1 – X 2 ) + 1 ( X 1 + 3 X 2 ) 좌측 및 대 9 ( 오른쪽은 1 ) + 1 ( 9 ) 입니다. 첫 번째 제약 조건은 평등이고 두 번째 제약 조건은 불평등이므로9

$9$

$9$1

$1$

$1$9(2x1−x2)+1(x1+3x2)

$9(2x_1-x_2)+1(x_1+3x_2)$

$9(2x_1 - x_2) + 1(x_1 +3 x_2)$9(1)+1(9)

$9(1)+1(9)$

$9(1) + 1(9)$
하지만 이후 X 1 ≥ 0 , 또한 사실이 5 X 1 ≤ 19 X 1 등 5 X 1 – 6 X 2 ≤ 19 X 1 – 6 X 2 ≤ 18.
그러므로 , 18 원초적 문제의 최적 값에 상한선이다.

$$19x_1 - 6x_2 \leq 18.$$ x1≥0

$x_1\ge 0$

$x_1 \geq 0$5x1≤19x1

$5x_1\le 19x_1$

$5x_1 \leq 19x_1$

$$5x_1 - 6x_2 \leq 19x_1 - 6x_2 \leq 18.$$ 18

$18$

$18$

그러나 우리는 그보다 더 잘할 수 있습니다. 와 1 을 승수로 추측하는 대신 변수로 사용합시다. 따라서 우리는 승산기 찾는 Y 1 및 Y 2 힘 5 X 1 – 6 X 2 ≤ Y (1) ( 2 X 1 – X 2 ) + (Y) 2 ( X 1 + 3 X 2 ) ≤ Y 1 ( 1 ) + y 29

$9$

$9$1

$1$

$1$y1

$y_1$

$y_1$y2

$y_2$

$y_2$

$$5x_1 - 6x_2 \leq y_1(2x_1-x_2) + y_2(x_1 + 3x_2) \leq y_1(1) + y_2(9).$$

자,이 불평등이 유지 되려면 과 y 2에 대해 무엇이 진실 입니까? 한 번에 하나씩 두 불평등을합시다.y1

$y_1$

$y_1$y2

$y_2$

$y_2$

---

첫 번째 불평등 : 5x1−6x2≤y1(2x1−x2)+y2(x1+3x2)

$5x_1-6x_2\le y_1(2x_1-x_2)+y_2(x_1+3x_2)$

$5x_1 - 6x_2 \leq y_1(2x_1-x_2) + y_2(x_1 + 3x_2)$

및 x 2 변수 의 계수를 별도로 추적해야합니다 . 먼저 우변 의 총 x 1 계수가 5 이상이어야 합니다. 정확히 5를 얻는 것은 좋지만 x 1 ≥ 0 이기 때문에 5 보다 큰 것은 x 1 의 부등식을 만족시킬 것 입니다. 수학적으로 말하자면, 이것은 2 y 1 + y 2 ≥ 5 가 필요하다는 것을 의미합니다 .x1

$x_1$

$x_1$x2

$x_2$

$x_2$x1

$x_1$

$x_1$5

$5$

$5$5

$5$

$5$x1≥0

$x_1\ge 0$

$x_1 \geq 0$5

$5$

$5$x1

$x_1$

$x_1$2y1+y2≥5

$2y_1+y_2\ge 5$

$2y_1 + y_2 \geq 5$

x2

$x_2$

$x_2$x2

$x_2$

$x_2$−6

$-6$

$-6$x2

$x_2$

$x_2$−6

$-6$

$-6$x2

$x_2$

$x_2$−6

$-6$

$-6$x2

$x_2$

$x_2$x2

$x_2$

$x_2$ .−y1+3y2=−6

$-y_1+3y_2=-6$

$-y_1 + 3y_2 = -6$

---

두 번째 불평등 : 와이1( 2 x1− x2) + y2( x1+ 3 x2) ≤ y1( 1 ) + y2( 9 )

${\mathrm{와이}}_1(2{\mathrm{엑스}}_1-{\mathrm{엑스}}_2)+{\mathrm{와이}}_2({\mathrm{엑스}}_1+\mathrm{삼}{\mathrm{엑스}}_2)\le {\mathrm{와이}}_1(1)+{\mathrm{와이}}_2(9)$

$y_1(2x_1-x_2) + y_2(x_1 + 3x_2) \leq y_1(1) + y_2(9)$

와이1

${\mathrm{와이}}_1$

$y_1$와이2

${\mathrm{와이}}_2$

$y_2$와이1

${\mathrm{와이}}_1$

$y_1$와이1

${\mathrm{와이}}_1$

$y_1$와이1

${\mathrm{와이}}_1$

$y_1$와이2

${\mathrm{와이}}_2$

$y_2$와이2

${\mathrm{와이}}_2$

$y_2$와이2≥ 0

${\mathrm{와이}}_2\ge 0$

$y_2 \geq 0$

와이1+ 9 년2

${\mathrm{와이}}_1+9{\mathrm{와이}}_2$

$y_1 + 9y_2$

---

와이1

${\mathrm{와이}}_1$

$y_1$와이2

${\mathrm{와이}}_2$

$y_2$

$$\begin{align*} \text{Minimize }\:\:\:\:\: y_1 + 9y_2& \\ \text{subject to }\:\:\:\:\: 2y_1 + y_2& \geq 5 \\ -y_1 + 3y_2& = -6\\ y_2 & \geq 0. \end{align*}$$

그리고 그것은 이중입니다.

---

가능한 모든 형태의 원초와 이원에 대한이 주장의 의미를 요약 할 가치가있다. 다음 표는 p. 214 운영 연구 소개 힐러와 리버만에 의해, 8 판,. 이를 SOB 방법이라고합니다. 여기서 SOB는 최대화 또는 최소화 문제에서 특정 제한 또는 변수 제한을 찾을 가능성에 따라 Sensible, Odd 또는 Bizarre를 나타냅니다.

             Primal Problem                           Dual Problem
             (or Dual Problem)                        (or Primal Problem)

             Maximization                             Minimization

Sensible     <= constraint            paired with     nonnegative variable
Odd          =  constraint            paired with     unconstrained variable
Bizarre      >= constraint            paired with     nonpositive variable

Sensible     nonnegative variable     paired with     >= constraint
Odd          unconstrained variable   paired with     = constraint
Bizarre      nonpositive variable     paired with     <= constraint

---

답변