문단 (context)
4장에서 우리는 공사 발행 MBS에 대해 발행금액 최대화라는 모델을 수립했다. 이제는 이 모델의 복잡성을 분석한다. 최적화 문제는 목적식과 제약식이 일차식 즉 linear한지 여부, 목적식이나 제약식이 이차 이상의식을 포함하는지 여부에 따라 최적화 문제의 난이도를 결정한다. 목적식과 제약식이 모두 일차식인 선형계획(LP,Linear Programming)의 최적해는 간단하게 나온다. LP 문제에 대해서는 심플렉스 방법(simplex method)이라는 알고리즘이 일반적으로 잘 알려져 있다. 1947년 George Dantzig가 개발한 수리적 알고리즘으로 다양한 조건에서 짧은 시간(polynominal time algorithm)에 최적해를 찾는다.
기계독해 질의응답 4건
| question_id | 질문 | 답변 불가 | 정답 |
|---|---|---|---|
| 923021 | 짧은 시간 최적해를 찾는 알고리즘을 George Dantzig가 언제 개발했지 | 가능 | 1947년 |
| 923022 | George Dantzig가 짧은 시간 최적해를 찾는 알고리즘을 고안한 게 언제야 | 가능 | 1947년 |
| 923023 | 언제 George Dantzig가 짧은 시간 최적해를 찾는 규칙을 만들었니 | 가능 | 1947년 |
| 923024 | George Dantzig가 언제 정확한 최적해를 찾는 규칙을 폐기했어 | 불가 | 1947년 |