AI를 위한 필수 수학

443

Chapter 10 -

운용 과학

●

일반형 문제에서 비롯되지 않은 문제, 특히 많은 변수가 있는 문제의 경우 초기 기저

B

와 관련된 기저 실행

가능 해

x

를 선택하는 방법이 항상 명확하지 않을 수 있다(

A

의 어떤

m

개 열이 선형 독립인지 명확하지 않

기 때문이다 ). 이 경우에는 인공 변수

artificial

variable

를 도입하고 보조 선형 계획 문제를 풀어서 원래 문제가 실

행 불가능한지, 해가 없는지 여부를 판단한다. 문제가 실행 가능한 경우 인공 변수를 기저에서 제외하고 원

래 문제에 대한 초기 기저와 관련된 기본 실행 가능 해를 구한다. 이 과정을 단체법

1

단계라고 한다. 나머지

는 단체법

2

단계라고 한다.

●

빅-

M

방법은 다음과 같이 단체법의

1

단계와

2

단계를 결합한 것이다.

,xy00$$

v

v

min cx My y y

Ax b

m12

$ g

+ ++ +

=

v

v

v

v

QQ

VV

충분히 큰

M

값을 선택했다는 가정하에 원 문제가 실행 가능하고 최적 비용이 유한하다면, 모든 인공 변수

y

1

,

y

2

,

…

y

m

은 결국

0

으로 수렴하게 되어 원래의 문제로 되돌아간다. 우리는

M

을 부정

undetermined

파라미터

로 취급하여 환산 비용

reduced

cost

을

M

에 대한 함수로 만들고 환산 비용이 음수인지 판단할 때

M

을 매우 큰

수로 취급한다.

변형된 단체법

계산 ...