M.S./OR-Tools23 [OR-Tools 스터디] Minimum Cost Flows max flow problem과 밀접하게 관련되어있는 것이 minimum cost(min cost) flow problem이다. 이는 그래프 상의 각 호가 그것들을 가로질러서 수송되는 material에 대한 단위 비용을 가진다. 이 문제는 최소 전체 비용의 흐름을 찾기 위한 것이다. min cost flow problem은 또한 특별한 노드들을 가지고 있는데, 이 노드는 공급 노드 혹은 수요 노드라고 불린다. 이들은 max flow problem에서 source와 sink와 유사하다. material은 공급 노드에서 수요 노드로 수송된다. 공급 노드에서, 양수의 양인 공급은 flow에 추가하는 것이다. 예로, 공급은 노드의 생산을 표현할 수 있다. 수요 노드에서, 음수의 양인 수요는 flow에서 제외된다.. 2023. 2. 26. [OR-Tools 스터디] Maximum Flows 따르는 섹션에서는, maximum flow(max flow) 문제의 예시를 보여준다. A max flow example 이 문제는 아래 그래프에 의해 정의되는데, 이는 transportation network를 표현한다. 우리는 노드 0(source)에서 노드 4(sink)로 material을 수송하길 원한다. 호 옆에 있는 숫자들은 그들의 capacity를 나타낸다. - 호의 capacity는 고정된 시간 안에 이를 가로질러서 수송할 수 있는 최대 양을 의미한다. capacity들은 문제에서 constraint들이다. flow는 따르는 flow conservation rule을 만족시키는 각 호에 양수를 부여하는 것이다. 최대 flow 문제는 전체 네트워크의 흐름의 양의 합이 가능한 크도록 하는 흐름을.. 2023. 2. 25. [OR-Tools 스터디] Network Flows cs에서 많은 문제들은 노드들과 그들 사이를 연결하는 링크들로 구성된 그래프에 의해 나타낼 수 있다. 예제들은 network flow문제들로, 철로 시스템과 같은 화물 운송 혹은 네트워크를 통한 자료들을 포함하고 있다. 우리는 노드들이 도시들이고 호가 그들 사이의 철로인 그래프로 network flow를 나타낼 수 있다. (그들을 flows라고도 부르는데, 그들의 특성들이 파이프의 네트워크를 통해 흘러가는 물들과 유사하기 때문이다.) network flow들에서 핵심 constraint는 각 호들이 capacity를 가지고 있다는 것이다. 즉, 고정된 시간 내에 호를 가로질러 수송될 수 있는 최대 양을 말한다. maximum flow problem은 capacity constraint의 영향을 받는 ne.. 2023. 2. 25. [OR-Tools 스터디] The Job Shop Problem 한가지 흔한 스케줄링 문제는 Jop shop으로, 이는 여러개의 job들을 몇가지 기계들에 동작시키는 것이다. 각 job은 일련의 task들로 구성되며, 주어진 순서에 맞게 반드시 동작되어야 한다. 그리고 각 task들은 특정 기계에서 동작되어야한다. 예로, job은 자동자와 같은 단일 소비재의 제조일 수 있다. 문제는 모든 작업이 완료되는 데 걸리는 시간인 schedule(예정시간)의 길이를 최소화하기 위해 시스템에 task를 schedule(예정시간)하는 것이다. jop shop 문제에 대해 몇가지 constraint가 있다. 이전 job의 task가 완료될 때 까지 다른 job의 task를 시작할 수 없다. 기계는 한번에 하나의 task만 동작시킬 수 있다. task는 한번 시작하면 반드시 완성될 .. 2023. 2. 25. 이전 1 2 3 4 ··· 6 다음
