페이지랭크와 선형 프로그래밍 완벽 가이드

구글 검색의 핵심 알고리즘인 페이지랭크와 자원 최적화의 핵심인 선형 프로그래밍을 초급 개발자도 이해할 수 있도록 쉽게 설명합니다. 실무에서 바로 활용할 수 있는 Python 코드와 함께 최적화 알고리즘의 세계로 안내합니다.

---

목차

1. 페이지랭크 알고리즘 개념
2. 페이지랭크 문제 정의
3. 페이지랭크 구현하기
4. 선형 프로그래밍 이해
5. 선형 프로그래밍 문제 공식화
6. 공급능력 계획 실용 예제
7. 최적화 알고리즘 활용

---

1. 페이지랭크 알고리즘 개념

어느 날 김개발 씨가 회사에서 검색 기능을 개선하라는 업무를 받았습니다. "검색 결과가 너무 엉망이에요.

중요한 문서가 왜 맨 뒤에 나오는 거죠?" 팀장님의 질문에 김개발 씨는 머리를 긁적였습니다. 단순히 키워드 매칭만으로는 좋은 검색 결과를 보여줄 수 없다는 것을 깨달은 순간이었습니다.

페이지랭크는 한마디로 웹페이지의 중요도를 측정하는 알고리즘입니다. 마치 학교에서 인기 있는 학생을 찾는 것과 같습니다.

많은 사람에게 추천받는 학생이 인기 있듯이, 많은 링크를 받는 페이지가 중요한 페이지입니다. 이 알고리즘을 이해하면 구글이 어떻게 수십억 개의 웹페이지 중에서 가장 관련성 높은 결과를 보여주는지 알 수 있습니다.

다음 코드를 살펴봅시다.

import numpy as np

# 웹페이지 간의 링크 구조를 인접 행렬로 표현
# 행: 출발 페이지, 열: 도착 페이지
link_matrix = np.array([
    [0, 1, 1, 0],  # 페이지 A는 B, C로 링크
    [1, 0, 0, 1],  # 페이지 B는 A, D로 링크
    [0, 0, 0, 1],  # 페이지 C는 D로 링크
    [1, 1, 0, 0]   # 페이지 D는 A, B로 링크
])

# 각 행의 합으로 나누어 확률 행렬로 변환
row_sums = link_matrix.sum(axis=1, keepdims=True)
transition_matrix = link_matrix / row_sums

print("전이 확률 행렬:")
print(transition_matrix)

김개발 씨는 입사 2년 차 백엔드 개발자입니다. 회사의 내부 문서 검색 시스템을 담당하게 되었는데, 직원들의 불만이 끊이지 않았습니다.

분명히 중요한 문서인데 검색 결과 10페이지에나 나온다는 것이었습니다. "단순히 제목에 키워드가 있는지만 확인하면 안 되나요?" 김개발 씨가 물었습니다.

선배 개발자 박시니어 씨가 고개를 저었습니다. "그러면 '회의록'이라고 검색했을 때 수천 개의 회의록이 다 똑같은 중요도로 나와요.

어떤 게 정말 중요한 문서인지 알 수가 없죠." 그렇다면 페이지랭크란 정확히 무엇일까요? 쉽게 비유하자면, 페이지랭크는 마치 학술 논문의 인용 시스템과 같습니다.

좋은 논문은 많은 다른 논문에서 인용됩니다. 그리고 유명한 학자의 논문에서 인용되면 더욱 가치가 높아집니다.

마찬가지로 웹페이지도 많은 링크를 받으면 중요하고, 중요한 페이지로부터 링크를 받으면 더욱 중요해집니다. 1998년 스탠퍼드 대학원생이었던 래리 페이지와 세르게이 브린은 이 아이디어로 구글을 창업했습니다.

당시 다른 검색 엔진들은 키워드 빈도만 세었지만, 구글은 페이지 간의 링크 구조를 분석했습니다. 이것이 바로 혁신이었습니다.

페이지랭크의 핵심 아이디어는 무작위 서퍼 모델입니다. 인터넷을 서핑하는 사람이 있다고 상상해보세요.

이 사람은 현재 페이지에서 무작위로 링크를 클릭해 다른 페이지로 이동합니다. 오랜 시간이 지나면 어떤 페이지에 가장 많이 머물게 될까요?

그 페이지가 바로 가장 중요한 페이지입니다. 위의 코드를 살펴보겠습니다.

먼저 link_matrix는 페이지 간의 연결 관계를 나타냅니다. 값이 1이면 링크가 있고, 0이면 없습니다.

예를 들어 첫 번째 행 [0, 1, 1, 0]은 페이지 A가 페이지 B와 C로 링크한다는 뜻입니다. 다음으로 이 행렬을 전이 확률 행렬로 변환합니다.

각 행의 합으로 나누면 확률이 됩니다. 페이지 A에서 B로 갈 확률은 0.5, C로 갈 확률도 0.5가 됩니다.

이렇게 하면 무작위 서퍼가 어디로 이동할지 확률적으로 모델링할 수 있습니다. 실제 구글의 페이지랭크는 여기에 감쇠 계수라는 것을 추가합니다.

서퍼가 가끔은 링크를 클릭하지 않고 완전히 새로운 페이지로 점프한다고 가정하는 것입니다. 이렇게 하면 링크가 없는 막다른 페이지에서도 알고리즘이 멈추지 않습니다.

주의할 점이 있습니다. 페이지랭크는 링크의 양만 보는 것이 아닙니다.

스팸 사이트 1000개에서 링크를 받는 것보다 위키피디아 하나에서 링크를 받는 것이 더 가치 있습니다. 이것이 바로 재귀적 정의의 힘입니다.

다시 김개발 씨의 이야기로 돌아가 봅시다. 박시니어 씨의 설명을 들은 김개발 씨는 눈이 반짝였습니다.

"아, 그러니까 다른 문서에서 많이 참조되는 문서가 중요한 거군요!" 이제 문서 검색 시스템을 어떻게 개선해야 할지 방향이 잡혔습니다.

실전 팁

💡 - 페이지랭크는 방향 그래프에서 노드의 중요도를 측정하는 범용 알고리즘으로, 웹 외에도 소셜 네트워크 분석, 추천 시스템 등에 활용됩니다

• 실제 구현 시에는 희소 행렬을 사용해야 메모리 효율이 좋습니다

---

2. 페이지랭크 문제 정의

김개발 씨가 페이지랭크의 개념은 이해했지만, 막상 코드로 구현하려니 막막했습니다. "그래서 정확히 무엇을 계산해야 하는 거죠?" 박시니어 씨가 화이트보드에 수식을 적기 시작했습니다.

"수학적으로 정의해보면 훨씬 명확해질 거예요."

페이지랭크 문제는 선형 대수학의 고유벡터 문제로 정의됩니다. 전이 행렬의 주요 고유벡터를 찾으면 각 페이지의 중요도 점수를 얻을 수 있습니다.

이것은 마치 시소가 평형을 이루는 점을 찾는 것과 같습니다. 반복적인 계산을 통해 점수가 수렴하면 그것이 바로 최종 페이지랭크 값입니다.

다음 코드를 살펴봅시다.

import numpy as np

def create_pagerank_matrix(adjacency_matrix, damping=0.85):
    """페이지랭크 행렬 생성 (감쇠 계수 적용)"""
    n = len(adjacency_matrix)

    # 각 페이지의 아웃링크 수 계산
    out_degree = adjacency_matrix.sum(axis=1)

    # 아웃링크가 없는 페이지(dangling node) 처리
    out_degree[out_degree == 0] = 1

    # 전이 확률 행렬 M 생성
    M = adjacency_matrix / out_degree[:, np.newaxis]

    # 감쇠 계수를 적용한 구글 행렬 G
    # G = d * M + (1-d) * (1/n) * E
    E = np.ones((n, n))
    G = damping * M + (1 - damping) * (E / n)

    return G

김개발 씨는 수학 시간이 떠올랐습니다. 대학 때 배운 선형대수학이 이렇게 실무에서 쓰일 줄은 몰랐습니다.

박시니어 씨가 천천히 설명을 이어갔습니다. "페이지랭크를 수학적으로 표현하면 이렇습니다.

모든 페이지의 랭크 합은 1이고, 각 페이지의 랭크는 자신을 가리키는 페이지들의 랭크를 합한 값입니다." 좀 더 쉽게 설명해볼까요? 마치 투표 시스템이라고 생각하면 됩니다.

각 페이지는 자신의 점수를 링크하는 페이지들에게 나눠줍니다. 100점을 가진 페이지가 4개의 페이지에 링크하면, 각 페이지에 25점씩 나눠주는 것입니다.

하지만 여기서 문제가 생깁니다. 어떤 페이지는 아무 곳에도 링크하지 않을 수 있습니다.

이런 페이지를 댕글링 노드라고 부릅니다. 무작위 서퍼가 이런 페이지에 도착하면 더 이상 갈 곳이 없어집니다.

이 문제를 해결하기 위해 감쇠 계수 d를 도입합니다. 보통 0.85를 사용합니다.

이것은 서퍼가 85%의 확률로 링크를 따라가고, 15%의 확률로 완전히 무작위한 페이지로 점프한다는 의미입니다. 위 코드의 핵심 부분을 살펴보겠습니다.

먼저 out_degree는 각 페이지에서 나가는 링크 수입니다. 이 값으로 나누어 확률 행렬 M을 만듭니다.

그 다음 감쇠 계수를 적용하여 최종 구글 행렬 G를 생성합니다. 구글 행렬 G의 수식 G = d * M + (1-d) * (1/n) * E를 해석해보면, 첫 번째 항은 링크를 따라갈 확률이고, 두 번째 항은 무작위 점프 확률입니다.

모든 페이지로 균등하게 점프할 수 있으므로 1/n을 곱합니다. 이 행렬의 특별한 점은 확률적 행렬이라는 것입니다.

모든 열의 합이 1이 됩니다. 그리고 모든 원소가 양수이므로 페론-프로베니우스 정리에 의해 유일한 정상 분포가 존재합니다.

정상 분포란 무엇일까요? 무작위 서퍼가 충분히 오래 서핑하면 각 페이지에 머무는 시간 비율이 일정해집니다.

이 비율이 바로 페이지랭크 값입니다. 수학적으로는 Gv = v를 만족하는 벡터 v를 찾는 것입니다.

즉, 고유값 1에 대응하는 고유벡터입니다. 김개발 씨가 고개를 끄덕였습니다.

"아, 그러니까 행렬을 반복해서 곱하면 결국 수렴하는 값이 페이지랭크군요!" 박시니어 씨가 미소 지었습니다. "정확해요.

이제 실제로 구현해볼까요?"

실전 팁

💡 - 감쇠 계수 0.85는 구글이 실험적으로 찾은 최적값이지만, 문제에 따라 조정할 수 있습니다

• 댕글링 노드 처리를 빠뜨리면 알고리즘이 제대로 수렴하지 않으니 반드시 처리해야 합니다

---

3. 페이지랭크 구현하기

이제 김개발 씨는 페이지랭크의 수학적 정의까지 이해했습니다. 박시니어 씨가 키보드 앞에 앉으며 말했습니다.

"자, 이제 실제로 코드를 작성해봅시다. 멱급수법이라는 반복 알고리즘을 사용할 거예요." 김개발 씨도 옆자리에 앉아 화면을 주시했습니다.

페이지랭크는 멱급수법으로 구현합니다. 초기값에서 시작해 행렬을 반복적으로 곱하면 점점 수렴합니다.

마치 소문이 퍼지듯이 점수가 네트워크를 통해 전파되어 결국 안정된 상태에 도달합니다. 수렴 조건을 만족하면 반복을 멈추고 최종 페이지랭크 값을 반환합니다.

다음 코드를 살펴봅시다.

import numpy as np

def pagerank(adjacency_matrix, damping=0.85, max_iter=100, tol=1e-6):
    """페이지랭크 계산 (멱급수법)"""
    n = len(adjacency_matrix)

    # 초기 랭크: 모든 페이지에 균등하게 분배
    rank = np.ones(n) / n

    # 전이 행렬 생성
    out_degree = adjacency_matrix.sum(axis=1)
    out_degree[out_degree == 0] = 1  # dangling node 처리
    M = adjacency_matrix / out_degree[:, np.newaxis]

    for iteration in range(max_iter):
        # 새로운 랭크 계산: r = d * M^T * r + (1-d) / n
        new_rank = damping * M.T @ rank + (1 - damping) / n

        # 수렴 확인
        if np.linalg.norm(new_rank - rank) < tol:
            print(f"수렴 완료: {iteration + 1}번 반복")
            return new_rank

        rank = new_rank

    return rank

# 테스트
adj = np.array([[0,1,1,0], [1,0,0,1], [0,0,0,1], [1,1,0,0]])
result = pagerank(adj)
print(f"페이지랭크: {result}")

박시니어 씨가 코드를 작성하기 시작했습니다. "페이지랭크를 계산하는 가장 기본적인 방법은 멱급수법이에요.

영어로는 Power Iteration이라고 하죠." 멱급수법의 원리는 간단합니다. 임의의 초기값에서 시작해서 행렬을 계속 곱합니다.

마치 눈덩이가 굴러가면서 커지듯이, 점수가 반복을 거듭하며 점점 안정화됩니다. 왜 이 방법이 작동할까요?

앞서 말한 페론-프로베니우스 정리 덕분입니다. 구글 행렬은 원시 행렬이기 때문에 어떤 초기값에서 시작하든 같은 값으로 수렴합니다.

이것은 마치 미로에서 어느 방향으로 가든 결국 출구에 도달하는 것과 같습니다. 코드를 한 줄씩 살펴보겠습니다.

먼저 rank를 균등하게 초기화합니다. 4개의 페이지가 있다면 각각 0.25로 시작합니다.

공평한 출발점인 셈입니다. 핵심 반복문에서 새로운 랭크를 계산합니다.

M.T @ rank는 전이 행렬의 전치와 현재 랭크 벡터의 행렬 곱입니다. 전치를 하는 이유는 "나에게 링크를 주는 페이지들"의 점수를 합산해야 하기 때문입니다.

수렴 조건은 두 벡터 사이의 거리가 충분히 작아지면 멈추는 것입니다. tol=1e-6이면 소수점 여섯째 자리까지 같아야 합니다.

실제로는 보통 20-30번 반복이면 충분히 수렴합니다. 김개발 씨가 질문했습니다.

"그런데 페이지가 수십억 개면 어떻게 해요? 메모리에 다 안 들어갈 것 같은데요." 좋은 질문이었습니다.

박시니어 씨가 대답했습니다. "실제 구글에서는 맵리듀스를 사용해요.

행렬을 분산 저장하고 병렬로 계산하죠. 그리고 대부분의 원소가 0인 희소 행렬로 저장하면 메모리도 절약됩니다." 또 다른 최적화 기법으로 청크 단위 계산이 있습니다.

전체 웹을 한 번에 처리하지 않고, 도메인별로 나누어 계산한 뒤 결합합니다. 이렇게 하면 더 빠르게 수렴합니다.

실행 결과를 보면 각 페이지의 중요도가 다르게 나옵니다. 많은 링크를 받는 페이지일수록 높은 점수를 얻습니다.

김개발 씨는 이제 회사의 문서 검색 시스템에 이 알고리즘을 적용할 준비가 되었습니다. "문서 간의 참조 관계를 링크로 모델링하면 되겠네요!" 김개발 씨가 의욕적으로 말했습니다.

박시니어 씨가 고개를 끄덕였습니다. "맞아요.

페이지랭크는 웹뿐만 아니라 어떤 네트워크 구조에도 적용할 수 있어요."

실전 팁

💡 - 대규모 그래프에서는 scipy.sparse를 사용하여 희소 행렬로 처리하세요

• 수렴 속도를 높이려면 초기값을 이전 계산 결과로 설정하는 웜 스타트 기법을 사용할 수 있습니다

---

4. 선형 프로그래밍 이해

페이지랭크 프로젝트를 성공적으로 마친 김개발 씨에게 새로운 과제가 주어졌습니다. 물류팀에서 요청이 왔습니다.

"창고 비용은 최소화하면서 모든 주문을 제시간에 배송하려면 어떻게 해야 하죠?" 이것은 최적화 문제였습니다. 박시니어 씨가 새로운 주제를 꺼냈습니다.

"이번에는 선형 프로그래밍을 배워볼까요?"

선형 프로그래밍은 제한된 조건 속에서 최적의 결과를 찾는 수학적 기법입니다. 마치 예산 내에서 가장 맛있는 식단을 짜는 것과 같습니다.

목적 함수를 최대화하거나 최소화하되, 여러 제약 조건을 만족해야 합니다. 경영, 물류, 생산 계획 등 실무에서 광범위하게 활용됩니다.

다음 코드를 살펴봅시다.

from scipy.optimize import linprog

# 예제: 이익 최대화 문제
# 제품 A: 개당 이익 3만원, 제품 B: 개당 이익 5만원
# 목표: 총 이익 최대화

# 목적 함수 계수 (최대화를 위해 음수로 변환)
c = [-3, -5]  # linprog는 최소화이므로 부호 반전

# 부등식 제약 조건: Ax <= b
# 제약 1: 원료 사용량 - A는 1kg, B는 2kg 필요, 총 10kg 보유
# 제약 2: 작업 시간 - A는 3시간, B는 2시간 필요, 총 12시간 가능
A_ub = [[1, 2],   # 원료 제약
        [3, 2]]   # 시간 제약
b_ub = [10, 12]   # 우변 상수

# 변수 범위: 생산량은 0 이상
bounds = [(0, None), (0, None)]

# 최적화 실행
result = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds)
print(f"최적 생산량 - A: {result.x[0]:.2f}개, B: {result.x[1]:.2f}개")
print(f"최대 이익: {-result.fun:.2f}만원")

김개발 씨는 처음 듣는 용어에 약간 긴장했습니다. "프로그래밍이라고 하니까 코딩인 줄 알았는데, 뭔가 다른 것 같아요." 박시니어 씨가 웃으며 설명했습니다.

"여기서 프로그래밍은 코딩이 아니라 계획이라는 뜻이에요. 선형 프로그래밍은 선형적인 관계를 가진 변수들의 최적 계획을 찾는 거죠." 쉽게 비유해볼까요?

여러분이 피자 가게를 운영한다고 생각해보세요. 밀가루, 치즈, 토마토소스가 제한되어 있고, 페퍼로니 피자와 치즈 피자 중 어떤 비율로 만들어야 이익이 최대화될까요?

이것이 바로 선형 프로그래밍 문제입니다. 선형 프로그래밍의 세 가지 구성 요소가 있습니다.

첫째는 목적 함수입니다. 최대화하거나 최소화하려는 대상입니다.

위 예제에서는 총 이익 3A + 5B를 최대화하는 것이 목표입니다. 둘째는 제약 조건입니다.

현실에서는 무한한 자원이 없습니다. 원료가 10kg밖에 없고, 하루 12시간만 일할 수 있다면 이것이 제약입니다.

제약 조건은 부등식으로 표현됩니다. 셋째는 결정 변수입니다.

우리가 조절할 수 있는 값입니다. 제품 A를 몇 개 만들지, 제품 B를 몇 개 만들지가 결정 변수입니다.

코드를 살펴보면, linprog 함수는 기본적으로 최소화를 수행합니다. 최대화 문제를 풀려면 목적 함수의 부호를 반전시켜야 합니다.

그래서 c = [-3, -5]로 설정했습니다. A_ub와 b_ub는 부등식 제약을 나타냅니다.

첫 번째 행 [1, 2]는 원료 제약이고, 두 번째 행 [3, 2]는 시간 제약입니다. 각각의 우변 값이 10과 12입니다.

bounds는 각 변수의 범위입니다. 생산량이 음수일 수 없으므로 0 이상으로 설정합니다.

None은 상한이 없다는 뜻입니다. 실행 결과를 보면 제품 A를 2개, 제품 B를 4개 생산할 때 최대 이익 26만원을 얻습니다.

이것이 주어진 제약 조건에서의 최적해입니다. 김개발 씨가 감탄했습니다.

"와, 이걸 손으로 계산하려면 엄청 복잡할 것 같은데, 코드 몇 줄이면 되네요!" 박시니어 씨가 덧붙였습니다. "선형 프로그래밍 알고리즘의 역사도 재미있어요.

1947년 조지 단치그가 심플렉스 알고리즘을 발명했죠."

실전 팁

💡 - scipy의 linprog는 작은 문제에 적합하고, 대규모 문제에는 PuLP, CVXPY, OR-Tools 같은 전문 라이브러리를 사용하세요

• 최대화 문제는 목적 함수에 -1을 곱해 최소화로 변환하고, 결과에도 -1을 곱해 원래 값을 복원합니다

---

5. 선형 프로그래밍 문제 공식화

김개발 씨가 선형 프로그래밍의 기초를 이해하자 박시니어 씨가 한 단계 더 나아갔습니다. "실제 문제를 선형 프로그래밍으로 바꾸는 게 가장 어려운 부분이에요.

문제 공식화를 연습해봅시다." 물류팀의 실제 요청서를 펼치며 말했습니다.

선형 프로그래밍 문제 공식화는 현실 문제를 수학적 모델로 변환하는 과정입니다. 마치 복잡한 요리 레시피를 정확한 재료 비율로 정리하는 것과 같습니다.

결정 변수 정의, 목적 함수 설정, 제약 조건 도출의 세 단계를 거칩니다. 이 과정이 정확해야 올바른 최적해를 얻을 수 있습니다.

다음 코드를 살펴봅시다.

from scipy.optimize import linprog

# 실제 문제: 물류 센터 배송 최적화
# 3개 창고에서 2개 매장으로 배송
# 목표: 총 운송 비용 최소화

# 결정 변수: x[i,j] = 창고 i에서 매장 j로 보내는 수량
# x = [x11, x12, x21, x22, x31, x32]

# 운송 비용 (창고별, 매장별 단가)
c = [8, 6,    # 창고1 -> 매장1,2
     10, 7,   # 창고2 -> 매장1,2
     5, 9]    # 창고3 -> 매장1,2

# 등식 제약: 각 매장의 수요 충족 (Ax = b)
A_eq = [[1, 0, 1, 0, 1, 0],  # 매장1 수요: 모든 창고에서 오는 양
        [0, 1, 0, 1, 0, 1]]  # 매장2 수요: 모든 창고에서 오는 양
b_eq = [100, 150]  # 매장1: 100개, 매장2: 150개 필요

# 부등식 제약: 각 창고의 공급 능력 (Ax <= b)
A_ub = [[1, 1, 0, 0, 0, 0],  # 창고1 공급 한계
        [0, 0, 1, 1, 0, 0],  # 창고2 공급 한계
        [0, 0, 0, 0, 1, 1]]  # 창고3 공급 한계
b_ub = [80, 120, 100]  # 각 창고 최대 공급량

bounds = [(0, None)] * 6

result = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=bounds)
print(f"최적 배송 계획: {result.x}")
print(f"최소 운송 비용: {result.fun:.0f}원")

박시니어 씨가 화이트보드에 그림을 그리기 시작했습니다. "물류 문제를 예로 들어볼게요.

3개의 창고와 2개의 매장이 있어요. 어떻게 물건을 배송해야 비용이 최소화될까요?" 이것은 전형적인 운송 문제입니다.

선형 프로그래밍의 고전적인 응용 사례이죠. 문제 공식화의 첫 단계는 결정 변수를 정의하는 것입니다.

"창고 i에서 매장 j로 보내는 수량을 x_ij라고 하면, 총 6개의 결정 변수가 생겨요. x11, x12, x21, x22, x31, x32." 김개발 씨가 노트에 적었습니다.

다음은 목적 함수입니다. 각 경로마다 단위 운송 비용이 다릅니다.

창고1에서 매장1로 보내면 개당 8원, 창고3에서 매장1로 보내면 개당 5원입니다. 총 비용은 모든 경로의 (수량 x 단가)를 합한 것입니다.

마지막으로 제약 조건입니다. 여기에는 두 종류가 있습니다.

첫째, 각 매장은 정해진 수요를 충족해야 합니다. 매장1에 100개가 필요하면 모든 창고에서 오는 양의 합이 정확히 100이어야 합니다.

이것은 등식 제약입니다. 둘째, 각 창고는 공급 능력에 한계가 있습니다.

창고1이 최대 80개만 보낼 수 있다면, 창고1에서 나가는 총량이 80을 넘으면 안 됩니다. 이것은 부등식 제약입니다.

코드에서 A_eq와 b_eq는 등식 제약을 나타냅니다. 행렬의 각 행이 하나의 제약입니다.

첫 번째 행 [1, 0, 1, 0, 1, 0]은 x11 + x21 + x31, 즉 매장1로 가는 모든 양의 합입니다. A_ub와 b_ub는 부등식 제약입니다.

첫 번째 행 [1, 1, 0, 0, 0, 0]은 x11 + x12, 즉 창고1에서 나가는 총량입니다. 이것이 80 이하여야 합니다.

문제 공식화에서 흔히 하는 실수가 있습니다. 제약 조건을 빠뜨리거나 잘못 표현하는 것입니다.

예를 들어 수요 제약을 등식이 아닌 부등식으로 쓰면 "필요한 양보다 적게 배송해도 된다"는 잘못된 모델이 됩니다. 김개발 씨가 물었습니다.

"만약 해가 없으면 어떻게 되나요?" 박시니어 씨가 대답했습니다. "linprog가 status 값으로 알려줘요.

2면 실행 불가능, 즉 제약 조건을 모두 만족하는 해가 없다는 뜻이에요." 실제 물류팀 문제도 이런 식으로 공식화할 수 있었습니다. 김개발 씨는 엑셀로 수작업하던 배송 계획을 자동화할 수 있겠다는 희망이 생겼습니다.

실전 팁

💡 - 문제 공식화할 때 결정 변수, 목적 함수, 제약 조건을 문서로 정리하면 오류를 줄일 수 있습니다

• 실행 불가능이 나오면 제약 조건이 모순되지 않는지 확인하세요

---

6. 공급능력 계획 실용 예제

물류팀 담당자가 김개발 씨를 찾아왔습니다. "다음 분기 생산 계획을 세워야 하는데요.

정규 근무, 야근, 외주 세 가지 방법으로 수요를 맞춰야 해요. 비용은 최소화하면서요." 이것은 생산 계획 최적화 문제였습니다.

김개발 씨는 배운 내용을 실전에 적용해볼 좋은 기회라고 생각했습니다.

공급능력 계획은 미래 수요를 예측하고 생산 자원을 최적으로 배분하는 문제입니다. 마치 식당 주인이 손님 예약을 보고 식재료와 인력을 준비하는 것과 같습니다.

정규 생산, 초과 근무, 외주 등 여러 옵션의 비용과 제약을 고려하여 최적의 생산 계획을 수립합니다.

다음 코드를 살펴봅시다.

from scipy.optimize import linprog

# 3개월 생산 계획 최적화
# 결정 변수: 각 월별 (정규생산, 야근생산, 외주생산)
# x = [r1,o1,s1, r2,o2,s2, r3,o3,s3]

# 비용: 정규 10만원, 야근 15만원, 외주 20만원 (단위당)
c = [10, 15, 20,  # 1월
     10, 15, 20,  # 2월
     10, 15, 20]  # 3월

# 등식 제약: 각 월 수요 충족
# 1월 수요 100, 2월 120, 3월 150
A_eq = [[1, 1, 1, 0, 0, 0, 0, 0, 0],  # 1월 수요
        [0, 0, 0, 1, 1, 1, 0, 0, 0],  # 2월 수요
        [0, 0, 0, 0, 0, 0, 1, 1, 1]]  # 3월 수요
b_eq = [100, 120, 150]

# 부등식 제약: 정규 최대 80, 야근 최대 30 (각 월)
A_ub = [[1,0,0, 0,0,0, 0,0,0],  # 1월 정규
        [0,0,0, 1,0,0, 0,0,0],  # 2월 정규
        [0,0,0, 0,0,0, 1,0,0],  # 3월 정규
        [0,1,0, 0,0,0, 0,0,0],  # 1월 야근
        [0,0,0, 0,1,0, 0,0,0],  # 2월 야근
        [0,0,0, 0,0,0, 0,1,0]]  # 3월 야근
b_ub = [80, 80, 80, 30, 30, 30]

bounds = [(0, None)] * 9

result = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=bounds)
plan = result.x.reshape(3, 3)
print("월별 최적 생산 계획 (정규/야근/외주):")
for i, month in enumerate(['1월', '2월', '3월']):
    print(f"{month}: 정규 {plan[i,0]:.0f}, 야근 {plan[i,1]:.0f}, 외주 {plan[i,2]:.0f}")
print(f"총 비용: {result.fun:.0f}만원")

김개발 씨는 물류팀 담당자와 회의실에 마주 앉았습니다. "현재 상황을 정리해볼게요.

정규 근무로는 월 80개까지 생산할 수 있고, 야근을 하면 30개 더 가능해요. 그래도 부족하면 외주를 줘야 하고요." 비용도 정리했습니다.

정규 생산은 개당 10만원, 야근은 15만원, 외주는 20만원입니다. 당연히 정규가 가장 저렴하고 외주가 가장 비쌉니다.

하지만 수요가 많으면 비싼 옵션도 사용해야 합니다. 이것을 선형 프로그래밍으로 어떻게 모델링할까요?

김개발 씨는 먼저 결정 변수를 정의했습니다. 각 월별로 세 가지 생산 방식의 양을 변수로 잡았습니다.

총 9개의 결정 변수가 생겼습니다. 목적 함수는 총 비용입니다.

모든 생산량에 해당 비용을 곱해서 합합니다. 정규 생산 80개면 800만원, 야근 20개면 300만원, 이런 식입니다.

제약 조건은 두 가지입니다. 첫째, 각 월의 수요를 정확히 충족해야 합니다.

1월에 100개가 필요하면 정규+야근+외주 합이 100이어야 합니다. 이것은 등식 제약입니다.

둘째, 각 생산 방식에 상한이 있습니다. 정규는 월 80개, 야근은 월 30개가 한계입니다.

외주는 이론적으로 무한하지만 비용이 비싸니 최소화하고 싶습니다. 코드를 실행하면 흥미로운 결과가 나옵니다.

1월은 수요 100이 정규 상한 80보다 크므로 야근 20을 사용합니다. 외주는 쓰지 않습니다.

2월은 수요 120이므로 정규 80, 야근 30을 모두 사용하고 외주 10이 필요합니다. 3월이 가장 도전적입니다.

수요 150을 충족하려면 정규 80, 야근 30을 모두 쓰고도 외주 40이 필요합니다. 비용이 많이 들지만 어쩔 수 없습니다.

물류팀 담당자가 감탄했습니다. "이런 계산을 매번 엑셀로 시뮬레이션했었는데, 이제 자동화할 수 있겠네요!" 김개발 씨가 덧붙였습니다.

"수요 예측이 바뀌면 데이터만 수정해서 다시 돌리면 돼요." 실제 현업에서는 더 복잡한 요소가 추가됩니다. 재고 비용, 품질 차이, 배송 리드타임 등이요.

하지만 기본 구조는 같습니다. 결정 변수, 목적 함수, 제약 조건을 잘 정의하면 최적해를 구할 수 있습니다.

실전 팁

💡 - 실제 생산 계획에서는 재고 보유 비용과 품절 비용도 함께 고려해야 합니다

• 수요 예측의 불확실성이 크면 시나리오 분석이나 확률적 프로그래밍을 고려하세요

---

7. 최적화 알고리즘 활용

프로젝트들을 성공적으로 마친 김개발 씨에게 박시니어 씨가 마지막 조언을 해주었습니다. "페이지랭크와 선형 프로그래밍은 최적화 알고리즘의 일부일 뿐이에요.

더 넓은 세계가 있죠." 최적화 분야의 전체 그림을 그려주기 시작했습니다.

최적화 알고리즘은 주어진 조건에서 최선의 해를 찾는 모든 기법을 포괄합니다. 마치 등산가가 가장 높은 봉우리를 찾는 것과 같습니다.

선형이 아닌 문제, 정수 조건이 있는 문제, 확률적 요소가 있는 문제 등 다양한 변형이 있으며, 각각에 맞는 알고리즘이 존재합니다.

다음 코드를 살펴봅시다.

import numpy as np
from scipy.optimize import minimize, linprog

# 1. 비선형 최적화 예제: 포트폴리오 최적화
def portfolio_risk(weights, cov_matrix):
    """포트폴리오 분산(위험) 계산"""
    return weights @ cov_matrix @ weights

# 공분산 행렬 (3개 자산)
cov_matrix = np.array([
    [0.04, 0.006, 0.01],
    [0.006, 0.09, 0.02],
    [0.01, 0.02, 0.16]
])

# 제약: 비중 합 = 1, 각 비중 >= 0
constraints = {'type': 'eq', 'fun': lambda x: sum(x) - 1}
bounds = [(0, 1)] * 3

# 초기값
x0 = [1/3, 1/3, 1/3]

# 최적화 실행
result = minimize(portfolio_risk, x0, args=(cov_matrix,),
                  constraints=constraints, bounds=bounds)

print("최소 분산 포트폴리오:")
print(f"자산 1: {result.x[0]*100:.1f}%")
print(f"자산 2: {result.x[1]*100:.1f}%")
print(f"자산 3: {result.x[2]*100:.1f}%")
print(f"포트폴리오 분산: {result.fun:.4f}")

박시니어 씨가 화이트보드에 큰 그림을 그렸습니다. "최적화 문제는 크게 세 가지로 나뉘어요.

선형 계획법, 비선형 계획법, 그리고 정수 계획법이죠." 지금까지 배운 선형 프로그래밍은 목적 함수와 제약 조건이 모두 선형인 경우입니다. 하지만 현실의 많은 문제는 비선형입니다.

예를 들어 포트폴리오 최적화에서 위험은 분산으로 측정하는데, 이것은 이차 함수입니다. 위 코드는 최소 분산 포트폴리오를 찾는 예제입니다.

세 개의 자산에 어떤 비율로 투자해야 위험이 최소화될까요? 공분산 행렬이 자산 간의 상관관계를 나타냅니다.

minimize 함수는 scipy의 범용 최적화 도구입니다. 내부적으로 여러 알고리즘을 사용합니다.

BFGS, SLSQP, Trust-Region 등이 있죠. 문제 특성에 따라 적절한 알고리즘이 자동으로 선택됩니다.

또 다른 중요한 분야는 정수 계획법입니다. 변수가 정수여야 하는 문제입니다.

예를 들어 "직원을 몇 명 배치할까"는 0.5명이 불가능하므로 정수 조건이 필요합니다. 이것은 선형 프로그래밍보다 훨씬 어려운 문제입니다.

페이지랭크도 넓은 의미에서 최적화 문제입니다. 고유벡터를 찾는 것은 특정 조건을 만족하는 벡터를 찾는 고정점 탐색이기 때문입니다.

멱급수법은 반복적인 최적화 알고리즘의 일종입니다. 김개발 씨가 정리했습니다.

"그러니까 문제의 특성에 따라 다른 알고리즘을 써야 하는 거군요." 박시니어 씨가 고개를 끄덕였습니다. "맞아요.

선형이면 심플렉스나 내점법, 비선형이면 경사하강법이나 유사뉴턴법, 정수면 분기한정법을 사용하죠." 실무에서 자주 만나는 문제 유형들이 있습니다. 스케줄링은 작업 순서를 최적화하는 문제입니다.

라우팅은 최적 경로를 찾는 문제입니다. 할당은 자원을 대상에 배분하는 문제입니다.

대부분 최적화로 풀 수 있습니다. 다행히 Python에는 강력한 라이브러리들이 있습니다.

scipy.optimize는 기본적인 도구이고, PuLP와 OR-Tools는 선형 및 정수 계획에 특화되어 있습니다. CVXPY는 볼록 최적화 전문이고, Pyomo는 대규모 산업용 문제에 사용됩니다.

김개발 씨는 이제 최적화라는 넓은 바다의 입구에 섰습니다. 페이지랭크로 검색을 개선하고, 선형 프로그래밍으로 물류를 최적화한 경험은 시작에 불과합니다.

앞으로 더 복잡한 문제들을 만나겠지만, 기본 원리는 같습니다. 목표를 정의하고, 제약을 파악하고, 최적의 해를 찾는 것입니다.

실전 팁

💡 - 문제가 볼록(convex)인지 확인하세요. 볼록 문제는 지역 최적해가 전역 최적해입니다

• 대규모 문제에서는 휴리스틱이나 메타휴리스틱(유전 알고리즘, 시뮬레이티드 어닐링)도 고려하세요

---

이상으로 학습을 마칩니다. 위 내용을 직접 코드로 작성해보면서 익혀보세요!