수송문제에서 초기해에 대한 최적해 검사기법으로 옳은 것은?
화물운송론- ①디딤돌법(Stepping Stone Method)
- ②도해법(Graphical Method)
- ③트리라벨링법(Tree Labelling Algorithm)
- ④의사결정수모형(Decision Tree Model)
- ⑤후방귀납법(Backward Induction)
선지를 골라 바로 채점해 보세요.
정답 ① — 수송문제에서 수립된 초기 기본가능해의 최적성 여부를 검사하고 비용을 개선하기 위해 사용되는 대표적인 최적해 검사기법은 디딤돌법(Stepping Stone Method)과 수정배분법(MODI)이다.
선지별 오답 이유
- ① 디딤돌법은 빈 셀(비기저변수)에 단위 화물을 할당했을 때 발생하는 운송비용의 변화를 폐회로(Closed Loop)를 구성하여 평가함으로써, 현재 해의 최적성 여부를 검사하고 개선안을 찾는 기법이다.
- ② 도해법은 수송문제의 해법이 아니라, 결정변수가 2개인 일반 선형계획모형의 실행가능영역을 2차원 평면에 그려 최적해를 도출하는 기법이다.
- ③ 트리라벨링법은 수송문제의 최적해 판정 도구가 아니라, 네트워크 모델에서 최소신장트리나 최단경로, 최대유량 등을 탐색할 때 노드에 라벨을 붙여가며 계산하는 알고리즘이다.
- ④ 의사결정수모형은 시간에 따른 순차적 의사결정과 불확실성을 나무 구조 형태로 표현하여 각 대안의 기대화폐가치를 분석하는 의사결정 분석 기법이다.
- ⑤ 후방귀납법은 동적계획법이나 게임이론, 의사결정수 등에서 최종 단계의 결과부터 역방향으로 거슬러 올라가며 각 마디의 최적 대안을 역산하는 풀이 기법이다.
관련 개념
수송문제(Transportation Problem)의 해결 절차는 크게 초기 기본가능해 도출 단계와 최적해 검사 및 개선 단계로 나뉜다.
첫 번째 단계에서는 북서코너법, 최소비용법, 보겔의 근사법(VAM) 등을 이용하여 공급과 수요 제약을 충족하는 초기 실행가능해를 구한다.
두 번째 단계에서는 도출된 초기해가 총비용을 최소화하는 최적해인지 판정하고 개선하게 되며, 이때 디딤돌법(Stepping Stone Method)이나 수정배분법(MODI)을 적용한다.
첫 번째 단계에서는 북서코너법, 최소비용법, 보겔의 근사법(VAM) 등을 이용하여 공급과 수요 제약을 충족하는 초기 실행가능해를 구한다.
두 번째 단계에서는 도출된 초기해가 총비용을 최소화하는 최적해인지 판정하고 개선하게 되며, 이때 디딤돌법(Stepping Stone Method)이나 수정배분법(MODI)을 적용한다.
출처: 한국산업인력공단, Q-Net 자료실 · 공공누리 제1유형 · AI 해설 · 자동 검증 통과