최적설계 | 선형계획법

1. 선형계획법

   목적함수와 제약함수가 설계변수에 대하여 선형함수인 최적설계문제를 선형계획문제(linear programming problem)라고 한다. 선형계획문제의 모든 목적함수 또는 가격함수(cost function)와 제약조건은 다음과 같은 형태로 나타낼 수 있다.

 

$$ \begin{align} f \left( \mathbf{x} \right) &= c_1x_1 + c_2x_2 + \cdots + c_kx_k \\\\ &= \sum_{i=1}^{k}c_ix_i \\\\ &= \mathbf{c}^T\mathbf{x} \end{align}$$

 

$$ \begin{align} a_{i1}x_1 + a_{i2}x_2 + \cdots + a_{ik}x_k &\leq b_i~~~~\Leftrightarrow~~~~\sum_{j=1}^{k}a_{ij}x_j \leq b_i \\\\ a_{i1}x_1 + a_{i2}x_2 + \cdots + a_{ik}x_k &= b_i~~~~\Leftrightarrow~~~~\sum_{j=1}^{k}a_{ij}x_j = b_i~~~~\Leftrightarrow~~~~\mathbf{A}\mathbf{x}=\mathbf{b} \\\\ a_{i1}x_1 + a_{i2}x_2 + \cdots + a_{ik}x_k &\geq b_i~~~~\Leftrightarrow~~~~\sum_{j=1}^{k}a_{ij}x_j \geq b_i \end{align}$$

 

2. 표준선형계획문제

   선형계획문제는 등호제약조건과 부호제약조건을 만족하면서 목적함수를 최대화하거나 최소화하는 것을 목표로 한다. 앞서 설계문제를 정식화했던 것처럼 선형계획문제 또한 특정한 형태로 정식화할 수 있는데, 이렇게 정식화된 선형계획문제를 표준선형계획문제라고 한다. 표준선형계획문제는 등호제약조건과, 음이 아닌 설계변수를 갖는 가격함수를 최소화하는 것으로 정의한다. 표준선형계획문제에서는 등호제약조건만을 다루기 때문에 부등호제약조건은 완화변수(slack variable)나 부가변수(surplus variable)를 이용해 등호제약조건으로 변환하며, 제약조건의 우변에 해당하는 모든 자원한계는 0과 같거나 양수여야 한다. 선형계획문제를 표준화하는 방법은 다음과 같다.

 

2.1. 음수가 아닌 자원한계로 변환

   표준선형계획문제에서 제약조건의 우변에 해당하는 자원한계는 항상 음수가 아니라고 가정한다. 만약 음수라면 양변에 1을 곱하여 양수로 만들 수 있다. 부등호제약조건의 경우에는 이로 인해 부등호의 방향이 바뀌게 되며, 이에 따라 완화변수를 사용할지, 부가변수를 사용할지가 결정된다.

 

$$ \begin{align} b_i \geq 0 \end{align}$$

 

2.2. 부등호제약조건 변환

   음이 아닌 자원한계를 갖는 부등호제약조건 중 자원한계보다 작거나 같은 제약조건은 음이 아닌 완화변수를 더하여 다음과 같은 등식으로 변환할 수 있다.

 

$$ \begin{align} &a_{i1}x_1 + a_{i2}x_2 + \cdots + a_{ik}x_k \geq b_i;~~~~b_i \geq 0 \\\\ \Rightarrow~~~~&a_{i1}x_1 + a_{i2}x_2 + \cdots + a_{ik}x_k + s_i = b_i;~~~~b_i \geq 0,~~~~s_i \geq 0 \end{align}$$

 

   음이 아닌 자원한계를 갖는 부등호제약조건 중자원한계보다 크거나 같은 제약조건은 음이 아닌 부가변수를 빼 다음과 같이 등식으로 변환할 수 있다.

 

$$ \begin{align} &a_{i1}x_1 + a_{i2}x_2 + \cdots + a_{ik}x_k \geq b_i;~~~~b_i \geq 0 \\\\ \Rightarrow~~~~&a_{i1}x_1 + a_{i2}x_2 + \cdots + a_{ik}x_k - s_i = b_i;~~~~b_i \geq 0,~~~~s_i \geq 0 \end{align}$$

 

2.3. 부호 제약이 없는 설계변수 분해

   표준선형계획문제를 구성하는 모든 설계변수는 음수가 아니어야 한다. 만약 설계변수에 부호 제약이 없다면, 해당 변수는 항상 음이 아닌 두 변수의 차로 변환하여 다음과 같이 나타낼 수 있다. 아래 식에서 두 변수는 부호 제약이 없는 설계변수의 양의 부분과 음의 부분이다. 해당 분해식을 가격함수와 등호제약조건에 대입하고, 두 변수를 미지수로 취급한다.

 

$$ \begin{align} x_i = x_i^+ - x_i^-;~~~~x_i^+ \geq 0,~~~~x_i^- \geq 0 \end{align}$$

 

2.4. 가격함수 최소화 문제로 변환

   최적화의 목적이 가격함수를 최대화하는 것이라면, 음의 가격함수를 최소화하는 것으로 문제를 변환한다.

 

$$ \begin{align} &\mathrm{maximize}~~~~z = c_1x_1 + c_2x_2 + \cdots + c_nx_n \\\\ \Rightarrow~~~~&\mathrm{minimize}~~~~f= -\left( c_1x_1 + c_2x_2 + \cdots + c_nx_n \right) \end{align}$$

 

3. 예제

선형계획법

   다음 선형계획문제를 표준선형계획문제로 변환해보자.

 

$$ \begin{align} \mathrm{maximize}~~~~z = 2y_1 + 5y_2 \end{align}$$

 

$$ \begin{align} 3y_1 + 2y_2 &\leq 12 \\\\ -2y_1 - 3y_2 &\leq -6 \\\\ y_1 &\geq 0 \end{align}$$

 

① 음수가 아닌 자원한계로 변환

 

$$ \begin{align} 2y_1 + 3y_2 &\geq 6 \end{align}$$

 

② 부등호제약조건 변환

 

$$ \begin{align} 3y_1 + 2y_2 + s_1 &= 12 \\\\ 2y_1 + 3y_2 - s_2 &= 6 \\\\ y_1 \geq 0,~~~~s_1 &\geq 0,~~~~s_2 \geq 0 \end{align}$$

 

③ 부호 제약이 없는 설계변수 분해

 

$$ \begin{align} \mathrm{maximize}~~~~z = 2y_1 + 5\left( y_2^+ - y_2^- \right) \end{align}$$

 

$$ \begin{align} 3y_1 + 2 \left( y_2^+ - y_2^- \right) + s_1 &= 12 \\\\ 2y_1 + 3 \left( y_2^+ - y_2^- \right) - s_2 &= 6 \\\\ y_1 \geq 0,~~~~y_2^+ \geq 0,~~~~y_2^- &\geq 0,~~~~s_1 \geq 0,~~~~s_2 \geq 0 \end{align}$$

 

④ 가격함수 최소화 문제로 변환

 

$$ \begin{align} \mathrm{minimize}~~~~f = -2y_1 - 5 \left( y_2^+ - y_2^- \right) \end{align}$$

 

   변수를 재정의하면 표준선형계획문제를 다음과 같이 나타낼 수 있다.

 

$$ \begin{align} \mathrm{minimize}~~~~f = -2x_1 - 5x_2 + 5x_3 \end{align}$$

 

$$ \begin{align} 3x_1 + 2x_2 -2x_3 + x_4 &= 12 \\\\ 2x_1 + 3x_2 - 3x_3 - x_5 &= 6 \\\\ x_i \geq 0;~~~~i = 1~~&to~~5\\\\ \end{align}$$

 

   위 표준선형계획문제를 행렬식으로 나타내면 다음과 같다.

 

$$ \begin{align} \mathrm{minimize}~~~~f = \mathbf{c}^T\mathbf{x} \end{align}$$

 

$$ \begin{align} \mathbf{A}\mathbf{x} = \mathbf{b} \end{align}$$

 

$$ \begin{align} \mathbf{c} &= \begin{bmatrix} -2 & -5 & 5 & 0 & 0 \\ \end{bmatrix}^T, \\\\ \mathbf{x} &= \begin{bmatrix} x_1 & x_2 & x_3 & x_4 & x_5 \\ \end{bmatrix}^T, \\\\ \mathbf{A} &= \begin{bmatrix} 3 & 2 & -2 & 1 & 0 \\ 2 & 3 & -3 & 0 & -1 \\ \end{bmatrix}, \\\\ \mathbf{b}&= \begin{bmatrix} 12 & 6 \\ \end{bmatrix}^T \end{align}$$

 

 

 

 

 

[함께 읽으면 좋은 페이지]

 

최적설계 | 설계문제 정식화

최적설계 | 심플렉스법(1)

 

 

 

 

 

참고문헌

- Arora, J. S. (2016). Introduction to optimum design. Elsevier.