Bài toán quy hoạch toàn phương lồi ngặt với nhiễu giới nội

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG

HỌC VIỆN KỸ THUẬT QUÂN SỰ

Bài toán quy hoạch toàn phương lồi ngặt với nhiễu giới nội

Võ Minh Phổ

Chuyên ngành: Toán học

Mã số: 62 46 30 01

Người hướng dẫn khoa học:

1. GS. TSKH Hoàng Xuân P

2. PGS. TS. Phan Thành Anh

2011

LO`

.

I CAM D- OAN

Tˆoi xin cam d¯oan nh˜u.ng kˆe´t qua˙’ d¯u.o

.

. c tr`ınh b`ay trong luˆa.n ´an l`a

m´o.

i, d¯˜a d¯u.o

.

. c cˆong bˆo´ trˆen c´ac ta.p ch´ı To´an ho. c quˆo´c tˆe´. C´ac kˆe´t qua˙’ viˆe´t

chung v´o.

i GS. TSKH. Ho`ang Xuˆan Ph´u v`a PGS. TS. Phan Th`anh An d¯˜a

d¯u.o

.

. c su.

. d¯ˆo`ng ´y cu˙’a c´ac d¯ˆo`ng t´ac gia˙’ khi d¯u.a v`ao luˆa.n ´an. C´ac kˆe´t qua˙’

nˆeu trong luˆa.n ´an l`a trung thu.

. c v`a chu.a t`u.ng d¯u.o

.

. c ai cˆong bˆo´ trong bˆa´t

k`y cˆong tr`ınh n`ao kh´ac tru.´o

.

c d¯´o.

Nghiˆen c´u.u sinh

LO`

.

I CA

˙’

M O.N

Luˆa.n ´an d¯u.o

.

. c ho`an th`anh du.´o

.

i su.

. hu.´o

.ng dˆa˜n, chı˙’ ba˙’o cu˙’a GS. TSKH.

Ho`ang Xuˆan Ph´u v`a PGS. TS. Phan Thanh An. T´ac gia˙’ chˆan th`anh ca˙’m

o

.n su.

. gi´up d¯˜o. mo.

i mˇa.

t m`a c´ac Thˆa`y d¯˜a d`anh cho. T´ac gia˙’ b`ay to˙’ l`ong

biˆe´t o.n sˆau sˇa´c v`a chˆan th`anh t´o.

i GS. TSKH. Ho`ang Xuˆan Ph´u, Thˆa`y d¯˜a

quan tˆam, hu.´o

.ng dˆa˜n tˆa.n t`ınh, nghiˆem khˇa´c v`a ta.o mo.

i d¯iˆe` u kiˆe.n d¯ˆe˙’ t´ac

gia˙’ c´o thˆe˙’ ho`an th`anh nh˜u.ng mu. c tiˆeu d¯ˇa.

t ra cho luˆa.n ´an. T´ac gia˙’ xin

b`ay to˙’ l`ong biˆe´t o.n d¯ˆe´n GS. TSKH. Nguyˆe˜n D- ˆong Yˆen, PGS. TS. Ta. Duy

Phu.o

.

. ng, PGS. TS. Nguyˆe˜n Nˇang Tˆam v`a c´ac d¯ˆo`ng nghiˆe.p thuˆo.c Ph`ong

Gia˙’i t´ıch sˆo´ v`a T´ınh to´an Khoa ho. c Viˆe.n To´an ho. c v`ı d¯˜a c´o nh˜u.ng ´y kiˆe´n

qu´y b´au cho t´ac gia˙’ trong qu´a tr`ınh nghiˆen c´u.u.

T´ac gia˙’ xin d¯u.o

.

. c b`ay to˙’ l`ong ca˙’m o.n d¯ˆe´n Ban chu˙’ nhiˆe.m Khoa Cˆong

Nghˆe.

thˆong tin, Ph`ong Sau d¯a.

i ho. c v`a Ban Gi´am d¯ˆo´c Ho.c viˆe.n K˜y thuˆa.

t

Quˆan su.

. d¯˜a ta.o mo.

i d¯iˆe` u kiˆe.n thuˆa.n lo.

.

i d¯ˆe˙’ t´ac gia˙’ c´o nhiˆe` u th`o.

i gian thu.

. c

hiˆe.n luˆa.n ´an.

T´ac gia˙’ c˜ung b`ay to˙’ l`ong biˆe´t o.n d¯ˆe´n PGS. TS. D- `ao Thanh T˜ınh,

PGS. TS. Nguyˆe˜n D- ´u

.

c Hiˆe´u, PGS. TS. Nguyˆe˜n Thiˆe.n Luˆa.n, PGS. TS.

Tˆo Vˇan Ban, TS. Nguyˆe˜n Nam Hˆo`ng, TS. Nguyˆe˜n H˜u.u Mˆo.ng, TS. V˜u

Thanh H`a, TS. Nguyˆe˜n Ma.nh H`ung, TS. Nguyˆe˜n Tro.ng To`an, TS. Ngˆo

H˜u.u Ph´uc, TS. Tˆo´ng Minh D- ´u

.

c, TS. Lˆe D- `ınh So.n, TS. Trˆa`n Nguyˆen Ngo. c

v`a tˆa´t ca˙’ c´ac d¯ˆo`ng nghiˆe.p trong Khoa Cˆong Nghˆe.

thˆong tin, HVKTQS,

d¯˜a d¯ˆo.ng viˆen, kh´ıch lˆe. v`a c´o nh˜u.ng trao d¯ˆo˙’i h˜u.u ´ıch trong suˆo´t th`o.

i gian

nghiˆen c´u.u v`a cˆong t´ac.

T´ac gia˙’ ca˙’m o.n sˆau sˇa´c GS. TSKH. Pha.m Thˆe´ Long, Gi´am d¯ˆo´c Ho. c

Viˆe.n KTQS, ngu.`o

.

i d¯˜a ta.o mo.

i d¯iˆe` u kiˆe.n vˆe` mˇa.

t thu˙’ tu. c c˜ung nhu.

chuyˆen

mˆon d¯ˆe˙’ t´ac gia˙’ c´o thˆe˙’ ho`an th`anh luˆa.n ´an n`ay.

Cuˆo´i c`ung t´ac gia˙’ gu.

˙’ i l`o.

i c´am o.n t´o.

i vo.

. v`a c´ac con, nh˜u.ng ngu.`o

.

i d¯˜a

d¯ˆo.ng viˆen, chˇam s´oc v`a ta.o mo.

i d¯iˆe` u kiˆe.n cho t´ac gia˙’ trong qu´a tr`ınh l`am

luˆa.n ´an.

Mu.

c lu.

c

L`o.

i cam d¯oan 1

L`o.

i ca˙’m o.n 2

Danh mu.

c c´ac k´y hiˆe.u thu.`o

.ng d`ung 5

Mo.

˙’ d¯ˆa`u 1

1 B`ai to´an quy hoa.

ch lˆo`i, quy hoa.

ch to`an phu.o

.ng v`a h`am lˆo`i

thˆo 8

1.1. B`ai to´an quy hoa. ch lˆo`i, quy hoa.ch to`an phu.o

.ng . . . . . . 9

1.2. H`am lˆo`i suy rˆo.ng thˆo . . . . . . . . . . . . . . . . . . . . . 12

1.3. H`am γ-lˆo`i ngo`ai . . . . . . . . . . . . . . . . . . . . . . . . 13

1.4. H`am Γ-lˆo`i ngo`ai . . . . . . . . . . . . . . . . . . . . . . . . 15

1.5. H`am γ-lˆo`i trong . . . . . . . . . . . . . . . . . . . . . . . . 17

2 D- iˆe˙’m infimum to`an cu.

c cu˙’a B`ai to´an (P˜) 20

2.1. T´ınh γ-lˆo`i ngo`ai cu˙’a h`am bi

. nhiˆe˜u . . . . . . . . . . . . . . 20

2.2. D- iˆe˙’m cu.

.

c tiˆe˙’u to`an cu. c v`a d¯iˆe˙’m infimum to`an cu. c . . . . . 27

2.3. C´ac t´ınh chˆa´t cu˙’a d¯iˆe˙’m infimum to`an cu. c . . . . . . . . . 28

2.4. T´ınh chˆa´t tu.

.a v`a d¯iˆe` u kiˆe.n tˆo´i u.u . . . . . . . . . . . . . . 33

3 T´ınh Γ-lˆo`i ngo`ai cu˙’a h`am bi

. nhiˆe˜u v`a d¯iˆe˙’m infimum to`an

3

cu.

c cu˙’a B`ai to´an (P˜) 43

3.1. T´ınh Γ-lˆo`i ngo`ai cu˙’a h`am bi

. nhiˆe˜u . . . . . . . . . . . . . . 43

3.2. D- iˆe˙’m infimum to`an cu. c cu˙’a b`ai to´an nhiˆe˜u . . . . . . . . . 52

3.3. T´ınh ˆo˙’n d¯i

.nh cu˙’a tˆa.p c´ac d¯iˆe˙’m infimum to`an cu. c . . . . . 55

3.4. Du.´o

.

i vi phˆan suy rˆo.ng thˆo v`a d¯iˆe` u kiˆe.n tˆo´i u.u . . . . . . . 58

4 D- iˆe˙’

m supremum cu˙’a B`ai to´an (Q˜) 64

4.1. T´ınh γ-lˆo`i trong cu˙’a h`am bi

. nhiˆe˜u . . . . . . . . . . . . . . 64

4.2. D- iˆe˙’m supremum to`an cu. c cu˙’a h`am bi

. nhiˆe˜u . . . . . . . . 66

4.3. T´ınh chˆa´t cu˙’a tˆa.p c´ac d¯iˆe˙’m supremum to`an cu. c . . . . . . 73

4.4. T´ınh chˆa´t cu˙’a tˆa.p c´ac d¯iˆe˙’m supremum d¯i

.a phu.o

.ng . . . . 86

Kˆe´t luˆa.n chung 94

Danh mu.

c cˆong tr`ınh cu˙’a t´ac gia˙’ liˆen quan d¯ˆe´n luˆa.n ´an 96

T`ai liˆe.u tham kha˙’o 97

DANH MU. C CAC K ´ Y HI ´ Eˆ

. U THU.O`

.NG DUNG `

• IRn

: Khˆong gian Euclide n chiˆe` u

• k · k : Chuˆa˙’n Euclide trong IRn

• hx, yi : T´ıch vˆo hu.´o

.ng cu˙’a v´ec to. x, y

• B(x, r) := {y | ky − xk < r} : H`ınh cˆa`u mo.

˙’ b´an k´ınh r tˆam x

• B¯(x, r) := {y | ky − xk ≤ r} : H`ınh cˆa`u d¯´ong b´an k´ınh r tˆam x

• A ∈ IRn×n

, A  0 : Ma trˆa.n d¯ˆo´i x´u.ng x´ac d¯i

.nh du.o

.ng

• AT

: Ma trˆa.n chuyˆe˙’n vi

. cu˙’a ma trˆa.n A

• λmin,(λmax) : Gi´a tri.

riˆeng nho˙’ nhˆa´t (l´o.n nhˆa´t) cu˙’a ma trˆa.n A

• λ(A) : Tˆa.p c´ac gi´a tri

.

riˆeng cu˙’a ma trˆa.n A

• kAk = {

√

max λ | λ ∈ λ(ATA)} : Chuˆa˙’n cu˙’a ma trˆa.n A trong IRn×n

• f(x) = hAx, xi + hb, xi : H`am to`an phu.o

.ng lˆo`i ngˇa.

t

• p(x), supx∈D |p(x)| ≤ s v´o.

i s ∈ [0, +∞[ : H`am nhiˆe˜u gi´o.

i nˆo.

i

•

˜f = f + p : H`am to`an phu.o

.ng lˆo`i ngˇa.

t v´o.

i nhiˆe˜u gi´o.

i nˆo.

i

• f(x) := hAx, xi + hb, xi → inf, x ∈ D : B`ai to´an quy hoa. ch to`an

phu.o

.ng (P)

• f(x) := hAx, xi + hb, xi → sup, x ∈ D : B`ai to´an quy hoa. ch to`an

phu.o

.ng (Q)

• f(x) := hAx, xi + hb, xi + p(x) → inf, x ∈ D : B`ai to´an quy hoa. ch

to`an phu.o

.ng lˆo`i ngˇa.

t v´o.

i nhiˆe˜u (P˜)

• f(x) := hAx, xi + hb, xi + p(x) → sup, x ∈ D : B`ai to´an quy hoa. ch

to`an phu.o

.ng lˆo`i ngˇa.

t v´o.

i nhiˆe˜u (Q˜)

• ∂g(x

∗

) : Du.´o

.

i vi phˆan cu˙’a g ta.

i d¯iˆe˙’m x

∗

• L(x, µ0, . . . , µm) := Pm

i=0 µigi(x) : H`am Lagrange

• T´ınh chˆa´t (Mγ) : Mˆo˜i d¯iˆe˙’m γ-cu.

. c tiˆe˙’u x

∗

cu˙’a f l`a d¯iˆe˙’m cu.

. c tiˆe˙’u

to`an cu. c

• T´ınh chˆa´t (Iγ) : Mˆo˜i d¯iˆe˙’m γ-infimum x

∗

cu˙’a f l`a d¯iˆe˙’m infimum

to`an cu. c

• Lα(

˜f) := {x | x ∈ D, ˜f(x) ≤ α}, α ∈ IR : Tˆa.p m´u.

c du.´o

.

i cu˙’a h`am

˜f = f + p

• h1(γ) := infx0, x1∈D, kx0−x1k=γ



1

2

(f(x0) + f(x1)) − f(

1

2

(x0 + x1))

• h2(γ) := infx0, x1∈D, kx0−x1k=γ,−x0+2x1∈D



f(x0)−2f(x1)+f(−x0+2x1)



• aff D : Bao aphin cu˙’a tˆa.p D

• ext D : Tˆa.p c´ac d¯iˆe˙’m cu.

. c biˆen cu˙’a tˆa.p lˆo`i d¯a diˆe.n D

• JD(x

∗

) := ext D \ {x

∗}, x∗ ∈ ext D

• d(x, D) := infy∈D kx − yk : Khoa˙’ng c´ach t`u. x d¯ˆe´n D

• conv D : Bao lˆo`i cu˙’a tˆa.p D

• dD := minx

∗∈ext D{d

￾

x

∗

, conv JD(x

∗

)

}

• D(x

∗

, β) := {x ∈ D | x = (1 − α)x

∗ + αy, y ∈ D, 0 ≤ α ≤ 1 − β},

x

∗ ∈ ext D, β ∈ [0, 1]

• C

0

(D) := {p : D → IR | kpkC0 := supx∈D |p(x)| < +∞}

• B¯

C0 (0, r) : H`ınh cˆa`u d¯´ong b´an k´ınh r tˆam 0 trong C

0

(D

1

MO.

˙’

D- `Aˆ U

B`ai to´an quy hoa. ch to`an phu.o

.ng truyˆe` n thˆo´ng c´o da.ng

f(x) := hAx, xi + hb, xi → inf, x ∈ D

trong d¯´o A ∈ IRn×n

l`a ma trˆa.n vuˆong, b ∈ IRn

l`a v´ec to. v`a D ⊂ IRn

l`a tˆa.p

lˆo`i.

C`ung v´o.

i b`ai to´an quy hoa.ch lˆo`i, b`ai to´an quy hoa.ch to`an phu.o

.ng

d¯u.o

.

. c nhiˆe` u nh`a to´an ho. c Viˆe.

t nam v`a quˆo´c tˆe´ nghiˆen c´u.u, v´ı du. nhu. H.

W. Kuhn v`a A. W. Tucker [22], B. Bank v`a R. Hasel [5], E. Blum v`a W.

Oettli [7], B. C. Eaves [12], M. Frank v`a P. Wolfe [13], O. L. Magasarian

[26], G. M. Lee, N. N. Tam v`a N. D. Yen [31], H. X. Phu [45], H. X. Phu

v`a N. D. Yen [53], M. Schweighofer [57], H. Tuy [63], [64], [72], H. H. Vui

v`a P. T. Son [66]. . .

C´ac kˆe´t qua˙’ quan tro.ng d¯˜a thu d¯u.o

.

. c khi nghiˆen c´u.u c´ac b`ai to´an

quy hoa. ch to`an phu.o

.ng cu˙’a c´ac nh`a to´an ho. c l`a vˆe` su.

.

tˆo`n ta.

i nghiˆe.m tˆo´i

u

.u, d¯iˆe` u kiˆe.n cˆa`n tˆo´i u.u, d¯iˆe` u kiˆe.n d¯u˙’ tˆo´i u.u, thuˆa.

t to´an t`ım nghiˆe.m tˆo´i

u

.u, t´ınh ˆo˙’n d¯i

.nh cu˙’a nghiˆe.m tˆo´i u.u khi c´ac b`ai to´an trˆen bi

.

t´ac d¯ˆo.ng bo.

˙’ i

nhiˆe˜u. Nhiˆe` u kˆe´t qua˙’ nghiˆen c´u.u vˆe` b`ai to´an trˆen d¯˜a d¯u.o

.

. c ´u.ng du.ng d¯ˆe˙’

gia˙’i c´ac b`ai to´an trong kinh tˆe´ v`a k˜y thuˆa.

t, nhu. b`ai to´an lu.

. a cho.n d¯ˆa`u tu.

(portfolio selection) ([27], [28]), b`ai to´an ph´at d¯iˆe.n tˆo´i u.u (economic power

dispatch) ([6], [11], [69]), b`ai to´an kinh tˆe´ d¯ˆo´i s´anh (matching economic),

([17]), b`ai to´an m´ay hˆo˜ tro.

. v´ec to.

(support vector machine) ([29]). . .

Khi A l`a nu.

˙’ a x´ac d¯i

.nh du.o

.ng hoˇa. c nu.

˙’ a x´ac d¯i

.nh ˆam th`ı b`ai to´an trˆen

c´o thˆe˙’ phˆan r˜a th`anh hai b`ai to´an kh´ac nhau sau:

f(x) := hAx, xi + hb, xi → inf, x ∈ D (P)

v`a

f(x) := hAx, xi + hb, xi → sup, x ∈ D. (Q)

2

Luˆa.n ´an n`ay nghiˆen c´u.u c´ac b`ai to´an quy hoa.ch to`an phu.o

.ng lˆo`i ngˇa.

t

v´o.

i nhiˆe˜u gi´o.

i nˆo.

i sau:

˜f(x) := hAx, xi + hb, xi + p(x) → inf, x ∈ D (P˜)

v`a

˜f(x) := hAx, xi + hb, xi + p(x) → sup, x ∈ D, (Q˜)

trong d¯´o p : D → IR tho˙’a m˜an d¯iˆe` u kiˆe.n supx∈D |p(x)| ≤ s v´o.

i gi´a tri

.

s ∈ [0, +∞[ v`a A trong c´ac b`ai to´an (P),(Q),(P˜) v`a (Q˜) d¯u.o

.

. c gia˙’ thiˆe´t l`a

ma trˆa.n d¯ˆo´i x´u.ng x´ac d¯i

.nh du.o

.ng.

V`ı sao c´ac b`ai to´an trˆen d¯u.o

.

. c cho.n d¯ˆe˙’ nghiˆen c´u.u? R˜o r`ang, khi s = 0

th`ı c´ac b`ai to´an (P˜) v`a (Q˜) ch´ınh l`a c´ac b`ai to´an (P) v`a (Q), hay n´oi c´ach

kh´ac c´ac b`ai to´an (P) v`a (Q) l`a c´ac tru.`o

.ng ho.

. p riˆeng cu˙’a c´ac b`ai to´an (P˜)

v`a (Q˜). D- ˆay l`a l´y do d¯ˆe˙’ tiˆe´n h`anh nghiˆen c´u.u c´ac b`ai to´an trˆen, tˆo´i thiˆe˙’u

t`u. quan d¯iˆe˙’m l´y thuyˆe´t. Tuy nhiˆen, c`on mˆo.

t sˆo´ l´y do thu.

. c tˆe´ kh´ac du.´o

.

i

d¯ˆay, cho thˆa´y viˆe.c nghiˆen c´u.u c´ac b`ai to´an (P˜),(Q˜) l`a thu.

. c su.

. cˆa`n.

L´y do th´u. nhˆa´t: f(x) = hAx, xi + hb, xi l`a h`am mu. c tiˆeu ban d¯ˆa`u v`a

p l`a h`am nhiˆe˜u n`ao d¯´o. H`am nhiˆe˜u p c´o thˆe˙’ bao gˆo`m c´ac t´ac d¯ˆo.ng bˆo˙’ sung

(tˆa´t d¯i

.nh hoˇa. c ngˆa˜u nhiˆen) lˆen h`am mu. c tiˆeu v`a c´ac lˆo˜i gˆay ra trong qu´a

tr`ınh mˆo h`ınh h´oa, d¯o d¯a.c, t´ınh to´an. . . D- iˆe˙’m d¯ˇa. c biˆe.

t l`a o.

˙’ chˆo˜, ch´ung

ta ha.n chˆe´ chı˙’ x´et nhiˆe˜u gi´o.

i nˆo.

i. Ha.n chˆe´ n`ay l`a khˆong qu´a ngˇa.

t, c´o thˆe˙’

d¯u.o

.

. c tho˙’a m˜an trong nhiˆe` u b`ai to´an thu.

. c tˆe´, chˇa˙’ng ha.n nhu.

trong hai v´ı

du. minh ho.a sau d¯ˆay.

Mˆo.

t trong nh˜u.ng ´u.ng du.ng nˆo˙’i bˆa.

t cu˙’a quy hoa. ch to`an phu.o

.ng l`a

b`ai to´an lu.

. a cho.n d¯ˆa`u tu.

(H. M. Markowitz [27], [28]). B`ai to´an ph´at

biˆe˙’u nhu.

sau: Phˆan phˆo´i vˆo´n qua n ch´u.ng kho´an (asset) c´o sˇa˜n d¯ˆe˙’

c´o thˆe˙’ gia˙’m thiˆe˙’u ru˙’i ro v`a tˆo´i d¯a lo.

.

i nhuˆa.n, t´u.

c l`a t`ım v´ec to.

tı˙’ lˆe.

x ∈ D, D := {x = (x1, x2, . . . , xn) |

Pn

j=1 xj = 1} d¯ˆe˙’ f(x) = ωxTΣx − ρ

T x

d¯a.

t gi´a tri

. nho˙’ nhˆa´t, trong d¯´o xj

, j = 1, . . . , n, l`a ty˙’ lˆe. ch´u.ng kho´an th´u.

j trong danh mu. c d¯ˆa`u tu.

, ω l`a tham sˆo´ ru˙’i ro, Σ ∈ IRn×n

l`a ma trˆa.n

hiˆe.p phu.o

.ng sai, ρ ∈ IRn

l`a v´ec to.

lo.

.

i nhuˆa.n k`y vo.ng. V`ı Σ v`a ρ thu.`o

.ng

3

khˆong d¯u.o

.

. c x´ac d¯i

.nh ch´ınh x´ac m`a chı˙’ xˆa´p xı˙’ bo.

˙’ i Σ v`a ˜ ˜ ρ, do d¯´o ch´ung

ta pha˙’i cu.

. c tiˆe˙’u h´oa h`am ˜f(x) = ωxTΣ˜x − ρ˜

T x = f(x) + p(x), trong d¯´o

p(x) = ωxT

(Σ˜ − Σ)x − (˜ρ − ρ)

T x. Khi quy d¯i

.nh, khˆong d¯u.o

.

. c b´an khˆo´ng,

t´u.

c l`a xj ≥ 0, j = 1, . . . , n, th`ı tˆa.p chˆa´p nhˆa.n d¯u.o

.

. c D l`a gi´o.

i nˆo.

i. V`ı vˆa.y

nhiˆe˜u p c˜ung gi´o.

i nˆo.

i trˆen D. N´oi mˆo.

t c´ach tˆo˙’ng qu´at, t´ınh gi´o.

i nˆo.

i cu˙’a

nhiˆe˜u luˆon d¯u.o

.

. c d¯a˙’m ba˙’o khi D gi´o.

i nˆo.

i v`a p liˆen tu. c trˆen D. Gia˙’ thiˆe´t

n`ay c˜ung ph`u ho.

. p v´o.

i nhiˆe` u b`ai to´an thu.

. c tˆe´.

Mˆo.

t v´ı du. n˜u.a cho thˆa´y l`a nhiˆe˜u gi´o.

i nˆo.

i luˆon xuˆa´t hiˆe.n khi gia˙’i mˆo.

t

b`ai to´an tˆo´i u.u (P) hoˇa. c (Q) n`ao d¯´o bˇa`ng m´ay t´ınh. Do phˆa`n l´o.n c´ac sˆo´

thu.

. c khˆong thˆe˙’ biˆe˙’u diˆe˜n ch´ınh x´ac bˇa`ng m´ay t´ınh, nˆen d¯ˆo´i v´o.

i hˆa`u hˆe´t

x ∈ D ta khˆong thˆe˙’ t´ınh ch´ınh x´ac d¯a.

i lu.o

.

. ng f(x) = hAx, xi + hb, xi m`a

chı˙’ c´o thˆe˙’ xˆa´p xı˙’ f(x) bo.

˙’ i mˆo.

t sˆo´ dˆa´u chˆa´m d¯ˆo.ng ˜f(x) n`ao d¯´o. H`am ˜f

khˆong lˆo`i, khˆong to`an phu.o

.ng v`a thˆa.m ch´ı l`a khˆong liˆen tu. c trˆen D. Khi

d¯´o h`am p := ˜f −f mˆo ta˙’ c´ac lˆo˜i t´ınh to´an. C´ac lˆo˜i d¯´o bi

. chˇa.n bo.

˙’ i mˆo.

t cˆa.n

trˆen s ∈ [0, +∞[ n`ao d¯´o c´o thˆe˙’ u

.´o

.

c lu.o

.

. ng d¯u.o

.

. c, t´u.

c l`a supx∈D |p(x)| ≤ s.

Ngo`ai ra, bˇa`ng c´ach su.

˙’ du.ng c´ac sˆo´ dˆa´u chˆa´m d¯ˆo.ng d`ai ho.n v`a/hoˇa. c c´ac

thuˆa.

t to´an tˆo´t ho.n, ta c´o thˆe˙’ gia˙’m cˆa.n trˆen s.

L´y do th´u. hai: ˜f l`a h`am mu. c tiˆeu d¯´ıch thu.

. c v`a f l`a h`am mu. c tiˆeu

d¯u.o

.

. c l´y tu.o

.

˙’ ng h´oa hoˇa. c l`a h`am mu. c tiˆeu thay thˆe´. Trong thu.

. c tˆe´, nhiˆe` u

h`am thˆe˙’ hiˆe.n mˆo.

t sˆo´ mu. c tiˆeu thu.

. c tiˆe˜n d¯u.o

.

. c gia˙’ d¯i

.nh l`a lˆo`i, hoˇa.c to`an

phu.o

.ng, hoˇa. c c´o mˆo.

t sˆo´ t´ınh chˆa´t thuˆa.n tiˆe.n d¯˜a d¯u.o

.

. c nghiˆen c´u.u k˜y, hoˇa. c

dˆe˜ nghiˆen c´u.u, nhu.ng thu.

. c ra th`ı khˆong pha˙’i l`a nhu. vˆa.y. D- iˆe` u n`ay d¯˜a d¯u.o

.

. c

H. X. Phu, H. G. Bock v`a S. Pickenhain d¯ˆe` cˆa.p d¯ˆe´n trong [48]. Trong bˆo´i

ca˙’nh d¯´o, p = ˜f − f l`a h`am hiˆe.u chı˙’nh. C´o thˆe˙’ gia˙’ thiˆe´t p l`a gi´o.

i nˆo.

i (tˆo´i

thiˆe˙’u trˆen tˆa.p chˆa´p nhˆa.n d¯u.o

.

. c) bo.

˙’ i mˆo.

t sˆo´ du.o

.ng kh´a b´e s, v`ı nˆe´u |p(x)|

qu´a l´o.n th`ı su.

.

thay thˆe´ khˆong c`on ph`u ho.

. p n˜u.a.

D- ˆe˙’ gia˙’i th´ıch d¯iˆe` u n`ay, ta d¯ˆe` cˆa.p d¯ˆe´n vˆa´n d¯ˆe` thu.`o

.ng d¯u.o

.

. c nghiˆen c´u.u

cu˙’a ph´at d¯iˆe.n tˆo´i u.u, t´u.

c l`a b`ai to´an phˆan bˆo´ lu.o

.

. ng d¯iˆe.n nˇang cho t`u.ng

tˆo˙’ m´ay ph´at nhiˆe.

t d¯iˆe.n sao cho tˆo˙’ng chi ph´ı (gi´a th`anh) l`a cu.

. c tiˆe˙’u, d¯ˆo`ng

th`o.

i vˆa˜n d¯´ap ´u.ng d¯u.o

.

. c nhu cˆa`u lu.o

.

. ng d¯iˆe.n nˇang v`a thoa˙’ m˜an r`ang buˆo. c

4

vˆe` cˆong suˆa´t ph´at ra cu˙’a mˆo˜i tˆo˙’ m´ay. Ngu.`o

.

i ta thu.`o

.ng gia˙’ thiˆe´t (xem

[6], [11], [69],. . . ) h`am chi ph´ı tˆo˙’ng cˆo.ng (bao gˆo`m c´ac chi ph´ı nhiˆen liˆe.u

(fuel cost), chi ph´ı ta˙’i sau (load-following cost), chi ph´ı du.

. ph`ong quay

(sprinning-reserve cost), chi ph´ı du.

. ph`ong bˆo˙’ sung (supplemental-reserve

cost), chi ph´ı tˆo˙’n thˆa´t ph´at v`a truyˆe` n dˆa˜n d¯iˆe.n nˇang) l`a h`am to`an phu.o

.ng,

lˆo`i ngˇa.

t v`a c´o da.ng

F(P) = X

n

i=1

Fi(Pi),

trong d¯´o n l`a sˆo´ tˆo˙’ m´ay ph´at, P := (P1, P2, . . . , Pn), Pi ∈ [Pi min, Pi max] l`a

lu.o

.

. ng d¯iˆe.n nˇang ph´at ra cu˙’a tˆo˙’ m´ay th´u.

i, Pi min, Pi max l`a cˆong suˆa´t ph´at

nho˙’ nhˆa´t v`a l´o.n nhˆa´t cu˙’a tˆo˙’ m´ay ph´at th´u.

i, Fi(Pi) = ai + biPi + ciP

2

i

l`a

h`am chi ph´ı cu˙’a tˆo˙’ m´ay ph´at th´u.

i v`a ai

, bi

, ci

l`a c´ac hˆe.

sˆo´ gi´a cu˙’a tˆo˙’ m´ay

ph´at th´u.

i ∈ {1, 2, . . . , n}.

D˜ı nhiˆen, gia˙’ thiˆe´t to`an phu.o

.ng, lˆo`i ngˇa.

t cu˙’a h`am mu. c tiˆeu l`a qu´a l´y

tu.o

.

˙’ ng. Chi ph´ı thu.

. c tˆe´ c´o thˆe˙’ khˆong l`a h`am to`an phu.o

.ng v`a c˜ung khˆong

l`a h`am lˆo`i ngˇa.

t. Nhu. vˆa.y, d¯ˆe˙’ gia˙’ thiˆe´t vˆe` t´ınh to`an phu.o

.ng v`a lˆo`i ngˇa.

t

cu˙’a h`am mu. c tiˆeu d¯u.o

.

. c tho˙’a m˜an, cˆa`n h`am gi´o.

i nˆo.

i p hiˆe.u chı˙’nh h`am chi

ph´ı thu.

. c tˆe´. D- ˇa. c biˆe.

t (xem [62], [6], [11], [69],. . . ), nˆe´u hiˆe.u ´u.ng d¯iˆe˙’m-van

d¯u.o

.

. c x´et d¯ˆe´n th`ı h`am chi ph´ı to`an phu.o

.ng pha˙’i d¯u.o

.

. c hiˆe.u chı˙’nh bo.

˙’ i tˆo˙’ng

h˜u.u ha.n c´ac h`am da.ng sin, t´u.

c l`a

F(P) = X

n

i=1

￾

Fi(Pi) + |ei sin(fi(Pi min − Pi))|

,

trong d¯´o ei

, fi

l`a c´ac hˆe.

sˆo´ hiˆe.u ´u.ng d¯iˆe˙’m-van. R˜o r`ang h`am hiˆe.u chı˙’nh

p := Pn

i=1 |ei sin(fi(Pi min − Pi))| l`a gi´o.

i nˆo.

i.

D- ˆe˙’ ngˇa´n go.n, ta thu.`o

.ng go.

i p l`a h`am nhiˆe˜u (mˇa. c d`u n´o khˆong chı˙’

d¯´ong vai tr`o d¯´o nhu. d¯˜a gia˙’i th´ıch o.

˙’ trˆen), ˜f l`a h`am bi

. nhiˆe˜u v`a (P˜) v`a

(Q˜) l`a c´ac b`ai to´an nhiˆe˜u. Thˆa.

t ra, ch´ung chı˙’ l`a c´ac thuˆa.

t ng˜u. vay mu.o

.

. n,

khˆong pha˙’i l´uc n`ao c˜ung ch´ınh x´ac nhu.

thu.`o

.ng lˆe.

.

Nh˜u.ng vˆa´n d¯ˆe` g`ı l`a m´o.

i cu˙’a c´ac b`ai to´an (P˜) v`a (Q˜) cˆa`n d¯u.o

.

. c nghiˆen

c´u.u? Cˆau ho˙’i n`ay l`a cˆa`n thiˆe´t, v`ı d¯˜a c´o nh˜u.ng kˆe´t qua˙’ nghiˆen c´u.u d¯ˇa.