무작위 추출로 확률분포의 미지 특성값을 추정하는 방법은 몬테 카를로 시뮬레이션이다.
확률적 요소를 난수로 반복 재현하고, 그 결과의 평균·분포로 기대값이나 확률을 근사한다.
- 병렬 시뮬레이션: 여러 처리기에 계산을 나눠 동시에 수행하는 실행 방식으로, 추정 원리와는 무관하다.
- 연속형 시뮬레이션: 상태가 시간에 따라 연속적으로 변하는 시스템을 미분방정식 등으로 다룬다.
- 이산 사건 시뮬레이션: 사건이 발생하는 시점에만 상태가 바뀌는 시스템을 다루는 모형 구조의 분류다.
- 스프레드시트 시뮬레이션: 구현 도구에 따른 명칭일 뿐 무작위 추출에 의한 추정을 정의하는 용어가 아니다.
주경로는 여러 개일 수 있다.
주경로는 시작점에서 완료점까지 소요시간 합이 가장 긴 경로이며, 길이가 같은 최장 경로가 둘 이상이면 모두 주경로가 된다.
- 가장 짧은 경로라는 설명: 주경로는 가장 긴 경로이다.
- 여유시간이 양의 값이라는 설명: 주경로 위 활동의 여유시간은 0이다.
- 프로젝트를 단축해도 주경로 일정이 변하지 않는다는 설명: 프로젝트 단축은 주경로 활동을 줄여야 가능하므로 주경로 일정이 바뀐다.
- 비용이 가장 많이 드는 활동의 모음이라는 설명: 주경로는 비용이 아니라 소요시간 기준으로 정해진다.
제약조건
목적함수가 제약식 하나와 평행하므로 최적해는 무한개이다.
목적함수 계수가 제약식 과 같아, 최댓값 이 이 제약선 위 실행가능 구간 전체에서 달성된다.
- 최적해가 1개라는 판단: 두 꼭짓점이 모두 최댓값을 내므로 유일해가 아니다.
- 최적해가 2개라는 판단: 두 최적 꼭짓점을 잇는 선분 위의 모든 점이 최적이다.
- 최적해가 3개라는 판단: 선형계획에서는 유한 개의 복수 최적해가 생기지 않는다.
- 최적해가 4개라는 판단: 마찬가지로 최적해가 둘 이상이면 곧 무한히 많다.
포아송 도착이면 도착 간격은 지수분포를 따른다.
단위시간당 도착 수가 평균 인 포아송분포이면, 연속 도착 사이의 간격은 평균 인 지수분포가 된다. 이 분포의 무기억성 덕분에 M/M 모형 분석이 간단해진다.
- 정규분포: 도착 간격은 음수가 될 수 없고 비대칭이므로 해당하지 않는다.
- 이항분포: 고정된 시행 횟수에서 성공 횟수를 세는 이산분포다.
- 베타분포: 유한 구간의 연속분포로 PERT 활동시간 추정에 쓰인다.
- 일양분포: 구간 내 모든 값이 같은 확률을 갖는 분포로 포아송 도착과 무관하다.
결정이 시간 단계마다 이어지고 변수 값이 단계별로 달라지는 문제에는 동적계획법이 적합하다.
동적계획법은 문제를 여러 단계로 나누고 각 단계의 상태에 따른 최적 결정을 재귀적으로 연결해 전체 최적해를 구한다.
- 선형계획법: 선형 목적함수·제약식을 한 시점에서 정적으로 최적화한다.
- 비선형계획법: 목적함수나 제약식이 비선형인 정적 최적화 기법이다.
- 정수계획법: 변수가 정수값을 가져야 하는 문제를 다룬다.
- 목표계획법: 여러 목표의 편차를 우선순위에 따라 최소화하는 다목표 기법이다.
M/M/1에서 시스템이 비어 있을 확률은 이다.
서버가 바쁠 확률, 즉 이용률이 이므로 고객이 한 명도 없을 확률은 그 여사건이다.
- : 서버가 바쁠 확률(이용률)이다.
- : 시스템에 고객이 정확히 한 명 있을 확률 이다.
- : 시스템 내 평균 고객 수 이다.
- : 대기열의 평균 고객 수 이다.
| 가지 | 거리 | 가지 | 거리 | 가지 | 거리 |
|---|---|---|---|---|---|
| O-A | 3 | A-D | 8 | C-E | 5 |
| O-B | 6 | B-C | 1 | D-E | 1 |
| O-C | 5 | B-D | 5 | D-T | 5 |
| A-B | 1 | B-E | 3 | E-T | 8 |
최단 경로는 O-A-B-E-D-T(길이 13)이며, 여기에 포함되지 않는 가지는 B-D이다.
출발점에서 가까운 마디부터 최단거리를 확정한다.
A: 3 (O-A)
B: min(6, 3+1) = 4 (O-A-B)
C: min(5, 4+1) = 5
E: min(4+3, 5+5) = 7 (B-E)
D: min(3+8, 4+5, 7+1) = 8 (E-D)
T: min(8+5, 7+8) = 13 (D-T)
B에서 D로 바로 가면 9이지만 B-E-D로 돌아가면 8이므로 B-D 가지는 쓰이지 않는다.
- O-A: 출발점에서 A로 가는 첫 가지로 최단 경로에 포함된다.
- A-B: O에서 B까지 거리 4로 가는 데 쓰인다.
- B-E: B에서 E로 이어 E까지 거리 7을 만든다.
- D-T: D에서 목적지 T로 가는 마지막 가지다.
우변 상수의 변화가 허용가능 범위를 벗어나면 최적 기저가 바뀌므로, 잠재가격만으로는 목적함수값에 미치는 영향을 알 수 없다.
잠재가격은 제약식 우변 상수를 한 단위 늘릴 때 최적 목적함수값이 변하는 크기로, 현재 최적 기저가 유지되는 범위 안에서만 유효하다.
- 목적함수 비용계수를 증감할 때의 변화라는 설명: 잠재가격은 비용계수가 아니라 우변 상수 변화에 대한 값이다.
- 잠재가격이 0이면 비용계수 증감이 영향이 없다는 설명: 잠재가격 0은 그 제약의 우변을 바꿔도 목적함수값이 변하지 않는다는 뜻이며 비용계수와는 관계없다.
- 비용 최소화에서 잠재가격이 큰 제약을 고른다는 설명: 우변을 늘리면 비용이 잠재가격만큼 변하므로 비용 증가가 작은 쪽을 택해야 경제적이다.
- 잠재가격이 항상 0 이상이라는 설명: 최적화 방향과 부등호 방향에 따라 음수가 될 수 있다.
측량소 내 평균 트럭 수 은 5대이다.
도착률은 시간당 이고, 평균 서비스 시간이 5분이므로 서비스율은 시간당 이다.
- : 평균 체류시간 를 시간 단위로 구한 값이다.
- : 이용률 이다.
- : 서비스율과 도착률의 차 일 뿐이다.
- : 평균 체류시간을 분 단위로 나타낸 값이다.
선형계획법에서 유한한 개수의 복수 최적해는 나올 수 없다.
실행가능영역이 볼록집합이므로 두 점이 최적이면 그 사이 선분 위 모든 점도 같은 목적함수값을 가진다. 따라서 최적해가 둘 이상이면 곧 무한히 많다.
- 유일한 최적해: 최적 꼭짓점이 하나뿐인 일반적인 경우다.
- 무한히 많은 복수 최적해: 목적함수가 최적 경계선과 평행할 때 나타난다.
- 실현가능해가 존재하지 않음: 제약식끼리 모순되면 실행불가능 문제가 된다.
- 목적함수값이 무한대: 실행가능영역이 최적화 방향으로 열려 있으면 비유계 문제가 된다.
매출이 증가할 확률은 0.55이다.
전확률 공식으로 경기가 좋을 때와 나쁠 때를 나눠 더한다. 경기가 나쁠 확률은 0.7이고, 이때 매출이 증가할 확률은 이다.
- : 경기가 좋으면서 매출이 증가하는 경우만 구하고 경기가 나쁠 때의 증가 확률을 빠뜨린 값이다.
- : 경기가 좋을 확률 자체로, 매출 증가 확률과 다르다.

경로 1-3-4-6-7로 보낼 수 있는 양은 경로상 호의 최소 용량인 3이다.
경로의 유량은 가장 작은 용량의 호(병목)가 결정한다. 각 호의 출발 노드 쪽 용량은 1→3이 4, 3→4가 3, 4→6이 4, 6→7이 8이다.
- 0은 경로상 모든 호의 정방향 용량이 양수이므로 해당하지 않는다.
- 4는 1→3, 4→6의 용량일 뿐이며 3→4 호의 용량 3을 넘을 수 없다.
- 8은 마지막 6→7 호의 용량으로, 앞쪽 병목을 무시한 값이다.
- 19는 용량을 모두 더한 값으로, 경로 유량은 합이 아니라 최솟값으로 정해진다.
구간 -20~80 일양분포의 관측치는 (-12, 14, 70)이다.
역변환법으로 난수 을 구간에 선형 변환한다.
- (8, 34, 90): 하한 -20을 더하지 않고 만 계산한 값이다.
- (-2, 24, 80): 첫 관측치부터 변환 결과 -12와 맞지 않는다.
- (-5, 40, 79): 변환식 로 얻어지지 않는 값이다.
- (14, 25, 50): 난수 크기 순서는 맞지만 변환식 결과와 다르다.
기저해의 수는 10개이다.
여유변수 3개를 더하면 변수 5개·제약식 3개가 되고, 기저해는 5개 변수 중 3개를 기저변수로 고르고 나머지 2개를 0으로 둔 해다.
세 제약선과 두 좌표축 중 평행한 쌍이 없어 두 직선의 교점 10개가 모두 존재하므로, 실행가능 여부와 관계없이 10개가 모두 기저해다.
- 5개: 실행가능 영역의 꼭짓점 (0, 0), (10, 0), (7, 6), (4, 9), (0, 11)만 센 실행가능 기저해의 수다.
기대 소요시간은 시간이다.
PERT는 활동시간을 베타분포로 보고 가중평균한다.
- : 세 소요시간을 가중치 없이 단순 평균한 값이다.
- : 최빈 소요시간을 그대로 쓴 값이다.
- : 낙관·비관 소요시간만 단순 평균한 값이다.
분지한계법은 정수계획법의 대표 해법이다.
정수 조건을 완화한 선형계획을 먼저 풀고, 해가 정수가 아니면 변수 범위를 나눠(분지) 하위 문제를 만든 뒤 하위 문제의 목적함수값을 한계로 삼아 가망 없는 가지를 잘라낸다.
- 선형계획법: 심플렉스법으로 직접 푼다.
- 비선형계획법: 라그랑주 승수법·KKT 조건·경사법 등을 쓴다.
- 목표계획법: 편차변수를 둔 우선순위 심플렉스법으로 푼다.
- 동적계획법: 단계별 재귀식으로 푼다.
평균 도착 간격이 길어지면 도착률 가 줄어 서버 활용도가 낮아진다.
활용도는 이고 평균 고객 수는 이므로, 가 클수록 고객 수와 대기시간이 급격히 증가한다.
- 도착 간격이 길어지면 평균 고객 수가 증가한다는 설명: 가 작아지므로 평균 고객 수는 감소한다.
- 활용도가 100%에 가까울수록 대기시간이 감소한다는 설명: 활용도가 1에 가까워지면 대기시간은 한없이 커진다.
- 평균 서비스 시간이 길어지면 평균 고객 수가 감소한다는 설명: 서비스율 가 줄어 가 커지므로 고객 수는 증가한다.
- M/M/3이 서비스 단계가 셋이라는 설명: 켄달 표기의 세 번째 자리는 단계 수가 아니라 병렬 서버 수다.
| B회사의 전략 | ||||
|---|---|---|---|---|
| A회사의 전략 | 80 | 40 | 75 | |
| 70 | 35 | 30 | ||
안장점이 존재하여 최적 전략은 (, )이다.
A회사는 각 전략의 최솟값 중 최대를 고른다(최대최소).
B회사는 각 전략의 최댓값 중 최소를 고른다(최소최대).
두 값이 40으로 같아 안장점이 성립한다.
- (, ): B회사가 점유율 80을 내주는 전략을 택할 이유가 없다.
- (, ): B회사는 75보다 작은 40을 주는 전략으로 옮겨 간다.
- (, ): A회사의 두 번째 전략은 모든 경우에 첫 번째 전략보다 성과가 낮아 지배된다.
- (, ): 같은 이유로 A회사가 지배되는 전략을 택하지 않는다.
낙관계수로 최선과 최악의 성과를 가중평균하는 방법은 후르비츠 기준이다.
대안마다 최대 성과에 낙관계수 , 최소 성과에 를 곱해 더한 값이 가장 큰 대안을 고른다.
- 맥시맥스 기준: 최대 성과만 보는 완전 낙관 기준으로, 낙관계수가 1인 극단에 해당한다.
- 미니맥스 기준: 최악의 결과만 보는 비관 기준으로, 낙관 정도를 조절하지 않는다.
- 라플라스 기준: 모든 상황의 확률을 같게 보고 평균 성과로 판단한다.
- 미니맥스 후회 기준: 기회손실의 최댓값을 최소화하는 방법이다.
| 골키퍼 | |||
|---|---|---|---|
| 왼쪽 | 오른쪽 | ||
| 키커 | 왼쪽 | 60% | 80% |
| 오른쪽 | 90% | 50% | |
키커는 왼쪽으로 찰 확률을 로 하는 혼합전략이 최선이다.
왼쪽으로 찰 확률을 라 하고, 골키퍼가 어느 쪽을 택해도 골인 확률이 같아지도록 정한다(무차별 조건).
골키퍼 왼쪽:
골키퍼 오른쪽:
이때 골인 확률은 어느 경우든 70%이다.
- : 골키퍼가 오른쪽을 막으면 골인 확률이 60%로 떨어진다.
- : 골키퍼가 오른쪽을 막으면 약 63%에 그친다.
- : 골키퍼가 오른쪽을 막으면 65%에 그친다.
- : 골키퍼가 오른쪽을 막으면 약 67%로 70%보다 낮다.