정식 레코드. 선형 프로그래밍 문제의 정식 형식입니다. 선형 계획법 문제를 해결하기 위한 그래픽 방법

13.03.2019

소개 3

1 할당 문제입니다. 헝가리 방식 4

1.1 할당 문제 4

1.2 할당 문제를 해결하기 위한 헝가리식 방법 7

2 헝가리식 방법을 사용한 할당 문제 해결 15

결론 20

참고문헌 21

할당 문제는 고전적인 전송 문제의 특별한 경우이며 결과적으로 전송 유형 문제입니다.

교통 문제가 가장 큰 문제다. 경제적으로생산 지점(출발역)에서 소비 지점(목적지 역)까지 동질적이거나 상호 교환 가능한 제품을 운송하는 것이 가장 중요한 특정 작업입니다. 선형 프로그래밍, 이는 운송 문제뿐만 아니라 광범위한 실제 응용 프로그램을 가지고 있습니다.

과제 문제와 관련해 단순 방법허용되는 기본 솔루션 중 하나라도 변질되었기 때문에 효과적이지 않습니다. 할당 문제의 특정 기능을 통해 개발이 가능해졌습니다. 효과적인 방법그 해법은 헝가리식 방법으로 알려져 있습니다.

있다고 가정해보자 피 다양한 작품, 각 작업은 다음 중 하나에 의해 수행될 수 있습니다. 피출연자들을 끌어들였습니다. i번째 작업을 수행하는 데 드는 비용 제이 - 중수행자에게 알려져 있으며 C i j(기존 화폐 단위)와 동일합니다. 전체 작품의 구현과 관련된 총 비용을 최소화하는 방식으로 작품 간에 출연자를 배포(각 작품에 한 명의 출연자를 할당)하는 것이 필요합니다.

운영 연구에서는 위에서 공식화한 문제를 할당 문제라고 합니다. i번째 작업이 수행되는 경우 Xij는 1의 값을 갖는 변수 Xij를 소개하겠습니다. j번째 수행자이고, 다른 모든 경우에는 값이 0입니다(i,j = 1). 피. 그렇다면 한계는

각 작업은 한 명의 연주자만 수행하도록 보장합니다.

각 수행자는 하나의 작업만 수행하도록 보장합니다. 전체 작업 복합체를 수행하는 데 드는 비용은 다음과 같습니다.

따라서 할당 문제는 다음과 같이 작성할 수 있습니다.

할당 문제 (1)은 고전적인 전송 문제의 특별한 경우로, 다음을 넣어야 합니다. 이 경우 조건은 변수 x와 j가 정수라는 요구 사항이 충족됨을 의미합니다. 이는 모든 소스와 싱크의 전력이 단일성과 동일하다는 사실에 기인합니다. 즉, 허용 범위 내에서 정수해변수값은 0과 1만 가능합니다.

어떻게 특별한 경우고전적인 교통 문제에서 할당 문제는 다음과 같이 간주될 수 있습니다. 선형 프로그래밍 문제.그러므로 이 경우선형 프로그래밍의 용어와 이론적 결과를 사용합니다.

할당 문제에서 변수 x i j는 0 또는 1의 값을 가질 수 있습니다. 또한 (1)에 따르면 허용되는 모든 솔루션에서만 피변수는 값 1을 취할 수 있습니다. 따라서 할당 문제에 대한 가능한 기본 솔루션은 퇴화됩니다.

실제로는 매개변수를 i번째 직무 수행의 효율성으로 이해하는 할당 문제가 있다. 제이 - 중수행자. 이러한 경우 구현의 전체 효율성이 최대가 되는 방식으로 수행자에게 작업을 배포해야 합니다.

(2)

여기서 (1)에 명시된 제한 사항에 따라 최대값을 구합니다.

옵션 할당 문제 (1)을 비용 매트릭스라고 불리는 매트릭스로 표현하는 것이 편리합니다. 그런 척하자 그리고 와 함께= (ci j) - 두 개의 비용 행렬, 그 요소는 다음과 같이 관련되어 있습니다.

상수는 어디에 있습니까? 따라서 행렬을 얻으려면 와 함께*행렬의 각 i번째 행의 요소에 필요한 와 함께숫자 d,-를 추가하고 각 요소에 제이 - G 영형열 - 숫자 씨.이 경우, 만약 엑스 - 수용 가능한 솔루션(1)의 제한 사항을 충족하고,

그런 다음 평등 유형 (1)의 제한 사항을 고려하여 다음을 얻습니다.

따라서 가능한 모든 솔루션에 대해 엑스해당 함수 값은 상수에 따라 다릅니다. 와이,의존하지 않는 것 엑스 . 따라서 동일한 세트에 두 개의 할당 문제가 있는 경우 G실현 가능한 솔루션과 목표 기능따라서 최적의 솔루션이 일치합니다. 고전적인 수송 문제도 비슷한 속성을 가지고 있다는 것을 쉽게 확인할 수 있습니다.

할당 문제가 최대화 문제인 경우, 즉 최대가 추구된다 목적함수세트에 G(1)의 제한 시스템에 의해 지정된 허용 가능한 솔루션과 동등한 최소화 문제

(3)

목적 함수의 계수가 양수가 아니기 때문에 공식적으로 할당 문제로 분류될 수 없습니다. 이러한 불일치는 (3)을 동등한 문제로 대체하여 극복할 수 있습니다.

(4)

여기서

왜냐면 이 경우에는 모두에게 해당되니까 불평등이 있습니다.

1.2 할당 문제를 해결하기 위한 헝가리식 방법

할당 문제의 공식화를 논의할 때, 이 문제는 고전적인 운송 문제의 특별한 경우이고 결과적으로 운송 유형 문제라는 점에 주목했습니다. 할당 문제에 적용할 때 단순 방법은 실행 가능한 기본 솔루션이 퇴보되기 때문에 효과적이지 않습니다. 할당 문제의 구체적인 특징으로 인해 헝가리식 방법으로 알려진 할당 문제를 해결하는 효과적인 방법을 개발할 수 있었습니다.

헝가리식 방법의 본질은 다음과 같습니다. 특정 방식으로 찾은 숫자를 일부 열에 더하고 일부 숫자를 빼면 소위 독립 0 시스템이 발견됩니다. 동일한 행(행 또는 열)에 두 개 이상의 0이 없는 경우 0 집합을 독립 0 시스템이라고 합니다. 독립적인 0의 개수가 n과 같으면, 진술 2에 따라 해당 변수 x ij를 1로 하고 나머지는 모두 0으로 하여 최적의 할당 계획을 얻습니다.

헝가리식 방법의 알고리즘은 다음과 같이 구성됩니다. 예비 단계(n-2)개 이하의 연속 반복 반복이 가능합니다. 예비 단계에서는 최대 문제를 해결하면 이를 등가 최소 문제로 변환한다. 같은 단계에서 독립적인 0 시스템이 식별됩니다. 각 후속 반복은 독립 0의 수를 1 이상 증가시키는 것을 목표로 합니다. 독립 영점 k의 개수가 행렬 차원(k=n)과 같아지자마자 문제가 해결됩니다.

최적의 계획할당은 마지막 반복에서 독립적인 0의 위치에 따라 결정됩니다.

1. 볼코프 I.K., 자고루이코 E.A. 운영 연구: Proc. 대학을 위해. 두 번째 굴레 / 편집자: V.S. 자루비나, A.P. 크리첸코. – M.: Uzd-vo MSTU im. N.E. 바우만, 2002. – 436p.

2. 자이첸코 Yu.P. 운영 연구: Proc. 대학생을 위한 매뉴얼. – 2판, 개정됨. 그리고 추가 – 키예프: 비슈차(Vishcha) 학교. 주요 출판사, 1979. 392 p.

3. I. A. Akulich. 수학 프로그래밍예와 문제에서. - M .: "고등학교", 1986.- 319 p.

4. 사코비치 V.A. 운영 연구(결정적 방법 및 모델): 참조 가이드. - Mn.: 더 높습니다. 학교, 1984.-256p.

5. Taha H. 운영 연구 소개: 두 권의 책으로 구성. 1,2권 영어로부터 -M .: 미르, 1985.

6. 카자노바 L.E. 경제학의 수학적 프로그래밍: 지도 시간. – M .: BEK 출판사, 1998. – 141 p.

솔루션 알고리즘:

1. 우리는 문제를 최소한으로 해결합니다. 표적 이 단계- 행렬 C에서 가능한 최대 0 수를 얻습니다. 이를 위해 각 행의 행렬 C에서 최소 요소를 찾아 해당 행의 각 요소에서 뺍니다. 마찬가지로 각 열에서 해당 최소 요소를 뺍니다.

지정하지 않은 경우 정사각 행렬, 그런 다음 주어진 행렬의 최대 수와 동일한 비용을 넣어 정사각형으로 만듭니다.

2. 첫 번째 단계를 완료한 후 할당이 가능하면, 즉 각 행과 열에서 0 요소를 선택하면 결과 솔루션이 최적이 됩니다. 예약을 할 수 없는 경우 세 번째 단계로 진행하세요.

3. 최소 선 수를 사용하여 행렬의 모든 0을 지우고 교차되지 않은 요소 중에서 최소 하나를 선택하여 선 교차점에 있는 요소에 추가하고 교차되지 않은 모든 요소에서 뺍니다. 아웃 요소. 다음으로 2단계로 넘어갑니다.

헝가리식 방법은 생산량과 소비량이 정수인 운송 문제를 해결할 때 가장 효과적입니다.

예

할당 문제는 ai = bj = 1인 전송 문제의 특별한 경우입니다. 따라서 전송 문제 알고리즘으로 해결할 수 있습니다. 세부 사항을 고려하여 더 효과적인 다른 방법을 고려해 보겠습니다. 수학적 모델. 이 방법을 헝가리 알고리즘이라고 합니다.

이는 다음 단계로 구성됩니다.

1) 행렬 행과 열의 변환;

2) 목적의 결정;

3) 변환된 행렬의 수정.

1단계. 이 단계의 목표는 행렬 C에서 가능한 최대 0개 요소 수를 얻는 것입니다. 이렇게 하려면 각 행의 모든 요소에서 해당 행의 최소 요소를 빼고, 모든 요소에서 해당 열의 최소 요소를 뺍니다. 각 열의.

2단계.첫 번째 단계를 수행한 후 행렬 C의 각 행과 열에서 하나의 0 요소를 선택할 수 있는 경우 결과 솔루션은 최적 할당이 됩니다.

3단계. 0으로 구성된 허용 가능한 솔루션을 찾지 못한 경우 모든 0이 지워지도록 일부 열과 행을 통해 최소 선 수를 그립니다. 교차되지 않은 가장 작은 요소를 선택합니다. 교차되지 않은 각 요소에서 이 요소를 빼고 그려진 선의 교차점에 있는 각 요소에 추가합니다.

3단계 이후라면 최적의 솔루션달성되지 않은 경우 허용 가능한 솔루션을 얻을 때까지 직선을 그리는 절차를 반복해야 합니다.

예.

개체 간에 리소스를 배포합니다.

해결책. 1단계. 행 1, 2, 3, 4의 최소 요소 값은 각각 2, 4, 11, 4입니다. 각 행의 요소에서 해당 최소값을 빼면 다음을 얻습니다.

1, 2, 3, 4열의 최소 요소 값은 각각 0, 0, 5, 0이다. 각 열의 요소에서 해당 최소값을 빼면 다음을 얻습니다.

2단계. 없음 전체 약속수신되지 않은 경우 비용 매트릭스를 수정해야 합니다.

3단계. 열 1, 행 3, 행 2(또는 열 2)를 지웁니다. 교차되지 않은 최소 요소의 값은 2입니다.

교차되지 않은 모든 요소에서 이를 빼고 두 선의 교차점에 있는 모든 요소를 추가하면 다음을 얻습니다.

답변. 첫 번째 리소스를 세 번째 개체로, 두 번째 리소스를 두 번째 개체로, 네 번째 리소스를 첫 번째 개체로, 세 번째 리소스를 네 번째 개체로 보냅니다. 목적지 비용: 9 + 4 + 11 + 4 = 28.

노트. 1. 원래 행렬이 정사각형이 아닌 경우 행렬을 정사각형으로 만들기 위해 가상의 리소스나 가상의 개체를 도입해야 합니다.

다음 예를 고려하십시오. 다섯 가지 다른 작업을 수행하는 데 다섯 사람이 있다고 가정합니다. 보고 데이터를 통해 우리는 각 직원이 각 작업을 완료하는 데 걸리는 시간을 알 수 있습니다. 이 데이터는 표에 나와 있습니다.

공연자






필요

이 경우, 값은 각 직원이 각 작업을 수행하는 데 소비한 시간을 나타내며, 값은 1 또는 0과 같으며, 직원 i가 할당된 경우 1과 같습니다. 작업 j, 기타 모든 경우에는 0입니다. 따라서 기능을 최소화하는 문제가 줄어듭니다. 비용 경로 선형 프로그래밍

다음 제한 사항이 적용됩니다.

마지막 조건을 버리고 다음 조건으로 바꾸면 분명합니다.

이로 인해 모든 필요와 모든 자원이 1이 되는 운송 문제가 발생합니다. 최적의 솔루션에서는 모두 정수이거나 0이며, 하나만 가능한 정수입니다. 따라서 이러한 조건에서 운송 문제를 해결하면 항상 평등이 발생합니다.

그러나 해결 방법의 퇴화로 인해 운송 작업할당 문제의 경우 효과가 없는 것으로 판명됩니다. 모든 할당에 대해 행별 공급은 항상 열별 수요와 자동으로 일치하므로 2n-1 대신 0이 아닌 n개의 값을 얻습니다. 이와 관련하여 n-1개의 e 값으로 행렬을 채워야 하며, 0이 아닌 값이 최적의 솔루션을 결정하는 것으로 나타날 수 있지만 검사에서는 이를 감지하지 못합니다. e의 위치가 잘못되었습니다.

할당 문제를 해결하는 방법은 상당히 분명한 두 가지 정리에 기초합니다. 그 중 첫 번째는 행렬의 열이나 행에 상수를 더하거나 빼도 해가 변하지 않는다는 것입니다. 이 정리는 다음과 같이 정확하게 공식화됩니다.

정리 1.

최소화하는 경우

다음과 같은 모든 사람을 위해

그런 다음 기능도 최소화합니다.

모두들 앞에 있는 곳

정리 2.

모든 것이 가능하다면 다음과 같은 집합을 찾는 것이 가능합니다.

그렇다면 이 솔루션이 최적입니다.

두 번째 정리는 분명합니다. 첫 번째 정리를 증명하기 위해 우리는

얻기 위해 Z에서 빼는 양은 의존하지 않기 때문에 Z가 최소화될 때마다 최소값에 도달하고 그 반대의 경우도 마찬가지입니다.

개발된 해법은 행과 열에 상수를 더하고 0과 같은 해를 얻기에 충분한 수의 값이 사라질 때까지 행과 열에서 상수를 빼는 것입니다.

해 찾기는 각 행과 열에서 가장 작은 요소를 빼는 것으로 시작됩니다. 표는 위 예의 결과를 보여줍니다.

표 A)

공연자		공제됨

표 B)

공연자






공제됨

열과 행에서 총 10개 단위가 제외되었습니다. 따라서 표 (B)를 사용하여 얻은 솔루션을 올바르게 평가하려면 결과에 10단위를 추가해야 합니다.

우선, 그들은 0개의 요소를 포함하는 표 (B)의 셀만 포함하는 솔루션을 찾으려고 노력합니다. 왜냐하면 그러한 솔루션을 찾을 수 있다면 가능한 최선의 솔루션이 될 것이기 때문입니다. 그러나 여러 솔루션의 품질이 동일한 경우가 있습니다. 허용 가능한 솔루션은 표 (B)에 괄호로 표시되어 있습니다. 그러나 해결방안의 개선이 가능한지 판단하기 위해 다음과 같은 알고리즘을 적용한다.

행이나 열에서 추가로 뺄셈을 하면 새로운 0이 나타날 수 있지만 필연적으로 음수 요소가 나타나므로 이제 0 솔루션이 반드시 최적인 것은 아닙니다. 그러나 행이나 열에 해당 숫자를 추가하면 음수 요소를 제거할 수 있습니다. 예를 들어, 표 (B)의 열 1에서 2를 빼면 요소 2가 행 1에 나타납니다. 이제 행 1에 2를 더하면 음수가 아닌 요소가 있는 행렬이 다시 생성됩니다. 문제는 새로운 0을 얻는 것입니다. 지정된 방법으로, 그러나 동시에 궁극적으로 0으로만 구성된 솔루션을 포함하는 행렬을 얻습니다. 아래에 설명된 알고리즘이 이 문제에 대한 솔루션을 제공한다는 것이 입증될 수 있습니다.

1. 교차하는 수평선과 수직선의 최소 수를 그립니다. 적어도일단 모두 0입니다. 표 (B)에서 이 단계를 수행하면 표 1에 결과가 표시됩니다.

1 번 테이블

이 경우에는 4개의 선만 사용되므로 0 셀에는 최적의 솔루션이 포함되지 않습니다.

2. 선이 그려지지 않는 가장 작은 요소를 선택합니다. 이 예에서는 셀 (5,2)에서 1입니다.
3. 선이 그려지지 않는 모든 요소에서 이 숫자를 빼고 두 선이 그려지는 모든 요소에 더합니다. 이 예는 표 2에 표시된 결과를 생성합니다.

표 2

이 단계를 수행하면 이전에는 0이 없었던 셀에 0이 표시됩니다. 고려 중인 예에서는 셀 (5,2)입니다.

4. 새로운 0 집합 중에 해법이 있는지 확인합니다. 해결책을 찾지 못한 경우(이 예에서는 해결책이 없음) 1단계로 돌아가서 해결책을 찾을 때까지 모든 후속 단계를 수행하십시오. 이 예를 계속해서 고려하면 표 3에 표시된 결과를 얻습니다.

표 3

이 테이블에는 이미 괄호로 표시된 솔루션이 포함되어 있으며, 이 솔루션은 원래의 실행 가능한 솔루션보다 1 더 나은 13의 값을 갖습니다. , .

예시 2.

4명의 학생과 4가지 유형의 작품이 발표되었습니다. 다음 표는 이 문제에 대한 비용 매트릭스에 해당합니다.

알고리즘의 첫 번째 단계를 수행해 보겠습니다.

이제 해당 행의 요소에서 최소 비용을 뺍니다.

알고리즘의 두 번째 단계에서는 열의 최소값을 찾아 해당 열의 요소에서 이를 뺍니다. 결과적으로 우리는 다음 표에 제시된 매트릭스를 얻습니다.

안에 마지막 행렬요소가 0개인 배열은 각 자녀에게 하나의 직업을 할당하는 것을 허용하지 않습니다. 예를 들어 Dasha에게 차고 청소를 할당하면 첫 번째 열은 추가 고려 사항에서 제외되며 Alla의 행에는 0 요소가 없습니다.

1) 마지막 행렬에서는 모든 0 요소를 제거하기 위해 행과 열을 따라 최소 수의 가로 및 세로 선을 그립니다.
2) 줄이 그어지지 않은 가장 작은 요소를 찾아서, 줄이 그어진 나머지 요소에서 이를 빼고 그려진 선의 교차점에 위치한 요소에 추가합니다.

문제에서 이 예세 개의 직선이 필요하며 이는 다음 표로 이어집니다.

교차되지 않은 가장 작은 요소는 1과 같습니다. 교차되지 않은 나머지 요소에서 이 요소를 빼고 선의 교차점에 있는 요소에 추가합니다. 결과적으로 우리는 다음 표에 제시된 매트릭스를 얻습니다.

표에 표시된 최적의 솔루션은 Dasha는 차고 청소, Katya는 잔디 깎기, Alla는 세차, Sasha는 개 산책을 제안합니다. 해당 값목적 함수는 1+10+5+5=21입니다. 의 값과 줄을 그어 지우지 않은 요소 중 가장 작은 요소의 값을 합하면 동일한 값을 얻을 수 있습니다.

그것은 밝혀졌습니다- 그래프. 왼쪽의 정점은 개발자이고, 오른쪽의 정점은 기술(작업)입니다. 이를 연결하는 가장자리는 개발자가 이를 얼마나 이해하고 있는지 나타냅니다. 이 숫자는 이 기술에 대한 개발자의 숙련도는 매우 중요하지만 이에 대해서는 잠시 후에 살펴보겠습니다. 그동안 우리는 이 문제를 효과적으로 해결하는 방향을 이미 정확하게 설명했습니다.

3. 그래프

그래프의 기본 사항은 기사 ()에 설명되어 있으므로 즉시 이 작업과 관련된 용어로 넘어가겠습니다.

이분 그래프– 정점 집합이 두 부분(공유)으로 분할되어 각 가장자리의 끝이 서로 다른 부분에 속하는 그래프입니다. 우리 작업에는 명확한 구분도 있습니다. 일부 정점은 개발자이고 다른 정점은 작업이며 연결(소유 효율성)은 개발자와 작업 사이에만 존재합니다.
어울리는무방향 그래프 G는 M의 두 모서리가 인접하지 않도록 선택된 모서리 E의 부분 집합 M입니다. 즉 공통 꼭지점이 없습니다. 우리 문제의 관점에서 이것의 동의어는 다음과 같습니다. "약속", 관련된 각 개발자가 별도의 작업을 수행하도록 합니다. 그리고 두 명의 개발자가 하나의 문제를 해결하고 있거나 한 명의 "불쌍한 사람"이 두 가지 작업을 담당하고 있는 것으로 밝혀지지 않았습니다.

그래프 이론에서 우리의 문제는 이상하게도 다음과 같이 불립니다. 할당 작업(ZN). =) 최대 매칭을 찾는 문제의 특별한 경우입니다. 실제로 우리는 동시에 작업할 수 있도록 리소스를 최대한 활용하려고 노력합니다. 최대 수따라서 기술의 관점에서 우리는 "최대 매칭"을 찾고, 최대 금액개발자-작업 쌍.

4. 최대 매칭

삶을 더 쉽게 만들기 위해 우리는 아직 사람들의 능력에 관심을 기울이지 않습니다. 우리는 모두를 위한 일자리를 찾고 싶습니다. 처음 몇 명의 개발자에게 익숙한 기술을 사용하여 작업할 기회를 제공하는 것은 문제가 되지 않습니다. 같은 정신으로 계속해서 몇 가지 작업을 더 분배할 예정이지만 이러한 방식으로 구성된 매칭은 최대가 아닐 것입니다. 그림에 표시된 것과 같은 상황이 가능합니다.

매칭(과제)을 늘리는 방법은 무엇입니까?

아직 작업이 할당되지 않은 유휴 개발자를 선택해 보겠습니다. 그가 무엇을 처리할 수 있는지 봅시다. 그에게 익숙한 기술. 그중에서 무료인 것을 찾으셨다면 좋습니다. 그것이 바로 우리가 찾던 것입니다. 우리가 임명합니다. 다른 개발자가 이미 작업을 "수취"한 경우에는 어떻게 되나요? 바쁜 개발자를 위해 또 다른 무료 기술을 찾아보도록 하겠습니다. 이 경우 이 기술을 유휴 병동에 할당하기 때문입니다. 일반적으로 작업을 재할당하려는 유휴 개발자 또는 개발자의 위에서 우리는 그에게 친숙한 모든 기술을 무료로 살펴봅니다.

무료를 찾으면 검색이 완료됩니다.
작업이 이미 누군가에게 할당된 경우 이 일치하는 가장자리를 통과한 후 이 할당에 참여하는 개발자에게 기술을 "재할당"하려고 시도합니다.

그래프를 탐색하는 동안 우리는 '관여되지 않은 개발자'에서 '무료 작업'으로 이동하려고 합니다. 따라서 검색은 다음 트리로 "확장"됩니다.

간단한 단어로 그래프 이론의 용어를 조금 더 추가해 보겠습니다.

노출된 상의– 현재 매칭에 관여하지 않는 정점이다. 저것들. "커밋되지 않은 개발자" 또는 "무료 작업"입니다.
교대 체인가장자리가 교대로 놓이거나 일치하지 않는 체인입니다. (... - 기술 숙달 - 할당된 작업 - 기술 숙달 - 할당된 작업 - ...)
대체 트리– 교대로 체인으로 구성된 트리
보강 체인– 이것은 초기 정점과 최종 정점이 노출되는 교대 체인입니다. 이것이 우리가 찾고 있는 것의 이름입니다! =)
증강 트리- 각각, 가지 중 적어도 하나가 증가 사슬인 트리입니다.

그래서 우리는 최대치를 얻으려고 노력하면서 매칭을 높이는 방법을 찾았습니다. 교대 트리를 구축하는 것이 필요합니다. 증강되면 "관련되지 않은 개발자"에서 "자유 작업"까지의 증강 체인을 찾은 다음 그에 따라 작업을 "재할당"합니다. 이것은 유익합니다. 왜냐하면 "처리 중인 작업" 수를 1만큼 늘립니다.

이제 우리는 사용할 수 있습니다 가장 큰 수프로젝트의 기술. 이제 우리에게 제기된 문제의 또 다른 중요한 조건, 즉 기술 소유권의 효율성을 고려할 때입니다. 우리는 정말로 원한다 최적의모든 사람에게 작업을 할당합니다.

5. 헝가리식 방법.

총 효율성(비용)이 최대인 솔루션을 찾으세요. 이는 어떤 의미에서는 다음 문제와 유사하게 들립니다. 최적의 포장배낭 생각하게 만드네요. 이제 우리가 "탐욕스러운 알고리즘"의 원칙에 따라 행동할 기회가 있었다면 좋았을 것입니다.

우리는 모든 개발자에게 최대 능력에 따라 작업을 할당하는 것부터 시작했습니다. 모든 개발자가 작업을 즉시 배포할 수 있다면 좋습니다. 그러나 이것은 자주 발생하지 않습니다. 두 사람이 동일한 기술에 대한 최적의 지식을 갖고 있다면, 누가 그것을 얻을 것이며, 이 상황에서 무엇을 해야 할까요? 개발자 중 한 명은 자신의 능력에 가장 적합한 또 다른 무료 작업을 찾아야 합니다. 현재 ( 최대 요구 사항) 조건에 무료 작업이 없으면 작업 중에서 하나를 찾으려고 노력해야 하며 먼저 요구 사항을 약간 낮춰야 합니다. 그래프에서 개발자의 능력을 인위적으로 낮추는 방법. 그러한 조건에서 무료 작업을 찾으면 증강 트리를 얻게 됩니다. 일치하는 체인을 따라 "변경"하면 +1이 됩니다. 그리고 우리는 모두에게 일자리를 찾을 때까지 이러한 최적의 방식으로 계속 임명할 것입니다.

전략은 분명하다.

헝가리 알고리즘의 원리를 거의 알아냈습니다. 그러나 "탐욕스러운 알고리즘"의 원칙에 따라 솔루션을 구축할 수 있는 방법은 다음과 같습니다. 최대 능력을 끝까지 할당한 다음 능력을 약간 낮추고 고려 사항에 새 작업을 추가하고 끝까지 할당하고 낮추는 등. ? 현재 과제의 능력과 최적성을 어떻게 평가합니까?

이 알고리즘의 전체 "트릭"은 다음과 같습니다. 그래프에는 단 하나의 매개변수, 즉 특정 문제를 해결하는 개발자의 효율성이 제공되며 이는 가장자리에 표시됩니다. 이 값은 개발자-작업 쌍에 할당됩니다. 우리는 이 양을 둘로 "나누"(쌍에서 분리)할 것입니다. 두 개의 추가 매개변수를 인위적으로 추가해 보겠습니다. 일부 값은 작업 정점에 할당되고 다른 값은 개발자 정점에 할당됩니다.

나는 이런 해석을 하려고 노력할 것이다:

개발자에게 알려드리겠습니다. "능력", 단순히 우리가 힘을 얼마나 효과적으로 사용할 수 있는지 또는 사용해 왔는지를 나타내는 "힘" 단위로 가정해 보겠습니다.
작업에 대해 표시하겠습니다. "공부했다", 또는 말하자면 "과도한 관심"입니다. 또한 이 매개변수를 "강도"로 측정하겠습니다. 다음 상황에서는 작업에 대한 과도한 관심이 발생합니다. 일부 개발자를 "과부하"한 경우, 즉 그는 5개로 문제를 해결할 수 있지만 3개만 얻었습니다. 그렇다면 그는 원칙적으로 자신에게 익숙한 일부 작업에 전념할 수 있는 2개의 "강점"을 여전히 가지고 있습니다. 사무실을 오가며 전화로 상담하고, 그가 좋아하는 기술 관련 사람들에게 조언을 제공하세요.

따라서 우리는 가장자리에 표시된 값을 정점에 할당된 2개의 값, 즉 문제 해결 효율성 = 개발자의 능력 + 문제에 대한 지식으로 "나눕니다". 원칙적으로는 논리적입니다. 개발자의 능력이 뛰어나거나 기술이 더 잘 알려져 있을수록 프로젝트의 이 부분이 더 잘 구현될 것입니다. 더 효율적입니다.

결국 우리가 해결책을 찾은 후에는 물론 가장자리의 값만 고려하게 되지만 이제 이 "트릭"은 해결책을 찾는 데 도움이 될 것입니다. =)

6. 알고리즘 설명

그래프를 초기화해 보겠습니다. 존재 " 완고한 낙천주의자", 각 개발자에 대해 우리는 그에게 친숙한 기술에 대한 그의 최대 "능력"을 계산하고 이 숫자를 그에게 할당합니다. 모든 사람은 자신에게 가장 적합한 일을 즐깁니다.. 아직 작업에 대해 알려진 바가 없으므로 "지식"을 0으로 초기화합니다.

"관련되지 않은 개발자"를 위한 "무료 작업"을 검색할 때 이제 그래프의 최적 가장자리로만 제한하겠습니다. 평등이 유지되는 것들: 문제해결 효율성(Edge) = 개발자 능력(Vertex) + 문제에 대한 지식(Vertex).

다음으로 최대 매칭을 찾을 때와 동일한 방식으로 진행합니다. 우리는 유휴 개발자를 하나씩 잡고 무료 작업을 찾아 교대 트리(교대 체인으로 구성)를 구축하지만 최적의 가장자리를 따라서만 구축합니다. 그러면 다음과 같은 2가지 상황이 발생할 수 있습니다.

우리는 무료 작업을 찾았습니다. 나무가 강화되었습니다. 우리는 작업을 "재할당"하고 일치도를 높입니다. 우리는 교대 트리를 다시 만들기 시작합니다. 왜냐하면 당신은 카운트가 어떻게 변했는지 전혀 알 수 없습니다
우리는 자유 최적 에지 문제를 발견하지 못했습니다(도달하지 못했습니다). 그리고 그것은 존재합니다. 왜냐하면 결국 우리는 무료 개발자로 시작했고 칼럼에는 동일한 수의 작업과 개발자가 있습니다. 결과로 나오는 교대 트리는 소위 헝가리 인(전체 방법은 동일하다고 불립니다). 이 경우 개발자에 대한 요구 사항을 약간 낮추고 검색을 다시 시작해야 합니다. 실패는 단순히 다시 시작할 수 있는 기회입니다. 이번에는 좀 더 지능적으로(c).

이제 우리는 헝가리식 방법의 마지막 순간에 이르렀습니다. 추가 옵션그리고 "능력"에 대해 생각했습니다. 교대 트리를 성장시켜 궁극적으로 헝가리 트리를 얻는다고 가정해 보겠습니다. 이 트리에 어떤 정점이 포함될지 생각해 보겠습니다.

관련되지 않은 개발자 우리가 나무 비용을 지불하기 시작하는 것은 그들로부터입니다
관련되지 않은 개발자가 최적의 가장자리를 따라 도달할 수 있는 개발자 및 작업입니다. 왜냐하면 우리가 후자를 채용하려는 것은 그들의 "재할당"을 통해서입니다.

이 트리 외부의 나머지 그래프에는 다음이 포함됩니다.

일치하지만 자유 정점(개발자)에서 액세스할 수 없는 개발자 및 작업입니다. 우리는 그들에게 일자리를 찾았습니다. 지금은 그들에게 손댈 것이 아무것도 없습니다.
최적의 가장자리를 사용하여 달성할 수 없는 작업은 우리가 달성해야 할 작업입니다. 따라서 트리를 구성할 때 우리가 도달한 정점을 표시합니다. 따라서 이러한 작업은 표시되지 않은 상태로 유지됩니다.

다음 루프에서 우리는 트리의 "경계"를 따라 실행합니다. 즉, 관련되지 않은 개발자나 접근 가능한 개발자("재할당"될 수 있음)를 인접한 작업(비최적 가장자리를 따라)과 연결하는 가장자리를 따라 실행합니다. 이 모서리를 사용하여 최소값을 계산합니다. 이 순간이 작업을 시작할 수 있도록 개발자 능력의 "불일치": delta = min(개발자 능력(Vertex) + 문제에 대한 지식(Vertex) - 문제 해결 효율성(Edge)).

그런 다음 헝가리 트리 내부에서 다음을 수행합니다.

최소한 하나의 가장자리를 교대 트리에 "부착"하기 위해 델타만큼 개발자의 능력을 낮추자. 다음번우리는 계속해서 무료 문제를 찾을 것입니다
이미 구성된 확대 그래프 내부의 가장자리가 최적으로 유지되도록 델타 문제에 대한 "지식"을 늘려보겠습니다. 저것들. 평등이 유지되도록: 문제 해결의 효율성(edge) = 개발자의 능력(vertex) + 문제에 대한 지식(vertex)

미니 해석: 개발자 중 적어도 하나를 "부착"하기 위해 개발자의 능력을 낮춥니다. 우리는 그를 위해 일자리를 찾을 것이지만 그는 그의 자격에 따라 일하지 않을 것입니다. 그는 더 많은 일을 할 수 있었습니다. 따라서 그는 자신이 가장 유능한 업무에 대해 동료들에게 조언할 시간을 확보합니다. 그녀는 팀에서 더 많이 연구됩니다. 이것은 아마도 다른 개발자에 의해 처리되었을 것이며, 이제 어떤 일이 발생하면 그 개발자도 그를 대체할 수 있을 것입니다. 작업에 대한 지식 측면에서 그의 역량을 줄일 수도 있습니다. 등등, 팀의 "체인을 따라" 작업에 대한 "지식"이 증가하고 개발자가 해당 작업에 대한 할당을 찾는 능력이 약간 감소합니다.

모두. 모든 단계 이 방법검토했습니다. 우리는 같은 정신으로 계속합니다 ... 성공은 최종적인 것이 아니며, 실패는 치명적이지 않습니다. 중요한 것은 계속하려는 용기입니다..

7. 알고리즘을 말로 표현하면 매우 간단합니다.

이제 모든 것을 종합해 보겠습니다.

초기화. 개발자 - 최대 능력. 작업이 연구되지 않았습니다.
아직 모든 개발자에게 작업이 부여된 것은 아닙니다.
- 지금까지 최적의 에지를 사용하여 증대 트리(무료 작업 찾기)를 구축하는 것이 가능합니다.
  - 매칭을 늘려 작업을 "재할당"
- 무료 작업에 도달하지 못했습니다. 헝가리 나무.
  - 개발자 능력을 최소한으로 줄이는 것

8. 상장

물론 코드는 전체 설명보다 짧습니다. =)

내가 가져 갔어. 제 생각에는 매우 좋은 구현입니다. 유일한 차이점은 저자가 할당을 최소화하는 방법에 대한 코드를 제공하고(예를 들어 가장자리에 급여가 있는 경우) 기사에서 작업을 분배하여 작업을 배포했다는 것입니다. 최대 효율성. 따라서 코드를 약간 수정하여 최대 메소드 구현을 아래에 제공합니다.

int n;
벡터< vector>아; // 성능 매트릭스 a[개발자][작업]
벡터 xy, yx; // 일치 항목: xy[개발자], yx[작업]
벡터 vx, vy; // 교대 트리 vx[developer], vy[task]
벡터 맥스로우, 민콜; // 능력, 지식
bool dotry (int i) (
if (vx[i]) 반환 false ;
vx[i] = 참 ;
for (int j=0; j if (a[i][j]-maxrow[i]-mincol[j] == 0)
vy[j] = 참 ;
for (int j=0; j if (a[i][j]-maxrow[i]-mincol[j] == 0 && yx[j] == -1) (
xy[i] = j;
yx[j] = i;
참을 반환 ;
}
for (int j=0; j if (a[i][j]-maxrow[i]-mincol[j] == 0 && dotry (yx[j])) (
xy[i] = j;
yx[j] = i;
참을 반환 ;
}
거짓을 반환 ;
}
int 메인() (
// ... 읽는 중 ...
Mincol.할당(n, 0);
minrow.할당(n, 0);
for (int i=0; i for (int j=0; j maxrow[i] = max(maxrow[i], a[i][j]);
Xy.할당(n, -1);
yx.할당(n, -1);
for (int c=0; c vx.할당(n, 0);
vy.할당(n, 0);
정수 k = 0;
for (int i=0; i if (xy[i] == -1 && dotry (i))
++k;
c += k;
if (k == 0) (
int z = INF;
for (int i=0; i if(vx[i])
for (int j=0; j 만약 (!vy[j])
z = min (z, maxrow[i]+mincol[j]-a[i][j]);
for (int i=0; i if (vx[i]) maxrow[i] -= z;
if (vy[i]) mincol[i] += z;
}
}
}
int ans = 0;
for (int i=0; i ans += a[i]];
printf("%d\n" , ans);
for (int i=0; i printf("%d " , xy[i]+1);
}
* 이 소스 코드는 소스 코드 하이라이터로 강조 표시되었습니다.

9. 합계

누군가 헝가리어를 처음 본다면. 그리고 설명과 목록을 읽은 후에는 "예, 목록에서도 이러한 설명 없이도 문제가 있다는 것이 모든 것이 분명합니다"라는 자신감을 갖게 될 것입니다. 나는 적어도 부분적으로 설명이 알고리즘 작동에 대한 이해를 더해주기를 바랍니다. 나는 진심으로 당신을 위해 행복할 것입니다! 그리고 결과적으로 이것은 내가 아마 이유가 있어서 이 글을 썼다는 느낌을 줄 것입니다. =)

태그:

할당 문제
헝가리어 알고리즘
쿤의 알고리즘

태그 추가

예선 .

1 단계. ~에 목적함수 최대화 와 함께최대 요소를 찾아 최대값에서 이 열의 각 요소를 뺍니다. ~에 목적 함수 최소화(처방 효율성 지표의 합) 매트릭스의 각 열에 와 함께최소 요소를 찾아 해당 열의 각 요소에서 뺍니다.

와 함께 음수가 아닌 요소로. 행렬의 각 열에서 와 함께 0이 하나 이상 있습니다.

2 단계. 행렬의 각 행에서 와 함께 최소 요소를 찾아 이 문자열의 각 요소에서 뺍니다.

결과적으로 매트릭스가 형성됩니다. 와 함께음수가 아닌 요소가 있는 0입니다. 행렬의 모든 열과 모든 행에서 와 함께 0 각각 적어도 하나의 0이 있습니다.

3단계. 첫 번째 열의 0은 별표로 표시하세요. 두 번째 열부터 시작하여 행렬의 각 열을 봅니다. 와 함께 0이고 0이 없는 줄에 있는 0을 별표로 표시합니다. 각 열에는 하나의 0만 별표로 표시될 수 있습니다. 분명히, 행렬의 0은 와 함께별표로 표시된 0은 구성에 의해 독립입니다. 이것으로 예비 단계가 종료됩니다.

( 케이 + 1)번째 반복 . 가정해보자 케이- 이미 반복이 수행되었으며 결과적으로 행렬이 얻어졌습니다. 와 함께 케이 . 매트릭스에 있는 경우 와 함께 케이 정확히 있어요 피별표가 있는 0이면 솔루션 프로세스가 종료됩니다. 별표가 있는 0의 개수가 적은 경우 피, 그런 다음 ( 케이+ 1)번째 반복.

각 반복은 첫 번째 단계에서 시작하여 두 번째 단계에서 끝납니다. 그 사이에 두 단계를 여러 번 수행할 수 있습니다. 세 번째 - 첫 번째. 반복을 시작하기 전에 "+" 기호를 사용하여 강조 표시합니다.기둥 행렬와 함께 케이 , 여기에는 0과 별표가 포함됩니다..

첫 단계 . 보다 선택되지 않음행렬 열 와 함께 케이. 그 중에 0개의 요소가 없으면 다음으로 이동합니다. 세 번째 단계.

선택되지 않은 행렬의 0이 와 함께 케이감지되면 다음 두 가지 경우 중 하나가 가능합니다.

이 줄에는 별표가 있는 0이 포함되어 있지 않습니다.

안에 첫 번째 경우 선택되지 않은 0을 대시로 표시그리고 라인 선택 , 오른쪽에 "+" 기호를 배치하여 해당 내용이 포함되어 있습니다. 그 다음에 "+" 기호에 동그라미를 쳐서 없애세요.그 이상 열 , 선택한 선과의 교차점에는 별표가 있는 0이 포함됩니다.

 그런 경우 영 이 발견되고 해당 열에 유일한 항목인 경우 표시 그의 뇌졸중 그리고 라인 선택 그러한 0을 포함하는 (라인)은 "+" 기호로 표시됩니다. 그런 다음 이 줄을 살펴보고 별표가 있는 0을 찾으세요.

 그런 경우 영 가 열에 있지만 열에 유일한 것이 아닌 경우 다음 0 중에서 선택해야 합니다.

우선, 0*이 없는 것과 같은 줄에 그러한 0이 있습니다.

둘째, 0*이 있는 동일한 행에 0이 있지만 이 0*이 있는 동일한 열에는 선택되지 않은 0이 있습니다.

마지막으로, 0*이 있는 한 행에는 0이 있지만 이 0*이 있는 한 열에는 선택되지 않은 0이 없습니다.

유한한 수의 단계로 구성된 이 프로세스는 다음 결과 중 하나로 끝납니다.

결과 1. 모든 행렬 0 와 함께 케이강조 표시됩니다. 즉, 선택한 행이나 열에 위치합니다. 이 경우 세 번째 단계로 이동;

출애굽기 2. 별표가 있는 0이 없는 문자열에 선택되지 않은 0이 있습니다. 그 다음에 두 번째 단계로 이동, 마지막 0을 획으로 표시 .

~ 안에 두 번째 경우 , 선택되지 않은 0을 스트로크로 표시한 후 즉시 두 번째 단계로 진행합니다.

두 번째 단계 . 다음과 같은 행렬 요소 체인을 구성합니다. 와 함께 케이: 소수가 있는 선행 0, 첫 번째 것과 동일한 열에 위치한 별표가 있는 0, 별표가 있는 선행 0과 같은 행에 위치한 소수가 있는 0 등. 따라서, 사슬은 움직임에 의해 형성된다 0"에서 0*까지 열별, 0*에서 0"까지 줄별로등.

체인을 구성하기 위해 설명된 알고리즘이 명확하고 유한하다는 것이 입증될 수 있습니다. 여기서 체인은 항상 시작되고 끝납니다 소수가 있는 0 . 다음으로, 홀수 위치(0")에 있는 체인 요소 위에 별표를 배치하고 짝수 요소(0*) 위에서 별표를 삭제합니다. 그런 다음 행렬 요소 위의 모든 스트로크를 삭제합니다. 와 함께 케이및 "+" 기호. 이 경우 독립된 0의 개수는 1씩 증가합니다.. (케이 + 1)번째 반복 완료.

세 번째 단계 . 이 단계로 넘어가야 합니다 첫 번째 단계 이후 만약에 행렬의 모든 0 와 함께 케이 강조 표시됨즉, 선택한 행이나 열에 있습니다. 이 경우, 행렬의 선택되지 않은 요소 중에서 와 함께 케이 선택하다 최소 요소그리고 표시해 시간 > 0.

덜다 시간 모든 강요 행렬 와 함께 케이 , 선택되지 않은 줄에 위치 , 그리고

추가하다 시간모든 강요 행렬 와 함께 케이 , 전용 열에 위치 .

결과는 다음과 같은 새로운 행렬입니다. 와 함께 케이 .

행렬의 선택되지 않은 요소 중에서
(정의에 따라) 새로운 0이 나타날 것입니다. 첫 번째 단계로 이동해야 하며, 행렬 대신 와 함께 케이 매트릭스를 봐
.

첫 번째 단계를 완료하거나 두 번째 단계 , 선택되지 않은 0이 별표가 붙은 0을 포함하지 않는 문자열에 있는 경우, 또는 다시 세 번째 단계로 돌아갑니다 , 첫 번째 단계의 결과로 모든 행렬이 0인 경우
강조될 것이다.

첫 번째 경우 두 번째 단계 이후 반복 종료.

두 번째 경우에는 세 번째 단계 이후에 행렬이 얻어집니다.
~
~와 함께 케이. 매트릭스에서
선택되지 않은 0이 나타나고 첫 번째 단계부터 시작하여 전체 작업 순서를 반복해야 합니다. 제한된 횟수의 반복 후에 다음 첫 번째 단계는 반드시 전환으로 종료됩니다. 두 번째 단계로 , 그 동안 독립된 0의 개수는 1씩 증가합니다. 그 후 (케이+ 1)번째 반복 종료.

실시예 9.헝가리식 방법을 사용하여 문제를 해결해 보겠습니다.

전투수상함은 5개의 대공화기(ASF)를 보유하고 있습니다. 선박에는 5 유닛의 동시 적 공습이 수행됩니다. 모두의 놀라운 잠재력 나- AIA 제이-번째 적 항공기는 다음과 같습니다. (잠재적으로 파괴된 수 제이– 한 대의 항공기가 북한을 공격하는 동안 x 항공기). 모든 AAM은 모든 목표물에 발사할 수 있다고 가정합니다.