검색어 입력폼

[수학] 연립부등식의 쌍대성 증명

등록일 2003.09.29 워드파일MS 워드 (doc) | 8페이지 | 무료

소개글

선형계획 문제의 쌍대성에 관한 증명입니다.

쌍대성을 이용하면 다음과 같은 문제

"x + 2y + 3z + 4w ≥ 10,
5x + 3y + 4z + 2w ≥ 20,
x, y, z, w ≥ 0
일 때 (4x + 3y + 2z + w)의 최소값을 구하라."

를 푸는 대신 이것의 쌍둥이 문제인

"a + 5b ≤ 4,
2a + 3b ≤ 3,
3a + 4b ≤ 2,
4a + 2b ≤ 1,
a, b ≥ 0
일 때 (10a + 20b)의 최대값을 구하라"

를 푸면 됩니다. 구체적인 예를 통해 이해하기 쉽도록

만들었습니다.

목차

1. 선형계획법(linear programming)
2. 단체법(simplex method)
3. 선형계획의 쌍대성(linear-programming duality)

본문내용

선형계획 문제의 쌍대성에 관한 증명입니다.

쌍대성을 이용하면 다음과 같은 문제

"x + 2y + 3z + 4w ≥ 10,
5x + 3y + 4z + 2w ≥ 20,
x, y, z, w ≥ 0
일 때 (4x + 3y + 2z + w)의 최소값을 구하라."

를 푸는 대신 이것의 쌍둥이 문제인

"a + 5b ≤ 4,
2a + 3b ≤ 3,
3a + 4b ≤ 2,
4a + 2b ≤ 1,
a, b ≥ 0
일 때 (10a + 20b)의 최대값을 구하라"

를 푸면 됩니다. 구체적인 예를 통해 이해하기 쉽도록

만들었습니다.

참고 자료

1. Advanced engineering mathematics(공업수학)
2. Introduction to Algorithms, Thomas H. Cormen 외 4인 저
다운로드 맨위로