300개의 예

최대 유량 문제

Maximum Flow Problem

모델 공식화 | 시행 착오 | 모델 풀기





에서 솔버 사용 뛰어나다 찾기 위해 최대 흐름 방향성 네트워크에서 노드 S에서 노드 T로 네트워크의 점을 노드(S, A, B, C, D, E 및 T)라고 합니다. 네트워크의 선을 호(SA, SB, SC, AC 등)라고 합니다.

모델 공식화

우리가 풀려는 모델은 Excel에서 다음과 같이 보입니다.





Excel의 최대 흐름 문제

1. 이것을 공식화하기 위해 최대 흐름 문제 , 다음 세 가지 질문에 답하십시오.



NS. 어떤 결정을 내려야 합니까? 이 문제의 경우 각 호의 흐름을 찾기 위해 Excel이 필요합니다. 예를 들어, SB의 흐름이 2이면 셀 D5는 2와 같습니다.

NS. 이러한 결정에 대한 제약은 무엇입니까? 노드 A, B, C, D 및 E의 Net Flow(Flow Out - Flow In)는 0과 같아야 합니다. 즉, Flow Out = Flow In입니다. 또한 각 호에는 고정 용량이 있습니다. 각 호의 흐름은 이 용량보다 작아야 합니다.

씨. 이러한 결정에 대한 전반적인 성과 측정은 무엇입니까? 성능의 전체 측정은 최대 흐름이므로 목표는 이 수량을 최대화하는 것입니다. 최대 흐름은 노드 S의 흐름과 같습니다.

2. 모델을 더 쉽게 이해할 수 있도록 다음을 생성합니다. 명명된 범위 .

범위 이름 세포
에서 B4: B15
NS C4:C15
흐름 D4:D15
용량 F4:F15
공급 수요 K5: K9
최대 흐름 D17

3. 다음 함수를 삽입합니다.

함수 삽입

설명: 수미프 함수는 각 노드의 Net Flow를 계산합니다. 노드 A의 경우 첫 번째 SUMIF 함수는 Flow 열의 값을 From 열의 'A'와 합산합니다(Flow Out). 두 번째 SUMIF 함수는 Flow 열의 값과 To 열(Flow In)의 'A'를 합산합니다. 최대 흐름은 노드 S의 흐름인 셀 I4의 값과 같습니다. 노드 A, B, C, D 및 E의 순 흐름은 0이므로 노드 S의 흐름은 노드 T의 흐름과 같습니다.

시행 착오

이 공식을 사용하면 모든 시험 솔루션을 쉽게 분석할 수 있습니다.

1. 예를 들어, 흐름이 2인 경로 SADT. 흐름이 ​​4인 경로 SCT. 흐름이 ​​2인 경로 SBET. 이 경로의 총 흐름은 8입니다.

평가판 솔루션

피벗 테이블이 좋은 이유

시행 착오를 사용할 필요는 없습니다. 우리는 다음 방법을 설명합니다 엑셀 솔버 최적의 솔루션을 빠르게 찾는 데 사용할 수 있습니다.

모델 풀기

최적의 솔루션을 찾으려면 다음 단계를 수행하십시오.

1. 데이터 탭의 분석 그룹에서 해 찾기를 클릭합니다.

솔버 클릭

참고: 솔버 버튼을 찾을 수 없습니까? 로드하려면 여기를 클릭하십시오 솔버 추가 기능 .

솔버 매개변수를 입력합니다(읽기). 결과는 아래 그림과 일치해야 합니다.

솔버 매개변수

범위 이름을 입력하거나 스프레드시트의 셀을 클릭할 수 있습니다.

2. 목표에 대해 MaximumFlow를 입력합니다.

3. 최대를 클릭합니다.

4. 변화하는 변수 셀에 대한 흐름을 입력합니다.

5. 추가를 클릭하여 다음 제약 조건을 입력합니다.

순 흐름 제약

6. 추가를 클릭하여 다음 제약 조건을 입력합니다.

용량 제약

7. '제약 없는 변수를 음이 아닌 변수로 만들기'를 선택하고 '단순 LP'를 선택합니다.

8. 마지막으로 해결을 클릭합니다.

결과:

솔버 결과

최적의 솔루션:

최대 유량 문제 결과

결론: 흐름이 2인 경로 SADT. 흐름이 ​​4인 경로 SCT. 흐름이 ​​2인 경로 SBET. 흐름이 ​​2인 경로 SCET. 흐름이 ​​1인 경로 SACET. 경로 SACDT 1의 흐름으로. 이 경로는 최대 12의 흐름을 제공합니다.

5/7 완료! 솔버에 대해 자세히 알아보기 >
다음 장으로 이동: 분석 도구



^