[이론] 선형 계획법

선형 계획법(Linear Programming)은 제한된 자원을 효율적으로 활용하여 목적 함수를 최적화하는 수학적 기법입니다. 이 방법은 다양한 분야에서 활용되며, 특히 경영, 경제, 공학 등에서 중요하게 사용됩니다.

선형 계획법의 주요 구성 요소

1. 의사결정 변수: 문제에서 결정해야 할 미지수를 나타냅니다.
2. 목적 함수: 최대화하거나 최소화하고자 하는 대상을 수학적으로 표현한 식입니다.
3. 제약 조건: 문제의 제한 사항을 나타내는 부등식이나 방정식입니다.

선형 계획법의 특징

• 모든 관계가 선형(1차 함수)으로 표현됩니다.
• 목적 함수와 제약 조건이 모두 선형 관계여야 합니다.
• 최적해는 가능 영역의 꼭짓점이나 모서리에서 발생합니다.

해결 방법

1. 그래프 방법: 2차원 문제의 경우 그래프를 그려 시각적으로 해결할 수 있습니다.
2. 심플렉스 방법(Simplex Method): 대부분의 선형 계획 문제를 해결하는 데 사용되는 알고리즘입니다.

선형 계획법의 응용 분야

• 생산 및 제조 분야
• 재무 및 투자 계획
• 광고 전략 수립
• 인력 배치 및 훈련
• 물류 및 유통 최적화
• 농업 계획
• 군사 작전 계획
• 식단 문제 해결

선형 계획법의 장단점

장점:

• 복잡한 문제를 단순화하여 해결할 수 있습니다.
• 컴퓨터를 이용한 빠른 계산이 가능합니다.

단점:

• 현실 세계의 모든 관계를 선형으로 표현하기 어려울 수 있습니다.
• 대규모 문제의 경우 계산 복잡도가 증가할 수 있습니다.

선형 계획법은 다양한 최적화 문제를 해결하는 데 유용한 도구이며, 특히 자원의 효율적 배분과 비용 최소화, 이익 최대화 등의 문제에 널리 적용됩니다.

참고 자료

https://greatjoy.tistory.com/29

[선형대수] 선형계획법(Linear Programming)과 Simplex method

 

https://blog.naver.com/ksj8406/221431564032

선형계획법

 

https://blog.naver.com/jerid1973/222592177432

6. 선형 계획법

 

---

마르코프 체인

마르코프 체인(Markov Chain)은 특정 확률적 규칙에 따라 한 상태에서 다른 상태로 전이하는 수학적 시스템입니다. 이 체인의 가장 중요한 특징은 "무기억성(memorylessness)"으로, 현재 상태에서 미래 상태로의 전이 확률은 오직 현재 상태에만 의존하고 과거 경로와는 무관합니다.

마르코프 체인의 주요 특성

마르코프 체인은 확률적 과정이지만, 일반적인 확률 과정과 달리 "무기억성"을 가집니다. 즉, 미래 행동의 확률은 현재 상태에 이르게 된 과정과는 독립적입니다. 시스템이 현재 어떤 상태에 있는지만 알면 미래 상태를 예측할 수 있으며, 이 예측은 전체 과정의 역사를 알고 있을 때와 동일합니다.

마르코프 체인의 유형

1. 유한 마르코프 체인: 유한한 수의 상태를 가진 마르코프 체인입니다. 상태 간 전이 확률은 고정되어 있으며, 시스템은 결국 각 상태에 있을 확률이 일정해지는 정상 상태에 도달합니다.
2. 무한 마르코프 체인: 무한한 수의 상태를 가진 마르코프 체인입니다. 상태 간 전이 확률은 고정되어 있지만, 시스템이 정상 상태에 도달하지 않을 수 있습니다.
3. 연속 시간 마르코프 체인(CTMC): 상태 간 전이가 이산적 시간 간격이 아닌 무작위 시간에 발생하는 마르코프 체인입니다. 전이 확률은 확률이 아닌 비율 함수로 정의됩니다.
4. 이산 시간 마르코프 체인(DTMC): 상태 간 전이가 이산적 시간 간격으로 발생하는 마르코프 체인입니다. 전이 확률은 전이 행렬로 정의됩니다.

마르코프 체인의 속성

• 비가역성(Irreducibility): 유한한 단계 내에서 어떤 상태에서든 다른 상태로 도달할 수 있을 때 마르코프 체인은 비가역적입니다.
• 비주기성(Aperiodicity): 시작 상태와 관계없이 유한한 단계 내에서 어떤 상태에서든 다른 상태로 도달할 수 있을 때 마르코프 체인은 비주기적입니다.
• 재귀성(Recurrence): 유한한 단계 내에서 특정 상태로 돌아올 수 있을 때 그 상태는 재귀적입니다.
• 일시성(Transience): 유한한 단계 내에서 특정 상태로 돌아올 수 없을 때 그 상태는 일시적입니다.
• 에르고딕성(Ergodicity): 마르코프 체인이 비가역적이고 비주기적이며, 시스템의 장기적 행동이 시작 상태와 독립적일 때 에르고딕합니다.
• 가역성(Reversibility): 한 상태에서 다른 상태로 전이할 확률이 그 상태에서 원래 상태로 돌아올 확률과 같을 때 마르코프 체인은 가역적입니다.

마르코프 체인의 응용 분야

마르코프 체인은 다양한 분야에서 활용됩니다:

• 마케팅: 사용자가 전환하기 전에 상호작용한 다양한 마케팅 채널에 대한 크레딧 할당
• 금융: 현재 시장 상황을 기반으로 다음 날 시장이 강세인지 약세인지 예측
• 생물학: 동물 개체군 진화의 단계를 한 상태에서 다른 상태로의 전이로 모델링
• 공학: 다양한 응용 분야에서 활용
• 물리학: 열역학 및 통계 역학에서 광범위하게 사용
• 자연어 처리: 텍스트 생성 및 음성 인식

마르코프 체인은 실제 세계의 많은 과정을 모델링할 수 있도록 설계될 수 있어 다양한 분야와 도메인에서 응용됩니다. 이는 현실 세계의 복잡한 시스템을 단순화하고 분석하는 데 매우 유용한 도구입니다.

참고 자료

https://brilliant.org/wiki/markov-chains/

Markov Chains | Brilliant Math & Science Wiki

https://www.shiksha.com/online-courses/articles/introduction-to-markov-chain/

Markov Chain: Types, Properties and Applications - Shiksha Online