--- title: "Stochastic programming — 확률적 프로그래밍" source: "https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D" wiki: "systems-analysis.info/int" article: "Stochastic_programming_—_확률적_프로그래밍" language: "ko" categories: - "Category:Korean" - "Category:Operations research" - "Category:Probability theory" revision_id: 6923 wiki_created_at: 2026-09-07T00:13:19Z wiki_modified_at: 2026-09-07T00:13:19Z downloaded_at: 2026-09-07T23:16:26Z --- # Stochastic programming — 확률적 프로그래밍 **확률적 프로그래밍** (영어: *stochastic programming*) — 모델의 일부 매개변수가 정확히 알려져 있지 않고 알려졌거나 추정된 확률 분포를 가진 확률 변수로 표현되는 불확실성 조건에서 최적화 문제를 해결하기 위한 모델과 방법을 개발하는 수학적 프로그래밍의 한 분야이다[\[1\]](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_note-shapiro2009-1)[\[2\]](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_note-birge2011-2). 모든 데이터가 주어진 상수로 간주되는 결정론적 문제와 달리, 확률적 프로그래밍은 어떤 통계적 의미에서 최적인 해(또는 의사결정 정책)를 찾는 것을 목표로 한다. 가장 일반적으로 이는 목적 함수의 기댓값을 최소화하거나 최대화하는 것을 의미한다[\[1\]](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_note-shapiro2009-1). 핵심 아이디어는 확률적 매개변수의 모든 가능한 실현에 대해 "평균적으로" 최선인 의사결정 정책을 찾는 것으로, 이는 유사한 조건에서 반복적으로 결정이 내려지는 문제(예: 재고 관리나 전력 시스템 관리)에 특히 중요하다[\[3\]](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_note-ru-wiki-sp-3). ## 문제의 수학적 정식화 일반적인 형태의 확률적 프로그래밍 문제는 다음과 같이 정식화할 수 있다: $\min\limits_{x \in X}{\mathbb{E}}\lbrack f(x,\xi)\rbrack$ 여기서: - $x$ — 결정해야 할 제어 변수(결정)의 벡터. - $X$ — 결정론적 제약 조건에 의해 정의되는 $x$의 허용 가능한 결정 집합. - $\xi$ — 문제의 불확실한 매개변수(예: 수요, 가격, 기상 조건)를 나타내는 확률 벡터. - $f(x,\xi)$ — 채택된 결정 $x$과 확률 벡터 $\xi$의 실현 모두에 의존하는 목적 함수. - ${\mathbb{E}}\lbrack \cdot \rbrack$ — 벡터 $\xi$의 확률 분포에 대해 계산되는 기댓값 연산자. 다단계 확률적 모델의 기초가 되는 가장 중요한 원리는 **비선행성 원리** (영어: *non-anticipativity principle*)이다. 이 원리는 어떤 단계에서 내려지는 결정이 그 시점까지 이용 가능한 정보에만 의존할 수 있으며 "미래를 내다볼" 수 없다는 것을 의미한다[\[2\]](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_note-birge2011-2). ### 재결정권이 있는 2단계 문제 가장 일반적인 모델은 **재결정권이 있는 2단계 확률적 프로그래밍** (영어: *two-stage stochastic program with recourse*)이다[\[1\]](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_note-shapiro2009-1). 의사결정 과정은 두 단계로 나뉜다: 1. **1단계:** "지금 여기에서"(*here-and-now*) 결정이 내려진다 — 벡터 $x$이 결정된다. 이 결정은 확률 벡터 $\xi$의 구체적인 실현이 알려지기 전에 이루어져야 한다. 2. **2단계:** 확률적 사건이 발생한 후, 1단계 결정 $x$과 결과 $\xi$의 조합으로 인해 발생한 부정적 결과를 최소화하거나 유리한 기회를 활용하기 위한 수정 또는 보완 결정(*recourse decision*) — 벡터 $y(\xi)$이 내려진다. 수학적으로 2단계 확률적 선형 프로그래밍 문제는 다음과 같이 정식화된다: $\min\limits_{x \in {\mathbb{R}}^{n_{1}}}\{ c^{T}x + {\mathbb{E}}_{\xi}\lbrack Q(x,\xi)\rbrack\}$ 1단계 제약 조건: $Ax = b,x \geq 0$. 여기서 $Q(x,\xi)$은 **보완 함수**(*recourse function*)로, 2단계 문제의 최적값을 나타낸다: $Q(x,\xi) = \min\limits_{y \in {\mathbb{R}}^{n_{2}}}\{ q(\xi)^{T}y \mid T(\xi)x + Wy = h(\xi),y \geq 0\}$ 여기서 $\xi$은 매개변수 $q(\xi),T(\xi)$과 $h(\xi)$를 포함하는 확률 벡터이고, $c,A,b$과 $W$는 결정론적 매개변수이다[\[2\]](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_note-birge2011-2). ## 주요 성질 및 정리 - **볼록성**: 이론의 근본적인 결과 중 하나는, 2단계 확률적 선형 프로그래밍 문제에서 기대 보완 함수 $Q(x) = {\mathbb{E}}_{\xi}\lbrack Q(x,\xi)\rbrack$가 볼록 함수라는 것이다. 이 성질은 매우 중요한데, 1단계 전체 문제가 볼록 프로그래밍 문제임을 보장하며, 이에 대해 효율적인 해법이 존재하고 전역 최적해와 지역 최적해가 일치하기 때문이다[\[1\]](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_note-shapiro2009-1). - **결정론적 등가 문제**: 확률 벡터 $\xi$이 확률 $p_{1},\ldots,p_{K}$을 가진 유한 개의 가능한 실현(시나리오) $\xi_{1},\ldots,\xi_{K}$을 가지는 경우, 확률적 프로그래밍 문제를 하나의 큰 결정론적 최적화 문제로 재정식화할 수 있다. 이 경우 기댓값은 모든 시나리오에 대한 가중 합으로 대체된다. 그러나 이 문제의 크기는 시나리오 수에 따라 선형적으로 증가하므로, 이는 "차원의 저주"로 이어져 시나리오 수가 많을 경우 계산상 해결 불가능하게 된다[\[2\]](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_note-birge2011-2). ## 강건 최적화와의 비교 확률적 프로그래밍은 불확실성 조건에서의 최적화에 대한 여러 접근법 중 하나이다. 강건 최적화와의 주요 차이점은 불확실성을 모델링하는 방식과 최적성 기준에 있다[\[4\]](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_note-gorissen2015-4). | 기준 | 확률적 최적화 | 강건 최적화 | |---------------|-------------------------------------------------------------------------|----------------------------------------------------------------| | 불확실성 표현 | 매개변수는 알려진 확률 분포를 가진 확률 변수 | 매개변수는 주어진 불확실성 집합에 속하며, 분포는 필요하지 않음 | | 최적성 기준 | 목적 함수의 기댓값 최적화 | 최악의 시나리오에서의 최적화 (미니맥스) | | 해의 성격 | "평균적으로" 최적인 정책으로, 드문 시나리오에서는 허용 불가능할 수 있음 | 모든 실현에 대해 허용 가능함이 보장된 해; 보수적일 수 있음 | 불확실성 조건에서의 최적화 접근법 비교 ## 예시 - **신문 판매원 문제** (영어: *newsvendor problem*): 판매자가 정확한 미래 수요를 알지 못한 채 얼마나 많은 상품을 구입할지 결정해야 하는 고전적인 재고 관리 문제. 해는 과잉 재고로 인한 손실 위험과 부족으로 인한 기회 손실 위험 사이의 균형을 맞춘다. - **농부 문제**: 농부가 수확량에 영향을 미치는 미래 날씨를 알지 못한 채 전체 면적에서 여러 작물에 얼마나 많은 에이커를 배분할지 결정하는 문제. 날씨가 알려진 후, 농부는 수정 조치(예: 잉여분 판매 또는 시장에서 부족한 수확물 추가 구매)를 취할 수 있다[\[5\]](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_note-farmer-problem-uiowa-5). ## 같이 보기 - 수학적 프로그래밍 - 운용 과학 - 강건 최적화 - 동적 프로그래밍 - 제어 이론 ## 각주 [\[1\]](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_note-shapiro2009-1) [\[2\]](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_note-birge2011-2) [\[3\]](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_note-ru-wiki-sp-3) [\[4\]](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_note-gorissen2015-4) [\[5\]](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_note-farmer-problem-uiowa-5) \ 1. ↑ [1.0](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_ref-shapiro2009_1-0) [1.1](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_ref-shapiro2009_1-1) [1.2](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_ref-shapiro2009_1-2) [1.3](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_ref-shapiro2009_1-3) [1.4](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_ref-shapiro2009_1-4) Shapiro, A., Dentcheva, D., & Ruszczyński, A. (2009). *Lectures on Stochastic Programming: Modeling and Theory*. Society for Industrial and Applied Mathematics (SIAM). 2. ↑ [2.0](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_ref-birge2011_2-0) [2.1](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_ref-birge2011_2-1) [2.2](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_ref-birge2011_2-2) [2.3](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_ref-birge2011_2-3) [2.4](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_ref-birge2011_2-4) Birge, J. R., & Louveaux, F. (2011). *Introduction to Stochastic Programming* (2nd ed.). Springer Science+Business Media. 3. ↑ [3.0](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_ref-ru-wiki-sp_3-0) [3.1](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_ref-ru-wiki-sp_3-1) "Стохастическое программирование". *Википедия*. [1] 4. ↑ [4.0](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_ref-gorissen2015_4-0) [4.1](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_ref-gorissen2015_4-1) Gorissen, B. L., Yanıkoğlu, İ., & den Hertog, D. (2015). A practical guide to robust optimization. *Omega, 53*, 124-137. 5. ↑ [5.0](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_ref-farmer-problem-uiowa_5-0) [5.1](https://systems-analysis.info/int/Stochastic_programming_%E2%80%94_%ED%99%95%EB%A5%A0%EC%A0%81_%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D#cite_ref-farmer-problem-uiowa_5-1) Bricker, D. L. *SLPwR: Farmer Problem*. University of Iowa. [2]