에서 솔버 사용 뛰어나다 찾기 위해 최대 흐름 방향성 네트워크에서 노드 S에서 노드 T로 네트워크의 점을 노드(S, A, B, C, D, E 및 T)라고 합니다. 네트워크의 선을 호(SA, SB, SC, AC 등)라고 합니다.
모델 공식화
우리가 풀려는 모델은 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의 흐름을 제공합니다.
다음 장으로 이동: