G f : G R
x " G f(x ) = maxx"G f(x)
G
G
G
G
G
2G G B
2G
G
Õ : 2G R
G2 ‚" G1 ‚" G Ò! Õ(G2) d" Õ(G1)
x " G Ò! Õ({x}) = f(x)
Õ : 2G R
x " G1 ‚" G Ò! f(x) d" Õ(G1)
 x " G2 ‚" G1 ‚" G Ò! f(x) d" Õ(G2) d" Õ(G1)
Õ
Õ f Õ
Õ
G1 ‚" G Ò! Õ(G1) = max f(x).
x"G1
f K1 G1 K1
f K1
B1 = {G} G = " Õ(G) = -"
Õ(G) k
k = 1, 2, . . . Bk = {Q1, Q2, . . . , Qn }
k
nk
G Qi = G Qi i = 1, . . . , nk
i=1
Õ(Qi) k
Q " Dk Õ(Q) = maxQ"D Õ(Q) Õ(Q) = -"
k
maxx"G f(x) Õ(Q) > -"
Q
Q {x } = Q
maxx"G f(x)
x " Q f(x) = Õ(Q)
x maxx"G f(x)
mk
Q Q1, Q2, . . . , Qm Qi =
i=1
k
Q Õ(Qi) i = . . . , mk Qi
Õ(Qi) = -" Õ(Qi)
Bk+1 = Bk *" {Q1, . . . , Qm } \ {Q}
k
 x maxx"G f(x)
Bk k = 1, 2, . . . G
x
maxx"G f(x)
maxx"G f(x)
Q Õ(Q) = -"
maxx"G f(x)
x " Rn
Å„Å‚
ôÅ‚
ôÅ‚cx max
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
òÅ‚
Ax = b, (P LC)
ôÅ‚
ôÅ‚x e" 0,
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ółx " Z j = 1, . . . , n.
j
A = [aij] aij " Q b = [b1, . . . , bm]T " Qm c = [c1, . . . , cn] cj " R
i = 1, . . . , m j = 1, . . . , n
aij bi Q
DC D
C
Dopt Dopt
D = " Ò! DC = "
C
Dopt = " '" D = " Ò! Dopt = "

max f(x) d" [max f(x)] [a]- a
x"D
x"DC
C
Dopt )" DC = " Ò! Dopt = Dopt )" DC

Dopt = " '" DC = " '" Dopt )" DC = " Ò! max f(x) < max f(x)

x"D
x"DC
 D1, . . . , Dk D DC ‚" D1 *"D2 *"
. . . *" Dk ‚" D
max f(x) d" [max{max f(x), . . . , max f(x)}],
x"D1 x"Dk
x"DC
[a] a
C
[maxx"D f(x)] < f(x) s " {1, . . . , k} x " DC Dopt )"
s
Ds = "
Z0, Z1, . . . , Zp p
L Z0
x0 Zk k = 1, . . . , p
max f(x) Dk
x"Dk
Õ(Bk) = maxx"D f(x) Dk
k
Bk = DC )" Dk
x " DC fc
C C
f(x) D0 = {x} fc = -" D0 = "
 A = [aij] m × n aij " Q
b = [b1, . . . , bm]T bi " Q c = [c1, . . . , cn] cj " R " = Jc ‚" {1, . . . , n}

Å„Å‚
ôÅ‚
ôÅ‚cx max
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
òÅ‚Ax = b,
. (P ZJ)
ôÅ‚x1, . . . , xn e" 0,
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚xj d" 1, j " Jc,
ôÅ‚
ôÅ‚
ôÅ‚
ół
xj " Z, j " Jc