🧩 도해법

✨ 도해법

• 도표(Graph)를 이용하여 선형계획법의 해를 찾는 방법
• 제약식을 이용하여 실행가능영역(Feasible region)을 그래프로 표시
• 변수가 2개일 때만 가능한 시각적 방법

---

✨ 절차

1. 의사결정변수들로 이루어진 좌표계를 설정
2. 실행가능영역(개별 제약식을 만족하는 영역의 교집합)을 좌표계에 표시
   • 비음조건을 반영하여 좌표계의 1사분면을 기본으로 한다.
3. 목적함수로부터 기울기를 구하고 목적함수와 같은 기울기를 가지는 직선을 그린 후, 어느 방향으로의 평행이동이 목적함수의 값을 더 좋게 하는지를 찾아 평행이동 시킨다.
   • 목적함수 $Z=a{x}_1+b{x}_2$에서 기울기 $-a/b$를 계산한다.
   • $Z=a{x}_1+b{x}_2$를 $x_2=-\frac{a}{b}{x}_1+\frac{Z}{b}$ 형태로 바꾸면, 기울기가 $-\frac{a}{b}$임을 알 수 있다.
   • 문제의 성격(최대화 or 최소화)에 따라 목적함수와 같은 기울기를 가지는 직선을 평행이동하여 값을 개선하는 방향을 찾는다.
4. 평행이동 중 실행가능영역의 경계에서 마지막으로 접하는 점이 최적해이며, 보통 실행가능영역의 꼭짓점(Vertex) 중 하나이다.

---

✨ 예시

• 목적함수 (Objective Function)

$$\text{Maximize }Z=150,000x_1+100,000x_2$$

• 제약조건 (Constraints)

$$\begin{array}{r}2x_1+x_2\le 16\\ x_1+x_2\le 12\\ x_1\le 6\\ x_1\ge 0,x_2\ge 0\end{array}$$

---

• 실행가능영역 찾기

  ✅ Step 0: All $x_1,x_2\ge 0$

  • 실행가능영역의 초기 상태 : 1사분면 전체
  • 아직 어떤 제약도 받지 않은 상태

  ✅ Step 1: $2x_1+x_2\le 16$ 적용

  ✅ Step 2: $x_1+x_2\le 12$ 적용

  ✅ Step 3: $x_1\le 6$ 적용

  • 실행 가능 영역 최종 결정

---

• 목적함수와 같은 기울기를 가지는 직선을 평행이동하여 최적해 구하기

---

• 정점을 전부 조사하여 최적해 구하기

---

✨ 시사점

• 최적해가 존재한다면, 그것은 반드시 실행가능영역의 정점 중 하나에 존재한다.
  • 실행가능영역은 선형 제약조건의 교집합으로 이루어진 볼록 다각형(convex polygon) 이기 때문에 목적함수와 같은 기울기를 가지는 직선을 목적함수 값을 개선하는 방향으로 평행이동하다 보면 그 다각형의 꼭짓점 중 하나에서 최대값 또는 최소값이 발생하게 된다.
• 따라서 정점을 전부 조사하면 최적해를 찾을 수 있다.