[SAS 활용 FAQ] Mathematical Optimization in our Daily Lives

[#1]

일상 생활에서 마주할 수 있는 수학적 최적화

일상 생활에서 우리는 최적화된 알고리즘을 활용하여 다양한 이점을 누리고 있습니다. 예를 들어 GPS 시스템, 택배 운송업, 금융업, 항공 예약 시스템 등 다양한 곳에 적용되고 있습니다. 수학적 프로그래밍, 운영 연구 또는 간단히 최적화라고도 불리는 수학적 최적화는 다음과 같은 분야를 뜻합니다. 의학, 제조, 운송, 공급망, 금융, 정부, 물리학, 경제학, 인공 지능 등 다양한 영역에서 관련 문제를 해결합니다.

이 기사에서는 수학적 전문 용어를 최대한 배제하면서도 최적화 활용이 가능한 상황들을 소개합니다. 알고리즘을 도입해 창출할 수 있는 잠재적 가치를 발견하실 수 있습니다.

Gartner Analytics Maturity Model 은 설명, 진단, 예측 및 처방으로 이루어진 4 가지 단계를 소개합니다. 최적화는 일련의 조건에서 가능한 최상의 목표를 달성하기 위해 리소스를 효율적으로 사용하는 방법을 나타내는 처방 단계의 주축입니다.

최적화 모델의 목표는 예를 들어 정유업계 등과 같은 생산과정에서 노동, 원자재 등과 같은 자재를 투입하여 비용을 최소화 하고, 목표 생산성을 달성하는 것입니다. 병원의 경우는 의사, 간호사, 병실, 장비 등이 자원에 속하며 진료를 받기 전에 응급실에 있는 환자의 대기 시간을 최소화하는 것입니다. 마케팅의 경우 예산 및 운영 조건에서 적합한 고객을 대상으로부터 수익 창출을 극대화하는 것입니다. 인도주의 사업에서는 최적의 경로를 설계하여 자원, 식량 및 의료 서비스를 최단 시간 내 가능한 한 많은 대상에게 공급하는 것입니다.

최적화 문제가 여러 조건 또는 제약 조건에서 목표 기능을 최대화하거나 최소화하는 결정 변수를 도출해 낸다고 볼 수 있습니다. 최적화 문제를 수학적 모델로 표현하여 문제를 해결하려면 전문 교육이 필요합니다. 해당 기사에서는 몇 가지 예시를 통해 의사 결정 변수, 목표 및 제약 조건을 식별하고 정확한 정의를 제공하는 데 필요한 수학적 모델 작성이 포함하고 있으며 의사 결정 변수 및 제약 조건의 의미에 대한 자세히 설명합니다.

저는 Edelman Award 및 Wagner Prize 대회의 예제를 선택했습니다. 2017 년과 2018 년에 Wagner 대회 의장으로 역임한 바 있으며 Edelman Award에 심사위원 겸 코치로 참여했습니다. 최적화가 적용되는 다양한 영역을 안내하기 위해 이러한 예제를 선택했으며, 분석 및 최적화를 다시 적용 할 수 있는 유사한 상황을 쉽게 설명 할 수 있다고 생각합니다.

Edelman Award는 중요한 비즈니스 문제에 대한 수학적 프로그래밍 및 분석 구현을 탁월히 해낸 분께 수여됩니다. Wagner Prize는 명확하고 이해하기 쉬운 글쓰기와 검증 가능한 적용을 통해 실생활에 적용될 수 있는 수학을 강조합니다. Interfaces Journal은 1월호는 Edelman을 9월호는 Wagner를 다룹니다. 하단의 링크는 저널 기사에 해당하며 Edelman 동영상을 시청하실 수 있습니다.

Jan de Wit Company의 백합 생산 계획 및 거래 최적화

생산과 관련된 일반적인 예시에 해당하며 이는 가구, 직물, 젖산 제품, 농산물, 미용 제품 등을 생산하는 것과 같은 다른 상황과도 직결되어 있습니다. 대개 동일한 목표, 유사한 제약 및 결정 변수를 가지고 있습니다.

백합 화훼 사업을 관리하기 위해 Jan de Wit Company는 생산, 계획 및 거래를 위한 의사 결정 지원 시스템을 구현했습니다. 2001 년 Edelman을 통해 기업은 눈부신 부상을 이뤄냈으며, 1999 년과 2000 년간 회사 매출 26 % 증가하였고, 백합 화분 및 다발 매출이 각각 14.8 % 및 29.3 %으로 상승했으며 비용은 매출의 87.9 %에서 84.7 %로 감소했습니다. 또한 운영 수입 60 % 증가 및 자기 자본 수익률은 15.1 %에서 22.5 %로 증가 및 최고 품질의 절화 백합은 판매 수량이 11 %에서 61 %로 증가했습니다. Edelman 시스템은 또한 제품 구성의 변경을 권장했습니다.

선형 계획법 (LP) 목표는 시장에서 정의한 판매 제한, 시장 요구 사항, 생산주기 특성, 기술 요구 사항, 전구 재고 및 온실 제한과 같은 제약 조건에 따라 농장의 총 마진을 최대화하는 것이였습니다. 계산이 필요한 주요 결정 변수는 식재 및 예상 수확 기간을 고려하여, 특정 목적을 위해 길러진 특정 전구 배치(batch)내 특정 그린하우스에 있는 특정 품종의 화단의 수입니다.

Dell의 채널 혁신: 운영 연구를 활용하여 가치 사슬 전반에 걸쳐 잠재력 발휘

해당 예시는 Garner Analytics Maturity Mode의 4 단계가 통합된 방식과 Dell의 프로세스를 개선하는 데 사용된 다양한 분석 기술을 보여줍니다. Dell과 유사한 분석 프로세스를 도입하여, 다양한 산업분야에서도 수익을 창출해낼 수 있습니다.

2007 년 Dell은 온라인 채널, 소매 업체, 유통 업체 및 기타 채널 파트너를 통해 안정적인 구성을 제공함으로써 채널 혁신을 주도하기 위해 몇 가지 전략적 이니셔티브를 도입했습니다. 2014 년 Dell은 Edelman을 통해 2007 년부터 Operations Research(OR)가 Dell이 복잡한 비즈니스 문제에 도움이 되었으며, FHC 비즈니스의 성장을 150 억 달러로 촉진하는 계기가 되었다고 보고했습니다. 2010 년부터 이러한 OR 솔루션은 가격인하 비용 감소, 온라인 전환율 개선, 해상 운송 상승 및 고객 만족도 향상 등을 가능하게 해 1 억 4 천만 달러 이상의 마진 효과를 불러일으켰습니다.

하단에서는 Dell이 도입한 두 가지 유형의 수학적 최적화 모델과 다양한 분석 기술이 이러한 모델에 대한 입력을 생성하는 방법에 대해 알아 봅니다.

Dell은 비선형 혼합 정수 프로그램의 입력으로 A / B 테스트, 다변량 회귀, ANOV과 같은 다양한 분석 및 통계 기술을 사용하여 웹 사이트 디자인을 개선하여 잠재 고객의 구매자 전환율을 높였으며, 매출과 고객 만족도 또한 개선되었습니다.

Dell 분석팀은 요인 및 클러스터링 분석과 같은 기술을 기반으로 초기 고정 하드웨어 구성 (FHC) 세트를 생성했습니다. 이러한 초기 구성은 비용 및 예상 수익 범위를 고려하는 2 차 프로그래밍 모델을 통해 추가 옵션과 기능으로 업그레이드 되었습니다.

운영 연구, 암 치료학 향상 (2007 Edelman 수상작)

이 수상작은 수학적 프로그래밍 접근 방식을 기반으로 종양 내부에 방사성 ‘씨앗’배치하는 근접 치료를 통해 전립선 암의 수술 중 또는 실시간 치료를 위한 정교한 최적화 모델링 및 계산 기술을 선보였습니다. 그 결과 훨씬 더 안전하고 신뢰도 높은 치료법을 선보였습니다.

목표는 다음 조건에서 주어진 종양 지점에서 표적 경계에서 선량 수준의 편차를 최소화하는 것이 었습니다.

조건: 1) 각 복셀(voxel)에서 방사선 선량은 지정된 하한 및 상한 범위 내여야 합니다. 2) 종양에 대한 선량-용량 범위 제약이 존재합니다. 3) 총 방사능 선량을 초과하여 처방할 수 없습니다.  4) 사용할 총 바늘 수는 한정되어 있습니다. 5) 추가적인 기술적 제약이 이쓸 수 있습니다. .

이 Mixed Integer Programming 에서 다음과 같은 두 가지 즉 1) 종양에서 방사성 종자의 위치, 2) 종양의 특정 샘플 지점 즉 복셀까지 처방된 방사선의 도달 여부를 나타내는 변수입니다.

해당 연구는 다른 암에도 적용될 수 있습니다.

INDEVAL, Operations Research를 사용하여 새로운 운영 및 결제 시스템 개발 (2010 Edelman 수상작)

INDEVAL은 멕시코 CSD 기업(Central Securities Depository)입니다. CSD는 금융 증권의 보관 및 관리 및 결제와 관련된 서비스를 제공합니다. 거래 참여자 간에 증권과 자금이 이체 될 때 정산이 이루어집니다. 2010 년, Dali라고 불리는 INDEVAL의 수학적 최적화 시스템은 약 1,300 억 달러의 일일 유동성 요구 사항이 낮추어 시장 참여자의 일일 금융 비용을 연간 1 억 5 천만 달러 이상 감축할 수 있었습니다. Dali는 노출된 가격과 금융 거래가 발생하는 실제 가격 간의 차이를 최소화하기 위해 실시간에 가까운 결제를 수행하여 위험 노출을 효과적으로 줄였습니다. Lehman Brothers의 실패는 이러한 위험을 줄이는 것이 얼마나 중요한지를 상기시켜주는 좋은 예시입니다.

Dali의 목표는 1,814 개의 보안 잔액과 관련된 제한 사항을 완화하면서 실질적 거래량을 최대화하는 것이 었으며, 그 결정 변수는 예상 결제 거래였습니다.

이 문제는 정수 문제 (IP)에 해당합니다. 현금관련 제한사항이 없어질 경우, LP 공식은 단일 모듈식이 되며 정수인 최적의 솔루션을 갖습니다. 자세한 사항은 동영상을 통해 확인하실 수 있습니다.

다른 국가에서 적용이 가능한 CSD 및 금융 중개인을 위한 유사한 금융 애플리케이션이 있습니다. BNY Mellon Optimization Reduces Intraday Credit Risk by $1.4 Trillion 기사는 Bank of New York Mellon이 단기 담보 대출과 관련된 담보 관리 문제를 해결하기 위해 통합 혼합 정수 프로그래밍 모델 세트를 개발 한 방법을 설명합니다. 목표는 고객의 일일 신용 노출과 유동성 사용을 최소화하는 것이었습니다. 자세한 사항은 동영상을 통해 확인하실 수 있습니다.

Calibrated Route Finder: 스웨덴 내 트럭 라우팅의 안전성, 환경 의식 및 비용 효율성 개선 (2016 Wagner 수상작)

2016 년 우승자의 목표는 스웨덴에서 대형 벌목 트럭의 최적 경로가 이해관계자가 주안점으로 두는 최소 비용경로와 최대한 근접하도록 설계하는 것이었습니다.

대형 벌목 트럭의 경로는 산림의 공급 지점에서 시작하여 수요 지점 또는 제분소에서 끝나며 스웨덴 산림 산업의 많은 이해 관계자들로 인한 무수한 제약을 고려해야 합니다. 이러한 고려 사항 중 일부는 거리, 경사도 및 곡률과 같은 도로의 품질이며, 경로는 도시 센터, 병원, 유치원 등 특정장소를 포함해서는 안됩니다. 또한 경로에는 환경 고려 사항이 수반되어야 합니다.

전통적으로 스웨덴의 대형 벌목 트럭은 최상의 경로를 선호했습니다. 그러나 이러한 경로에는 상단의 경영과 관련된 비용은 고려되지 않은 것과는 달리, 우승작은 이를 모두 포함하는 최소 비용을 가능케하는 최적의 경로를 찾았습니다. 자세한 사항은 동영상을 통해 확인하실 수 있습니다.

유사한 응용 프로그램: 배송 및 픽업에 대한 라우팅 문제. 예: UPS, 배송 경로 최적화 참조 (2016 Edelman 수상작) 자세한 사항은 동영상을 통해 확인하실 수 있습니다.

Guns or Butter: 남아프리카 국방군의 규모와 조직 결성을 위한 방안(1996 Edelman 수상작)

기존의 군사적 위협이 적고 제한된 예산을 보유한 남아프리카 국방군 (SANDF)의 규모와 형태는 어떻게 개선해야할까요? 이 우승자의 목표는 제한된 예산과 특정 군대 임무 특성에 대한 조건에서 방어 가치를 극대화하거나 위험을 줄이는 데 있었습니다. 수학적 모델의 각 답변에는 작전, 경고 단계, 군사 전략, 부대 설계 및 비용이 포함되었습니다.

이 작품은 넬슨 만델라 남아프리카 대통령에 의해 높이 평가되었으며, Edelman 심사위원들 또한 극찬하였습니다.

미국 환경 보호국: 미국 환경 보호국, 운영 연구를 통한 식수 오염 위험도 축소

이 프로젝트는 2008 년 Edelman를 통해서 진행되었습니다. 고속 스트리밍 데이터를 분석하고 즉시 적절한 조치를 취할 수 있는 SAS ESP (Event Stream Processing)를 포함하도록 확장 할 수 있습니다.

미국 환경 보호국 (EPA) 위협 앙상블 취약성 평가 (TEVA-SPOT) 연구 프로그램은 수천 명의 생명과 수십억 달러에 달하는 잠재적 경제 손실 등 잠재적으로 공중 보건 결과를 감소시키는 미국 전역의 대규모 배수 네트워크에 대한 오염 위협에 대응하기 위해 오염 경고 시스템을 고안했습니다.

표준 TEVA-SPOT 최적화 모델의 목표는 지정된 위치와 예산에 센서를 배치 할 경우의 전반적인 영향을 고려하면서 오염 사고의 예상되는 영향을 최소화하는 것이었습니다.

이 프로그램은 식수 관리 네트워크에서 센서의 위치를 ​​결정 변수로 사용했습니다. 자세한 사항은 동영상을 통해 확인하실 수 있습니다.

2017년 Edelman Award 및 Wagner Prize 수상자인 비영리 정부 관련 프로젝트

2017 Wagner 수상작은 펜실베니아 C 부서의 적용 내 수감자 배치 및 수감 기간 문제 개선으로, 수감자를 교정 기관 (CI)에 배정하고 재활 치료 프로그램을 예약하는 복잡한 문제를 해결하면서 수감자의 범죄 이력, 인구 통계학적 특성 등과 같은 요인 등과 같은 약 100 개의 추가 사항을 고려했습니다. 재활 치료 프로그램을 적절히 받은 수감자는 가석방 자격이 주어지고, 조기 사면될 가능성이 높아지므로, 불필요한 교정기관의 과포화 상태를 개선할 수 있습니다.

해당 수상작은 다소 복잡한 모델에 속하며 몇 가지 지향점을 두고 있습니다. 다목적 혼합 정수 선형 최적화 문제는 모든 목표의 가중치 합에 대한 패널티를 최소화합니다. 일반 요인은 수감자를 CI에 배정 할 때 가장 높은 우선 순위를 갖습니다. 각 수감자의 최대 대기 시간을 최소화하는 것은 두 번째입니다. 각 시설의 최소 및 최대 용량 범위에서 할당하는 것이 그 다음입니다. 또한 CI내 과포화 상태를 방지하기 위해, 프로그램 대기자 명단은 또한 높은 우선 순위를 갖습니다. 수감자의 주거지 근처의 시설에 배정하는 것은 다소 중요한 부분이 아닙니다.

 몇 가지 결정 변수가 있으며, 그 중 일부는 수감자가 배정된 시설, 재활 프로그램 시작 시간, 시간 t에 재활 프로그램을 시작하는 각 CI에 배정 된 재소자 수, 프로그램 p 시작을 위한 최대 대기 시간 등입니다. 이러한 조건은 수감자 배정에 영향을 미치는 100 가지 요소와 관련이 있습니다. 예를 들어 각 CI의 수용 능력, 각 수감자에게 적용되는 요소, 주어진 시간에 이용할 수있 는 코스, 수감자의 거주지와의 거리 등입니다. 자세한 사항은 동영상을 통해 확인하실 수 있습니다.

2017년 Edelman 우승작은 US Federal Communications Commission으로, 수상작인 Unlocking the Beachfront: Using O.R. to Repurpose Wireless Spectrum을 통해 스펙트럼 크런치를 완하하기 위해 Operations Research와 인센티브 경매을 활용 했습니다. 이 프로젝트의 중요성은 FCC가 Edelman Award를 수상한 방법 기사에 다음과 같이 요약되어 있습니다.“… 기념비와 같은 프로젝트와 그에 따른 재정적 영향을 요약해 달라는 요청을 받았지만, Hoffman은 200 억 달러의 가치와 70 억 달러의 적자 감소는 중요한 부분이 아닙니다. 그보다는 미국이 5G 및 사물 인터넷에 필요한 무선 스펙트럼을 보유 할 수 있는 미래의 능력이 핵심입니다. 이것이 바로 무선 경제입니다. 이는 또한 앱 경제라 불리기도 하며, FCC가 이러한 방식을 도입히지 않았다면 이와 같은 성과는 없었을 것입니다.”  자세한 사항은 동영상을 통해 확인하실 수 있습니다.

결론

우리는 매일 생산 시스템 내 일상적인 사업 부분부터 5G 및 사물인터넷을 위한 무선 스펙트럼 및 인공지능을 통한 활용 등의 중요성에 이르기까지 수학적 최적화를 통해 전반적인 삶의 질을 개선해 나가고 있습니다. Edelman Award 및 Wagner Prize 웹 페이지에서 귀감이 될 만한 다양한 응용 프로그램을 찾아보실 수 있습니다.