본문 바로가기

산업공학 이모저모/최적화

(9)
[Optimization] 9. Multi-objective Optimization model (2) Multi-objective Optimization model을 푸는 방법은 크게 3가지가 있습니다. ​ 첫 번째 방법은, 우선 하나의 objective를 만족하는 최적의 값을 찾은 후, 이 최적의 값을 최대한 유지하면서, 다른 목적함수에서 더 좋은 해를 가지도록 만드는 것입니다. 이 방법을 Pareto optimal 방법으로 부릅니다. ​ 예를 들어서, 위와 같은 문제가 있다고 합시다. 두 가지 경우의 수에 대해서 두 번째 목적함수에서는 같은 값을 가지지만, 첫 번째 목적함수에서 더 높은 값을 가지는 후자가 더 좋은 것을 알 수 있습니다. ​ 또 다른 방법으로는 목적 함수들을 가중합하여 하나의 목적함수로 변형하는 것입니다. 위와 같이 하나의 목적 함수를 정의하는데, 더 중요한 목적 함수에 높은 가중치를..
[Optimization] 8. Multi-objective Optimization model 안녕하세요. 이번 포스팅에서는 Multi-objective Optimization model 에 대해서 배워보도록 하겠습니다. ​ 우선 Multi-objective Optimization model 에 대해서 정의를 해보자면, Objective function이 2개 이상 있는 최적화 모델입니다. 기본적인 LP 모델은 하나의 목적 함수와, 여러 개의 제약 조건을 가집니다. 하지만, 현실 상황에서 최적화 모델을 수립할 때, 다수의 목적을 필요로 하는 경우가 있습니다. ​ 예를 들어서, 투자 계획 설립이 있습니다. 아래의 예제를 보도록 하겠습니다. 은행이 투자 계획을 설립할 때, 8가지 경우의 수가 있습니다. 각 경우의 수마다, 수익 비율과, Risk 요소가 다를 수 밖에 없습니다. 수익 만을 목적함수로 정..
[Optimization] 7. Dual model 안녕하세요. 이번 포스티에서는 Dual model에 대해서 배워보도록 하겠습니다. Dual model은 복잡한 LP 모델을 보다 간단한 모델로 변환하는 방법입니다. ​ Primal problem은 아직 변환하기 전의 기존 문제로 정의됩니다. Dual problem은 변환된 문제입니다. Dual variable은 다음과 같은 변환을 따릅니다. Primal problem이 min 혹은 max에 따라 부등호의 방향이 달라지며, 제약 조건의 부등호에 의해서도 결정됩니다. 위와 같은 문제를 Dual problem으로 변환해보겠습니다. Dual variable의 부등호는 위와 같이 정의됩니다. Dual problem 은 위와 같습니다. ​ Dual problem 전환 과정을 쉽게 정리해보면 위와 같은 식입니다.
[Optimization] 6. Simplex 안녕하세요. 이번 포스팅부터는 LP 최적화에 꽃이라고 할 수 있는 Simplex method에 대해서 배워보도록 하겠습니다. Simplex method 는 LP 문제를 푸는 가장 기본적인 방법입니다. ​ 위와 같은 문제가 있을 때, 기본적으로 최적의 해는 꼭지점들 중에 있다고 가정할 수 있습니다. 초기 점으로 (0,0)을 선택하고, x축이나 y축을 따라, 두번 째 점으로 이동하고 계속해서 꼭지점으로 이동하면서 최적 해를 찾아야 합니다. 이 때, 어느 방향으로 먼저 가는가에 대한 알고리즘이 바로 Simplex method 라고 할 수 있습니다. ​ Simplex method를 가장 간단하게 이해하기 위해서는 예시를 보면서 배우는 것이 가장 좋다고 생각합니다. 위와 같은 문제를 풀어야합니다. 눈으로 보기에도..
[Optimization] 5. LP Model (4) Scheduling Models [Ref] Optimization in Operations Research, Rardin ​ 안녕하세요. 이번 포스팅에서 공부해볼 LP 모델은 Scheduling Model 입니다. 제가 생각하기에, Scheduling Model이 저희가 일상생활에서 가장 자주 접할 수 있는 최적화 문제인 것 같아요. ​ Scheduling Model로써 굉장히 유명한 예시를 공부해봅시다. 바로, 슈퍼마켓 근무 시간표 작성 문제입니다. 슈퍼마켓은 일반적으로, 낮 시간에는 한가하지만, 18시 이후에는 굉장히 바빠집니다. 따라서, 효율적인 스케쥴링이 굉장히 중요한 문제입니다. 근무에는 full time 근무자와, part time 근무자 두 종류가 존재합니다. 슈퍼마켓의 근무에 할당량이 있는데, full-time 근무자가 ..
[Optimization] 4. LP Model (3) Operations Planning Models [Ref] Optimization in Operations Research, Rardin ​ 안녕하세요. 이번에 배울 LP 모델은 Operations Planning Models입니다. Operations Planning Models을 한글로 직역하면, 조직 계획 모델입니다. Operations Planning Models은 조직이 계획을 세울 때, 언제 혹은 어디서 해당 문제를 해결하는게 좋은가에 대한 문제에 주로 사용됩니다. ​ Operations Planning Models이 사용되는 대표적인 예제를 배워봅시다. 문제를 요약하면 다음과 같습니다. 조직이 물건을 생산하는 데, 생산할 수 있는 물건이 여러 종류가 있으며, 생산 할 수 있는 공장 또한 여러 군데가 존재합니다. 그런데, 물건마다 특정 장소..
[Optimization] 3. LP Model (2) Blending Models [Ref] Optimization in Operations Research, Rardin ​ 안녕하세요, 이번 포스팅에서 배워볼 LP 모델은 Blending Model입니다. Blending Model을 한글로 직역하면, 혼합 모델입니다. 말그대로, 혼합이 자주 발생하는 화학문제에서 주로 사용되는 모델입니다. ​ Blending Models 또한 간단한 예제를 통해서 익혀보도록 하겠습니다. 고철들을 모아서, 금속을 하나 만든다고 해봅시다. 고철들에도 다양한 금속 성분이 들어있을겁니다. ​ 위에서 나오는 표가 그에대한 정보입니다. Molybdenum의 성분이 안적혀 있는데 Chrominum의 Molybdenum성분이 100으로 되어있는데, 아래 Molybdenum이 100으로 생각하시면 됩니다. (오타....
[Optimization] 2. LP Model (1) Allocation Models [Ref] Optimization in Operations Research, Rardin 안녕하세요. 이번 포스팅부터는 본격적으로 LP Model들에 대해서 공부해보려고 합니다. 첫 번째로 배워볼 LP모델은 Allocation Model 입니다. ​ Allocation Model을 한글로 직역하면 바로 할당 모델입니다. 말그대로, Allocation Model은 정해진 제약조건을 만족하면서, 문제의 목적에 가장 잘 맞도록 변수들의 값을 배정하는 문제에 사용됩니다. ​ Allocation Model을 잘 설명할 수 있는 예제를 가지고 왔습니다. 문제를 간단하게 요약하면 이렇습니다. 땅을 관리하는 정책을 만들고 싶은데, 목적함수로써, 순가치이익 (NPV)를 최대화하고 싶다는 것입니다. 이 때, 땅의 목적을 ..