알고리즘 디자인 및 분석 - 선형 계획

저 자 는 반 학기 동안 선형 계획 문 제 를 이해 하지 못 하고 무수 한 자 료 를 보 았 다.뒤에 또 몇 번 의 수업 을 듣 고 마침내 대충 알 게 되 었 다.현재 소감 코드 를 여기에 열거 하여 알고리즘 디자인 과 분석 에 시 달 리 는 후배 들 을 행복 하 게 합 니 다.표준 형:

min z = c.transpose().dot(x)
s.t. Ax <= b
	for all i, x_i >= 0

단순 형법: 일부 개념: 기, 기본 가능 해 (즉 특정한 그룹의 기 계수 에 있 는 x 만 0 이 아 닌 것) 유도: 벡터 형식 을 사용한다.이완 변수 추가:

min z = c.transpose().dot(x)
s.t. A*x' == b
	for all i, x_i >= 0

등식 양쪽 동 승 B 의 역 (여 기 는 내 가 바보 야. 사실은 A 는 방진 이 아니 라 mxn 이 고 B 야 말로 방진 이 고 역 을 함유 한 거 야)

np.dot(np.dot(np.linalg.inv(B), A),x) = np.linalg.inv(B).dot(b)

(다음은 위조 코드 를 사 용 했 습 니 다. 알 아 보면 됩 니 다. numpy 코드 를 치 는 것 은 너무 피곤 합 니 다) 아래 의 유도:

B-1*A*x = B-1*b
Ax = B*x_B + N*x_N
x_B + B-1*N*x_N = B-1*b
#        
z = c.transpose() * x
   = c_B.transpose() * x_B + c_N.transpose() * x_N
   = c_B.transpose() * (B-1*b - B-1*N*x_N) + c_N.transpose() * x_N
   = c_B.transpose() * B-1 * b + (c_N.transpose() - c_B.transpose() * B-1 * N) *x_N
   = c_B.t * B-1 * b + (c_B.t - c_B.t * B-1 * B)*x_B + (c_N.t - c_B.t * B-1 * N) *x_N
   = c_B.t * B-1 *b + (c_t -c_B.t * B-1 *A) * x

앞의 항목 을 z0 으로 기록 하고 뒤의 계 수 를 \ lambda 로 기록 하면 선형 변환 단일 형 법의 표준 식 을 얻 을 수 있 습 니 다. 그리고 우리 의 목 표 는 초기 실행 가능 한 해 를 변환 을 통 해 최 적 화 를 얻 는 것 입 니 다.z 를 가장 잘 만족 시 키 는 모든 lambda 계 수 는 0 보다 크 고 그러면 계수 가 0 이 아 닌 xi 모두 0 이면 z 가 극치 를 얻 을 수 있다.그렇지 않 으 면 x 는 무한대 로 향 할 수 있다.원래 의 목표 함 수 는 가장 좋 은 해 가 없다.만약 어떤 lambda 가 0 보다 작다 면, 이 x 는 제한 할 수 없다.우 리 는 이 x 를 바 꿔 야 한다.정 리 는 이미 증명 되 었 는데, x 를 바 꾼 후의 해 는 여전히 기본적으로 풀 수 있다.정리 적 인 방법 에 따 르 면 모든 alpha [i, k] 가 0 (모든 i) 보다 작 으 면 이 문 제 는 풀 리 지 않 습 니 다.우 리 는 다른 x 를 모두 0 으로 취하 면 alpha [i, k] 에 대응 하 는 x 는 무한대, 이완 변 수 를 보고 취 할 수 있 기 때문이다.여전히 b 보다 작은 조건 을 만족시킨다.그리고 모든 알파 가 0 보다 크 면 연산 을 하고 베타 / 알파 의 가장 작은 것 을 바 꿉 니 다.이렇게 바 꾸 는 것 은 앞의 정리 적 증명 과 일치 하 는 것 이 고 새로운 해 가 여전히 실행 가능 하 다 는 것 을 확보 하려 면 모든 베타 가 0 보다 크다 는 것 을 보증 해 야 한다.한편, theta 는 실제 적 으로 모든 베타 가 빼 야 할 양 으로 이 양 이 0 보다 많 도록 보장 한 다음 에 행렬 을 바 꾸 는 것 이다.변 경 된 변수 에 대응 하 는 열 을 epsilon (즉, 변 경 된 변수의 계 수 를 모두 1 로 바 꾸 는 것) 으로 바 꾸 고 해당 하 는 lambda 를 0 으로 제거 합 니 다.여기 서 z 와 lambda 는 위의 x 와 alpha 형식 으로 통일 되 고 z0 은 베타 열 에 기록 되 어 있 으 며 반대 수 를 취해 야 합 니 다.그리고 종료 조건 까지 순환 합 니 다.
그 다음은 인공 변수 와 2 단계 법 이다.앞에서 b 보다 작은 상황 만 논 의 했 고 b 보다 큰 상황 을 고려 해 야 한다 (마지막 에 똑 같은 상황 으로 전환 할 수 있다).이때 인공 변 수 를 넣 고 보조 문 제 를 해결 하 는 min w = 모든 인공 변 수 를 합 쳐 야 합 니 다.만약 w 가 0 이 라면, 원래 의 문제 가 풀 렸 다 는 것 을 설명 하고, 그렇지 않 으 면 풀 리 지 않 았 다.마지막 으로 한 조 의 실행 가능 한 해 를 얻 었 다.인공 변 수 를 포함 하지 않 으 면 인공 변 수 를 직접 삭제 하고 다시 단순 형 법 으로 해석 합 니 다. 그렇지 않 으 면 변 형 된 알파 베타 집합 을 처리 하거나 선형 관련 (즉, 원 변수의 계 수 는 모두 0) 의 열 을 삭제 합 니 다. 그렇지 않 으 면 특정한 계수 가 0 이 아 닌 변 수 를 바 꾸 어 다시 교체 하고 마지막 으로 이전 상황 으로 돌아 갑 니 다.여기 주의 하 시 면 두 단계 에서 z0 과 모든 lambda 값 은 다시 계산 해 야 합 니 다.이것 은 간단 한 단순 형법 에서 우 리 는 모든 이완 변수 (계 수 는 모두 1) 를 기본 으로 선택 하여 z 에 나타 나 지 않 기 때문이다. B = E, cB. t * b = 0 * b = 0. 즉 z0 = 0, lambda = c. t.따로 계산 안 해도 돼.그리고 구 해 를 시작 하면 됩 니 다.
대구 계획: 주요 한 정 리 는 원시 계획 과 대구 계획 이 동시에 가장 좋 은 해 를 얻 는 것 이다.그리고 하나의 계획 이 실행 가능 한 동시에 다른 계획 이 회전 하 는 것 이 가장 좋다.(목표 함수 에 경계 가 없 으 면 대구 계획 에 최 적 화 된 해석 이 없다) 정규 기: 대응 하 는 lambda 가 0 보다 크 면 B 가 정규 기 라면 y 가 실행 가능 하 다 는 것 을 증명 할 수 있다.실제 적 으로 모든 lambda 가 0 보다 크 면 x 를 변환 시 켜 실행 가능 한 해 가 되도록 하 는 것 이다. 즉, 모든 베타 가 0 보다 크 면 단순 형 법 을 거꾸로 하 는 것 이다.
저 자 는 앞의 두 가지 단순 형법 을 실현 하 였 다.세 번 째 는 조금 만 수정 하면 된다.구현 코드 링크:https://github.com/Murphy-OrangeMud/Algorithm-Analysis 문제 제기 환영 합 니 다.
그리고 정수 선형 계획 을 말 해 보 세 요.분기 한계 알고리즘 을 사용 하면 됩 니 다.상응하는 이완 알고리즘 에 대해 해답 을 구하 고 정수 요 구 를 만족 시 키 면 직접 출력 한다. 그렇지 않 으 면 조건 x < = 하 추출 알파 와 x > = 상 추출 알파 가 각각 해답 과 교 체 를 한다.차례로 실현 하 다.이 건 안 돼.재 귀 함 수 를 하나 더 해서 단순 형법 을 봉 하면 될 것 같다.