선형 계획법의 변형, 정수계획법과 목표계획법

선형계획법의 변형된 방법들

 

정수 프로그래밍(Integer Programming)과 목표 프로그래밍(Goal Programming)의 비교를 살펴보면, 정수 프로그래밍과 목표 프로그래밍은 모두 선형 프로그래밍(linear programming)의 변종으로, 의사 결정 문제를 해결하기 위해 사용되는 최적화 기법입니다. 하지만 두 기법은 목표 설정과 제약 조건 처리 방식 등에서 차이가 있습니다.

1. 정수 프로그래밍(Integer Programming)

- 정수 프로그래밍은 최적화 문제에서 변수들이 정수 값을 가져야 하는 경우에 사용됩니다. 정수 프로그래밍은 최적해로 정수만이 허용되는 확정적 수리모형으로 일반적인 선형계획법의 모형에 하나의 제약식을 추가하여 최적해가 정수가 되도록 하는 방법입니다. 정수 프로그래밍은 결정 변수를 정수로 제한하는 최적화 문제를 다루는 기법입니다. 일반적으로 이러한 문제는 이진 결정 변수(0 또는 1 값을 가지는 변수)를 포함하며, 예를 들어 특정 자원의 할당 문제나 최적 경로 문제 등에서 사용될 수 있습니다. 정수 프로그래밍은 이산적인 결정을 모델링하고, 문제의 특성에 따라 최적해를 찾기 위해 브랜치 앤 바운드(Branch and Bound) 등의 알고리즘을 사용합니다.

 

- 문제의 목적 함수와 제약 조건은 선형 함수로 표현됩니다.

- 예를 들어, 배낭 문제(knapsack problem)와 같이 물건의 일부만 선택해야 하는 경우에 정수 프로그래밍을 사용할 수 있습니다.

- 정수 프로그래밍은 정수 해를 찾기 위해 완전 탐색, 가지 치기(pruning), 동적 계획법 등 다양한 알고리즘과 기법을 활용합니다.

 

2. 목표 프로그래밍(Goal Programming)

- 목표 프로그래밍은 다중 목표를 가지고 있거나 목표를 정확하게 달성하기 어려운 경우에 사용됩니다. 목적함수에서 목표하는 하나 이상의 목적(objective)을 고려하는 선형계획법의 변형된 형태입니다.

 

- 목표 프로그래밍은 목표 함수에 대한 목표 수준(goal level)을 설정하고, 목표를 가능한 한 달성하면서 제약 조건을 최소화하는 해를 찾는 것을 목표로 합니다.

 

- 목표 간의 우선순위를 설정하거나, 목표와의 허용 오차를 고려하여 최적해를 찾습니다.

 

- 목표 프로그래밍은 현실적인 의사 결정 문제에서 다양한 목표를 동시에 고려할 수 있는 강력한 도구로 사용됩니다.

 

따라서, 정수 프로그래밍은 변수의 값이 정수로 제한되는 문제를 해결하는 데 사용되고, 목표 프로그래밍은 다중 목표를 고려하거나 목표 달성의 정확성이 중요한 문제를 해결하는 데 사용됩니다. 이 두 기법은 서로 다른 유형의 의사 결정 문제에 대해 다른 방식으로 접근하며, 각각의 장단점과 적용할 수 있는 상황이 있습니다.