[C++로 배우는 알고리즘과 자료구조 심화] Day 26: 선형 계획법 (Linear Programming)

선형 계획법 (Linear Programming)

선형 계획법은 주어진 선형 제약 조건하에서 선형 목표 함수를 최적화(최대화 또는 최소화)하는 문제를 해결하는 기법입니다. 선형 계획법은 경제학, 운영 연구, 엔지니어링 등 다양한 분야에서 사용됩니다. 가장 널리 알려진 방법은 단체법 (Simplex Method)과 내부 점 방법 (Interior Point Method)입니다.

선형 계획법 문제 정의

일반적인 선형 계획법 문제는 다음과 같이 정의됩니다:

[
\begin{aligned}
& \text{Maximize (or Minimize)} \quad & c^T x \
& \text{subject to} \quad & Ax \leq b \
& & x \geq 0
\end{aligned}
]

여기서 (c)는 목표 함수의 계수 벡터, (A)는 제약 조건의 계수 행렬, (b)는 제약 조건의 상수 벡터, (x)는 변수 벡터입니다.

단체법 (Simplex Method)

단체법은 선형 계획 문제를 해결하는 매우 효율적인 알고리즘입니다. 단체법은 기본 feasible 해에서 시작하여 목표 함수를 개선하는 방향으로 이동하여 최적해를 찾습니다.

예시 문제

다음과 같은 선형 계획 문제를 고려해봅시다:

[
\begin{aligned}
& \text{Maximize} \quad & 3x_1 + 2x_2 \
& \text{subject to} \quad & x_1 + x_2 \leq 4 \
& & x_1 \leq 2 \
& & x_2 \leq 3 \
& & x_1, x_2 \geq 0
\end{aligned}
]

단체법 구현

다음은 C++로 단체법을 구현한 예제입니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

const double EPSILON = 1e-9;
const double INF = 1e9;

// 단체법 클래스 정의
class Simplex {
public:
    Simplex(const std::vector<std::vector<double>>& A, const std::vector<double>& b, const std::vector<double>& c)
        : m(A.size()), n(A[0].size()), A(A), b(b), c(c), basic(m), nonbasic(n) {
        for (int i = 0; i < m; ++i) {
            basic[i] = n + i;
        }
        for (int j = 0; j < n; ++j) {
            nonbasic[j] = j;
        }
        tableau.resize(m + 1, std::vector<double>(n + m + 1, 0));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                tableau[i][j] = A[i][j];
            }
            tableau[i][n + i] = 1;
            tableau[i][n + m] = b[i];
        }
        for (int j = 0; j < n; ++j) {
            tableau[m][j] = -c[j];
        }
    }

    double solve() {
        while (true) {
            int pivotCol = -1;
            for (int j = 0; j < n + m; ++j) {
                if (tableau[m][j] < -EPSILON) {
                    pivotCol = j;
                    break;
                }
            }
            if (pivotCol == -1) break;

            int pivotRow = -1;
            double minRatio = INF;
            for (int i = 0; i < m; ++i) {
                if (tableau[i][pivotCol] > EPSILON) {
                    double ratio = tableau[i][n + m] / tableau[i][pivotCol];
                    if (ratio < minRatio) {
                        minRatio = ratio;
                        pivotRow = i;
                    }
                }
            }
            if (pivotRow == -1) {
                std::cerr << "Unbounded" << std::endl;
                return -INF;
            }

            pivot(pivotRow, pivotCol);
        }
        return tableau[m][n + m];
    }

private:
    int m, n;
    std::vector<std::vector<double>> A, tableau;
    std::vector<double> b, c;
    std::vector<int> basic, nonbasic;

    void pivot(int pivotRow, int pivotCol) {
        double pivotElement = tableau[pivotRow][pivotCol];
        for (int j = 0; j <= n + m; ++j) {
            tableau[pivotRow][j] /= pivotElement;
        }
        for (int i = 0; i <= m; ++i) {
            if (i != pivotRow) {
                double ratio = tableau[i][pivotCol];
                for (int j = 0; j <= n + m; ++j) {
                    tableau[i][j] -= ratio * tableau[pivotRow][j];
                }
            }
        }
        std::swap(basic[pivotRow], nonbasic[pivotCol]);
    }
};

int main() {
    std::vector<std::vector<double>> A = {
        {1, 1},
        {1, 0},
        {0, 1}
    };
    std::vector<double> b = {4, 2, 3};
    std::vector<double> c = {3, 2};

    Simplex simplex(A, b, c);
    double result = simplex.solve();
    std::cout << "최적해의 값: " << result << std::endl;

    return 0;
}

 

설명

1. 입력:
   • A: 제약 조건의 계수 행렬
   • b: 제약 조건의 상수 벡터
   • c: 목표 함수의 계수 벡터
2. 단체법 클래스:
   • Simplex 클래스는 선형 계획 문제를 정의하고 단체법을 사용하여 최적해를 찾습니다.
   • solve 함수는 단체법을 수행하여 최적해를 계산합니다.
3. 단체법 알고리즘:
   • pivot 함수는 피벗 연산을 수행하여 기본 feasible 해를 갱신합니다.
   • solve 함수는 최적해를 찾을 때까지 반복하여 피벗 연산을 수행합니다.

선형 계획법의 기본 개념과 단체법(Simplex Method)의 구현 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 27: 유전 알고리즘(Genetic Algorithms)"에 대해 학습하겠습니다.