여러개의 다른 목표를 동시에 고려해야하는 최적화 문제를 해결하기 위한 최적화 기법입니다. 일반적인 선형계획법이 하나의 목적함수를 최적화하는 대신에 목표계획법에서는 어려 목표들을 동시에 달성하거나, 목표 달성 수준의 편차를 최소화하는데 초점을 맞추는 방법론입니다.목표계획법은 의사결정자로부터 각 기준에 대한 목표치를 제공받고 여러 기준들의 중요도 순서도 의사결정자로부터 제공받습니다. 그리고 이것들을 모두 반영하여 선형계획법으로 문제를 해결합니다.일반적인 선형계획법과 가장 다른 부분이 목적함수에 대한 우선순위가 있다는 것입니다. 만약 목적 X와 목적 Y가 있다고 했을때 목적 X가 중요하다면 목적 X를 달성하는 최적해를 일차적으로 찾고 이를 반영하여 목적 Y를 달성하는 최적해를 찾습니다. 이와 같이 중요도에 따..

예전 포스팅에서 간단한 수송계획법을 다루어보았습니다.(https://direction-f.tistory.com/106) 이번 포스팅에서는 수송계획법을 확장하여 경유지를 포함한 수송계획법에 대해서 정리해보겠습니다.일반 수송계획법에서는 공급지와 수송지가 있었다면 경유지를 포함한 문제는 경유지가 포함됩니다. 따라서 3가지의 수송망이 있습니다.1. 공급지 - 제품을 공급하는 곳(공장)2. 경유지 - 제품이 중간에 보관되는 곳(창고)3. 수요지 - 공급지 또는 경유지로부터 제품을 공급받는곳(도시)예시 문제로 2개의 공장(P1,P2) / 2개의 창고(W1,W2) / 3개의 도시(C1, C2, C3)가 있다고 해보겠습니다. 이때 발생하는 Cost matrix는 아래와 같습니다.1) 공장 -> 창고(cost_pw) W..

선형계획법에서 사용하는 계수들은 시간에 흐름에 따라 변화하게 됩니다. 예를들어 지난 문제(https://direction-f.tistory.com/104)를 다시 가져와서 고려해본다고 한다면 풀어야 할 문제는 아래와 같습니다.이 때 목적함수 또는 제약함수에 활용된 계수들은 변화할 수 있습니다. 그렇다면 이렇게 변화하는 계수에 따라서 해가 어떻게 변화할지를 보는것이 민감도 분석입니다. 이는 불확실한 상황속에서도 조금 더 견고한 결정을 내릴 수 있도록 지원합니다. 구체적으로, 민감도 분석은 목표 함수 계수의 변화, 제약 조건의 우변 값 변화, 그리고 제약 조건 계수의 변화 등이 최적 해에 미치는 영향을 분석합니다. 이를 통해, 어떤 입력 변수가 결과에 가장 큰 영향을 미치는지 등을 파악할 수 있습니다.간단하..

Reduced Cost는 선형계획법에서 최적해에 대한 민감도를 나태는 수치입니다. 현재 최적해에 포함되어 있지 않은 변수가 추가되어 한 단위 변화할때 목적함수 값이 어떻게 변화하는 지를 나타냅니다. 다시 말해, 현재 해가 최적인 상황에서 특정 변수를 해에 포함시키는 것이 이득인지 손해인지를 알려주는 값이라고 생각하시면 됩니다.직관적으로는 현재는 최적해로 포함되어 있지 않은 변수를 포함시켰을 때 지불해야하는 비용이라고 이해하시면 편할 것 같습니다. 따라서 현재 최적해에 이미 포함되어 있는 변수들의 Reduced Cost는 0입니다. Reduced Cost의 해석은 다음과 같습니다.기본해(Basic Solution): 현재 최적해에서 0이 아닌 값을 가지는 변수들비기본해(Non-basic Solution):..

기존에 정리했던 선형계획법을 조금 더 확장하여, Shadow price(잠재가격)이 무엇인지 정리해보겠습니다. Shadow Price는 Dual Variable이라고도 불리며 쉽게 말해 제약조건이 완화 된다면 목적함수가 어떻게 변할지를 나타내는 수치라고 이해하면 편할 것 같습니다.예를 들어 지난번 포스팅에서 해결했던 문제(https://direction-f.tistory.com/104)를 가지고 와본다면 아래와 같습니다.결과적으로 위의 문제를 최적화를 해보면 군인 장난감(x1)은 20개 기차 장난감(x2)은 60개를 생산하는 것이 주어진 제약조건에서 최적화된 값이었습니다.그렇다면 제약조건이 바뀌게 된다면 목적함수는 어떻게 바뀌게 될까요? 이를 나타내는 개념이 Shadow Price입니다. 즉 생산시간제약..

해당 글에서는 선형계획법의 응용으로써 수송문제를 다루어보고자 합니다. 수송문제란 다수의 공급지와 다수의 수요지가 존재하는 상황에서 어떤 공급지에서 어떤 수요지로 얼마만큼의 물량이 가야하는지를 결정하는 문제입니다. 일반적으로 수송문제는 3가지 상황에 대한 이해가 필요합니다. 첫 번째로는 공급지에서 수요지로 물량을 이동할 때 발생하는 비용입니다. 두 번째는 공급지에서 공급가능한 양(Capacity), 마지막으로는 수요지에서 필요로 하는 수요량입니다. 위의 3가지 상황을 활용하여 목적함수, 의사결정변수 등을 정의하게 됩니다.예시를 통해 수송계획문제 해결방안에 대해서 정리해보도록 하겠습니다.장난감을 생산하는 한 회사가 3개의 공장(공장 1, 공장 2, 공장3)을 보유하고 있고, 해당 장난감을 받을 도시가 4개(..