우리는 시험 E = {E1, E2, ..., Em} 및 I = {I1, I2, ..., In}의 도구 세트를 가정하고 각 시험 Ej는 Rj의 서브 세트 I. 각 시험은 Pj $ 이익을 가지며 각 도구 비용은 Cj $입니다. 우리는 어떤 시험을 최대화하기 위해 선택하려고합니다 (이익의 합계 - 비용의 합계).네트워크 흐름을 사용하여 선형 프로그래밍을 해결하는 방법은 무엇입니까?
우리는 각 검사마다 m 변수 Xi가 있고 Xi = 0 또는 1 인 LP를 사용할 수 있다고 생각합니다. 목적 함수는 다음과 같습니다. 모든 i와 j에 대해 Xi (Pi) - (A) Cj 모든 Xi는 IJ가 필요합니다
하지만 네트워크 흐름에 의해이 문제를 모델링 할 수 없습니다. 내 문제는 우리가 시험을 선택하고 그 도구에 대해 지불 할 때 우리는 다른 시험을 위해 그러한 도구를 사용할 수 있다는 사실을 나타내는 방법입니다.
이 문제를 bipartite graph로 모델링하십시오. 왼쪽에 정점, 오른쪽에 instrument를 넣으십시오. 무한 용량의 가장자리를 통해 장비에 장비 검사를 연결하십시오. 이제 소스 S와 싱크 T를 소개합니다. 이익을 나타내는 가장자리를 통해 S를 시험에 연결하십시오. 비용을 나타내는 모서리를 통해 장비를 T에 연결하십시오.
최대 이익은 모든 Pi - min 컷의 합계가 입니다.
왜? 그래프에서 가장자리를 절단하여 T와 S를 분리하십시오. 각 검사마다 우리가 놓친 이익에 대한 "지불"또는 모든 도구를 잘라야합니다.
최적의 검사 집합은 잔류 흐름 네트워크에서 S에서 도달 할 수있는 검사 꼭지점 집합으로 나타냅니다.
최대 이익이 모든 파이 - 컷의 합계 인 이유를 이해할 수 없습니다. 최적의 시험 세트가 잔여 유량 망에서 S로부터 도달 할 수있는 것이면 모든 시험의 이익을 최종 이익에 추가하는 이유는 무엇입니까? – user3070752
@amir 최소 절단은 음이 아닌 가중치와 만 작동하므로, 시험 i에 비용 0이 있고 비용 Pi가없는 문제를 모델링합니다. 실제로는, 우리는 시험을하기 위해 비용 - 파이를하고 그것을하지 않기 때문에 0을 가지므로, 최소 컷 결과로부터 파이를 빼야합니다. –
최소 컷의 관점에서 생각해보기 –