AI를 위한 필수 수학

445

Chapter 10 -

운용 과학

단체법에서의 태블로 구현

단체법에서의 태블로

tableau

구현은 단 하나의 행렬만 저장하고 업데이트한다는 장점이 있다. 여

기서는

B

-

1

을 관리하고 업데이트하는 대신

m

×

n

+

1

크기의 행렬

x BA BbBA

B

1 11

=

- --

를

관리하고 업데이트한다. 기저에 편입되는 변수에 해당하는 열

u

=

B

-

1

A

j

를 피벗 열

pivot

column

이

라고 한다. 만약

l

번째 기저 변수가 기저에서 나간다면

l

번째 행을 피벗 행

pivot

row

이라고 한다.

피벗 행과 피벗 열 둘 모두에 속하는 요소를 피벗 요소

pivot

element

라고 한다. 이제 태블로 위에

0

번째 행을 추가하여 현재 비용의 음수

ccc

BB B

1

$ $$- =- =

-

xx Bb

를 추적한다. 따라서 태블

로는 다음과 같이 구성된다.

Bb BA

c Bbc c BA

BB

11

11

$$--

-

--

-

T

Y

더 확장해서 적어보면 다음과 같다.

cx

x

x

cc

BA BA

BB

B

Bm

n

n

1

1

1

1

1

$

h

g

g

g

g

-

--

rr

J

L

K

K

K

K

K

K

K

K

K

Q

Q

N

P

O

O

O

O

O

O

O

O

O

V

V

이러한 방법을 익히면 주어진 단체법 태블로에서

B

-

1

과

B

를 쉽게 추출할 수 있어 유용하다.

단체법의 가장 효율적인 구현은 변형된 단체법이다 (메모리 사용량은

O

(

m

2

)

, 단일 반복에 대

한 최악의 경우 시간 복잡도는

O

(

mn

)

, 단일 반복에 ...