Luận văn Thạc sĩ Toán học: Quy hoạch toàn phương

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH Nguyễn Mai Anh Phương

QUY HOẠCH TOÀN PHƯƠNG

LUẬN VĂN THẠC SĨ TOÁN HỌC

Thành phố Hồ Chí Minh – 2012

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH

Nguyễn Mai Anh Phương

QUY HOẠCH TOÀN PHƯƠNG

Chuyên ngành: Toán Giải Tích Mã số: 60 46 01

LUẬN VĂN THẠC SĨ TOÁN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC

TS. Trịnh Công Diệu

Thành phố Hồ Chí Minh – 2012

Lời Cảm Ơn

Trước khi trình bày nội dung của luận văn, tôi xin bày tỏ lòng biết ơn sâu sắc

tới TS. Trịnh Công Diệu người đã tận tình hướng dẫn để tôi có thể hoàn thành luận

văn này.

Tôi cũng xin bày tỏ lòng biết ơn chân thành tới toàn thể các thầy cô đã tham

gia giảng dạy lớp cao học toán giải tích khóa 21, cảm ơn các thầy cô trong ban giám

hiệu và phòng sau đại học của trường Đại học sư phạm Tp. Hồ Chí Minh.

Nhân dịp này tôi cũng xin được gửi lời cảm ơn tới gia đình, bạn bè đã luôn

bên tôi cổ vũ, động viên, giúp đỡ tôi trong suốt quá trình học tập và thực hiện luận

văn.

Tp. Hồ Chí Minh, năm 2012

Nguyễn Mai Anh Phương

Mục Lục Lời Nói Đầu ................................................................................................................ 1

Một Số Kí Hiệu .......................................................................................................... 3

Chương 1: MỞ ĐẦU ................................................................................................. 4

1.1. Một số kiến thức bổ sung ................................................................................. 4

1.1.1. Tập lồi ....................................................................................................... 4

1.1.2. Hàm lồi ...................................................................................................... 7

1.1.3. Ma trận nửa xác định dương, nửa xác định âm ......................................... 9

1.2. Một số kết quả cơ bản trong lý thuyết tối ưu ................................................... 9

1.2.1. Định nghĩa ................................................................................................. 9

1.2.2. Tính chất .................................................................................................. 10

1.3. Định nghĩa bài toán quy hoạch toàn phương ................................................. 11

1.3.1. Định nghĩa hàm toàn phương .................................................................. 11

1.3.2. Định nghĩa bài toán quy hoạch toàn phương .......................................... 11

1.3.3. Các dạng quy hoạch toàn phương ........................................................... 13

Chương 2: TÍNH CHẤT CỦA BÀI TOÁN QUY HOẠCH TOÀN PHƯƠNG 14

2.1. Điều kiện tồn tại nghiệm ................................................................................ 14

2.1.1. Định lý Frank-Wolfe ............................................................................... 14

2.1.2. Định lý Eaves .......................................................................................... 20

2.2. Tính chất tập nghiệm của bài toán quy hoạch toàn phương .......................... 28

2.2.1. Tính bị chặn của tập nghiệm ................................................................... 28

2.2.2. Tính đóng của tập nghiệm ....................................................................... 31

2.2.3. Tính hữu hạn của tập nghiệm .................................................................. 32

2.2.4. Tính lồi đa diện của tập nghiệm .............................................................. 33

2.2.5. Tính chất của tập

Sol P ∩ ∆ ............................................................ 34

int

(

)

Chương 3: PHƯƠNG PHÁP GIẢI BÀI TOÁN QUY HOẠCH TOÀN

PHƯƠNG ................................................................................................................. 35

3.1. Điều kiện Kuhn-Tucker ................................................................................. 35

3.2. Thuật toán giải quy hoạch toàn phương lồi ................................................... 37

3.2.1. Thuật toán Wolfe..................................................................................... 38

3.2.2. Ví dụ minh họa ........................................................................................ 45

Kết Luận................................................................................................................... 52

Tài Liệu Tham Khảo ............................................................................................... 53

1

Lời Nói Đầu

Lý thuyết tối ưu (ta thường gọi là bài toán Quy hoạch) có nhiều áp dụng

trong thực tế. Trong chương trình học đại học đã có giáo trình Quy hoạch tuyến tính

trình bày phương pháp giải các bài toán Quy hoạch tuyến tính. Tuy nhiên, khi xây

dựng mô hình toán cho một vấn đề thực tế không phải lúc nào ta cũng có mô hình

tuyến tính.

Chẳng hạn, Harry Markowitz đã mô hình hóa quá trình lựa chọn danh mục

đầu tư chứng khoán (nhờ đó nhận được giải Noben kinh tế năm 1990) dưới dạng

một bài toán Quy hoạch mà hàm mục tiêu không phải là tuyến tính. Mục tiêu của

bài toán Markowitz là tìm tỉ trọng của các chứng khoán trong danh mục đầu tư sao

cho giảm tới mức tối thiểu phương sai (rủi ro) của danh mục mà đạt được một mức

thu nhập đã định. Giải liên tiếp các bài toán với các mức thu nhập mục tiêu người ta

xác định được một tập hợp các danh mục đầu tư có hiệu quả. Từ đây nhà đầu tư có

thể lựa chọn một danh mục nằm trong tập hợp này dựa trên quan điểm của mình về

việc đánh đổi giữa thu nhập và rủi ro. Mô hình toán học như sau:

n

n

=

min

S

( ) f x

2 p

x x s ij i j

= ∑∑

= 1

= 1

i

j

với các ràng buộc:

n

=

,

r

x r i i

∑

= 1

i

n

=

1,

x i

∑

≤

=

= 1 i ≤ 0

1 ( i

1, 2,..., ) n

x i

Trong đó,

2

•

pS là phương sai thu nhập của danh mục đầu tư.

•

ix là tỉ trọng của chứng khoán i trong danh mục đầu tư gồm n chứng khoán.

•

ir là thu nhập kỳ vọng của chứng khoán i .

r là thu nhập dự tính của toàn bộ danh mục đầu tư.

•

2

Cũng có rất nhiều vấn đề trong thực tế khi mô hình hóa lên cũng có dạng

tương tự như trường hợp trên và trong nghiên cứu về lý thuyết tối ưu đã có một

hướng nghiên cứu dành cho lớp các bài toán có dạng này:

+

+

min{

T x Qx

T c x

xα |

∈ ∆ }

n

∈

với

Q

c

∆ ∈  là tập lồi đa

×∈  (là ma trận đối xứng cấp n),

,n α∈ 

 và

n n S

diện.

Người ta gọi lớp các bài toán Quy hoạch có dạng trên là bài toán Quy hoạch

toàn phương. Đó chính là đối tượng được khảo sát trong luận văn: Quy hoạch toàn

phương.

Bố cục của luận văn bao gồm 3 chương:

• Chương 1: Mở đầu. Trình bày một số khái niệm và tính chất cơ bản

của giải tích lồi, của lý thuyết tối ưu và định nghĩa bài toán quy hoạch

toàn phương.

• Chương 2: Tính chất của bài toán Quy hoạch toàn phương. Trình

bày định lý tồn tại nghiệm và các tính chất tập nghiệm của bài toán

quy hoạch toàn phương.

• Chương 3: Phương pháp giải bài toán Quy hoạch toàn phương.

Chương này đề cập đến phương pháp giải Quy hoạch toàn phương lồi

dựa trên sự mở rộng của phương pháp đơn hình.

Do thời gian thực hiện luận văn không nhiều, kiến thức còn hạn chế nên khi

làm luận văn không tránh khỏi những hạn chế và sai sót. Mong nhận được sự góp ý

và những ý kiến phản biện của quý thầy cô và bạn đọc.

Xin chân thành cảm ơn!

Tp. Hồ Chí Minh, năm 2012

Nguyễn Mai Anh Phương

3

Một Số Kí Hiệu

Kí hiệu

Nghĩa của kí hiệu

Không gian các vec tơ n chiều.

Không gian các ma trận cấp n m× .

Không gian các ma trận đối xứng cấp n m× .

n n m× ×

n m S

Tx

Vectơ chuyển vị của vectơ x ( x là ma trận cột tọa độ).

TA

Ma trận chuyển vị của ma trận A.

〉

Tích vô hướng của hai vectơ.

.,.〈

Bao affine của tập M.

affM

Tập các điểm cực biên của M.

extrM

domf

Miền hữu hiệu của hàm f .

epif

Trên đồ thị của hàm f .

∆

Tập ràng buộc của bài toán Quy hoạch toàn phương (QHTP)

(

),A b

xác định bởi Ax b≥ .

Tập nghiệm của bài toán QHTP.

Sol P ( )

Tập nghiệm cực tiểu địa phương của bài toán QHTP.

loc P ( )



Kết thúc chứng minh.

4

Chương 1: MỞ ĐẦU

1.1. Một số kiến thức bổ sung

1.1.1. Tập lồi

n

1.1.1.1. Tập affine 2

Cho

1 ,x x là hai điểm trong

n . Tập hợp tất cả các điểm

2

x ∈  sao cho:

1 λ x

được gọi là đường thẳng đi qua

1x và

2x .

n

Tập

= λ x + − (1 λ ) x , ∀ ∈ 

hai điểm bất kỳ của M , tức là:

∀

∈

λ

1 2 x x M

,

,

1 ∈ ⇒ + − λ x

(1

λ )

2 ∈ x M



k

n

i

Ta gọi một điểm

M ⊆  được gọi là tập affine nếu M chứa trọn cả đường thẳng đi qua

x ∈  có dạng

2

= 1

i

k

2

n

là tổ hợp affine của các điểm

x ,..., , λ λ λ ∈  và 1 k = ∑ với xλ i

1 x x ,

,...,

k x ∈  .

i

= 1

n

1 =∑ λ i

Mệnh đề 1.1 Tập

0

n

∈

M ⊆  , khác rỗng là tập affine nếu và chỉ nếu

,

0 x M L

⊆  là không gian con.

Khi đó, L được gọi là không gian con song song với tập affine M . Số chiều

của tập affine M cũng chính là số chiều của L .

n

Bao affine của một tập

+ trong đó = M x L

là tập affine nhỏ nhất chứa E , ký hiệu là affE . Số chiều của một tập M là số chiều

của bao affine của nó, ký hiệu là dim M .

n

Cho tập

E ⊆  là giao của tất cả các tập affine chứa E . Đó

ε ∩

B a

( , )

affM

⊂ . M

tương đối của M nếu tồn tại hình cầu mở

B a ε sao cho ( ( , )

)

Phần trong tương đối của tập M , ký hiệu là riM là tập chứa tất cả các điểm trong

tương đối của M .

M ⊆  có dim M n< . Một điểm a M∈ được gọi là điểm trong

5

1.1.1.2. Tập lồi và điểm cực biên

2

Cho hai điểm

1 ,x x thuộc

n . Tập tất cả các điểm có dạng:

2

=

x

1 λ x

+ − (1

λ )

x

, 0

≤ ≤ λ 1

2

2

được gọi là đoạn thẳng nối

.

1 ,x x . Ký hiệu:

1 x x ,

n

Tập

[ ]

bất kỳ thuộc nó, tức là:

M ⊆  được gọi là tập lồi nếu nó chứa trọn đoạn thẳng nối hai điểm

1 2 x x M

1 λ x

2 x M

k

k

n

i

là tổ hợp

Ta gọi một điểm

∀ ∈ ≤ ≤ ⇒ + − λ ∈ , ,0 (1 1 λ )

x ∈  có dạng

i

= 1

= 1

i

2

=

lồi của các điểm

0 x 1 λ λ ≥ và 1,..., k = ∑ với xλ i =∑ λ i

thì ta nói x là tổ

i

1, 2,...,

k

1 x x ,

,...,

k n x ∈  . Nếu

iλ > với mọi

2

n

hợp lồi chặt của các điểm

,...,

1 , x x

k x ∈  .

n

0

Mệnh đề 1.2 Một tập

hợp lồi của những phần tử thuộc nó.

M ⊂  là tập lồi khi và chỉ khi nó chứa tất cả các tổ

Mệnh đề 1.3 Nếu

cũng là tập lồi.

,

M N Mα+

,M N là tập lồi, α∈  thì

n

Bao lồi của tập

là convE . Đó là tập lồi nhỏ nhất chứa E .

n

n

Cho tập lồi

M ⊂  . Một điểm

x ∈  được gọi là điểm cực biên của M

nếu x không thể biểu diễn được dưới dạng tổ hợp lồi chặt của hai điểm phân biệt

bất kỳ nào của M . Số điểm cực biên của tập lồi có thể hữu hạn hoặc vô hạn. Khi

tập lồi có hữu hạn điểm cực biên thì chúng thường được gọi là các đỉnh.

n

E ⊂  là giao của tất cả các tập lồi chứa E và được ký hiệu

Mệnh đề 1.4 Một tập lồi đóng khác rỗng

M ⊂  có điểm cực biên khi và

chỉ khi nó không chứa trọn một đường thẳng nào.

Định lý 1.1 (định lý Krein-Milman) Một tập lồi đóng, bị chặn trong

n là

bao lồi của các điểm cực biên của nó.

1.1.1.3. Nón lồi, phương lùi xa, phương cực biên

n

λ

λ

Tập

≥ ⇒ ∈ . Nếu M vừa là

∈ x M

,

x M

0

M ⊂  được gọi là nón nếu

tập lồi vừa là nón thì M được gọi là nón lồi.

6

Cho tập lồi khác rỗng

n M ⊂  . Vectơ

+

≥ ⊂ với mỗi x M∈ . Rõ ràng, mọi nửa đường thẳng song

x

dλ λ |

0} M

d ≠ được gọi là phương lùi xa của 0

song với một phương lùi xa d xuất phát từ một điểm bất kỳ của M đều nằm trọn

trong M . Tập M không bị chặn khi và chỉ khi nó có một phương lùi xa. Tập tất cả

các phương lùi xa của tập lồi M cùng vectơ 0 tạo thành một nón lồi và được gọi là

nón lồi lùi xa của M .

1

2

1

2

Hai phương

với

M nếu {

0α> . Phương lùi xa d

,d d là khác biệt nếu

của M được gọi là phương cực biên của M nếu không tồn tại các phương lùi xa

1

2

1

2

=

+

khác biệt

d

;

,

> . 0

,d d của M sao cho

λ λ λ λ d 2 2

d 1

1

d dα≠

1.1.1.4. Các định lý tách tập lồi

n

n

Cho hai tập

với

,

C D ⊂  và siêu phẳng

{ = ∈ x

} 〉 = a x α ,

n

{ } \ 0

〈 H | 

và α∈  . Ta nói:

+ Siêu phẳng H tách hai tập C và D nếu:

〈

〉 ≤

α

≤ 〈

〉

a x ,

a y ,

∀ ∈ ∀ ∈ . x C y D ,

+ Siêu phẳng H tách hẳn (hay tách chặt) hai tập C và D nếu:

α

〈

〉 <

< 〈

〉

a x ,

a y ,

∀ ∈ ∀ ∈ . x C y D ,

n

a ∈ 

Định lý 1.2 (định lý tách I) Nếu hai tập lồi

,

C D ⊂  không rỗng và rời

nhau thì có một siêu phẳng tách chúng.

n

Định lý 1.3 (định lý tách II) Nếu hai tập lồi đóng

,

C D ⊂  không rỗng, rời

nhau và một trong hai tập ấy là compact thì có một siêu phẳng tách hẳn chúng.

1.1.1.5. Tập lồi đa diện n Tập lồi đa diện

P ⊂  là giao của một số hữu hạn nửa không gian con

đóng. Tập lồi đa diện là một tập lồi đóng. Nếu tập lồi đa diện bị chặn thì được gọi là

đa diện lồi hay gọi tắt là đa diện.

Mỗi điểm cực biên của tập lồi đa diện được gọi là đỉnh. Mỗi tập con lồi khác

rỗng F của tập lồi đa diện P được gọi là một diện của P nếu hễ F chứa một điểm

7

trong tương đối của một đoạn thẳng nào đó thuộc P thì F chứa trọn cả đoạn thẳng

đó, nghĩa là:

=

λ

∈ y z P x ,

,

λ y

+ − (1

λ )

∈ z F

,0

< < ⇒ ∈ 1

y F z F ,

∈ .

Định lý 1.4 Cho P là tập lồi đa diện được xác định bởi:

〈

〉 ≤

=

i

m

i a x ,

,

1,...,

b i

Khi đó, tập con lồi khác rỗng F

P⊂ là một diện của P nếu và chỉ nếu:

i 〈 x a x

i ∈ 〈 ; I a x

{

} ∉ I

= 〉 = 〉 ≤ F , | , b i , i b i , i

.

i 〈 i a x |

{ 1,...,

} m

0

trong đó {

} x P

Từ định lý trên suy ra, một diện của tập lồi đa diện cũng là một tập lồi đa diện và

mỗi đỉnh của một diện cũng là một đỉnh của P .

là tập các

= ⊂ ⊂ , I I 〉 = ∀ ∈ b , i

Định lý 1.5 (định lý biểu diễn tập lồi đa diện) Giả sử { 1,..., N v v

}

1,..., M d

là tập các phương cực biên của tập lồi đa diện P . Khi đó, mỗi

đỉnh và {

}

điểm x P∈ đều có thể biểu diễn dưới dạng:

N

M

i

j

=

x

d

µ j

+∑ λ v i

∑

= 1

= 1

i

j

N

d

.

trong đó

i

= 1

≥ = ≥ = 0, i 1,..., N ; 0, j 1,..., M ; 1 λ i µ j =∑ λ i

1.1.2. Hàm lồi

n

Cho hàm

X ⊂  . Khi đó, các tập:

: f X → −∞ +∞ xác định trên tập lồi ;

1.1.2.1. Định nghĩa [

]

domf

} < +∞

=

≤

epif

∈ × X

x

|

f x ( )

x X f x ( ) | ) α ,



{ = ∈ { (

} α

được gọi là miền hữu hiệu và trên đồ thị của hàm f . Nếu domf ≠ ∅ và

f x > −∞ ( )

thì hàm f gọi là chính thường.

Hàm f được xác định ở trên được gọi là hàm lồi nếu epif là một tập lồi

trên

n ×  .

8

Ta có nhận xét, nếu f là hàm lồi thì domf là tập lồi. Thật vậy, domf là hình chiếu

trên X của epif :

=

∃

∈

.

domf

x f x ( )

|

x

|

epif

{

} < +∞ =

( r x r , ,

)

{

}

Do đó, domf là ảnh của tập lồi epif qua một ánh xạ tuyến tính nên domf là tập lồi.

n

Định lý 1.6 Giả sử

(

X ⊂  là tập lồi và

] f X → −∞ +∞ . Khi đó, f lồi

trên X . Khi và chỉ khi:

2

2

2

: ;

.

1 λ ( x

1 f x (

1 x x ,

] 0,1

[

Ta gọi f là hàm lồi chặt trên tập lồi X nếu:

2

2

2

2

≤ λ ∀ λ f + − (1 λ ) x ) ) + − (1 λ ) f x ( ) ∈ ∀ ∈ , X

1 λ x (

1 f x (

1 x x ,

1 X x ,

< ∀ ∈ ≠ λ f x x + − (1 λ ) ) ) + − (1 λ ) f x ( ) ,0 < < . λ 1

Hàm f được gọi là hàm lõm nếu

chặt nếu

f− là hàm lồi chặt.

f− là hàm lồi, tương tự f được gọi là hàm lõm

1.1.2.2. Tính chất của hàm lồi

n

Mệnh đề 1.5 Nếu

X ⊂  là hàm lồi thì tập

∈

≤

( )

|

{

} x X f x α

là tập lồi với mọi α∈  .

Cho hàm lồi

n X ⊂  , hàm lồi

1

1f xác định trên tập lồi

2f xác định trên tập

n

lồi

0λ> . Ta định nghĩa các phép toán sau:

X ⊂  và số thực

2

f xác định trên tập lồi

1

λ= ∈ x X

2

2

( λ ( max

) ( ) : ) ,

( ) f x 1 = + f X f 1

2

2

Khi đó, ta có các kết quả sau:

( ), ( ) f x 1 = ( ) : max x f x X X f x 1 + { ( ) : x } ( ) f x 2 { f 1 f x 1 ∈ ∩ x X 1 } ( ) f x 2 ∈ ∩ 1

Mệnh đề 1.6 Cho

1f là hàm lồi trên tập

1X ,

2X và

các số thực

và

là hàm lồi trên

max

f

0α β > . Khi đó, các hàm

,

2f là hàm lồi trên tập }

{

,f 1

2

2

f α β+ f 1

1

2

n

X X∩ .

Mệnh đề 1.7 Nếu f là hàm lồi xác định trên tập lồi mở

X ⊂  thì f là

hàm liên tục trên X .

9

n

Định lý 1.7 Cho hàm f khả vi trên tập lồi mở

X ⊂  . Khi đó, f là hàm

lồi khi và chỉ khi:

n

− ≥ 〈∇ − 〉 ∀ f y ( ) f x ( ) f x y ( ), x ∈ x y X ,

Định lý 1.8 Cho f là hàm khả vi hai lần trên tập lồi mở

X ⊂  . Khi đó,

2

∇

là nửa xác định dương trên X .

f là hàm lồi khi và chỉ khi ma trận Hesse

f x ( )

2

∇

xác định dương trên X .

Hàm f là hàm lồi chặt trên X nếu

f x ( )

〉 + 〈

Áp dụng định lý trên cho hàm

f x ( )

x Qx ,

x c α ,

〉 + trong đó Q là ma

1 = 〈 2

trận đối xứng cấp n n× . Khi đó, f là hàm lồi (tương ứng, lồi chặt) trên

n nếu Q

là ma trận nửa xác định dương (tương ứng, xác định dương).

1.1.3. Ma trận nửa xác định dương, nửa xác định âm

n n

Định nghĩa: Ma trận

Tx Dx > 0

D

×∈  được gọi là xác đinh dương nếu

n

n

. Nếu

T x Dx

{ } \ 0

dương.

n n

x 0, x∀ ∈  ≥ ∀ ∈  thì D được gọi là ma trận nửa xác định

Định nghĩa: Ma trận

D

Tx Dx < 0

×∈  được gọi là xác đinh âm nếu

n

n

. Nếu

0,

T x Dx

x

{ } \ 0

≤ ∀ ∈  thì D được gọi là ma trận nửa xác định âm.

x∀ ∈ 

1.2. Một số kết quả cơ bản trong lý thuyết tối ưu

1.2.1. Định nghĩa

Bài toán tối ưu tổng quát được phát biểu như sau:

hoặc

∈ f x min ( ) ( ) x D P 1

n

trong đó

∈ f x max ( ) ( ) x D P 2

:f D →  là hàm mục tiêu.

Mỗi điểm x D∈ được gọi là một nghiệm chấp nhận được hay một phương

án chấp nhận được.

D ⊂  được gọi là tập nghiệm chấp nhận được hay tập ràng buộc và hàm

10

≤

∀ ∈ được gọi là nghiệm tối ưu, hoặc

Điểm x D∗ ∈ mà

f x

x D

*( f x

)

( ),

nghiệm toàn cục tối ưu, hoặc nghiệm cực tiểu toàn cục, hoặc đơn giản là nghiệm

của bài toán

Điểm x D∗ ∈ được gọi là nghiệm cực tiểu toàn cục chặt của bài toán

)P . Người ta còn gọi một nghiệm tối ưu là một phương án tối ưu. 1(

*

*

<

∀ ∈

≠

nếu:

.

f x (

)

f x

( ),

x D x

,

x

Điểm x D∗ ∈ được gọi là nghiệm tối ưu địa phương hoặc nghiệm cực tiểu

địa phương của bài toán

*,

)P 1(

( B x ε của điểm x D∗ ∈

)

*

*

)P nếu tồn tại một ε− lân cận 1(

sao cho

( x B x

) Dε ,

Điểm x D∗ ∈ được gọi là nghiệm tối ưu địa phương chặt hoặc nghiệm cực

*

*

*

≤ ∀ ∈ ∩ . f x ( ) f x ( ),

tiểu địa phương chặt của bài toán

.

( x B x

) ε ,

Các khái niệm tương tự cũng được định nghĩa cho bài toán

< ∀ ∈ ∩ ≠ f x ( ) f x ( ), D x , x )P nếu: 1(

)P . 2(

1.2.2. Tính chất

n

Định lý 1.9 Cho hàm lồi

f

:

D ⊂  . Xét bài

n →

 và tập lồi khác rỗng

toán

. Khi đó:

min

f x

( ) |

{

} x D∈

i) Nếu

*x là một nghiệm tối ưu địa phương của bài toán này thì

*x cũng là

nghiệm tối ưu toàn cục.

ii) Nếu

*x là một nghiệm tối ưu địa phương chặt hoặc f là hàm lồi chặt thì

*x là nghiệm tối ưu toàn cục chặt duy nhất của bài toán.

Định lý 1.10 Điều kiện cần và đủ để bài toán

≥

∈

đóng và có một cận dưới hữu hạn.

f D (

)

|

t

( ),

} f x x D



{ + = ∈ t

)P có nghiệm tối ưu là tập 1(

Định lý 1.11 Nếu tập D là tập compact và hàm f là hàm liên tục trên D

thì cả hai bài toán

)P đều có nghiệm tối ưu. 2( )P và 1(

11

1.3. Định nghĩa bài toán quy hoạch toàn phương

1.3.1. Định nghĩa hàm toàn phương

n n

Hàm

n →

×∈ 

n

và tồn tại vectơ

f : D  được gọi là hàm toàn phương nếu tồn tại ma trận

=

+

+ = 〈

α

〉 + 〈

〉 +

α

f x ( )

T x Dx

T c x

x Dx ,

c x ,

x

n ∀ ∈  . (1.1)

1 2

1 2

T

n

c ∈  và số thực α sao cho:

Ta có

T x Dx

) T + x D D x

(

thức (1.1) là ma trận đối xứng. Thật vậy, ta chỉ cần thay ma trận D trong công thức

T

(1.1) bởi ma trận đối xứng

.

D D+

)

(

1 2

T

2

= x , ∀ ∈  . Nên ta có thể giả sử ma trận D trong công 1 2

= + =

Ví dụ: xét hàm toàn phương

(

)

2 x 1

2 x x , 2

f x ( ) ∈  . Ta có: x x , 1 2

(

)

= f x ( ) . x x , 1 2 2 0 0 2 1 2 x 1 x 2      .       

Định nghĩa: Bài toán

f x

1.3.2. Định nghĩa bài toán quy hoạch toàn phương min

( ) |

x ∈ ∆ trong đó hàm mục tiêu f là hàm

{

}

n

toàn phương, tập ràng buộc

∆ ⊂  là tập lồi đa diện được gọi là bài toán quy

hoạch toàn phương (hay quy hoạch toàn phương).

Nếu D là ma trận không,

0α= thì f là hàm tuyến tính. Do đó, lớp các bài

x ∈ ∆ được gọi là quy hoạch toàn

( ) |

min

f x

Nếu f là hàm lồi thì bài toán

toán quy hoạch tuyến tính là lớp con của lớp các bài toán quy hoạch toàn phương. {

}

f x

x ∈ ∆ được gọi là quy

min

( ) |

phương lồi. Nếu f không là hàm lồi thì bài toán

{

}

hoạch toàn phương không lồi.

Nếu ta bỏ đi hằng số α trong công thức của hàm f thì ta vẫn không làm

thay đổi tập nghiệm của bài toán quy hoạch toàn phương ban đầu. Do đó, ta chỉ cần

=

+

∈ ∆

.

xét bài toán

min

( ) f x

T x Dx

T | c x x

1 2

  

  

12

=

+

∈ ∆

Nếu ta thay ma trận

thì bài toán

Q

min

( ) f x

T x Dx

T | c x x

1 D= 2

1 2

  

  

trở thành

T x Qx

T c x x |

{

} ∈ ∆ .

= + min f x ( )

Ví dụ: Cho bài toán quy hoạch toàn phương

2

)

(

2 x 1

2 x 2

} 3

{

Ta có:

− ∈ ≤ ≤ min | ;1  x x , 1 2 x x , 1 2

)

(

T

2

= f x ( ) . x x , 1 2 2 0  0 − 2 1 2 x 1 x 2     .      

(

)

{

} 3

n

=

+

+ trong đó

∆ = = ∈ ≤ ≤ x x | ;1  x x , 1 2 x x , 1 2

Định lý 1.12. Cho hàm

( ) f x

T x Dx

T c x α

D

×∈  ,

c ∈  ,

n n S

1 2

α∈  . Khi đó, nếu D là ma trận nử xác định dương thì f là hàm lồi.

Chứng minh

Ta có, hàm

là hàm lồi và tổng của hai hàm lồi là một hàm lồi.

T c x α+

Do đó, ta chỉ cần chứng minh

là hàm lồi. Thật vậy:

T x Dx

x

n

∈

Vì D là ma trận nửa xác định dương nên với mọi

u

,n ∈ v

 . Ta có:

T

−

−

=

−

≤ 0 (

(

)

2

T ) u v D u v

T u Du

T + . v Du v Dv

T

= f x 1( ) :

Suy ra:

T ≤ v Dv u Du

T ( v D u v

n

− − 2 ).

Lấy

. Ta đặt:

. Thế vào biểu

t ∈

(0;1)

z

= :

tx

+ − (1

t y )

thức trên ta được:

≤

−

−

z

2

(

)

≤

−

−

T z Dz T z Dz

T y Dy T x Dx

2

T z D y T z D x

(

z

)

∈ ∈ x ,n y   bất kỳ,

Vì

và

nên:

−

+

+

(1

T t z Dz )

T tz Dz

≤ − (1

T t y Dy )

T tx Dx .

− − = − − y − = z t y ( x ) x (1 z t x )( y )

Suy ra:

Vậy,

1f là hàm lồi. 

= ≤ tx ( + − (1 t y ) ) + − (1 t ) ( ). f 1 f z ( ) 1 tf x ( ) 1 f y 1

13

Từ định lý trên ta có nhận xét, nếu ma trận D trong hàm mục tiêu của bài

toán quy hoạch toàn phương là ma trận xác định dương thì bài toán được gọi là quy

hoạch toàn phương lồi.

1.3.3. Các dạng quy hoạch toàn phương

Tập ràng buộc ∆ của bài toán quy hoạch toàn phương là tập lồi đa diện. Nên

toán quy hoạch toàn phương có thể được phát biểu dưới các dạng sau:

n

+

∈

min

,

T x Dx

T : c x x

≥ Ax b



1 2

  

  

n

+

∈

≥

min

,

,

0

T x Dx

T : c x x

≥ Ax b x



1 2

  

  

n

+

∈

=

min

,

,

T x Dx

T : c x x

≥ Ax b Cx

d



1 2

  

  

n

+

∈

≥

min

,

,

0

T x Dx

T : c x x

≤ Ax b x



1 2

  

n

∆ có thể được biểu diễn qua các hệ phương trình, hệ bất phương trình. Do đó, bài

T x Qx

T c x x :

} 0 .

   {

+ ∈ ≥ min , ≤ Ax b x , 

14

Chương 2: TÍNH CHẤT CỦA BÀI TOÁN QUY HOẠCH TOÀN PHƯƠNG

2.1. Điều kiện tồn tại nghiệm

Xét bài toán quy hoạch toàn phương:

=

+

min

( ) :

f x

T x Dx

T c x

(2.1)

∈

,

. . v d k

x

≥ Ax b

1 2 n 

    

n

m

trong đó

×∈ m n 

viết dưới dạng:

n

∆

(

:

A b



θ

∈ ∆

inf

(

= :

{ = ∈ x ( ) : f x

x

A b

, ) : {

} ≥ Ax b } , ) .

∆

∆

= ∅ thì θ = +∞ (quy ước). Nếu

≠ ∅ thì có hai trường

Nếu

(

, )A b

(

, )A b

hợp xảy ra: hoặc là θ ∈  hoặc là θ = −∞ (khi đó, bài toán không có nghiệm). Một

vấn đề được đặt ra là khi trường hợp θ ∈  xảy ra thì bài toán có nghiệm tối ưu hay

không? Ta có nhận xét, bài toán tối ưu với hàm mục tiêu không phải là hàm toàn

phương có thể không có nghiệm ngay cả khi giá trị tối ưu của nó là hữu hạn. Chẳng

∈ ∈ D c b , ,   . Tập ràng buộc và giá trị tối ưu của bài toán được

hạn, xét ví dụ: cho bài toán

. Khi đó, bài toán không có

θ

=

∈

≥

=

nghiệm, trong khi giá trị tối ưu của nó

là hữu hạn.

inf

:

x

,

x

0



1 x

  

 1  

Định lý Frank-Wolfe được phát biểu sau đây sẽ cho ta biết điều kiện tồn tại

nghiệm của bài toán (2.1).

∈ ≥ min : x , x  1 x     1  

2.1.1. Định lý Frank-Wolfe

θ = ∈ ∆

Định lý 2.1 (định lý Frank-Wolfe) Nếu

là một số

{

} A b , )

thực hữu hạn thì bài toán (2.1) có nghiệm.

inf f x ( ) : x (

Chứng minh

15

Giả sử θ ∈  . Ta cần chứng minh bài toán (2.1) có nghiệm. Do θ ∈  nên

0

0

∆

∈ ∆

≠ ∅ . Lấy

, với

. Suy

(

, )A b

x

(

A b , )

0ρ> tùy ý. Đặt

ra, ρ∆ là tập lồi, khác rỗng và compact.

Xét bài toán:

(2.1’)

min

f x

( ) :

x

{

} ρ∈ ∆ .

Theo định lý Weierstrass tồn tại y

ρ∈ ∆ sao cho:

=

f y ( )

= : min

f x

( ) :

x

q ρ

{

} ∈ ∆ ρ

Vì tập nghiệm của bài toán (2.1’) là khác rỗng và compact nên tồn tại

yρ

ρ∈ ∆ sao cho:

0

0

∩ ( A b , ) B x ( , ρ ) ∆ = ∆ ρ

{

}

0

Khi đó, luôn tồn tại ˆ

(2.2)

− = − ∈ ∆ = x min y x : y f y ( ) . y ρ , ρ q ρ

< ∀ ≥ , ρ ρ ρ ˆ . 0ρ> sao cho − xρ y

Thật vậy, giải sử trái lại chúng ta tìm được dãy tăng {

} :

k

k

0

ρ ρ → +∞ sao cho

. Để đơn giản cho

với mỗi k tồn tại

ρ∈ ∆ sao cho

k

k

k

= − = x ) , yρ ρ k f y ( ρ k q ρ k y ρ k

nên

ký hiệu ta viết

i

≥ ∀ = ,

1,...,

m .

ky thay cho

ky

yρ . Vì

A y i

b i

k

Với

sao cho

bị chặn dưới nên tồn tại dãy { } 'k

{ } k⊂

kA y 1

1i = ta có dãy {

}

k

'

k

'

tồn tại (có thể xảy ra trường hợp

∈ ∆ ( A b , )

k

, khi đó

tồn tại. Tương tự, với

= +∞ ). Không mất tính tổng A y 1 A y 1 lim →∞ k ' lim →∞ k '

i = ta cũng có

2

quát ta giả sử { } { } k≡

k

k

tồn tại. Khi đó,

tồn tại. Tiếp tục quá trình trên với i m=

'k A y 1 lim →∞ k

ta có lim →∞

k

k

A y m A y 2 lim →∞ k

tồn tại.

với mỗi

{ 1,...,

} m

ta có lim →∞

k

k

k

=

=

>

Đặt

,

,

.

I

= ∈ i

I

I

\

I

= ∈ i

I

I =

{1,...,m}

A y i

b i

0

I 1

o

A y i

b i

∈ i A y i

{

{

}

}

: lim →∞ k

0 : lim →∞ k

k

Khi đó, tồn tại

0ε > sao cho

i ≥ + ∀ ∈ . ε , A y i b i I 1 lim →∞ k

16

0

k

x

y

0

−

=

Mặt khác,

x

1

∀ . k

= ⇒ ρ k

y ρ k

− ρ k

Vì quả cầu đơn vị trong

n là compact nên không mất tính tổng quát ta có

0

k

x

y

n

thể giả sử dãy

hội tụ về

v = .

1

v ∈  khi k → ∞ và

− ρ k

  

  

Vì

kρ → +∞ nên với mỗi

0

k

i

k

= − 0 A y i b i lim →∞ k

) − b i  

0

k

0

A y i = lim →∞ k ρ k I∈ , ta có: (   

y x A x i = + A i lim →∞ k lim →∞ k − ρ k ρ k          − b i  

Tương tự, với mỗi

= A v i

1

k

i I∈ ta có:

→∞

0

0

k

A y i ≤ 0 liminf k ρ k    − b i  

0

0

k

A y i A x i A x i b i = + liminf →∞ k − ρ k − ρ k   

x y A x i = + A i lim →∞ k lim →∞ k − ρ k ρ k             − b i  

Khi đó,

= A v i

iA v

0

iA v

∆

tập lồi đa diện

.

(

, )A b

∈ ∆

Do đó,

với mọi

.

(2.3)

t ≥ và 0

y

+ ∈ ∆ tv

(

A b , )

y

(

A b , )

Vì

k

= ∀ ∈ và ≥ ∀ ∈ . Suy ra, v là phương lùi xa của 0, I i 0, i I 1

= = f y ( ) ) f y ( ρ k q ρ k

ρ k

0

= ∈ ∆ f x x min ( ) :

} A b , )

} )

{ {

= ∈ ∆ ∩ f x x min ( ) : ( B x ( , ρ k

17

là dãy giảm và

và dãy {

}kρ là dãy tăng

kρ → +∞ nên ta có {

} )k

k

θ

θ

Với k đủ lớn, ta có:

≤ + . Sử dụng công thức của hàm f ta có thể

− ≤ 1

f y (

)

1

viết bất đẳng thức trên dưới dạng:

T

k

k

T

k

0

0

0

−

−

+

−

+

θ

y

x

x

c

y

x

− ≤ 1

(

)

)

)

( D y

(

1 2

k

0

0

0

+

−

+

+

≤ + θ

x

T c x

(

T 0 x Dx )

(

1

( T 0 x D y )

)

1 2

2

Chia các vế của bất đẳng thức trên cho

kρ và cho k → +∞ ta được

≤

≤ . Suy ra,

với mọi

0

0

Tv Dv

t ≥ 0

ky

+ ∈ ∆ tv

(

A b , )

Tv Dv = . Từ (2.3) suy ra,

0

1 2

Tv Dv = , ta có: 0

và k ∈  . Kết hợp với điều kiện

k

k

k

T

k

+

=

+

+

+

+

tv

y

tv

c

y

tv

( f y

)

(

T ( ) tv D y

(

)

T

T

k

k

k

k

=

+

+

+

y

Dy

T c y

t

y

Dv

T c v

(

)

(

)

θ→ . f y ( )k ( f y

)

) (

1 2 1 2

(2.4)

T c v

Suy ra: (

Tk )

k

+ ≥ y Dv 0, k ∀ ∈  .

T c v+

Giả sử trái lại (

Tk )

( f y

) tv+ → −∞

khi t → +∞ , điều này mâu thuẫn với giả thiết θ ∈  . Do đó, ta có công thức (2.4).

0

k

x

y

Mặt khác,

v

v v = và

1

,

→ nên tồn tại 1k ∈  sao cho:

− ρ k

0

k

y Dv 0 < với k ∈  nào đó, thì

x y > , v 0 k ∀ ≥ k 1 − ρ k

Cố định

ky

0, x v

1

2

2

2

2

k

0

k

0

k

k

0

− > . Suy ra: 0 k k≥ ta có,

(2.5)

0 x v ,

2 t v

− − = − − − + < − y x tv y x t y 2 y x

18

k

k

với

t > đủ nhỏ. Ta lại có:

0

0

0

)

( A y i

k

− = ≥ ∀ ∈ (do với tv I i , i I∈ ta có A y i b i

sao cho:

iA v = ). Mặt khác,

2

2

k

∀ ≥ k

,

A y i

≥ + b i

k i , 2

∈ . I 1

ε 2

≤ ∀ ∈

∈

Cố định chỉ số

và chọn

.

i

0,

∈ ≥ i ε , 0 k , k  A y i b i ≥ + ∀ ∈ nên tồn tại I 1 k 1 lim →∞ k

(

)

tA v i

δ k

I t 1,

2

kδ > sao cho

ε 2

k

k k≥ 0

−

≥

≥

∈

. Suy ra:

Khi đó:

ky

,

0,

tv

∀ ∈ i

(

)

(

), A b

, I t 1

b i

tA v i

b i

δ k

( A y i

)

ε + − 2

− ∈ ∆ tv

. Kết hợp với (2.5) ta có,

và:

với mọi

ky

)

), A b

(

( δ∈ 0, k

k

0

k

0

k

−

−

=

−

−

<

−

y

tv

x

y

x

tv

y

0 = x ρ k

(

)

với mọi

đủ nhỏ. Từ (2.4) ta có:

− ∈ ∆ tv t

)

( δ∈ 0, k

T

T

k

k

k

k

k

−

=

+

−

+

tv

y

Dy

T c y

t

y

Dv

T c v

( f y

)

(

)

(

)

t

)

(

1 2

T

k

k

−

+

=

t

y

Dv

T c v

(

)

)

(

k

≤

.

( f y ( f y

) )

Do đó,

là nghiệm của bài toán

. Từ bất đẳng thức

f x

x

min

( ) :

ky

tv−

ρ∈ ∆

}

{

k

k

0

k

0

−

−

<

−

suy ra

y

tv

x

y

x

ky không phải là nghiệm của bài toán trên với

)

(

khoảng cách tới

0x là nhỏ nhất. Điều này mâu thuẫn với:

0

0

−

=

−

∈ ∆

=

ky

x

min

y

x

:

y

,

f y ( )

.

ρ k

q ρ k

{

}

Vậy, ta đã chứng minh được tồn tại ˆ

0ρ> sao cho (2.2) được thỏa mãn. Tiếp

tục quá trình chứng minh ta cần chỉ ra tồn tại

(2.6)

ˆρ ρ≥ sao cho qρ θ= .

=

Vì

∈ ∆ nên từ (2.6) suy ra định lý đã chứng minh.

min

f x

( ) :

x

q ρ

ρ

{

}

Chứng minh khẳng định (2.6). Giả sử trái lại

(2.7)

> ∀ ≥ . qρ θ ρ ρ ˆ ,

19

'

Chú ý rằng,

với mọi

ρ≥ qρ q

'ρ ρ≥ và qρ θ→ khi ρ→ +∞ . Từ (2.7) suy

+∞

=

ra tồn tại

sao cho

và

. Vì

1, 2)

( i

( ρ ρ∈ ˆ,

)

ρ> q

i

2ρ ρ<

1

2ρ ρ> nên từ kết

q ρ 1

2

0

quả (2.2) ta có:

.

0

0

− < x ρ 2 y ρ 2

nên

(Thật vây, nếu

thì

Ta có:

ρ> q

2

− − x x ρ ≥ 1 ρ < 1 q ρ 1 y ρ 2 y ρ 2

, điều này mâu thuẫn với cách chọn

ρ∈ ∆ và

)

)

2

1

( f y ρ 2

( f y ρ 1

1

0

= < = yρ ). yρ q ρ 2 q ρ 1

ta có,

. Vì

Đặt

1

3

2

0

0

− < < ˆρ ρ< và ˆρ ρ> nên từ khẳng định x ρ = 3 ρ ρ ρ 3 2 y ρ 2

(2.2) ta có:

.

(2.8)

− < = − < x x ρ 3 ρ 2 y ρ 3 y ρ 2

Vì

nên

.

2

)

)

( f y ρ 3

( f y ρ 2

= ≥ = ρ ρ> 3 q ρ 3 q ρ 2

thì từ (2.8) suy ra

Nếu

)

)

3

( f y ρ 3

( f y ρ 2

toán:

.

(2.9)

min

f x

( ) :

x

{

}2 ρ∈ ∆

=

=

, mà

nên

với hàm mục tiêu có giá trị tối ưu

yρ cũng

)

)

)

( f y ρ 3

( f y ρ 2

q ρ 2

( f y ρ 2

3

là nghiệm của bài toán (2.9).

0

0

= yρ là vectơ chấp nhận được của bài

Mặt khác,

. Suy ra,

yρ không phải là nghiệm của bài

2

0x là nhỏ nhất, điều này mâu thuẫn với sự tồn tại của

0

− < − x x y ρ 3 y ρ 2

>

. Ta lại có,

nên

yρ . Do đó,

yρ là vectơ chấp nhận

)

toán (2.9) với khoảng cách tới ( ) f y ρ 3

( f y ρ 2

2

2

>

được của bài toán

. Từ bất đẳng thức

dẫn đến

min

f x

( ) :

x

)

)

{

( f y ρ 3

( f y ρ 2

}3 ρ∈ ∆

mâu thuẫn với sự kiện

yρ là nghiệm tối ưu của bài toán. Suy ra: khẳng định (2.6)

3

đã được chứng minh. Vậy, bài toán (2.1) có nghiệm. 

Trong định lý Frank-Wolfe, nếu thiếu một trong hai điều kiện f là hàm toàn

phương hoặc ∆ là tập lồi đa diện thì kết luận của định lý sẽ không còn đúng nữa.

− = x ρ 3 y ρ 2

20

=

Ví dụ 1: Xét bài toán

∈ ∆ trong đó

min

f x ( )

:

x

{

}

x 1

1

2

f x ( ) x= là hàm toàn

không phải là tập lồi

phương nhưng

Tx

)

(

{

} 0

đa diện.

=

∆ = = ∈ ≥ ≥ ≥ : 1, 0,  x x , 1 2 x x 1 2 x 1 x 2

Ta có:

x

min

f x ( )

:

{

} ∈ ∆

}

{

x 1

không có nghiệm.

∈

≥

trong đó,

là

θ = ∈ ∆ = nhưng bài toán inf f x ( ) : x 0

Ví dụ 2: Xét bài toán

min

:

,

x

x

} 1

{ ∆ = ∈



1 x

  

 1  

= không phải là hàm toàn phương.

tập lồi đa diện nhưng hàm

f x ( )

1 x

x ≥ : x

nhưng bài toán

Ta có,

không có nghiệm.

Mặt khác, do ∆ là tập lồi đa diện nên ta có thể phát biểu định lý dưới dạng:

θ = ∈ ≥ = ∈ ≥ inf : x , x 0 min : x , x   1 x 1 x  1       1     

Nếu một hàm toàn phương bị chặn dưới trên một tập lồi đa diện thì bài toán min

của hàm toàn phương trên tập lồi đa diện đó sẽ có nghiệm.

2.1.2. Định lý Eaves

Định lý 2.2 (Định lý Eaves) Bài toán (2.1) có nghiệm nếu và chỉ nếu các

điều kiện sau được thỏa mãn:

∆

i)

khác rỗng.

(

, )A b

21

ii) Nếu

Av ≥ thì 0

Tv Dv ≥ .

0

n v ∈  và

n

iii) Nếu

Av ≥ ,

0

Tv Dv = và Ax b≥ thì

n v ∈  và

T

0 x ∈  sao cho

(

)

+ Dx c v ≥ . 0

Chứng minh

iii) được thỏa mãn. Thật vậy:

∆

khác rỗng. Suy ra điều kiện i)

Vì x là nghiệm của bài toán (2.1) nên

(

, )A b

được thỏa mãn.

⇒ / Giả sử bài toán (2.1) có nghiệm là x . Ta cần chứng minh các điều kiện i), ii),

Giả sử

Av ≥ . Ta có,

0

n v ∈  và

+

≥

với mọi

∀ ≥ . Sử dụng công

tv

0

t

t ≥ . Suy ra,

0

x

+ ∈ ∆ tv

(

A b , )

( f x

)

( f x

),

T

+ = + ≥ ∀ ≥ nên A x ( tv ) Ax tAv b 0 t ,

thức của hàm

T t v Dv

f ta được:

( t Dx

)

21 2

Tv Dv ≥ (thật vậy, nếu

0

Tv Dv < thì ta cho t → +∞ ở bất đẳng thức trên sẽ dẫn

0

đến điều vô lý). Do đó, điều kiện ii) được thỏa mãn.

n

Giả sử

Av ≥ ,

0

Tv Dv = và Ax b≥ . Vì

0

n v ∈  và

x ∈  sao cho

với mọi

0

t ≥ và x là nghiệm của bài toán (2.1) nên

x

+ ∈ ∆ tv

(

A b , )

+ + ≥ ∀ ≥ . Từ đó suy ra, c v 0, 0 t

Tv Dv = suy ra: 0

( f x

),

( f x

)

T

+

+

+

≥

c

v

T x Dx

T c x

f x

( ),

∀ ≥ 0.

t

( t Dx

)

1 2

T

+

Dx

c

v

0

< thì ta cho t → +∞ ở bất đẳng thức trên sẽ dẫn đến điều vô lý.

Nếu (

)

Suy ra, điều kiện iii) được thỏa mãn.

+ ≥ ∀ ≥ . Từ điều kiện tv 0 t

nghiệm. Đặt

khác rỗng nên θ ≠ +∞ .

. Vì

{

Nếu θ ∈  thì theo định lý Frank-Wolfe bài toán (2.1) có nghiệm. Ta cần chứng

0

∈ ∆

minh θ = −∞ không xảy ra. Thật vậy, giả sử có θ = −∞ . Cố định

, với

x

(

A b , )

0

θ = ∈ ∆ , )A b ( ) : f x inf ,n x (  ⇐ / Giả sử các điều kiện i), ii) iii) được thỏa mãn. Ta chứng minh bài toán (2.1) có } ≥ Ax b

mỗi

ta định nghĩa

. Ta xét bài

toán

∩ ( A b , ) B x ( , ρ ) 0ρ> ∆ = ∆ ρ

22

min

f x

( ) :

x

ρ∈ ∆ sao cho

ρ∈ ∆ . Gọi qρ là giá trị tối ưu của bài toán này. Lấy yρ

{

}

0

0

−

=

−

∈ ∆

=

và

.

x

min

y

x

:

y

f y ( )

y ρ

, ρ

q ρ

ρ= q

( f y ρ

)

{

}

0

Khi đó, luôn tồn tại ˆ

0ρ> sao cho

< ∀ ≥ , ρ ρ ρ ˆ . − xρ y

Thật vậy, giải sử trái lại chúng ta tìm được dãy tăng {

} :

k

k

0

ρ ρ → +∞ sao cho

. Để đơn giản cho

với mỗi k tồn tại

yρ

ρ∈ ∆ sao cho

k

k

k

∈ ∆

nên

ký hiệu ta viết

≥ ∀ = ,

i

1,...,

m .

ky thay cho

ky

(

A b , )

yρ . Vì

A y i

b i

k

sao cho

Với

bị chặn dưới nên tồn tại dãy { } 'k

{ } k⊂

kA y 1

1i = ta có dãy {

}

k

k

'

'

tồn tại (có thể xảy ra trường hợp

= − = x ) , ρ k f y ( ρ k q ρ k y ρ k

k

, khi đó

tồn tại. Tương tự, với

'k

i = ta cũng có

2

quát ta giả sử { } { } k≡

= +∞ ). Không mất tính tổng A y 1 A y 1 lim →∞ k ' lim →∞ k '

k

k

tồn tại. Khi đó,

tồn tại. Tiếp tục quá trình trên với i m=

A y 1 lim →∞ k

ta có lim →∞

k

k

∈

với mỗi

tồn tại.

i

} m

{ 1,...,

A y m A y 2 lim →∞ k

ta có lim →∞

k

k

k

=

=

>

Đặt

,

,

.

I

= ∈ i

I

\

I

I

= ∈ i

I

I =

{1,...,m}

A y i

b i

o

A y i

b i

0

I 1

A y i

{

{

}

}

0 : lim →∞ k

: lim →∞ k

k

Khi đó, tồn tại

0ε > sao cho

0

k

i ≥ + ∀ ∈ . ε , A y i b i I 1 lim →∞ k

0

Mặt khác,

Vì quả cầu đơn vị trong

n là compact nên không mất tính tổng quát ta có

0

k

x

y

n

thể giả sử dãy

hội tụ về

v = .

1

v ∈  khi k → ∞ và

− ρ k

  

  

Vì

x y − = x ∀ . k 1 = ⇒ ρ k y ρ k − ρ k

kρ → +∞ nên với mỗi

0

i I∈ , ta có:

23

k

=

−

k

0 A y i b i lim →∞ k

=

) − b i  

(   

0

k

0

A y i lim →∞ k ρ k

=

+

− ρ k

ρ k

y x A x i A i lim →∞ k lim →∞ k          − b i  

Tương tự, với mỗi

= A v i

1

k

i I∈ ta có:

→∞

k

0

0

A y i ≤ 0 liminf k ρ k    − b i  

0

0

k

A y i A x i A x i b i = + liminf →∞ k − ρ k − ρ k   

x y A x i = + A i lim →∞ k lim →∞ k − ρ k ρ k             − b i  

= A v i

Khi đó,

iA v

0

iA v

∆

tập lồi đa diện

.

(

, )A b

∈ ∆

Do đó,

với mọi

.

(2.10)

t ≥ và 0

y

+ ∈ ∆ tv

(

A b , )

y

(

A b , )

Vì

k

=

=

)

)

( f y

( f y ρ k

q ρ k

=

∈ ∆

min

( ) :

f x

x

ρ k

0

=

∈ ∆

∩

min

( ) :

(

,

f x

x

} , ) A b

( B x

ρ k

} )

là dãy giảm và

= ∀ ∈ và ≥ ∀ ∈ . Suy ra, v là phương lùi xa của 0, I i 0, i I 1

f y → −∞ . (

)k

và dãy {

}kρ là dãy tăng

{ { kρ → +∞ nên ta có {

} )k

k

Suy ra,

( f y < với k đủ lớn. Sử dụng công thức của hàm f ta được:

) 0

T

k

k

T

k

0

0

0

−

−

+

−

+

y

x

x

c

y

x

)

( D y

)

(

)

(

1 2

k

0

0

0

+

−

+

+

<

(

(

0

x

T 0 ) x Dx

T c x

( T 0 ) x D y

)

1 2

f y (

24

2

Chia các vế của bất đẳng thức trên cho

kρ và cho k → +∞ ta được

0

Av ≥ nên từ điều kiện ii) suy ra

Tv Dv ≤ . Vì

Tv Dv = . Từ

Tv Dv ≥ . Do đó, 0

(2.10) suy ra,

với mọi

0

ky

+ ∈ ∆ tv

(

A b , )

t ≥ và k ∈  . Kết hợp với điều kiện

Tv Dv = , ta có: 0

k

k

k

T

k

+

=

+

+

+

+

tv

y

tv

c

y

tv

( f y

)

(

T ( ) tv D y

(

)

T

T

k

k

k

k

=

+

+

+

y

Dy

T c y

t

y

Dv

T c v

(

)

(

)

0 0

)

) (

1 2 1 2

k

∈ ∆

≥

Vì

= nên từ điều kiện iii) suy ra:

y

(

A b Av , ),

0,

T v Dv

0

k

(2.11)

T c v

T c v )

(

Tk )

0

k

x

y

Mặt khác,

v

v v = và

1

,

→ nên tồn tại 1k ∈  sao cho:

− ρ k

0

k

+ = + ≥ y Dv ( Dy 0, k ∀ ∈  .

x y > , v 0 k ∀ ≥ k 1 − ρ k

Cố định

ky

0, x v

1

2

2

2

2

k

0

k

0

k

k

0

− > . Suy ra: 0 k k≥ ta có,

(2.12)

0 x v ,

2 t v

k

k

− − = − − − + < − y x tv y x t y 2 y x

với

t > đủ nhỏ. Ta lại có:

0

0

0

)

( A y i

k

− = ≥ ∀ ∈ (do với tv I i , i I∈ ta có A y i b i

sao cho:

iA v = ). Mặt khác,

2

2

k

∀ ≥ k

,

k i , 2

∈ . I 1

A y i

≥ + b i

ε 2

≤ ∀ ∈

∈

và chọn

.

Cố định chỉ số

i

0,

∈ ≥ i ε , 0 k , k  A y i b i ≥ + ∀ ∈ nên tồn tại I 1 k 1 lim →∞ k

(

)

tA v i

I t 1,

δ k

2

kδ > sao cho

ε 2

k

k k≥ 0

−

≥

≥

∈

Khi đó:

. Suy ra:

ky

,

0,

tv

∀ ∈ i

(

)

(

), A b

, I t 1

b i

tA v i

b i

δ k

( A y i

)

ε + − 2

− ∈ ∆ tv

. Kết hợp với (2.12) ta có,

và:

với mọi

ky

)

(

), A b

( δ∈ 0, k

k

0

k

0

k

−

−

=

−

−

<

−

y

tv

x

y

x

tv

y

0 = x ρ k

(

)

− ∈ ∆ t tv

25

với mọi

đủ nhỏ. Từ (2.11) ta có:

)

( δ∈ 0, k

T

T

k

k

k

k

k

−

=

+

−

+

tv

y

Dy

T c y

t

y

Dv

T c v

( f y

)

(

)

(

)

t

)

(

1 2

T

k

k

−

+

=

t

y

Dv

T c v

(

)

)

(

k

≤

.

( f y ( f y

) )

Do đó,

là nghiệm của bài toán

. Từ bất đẳng thức

f x

x

min

( ) :

ky

tv−

ρ∈ ∆

{

}

k

k

0

k

0

suy ra

ky không phải là nghiệm của bài toán trên với

)

(

khoảng cách tới

0x là nhỏ nhất. Điều này mâu thuẫn với:

0

0

−

=

−

∈ ∆

=

ky

x

min

y

x

:

y

,

f y ( )

.

ρ k

q ρ k

{

}

Vậy, ta đã chứng minh được tồn tại ˆ

0ρ> sao cho:

0

− − < − y tv x y x

'

với mọi

Chú ý rằng,

ρ≥ qρ q

'ρ ρ≥ và qρ θ→ = −∞ khi ρ→ +∞ . Suy ra:

+∞

=

tồn tại

sao cho

và

. Vì

1, 2)

( i

( ρ ρ∈ ˆ,

)

ρ> q

i

2ρ ρ<

1

2ρ ρ> nên từ kết quả

q ρ 1

2

0

ρ ρ ρ ˆ < ∀ ≥ , (2.13) − xρ y

.

(2.13) ta có:

0

0

− < x ρ 2 y ρ 2

nên

(Thật vây, nếu

thì

Ta có:

ρ> q

q ρ 1

2

=

<

=

, điều này mâu thuẫn với cách chọn

yρ ).

yρ

ρ∈ ∆ và

)

)

( f y ρ 2

q ρ 2

q ρ 1

( f y ρ 1

2

1

1

0

− − x x ρ < 1 ρ ≥ 1 y ρ 2 y ρ 2

ta có,

. Vì

Đặt

1

3

2

0

0

< < − ˆρ ρ< và ˆρ ρ> nên từ khẳng định x ρ ρ ρ 3 2 ρ = 3 y ρ 2

.

(2.14)

(2.13) ta có:

=

≥

=

Vì

nên

.

− < = − < x x ρ 3 ρ 2 y ρ 3 y ρ 2

2

)

)

q ρ 3

( f y ρ 3

( f y ρ 2

q ρ 2

=

Nếu

thì từ (2.14) suy ra

yρ là vectơ chấp nhận được của

)

)

( f y ρ 3

( f y ρ 2

3

bài toán:

.

(2.15)

ρ ρ> 3

{

}2 ρ∈ ∆

min f x ( ) : x

26

=

=

với hàm mục tiêu có giá trị tối ưu

, mà

nên

yρ cũng

)

)

)

q ρ 2

( f y ρ 2

( f y ρ 3

( f y ρ 2

3

là nghiệm của bài toán (2.15).

0

0

Mặt khác,

. Suy ra,

2

toán (2.15) với khoảng cách tới

0

− < − x x yρ không phải là nghiệm của bài y ρ 3 y ρ 2

>

. Ta lại có,

nên

của

yρ . Do đó,

yρ là vectơ chấp

0x là nhỏ nhất, điều này mâu thuẫn với sự tồn tại )

)

( f y ρ 3

( f y ρ 2

2

2

− = x ρ 3 y ρ 2

nhận được của bài toán

. Từ bất đẳng thức

)

{

)

}3 ρ∈ ∆

( f y ρ 3

( f y ρ 2

dẫn đến mâu thuẫn với sự kiện

yρ là nghiệm tối ưu của bài toán. Do đó, trường

3

hợp θ = −∞ không xảy ra. Vậy, bài toán (2.1) có nghiệm. 

> min f x ( ) : x

Hệ quả 2.1 Giả sử D là ma trận nửa xác định dương thì bài toán (2.1) có

∆

nghiệm khi và chỉ khi

(

, )A b

T

n

n

∈

∈

≥

=

+

≥

,

,

0,

0,

0

v

x

Av

T v Dv

Ax

Dx

c

v

(

)





(

≠ ∅ và thỏa điều kiện: ) ≥ ⇒ 0

Chứng minh

T v Dv

0,

v

Ta có: D là ma trận nửa xác định dương, tức là

n ≥ ∀ ∈  . Suy ra,

điều kiện ii) của định lý Eaves được thỏa mãn. Do đó, áp dụng định lý Eaves ta có

điều phải chứng minh.



Hệ quả 2.2 Nếu D là ma trận xác định dương thì bài toán (2.1) có nghiệm

khi và chỉ khi

∆ ≠ ∅ . ( , )A b

Chứng minh

Ta có: D là ma trận xác định dương suy ra điều kiện ii) của định lý Eaves

được thỏa mãn. Hơn nữa, nếu

v = . Suy ra, điều kiện iii) cũng được

0

0

Tv Dv = thì

thỏa mãn. Áp dụng định lý Eaves ta có điều phải chứng minh. 

× n n

n

m

∈

∈

∈

∈

Hệ quả 2.3 Cho

D

,

A

,

c

,

b







 . Khi đó, bài toán quy

× n n S

hoạch toàn phương:

n

+

∈

≥

(2.16)

min

,

,

0

T x Dx

T : c x x

≥ Ax b x



1 2

  

  

có nghiệm nếu và chỉ nếu ba điều kiện sau được thỏa mãn:

27

n

khác rỗng.

} 0

i) Tập ràng buộc {

n

∈

≥

≥

thì

ii) Nếu

Tv Dv ≥ .

0

v

,

Av

0,

v

0



n

≥

≥

=

iii) Nếu

≥ thì

Av

v

T v Dv

≥ Ax b x

0,

0,

0,

,

0

n v ∈  và

∈ ≥ x ≥ Ax b x , , 

T

+

Dx

c

v

≥ . 0

(

)

x ∈  sao cho

Chứng minh

Đặt

trong đó, E là ma trận đơn vị cấp n n× và 0 là

+ m n

(

+ × m n n )

(

)

∈

∈

và bài toán (2.16) được viết

vectơ không trong

A

b

'

,

'

n . Khi đó,





lại dưới dạng:

n

= = A b ' , ' A E         b   0  

T x Dx

T : c x x

Áp dụng định lý Eaves ta có điều phải chứng minh. 

× m n

× s n

n

m

s

∈

∈

∈

∈

∈

∈

+ ∈ min , ' ' ≥ A x b  1 2      

Hệ quả 2.4 Cho

,

,

,

,

,

D

A

C

c

b

d











 . Khi đó,

× n n S

bài toán quy hoạch toàn phương:

n

+

∈

=

(2.17)

min

,

,

T x Dx

T : c x x

≥ Ax b Cx

d



1 2

  

  

có nghiệm nếu và chỉ nếu ba điều kiện sau được thỏa mãn:

n

khác rỗng.

i) Tập ràng buộc {

}

n

∈

≥

=

thì

ii) Nếu

Tv Dv ≥ .

0

v

,

Av

0,

Cv

0



n

≥

=

=

iii) Nếu

Av

0,

Cv

0,

T v Dv

0,

≥ Ax b Cx

,

= d

∈ = x ≥ Ax b Cx d , , 

n v ∈  và

T

x ∈  sao cho

thì (

)

+ Dx c v ≥ . 0

Chứng minh

×

+

(

m s n 2 )

(

+ m s 2 )

=

=

∈

∈

. Khi đó,

và bài toán

Đặt :

A

'

,

b

'

A

'

,

b

'





A C −

b d −

C

d

    

    

    

    

(2.17) được viết lại dưới dạng:

28

n

+

∈

min

T x Dx

T c x x :

,

≥ A x b

'

'



1 2

  

  

Áp dụng định lý Eaves ta có điều phải chứng minh. 

2.2. Tính chất tập nghiệm của bài toán quy hoạch toàn phương

Xét bài toán quy hoạch toàn phương:

n

T x Dx

T c x x :

× m n

× s n

s

m

∈

∈

∈

∈

∈

trong đó

D

,

C

,

b

d

,

,







 . Đặt:

× n n S

n

= + ∈ = ( P ) min f x ( ) , ≥ Ax b Cx , d  1 2      

{ 1,...,

} m J ,

{ 1,...,

} s

A { ∆ = ∈

 } d I ,

Ký hiệu:

Sol P là tập các nghiệm của bài toán quy hoạch toàn phương (P).

)

(

≥ = = = x : Ax b Cx , 

2.2.1. Tính bị chặn của tập nghiệm

Gọi

0(

liên kết với bài toán (P):

n

∈

≥

=

(

)

min

:

,

0,

0

T v Dv v

Av

Cv



P 0

1 2

  

  

n

=

+

≥

Sol P là tập nghiệm của bài toán quy hoạch toàn phương thuần nhất )

Định nghĩa: Nửa đường thẳng

trong đó:

w

x

tv t :

{

} 0

x ∈  ,

n

được gọi là nghiệm tia của bài toán (P) nếu nó là tập con của

Sol P . (

)

{ } \ 0

v ∈ 

Định lý 2.3. Tập nghiệm

Sol P không bị chặn nếu và chỉ nếu (P) có nghiệm ( )

tia. Hơn nữa, điều kiện cần và đủ để

và

T

∈

+

(2.18)

v

Dx

c

v

= . 0

{ } ) \ 0

sao cho: (

)

Sol P 0(

∈ Sol P không bị chặn là tồn tại ) ( x Sol P ( )

Chứng minh

trong

Giả sử

kx → +∞ khi k → +∞ . Không mất tính tổng quát ta giả sử

kx ≠ với mọi k và

( ) Sol P sao cho ( ) Sol P không bị chặn. Suy ra, tồn tại dãy { }kx

k

0

.

→ với v

v = . Ta sẽ chứng minh

1

k

x x

∈ v ) Sol P 0(

29

k

k

k

k

≥

=

∈

≥

A

C

Vì

nên

= . Suy ra:

.

,

kx

Sol P (

)

Ax

b Cx ,

d

k

k

x x

b k x

x x

d k x

Cho k → +∞ ta được

n

Mặt khác,

Tv Dv ≥ với mọi 0

Sol P ≠ ∅ theo định lý Eaves ta có,

)

(

v ∈  thỏa mãn

≥

= . Do đó,

Tv Dv ≥ .

0

0,

0

Av

Cv

k

k

+

≤

≥ Av 0, Cv 0 = . Do đó, v là vectơ chấp nhận được của (P0).

nên

Dx

T c x

k

x

Cố định ˆx ∈ ∆ . Vì

kx

( ) ˆ , f x

∀ ∈  .

(

Tk )

1 2

Chia hai vế của bất đẳng thức cho

và cho k → +∞ ta được,

2kx

Tv Dv ≤ . Suy ra, 0

Tv Dv = .

0

n

≥

Lấy bất kỳ

= . Từ

Av

0,

Cv

0

v ∈  là vectơ chấp nhận được của (P0), ta có

n

∈ Sol P ( )

đó suy ra,

T v Dv

T v Dv

Tv Dv ≥ . Do đó, 0

∈

∈

. Bây giờ ta cần chứng minh tồn tại

thỏa

v

x

Sol P (

)

(P0). Vậy,

{ } ) \ 0

Sol P 0(

mãn (2.18). Vì

kAx

b

k

,

≥ ∀ ∈  lý luận tương tự như trong chứng minh định lý

k

'

tồn tại

sao cho với mỗi i

I∈ thì giới hạn

{ } k⊂

(2.1) ta có dãy con { } 'k

≤ v , ∀ ∈  , v thuộc miền ràng buộc của

(giới hạn này có thể bằng +∞ ). Ta có:

'

k

≥

)

∀ ∈ ( i

I

A x i

b i

lim →∞ ' k

'

k

=

)

d

∀ ∈ ( j

J

C x j

lim →∞ ' k

=

. Đặt:

'k

I

= ∈ i

I

Không mất tính tổng quát ta có thể giả sử { } { } k≡

b i

0

A x i lim →∞ k '

{

}

: lim k A x i →∞ k

. Khi đó, tồn tại

và

00, k

{

}

k

'

ε

.

∀ ∈ ∀ ≥ ( I ,

k

i

k

)

A x i

≥ + b i

0

k

=

=

=

∀ ∈

Ta có:

i M

0 (

)

A v i

A i

0

k

lim →+∞ k

lim →+∞ k

x x

bi k x

k

ε

=

≥

=

∀ ∈

.

và

0 (

i M

)

A v i

A i

0

k

+ k

lim →+∞ k

lim →+∞ k

x x

bi x

> ε > = ∈ i I ∈  sao cho: I 1 b i : lim k A x i →∞ k

30

k

=

−

Đặt

trong đó,

. Ta có:

k x t ( )

x

tv

0

k

k

=

−

=

≥

k A x t ( )

∀ ∈ ( i

I

)

i

A x i

tA v i

A x i

b i

0

k

> ≥ t 0, k k

k A x t ( )

i

Cố định

. Từ các bất đẳng thức trên suy ra tồn tại

0δ > sao cho, với

= − ≥ + − ε i A x i tA v i b i tA v i ∀ ∈ ( I ) 1

0

k k≥

mỗi

ta có:

t

k A x t ( )

) ∀ ∈ ∪ . Hiển nhiên,

(

( )0, δ∈

k C x t ( ) j

j

i

0

. Ta có:

Suy ra,

t

kx t ∈ ∆ với mọi

≥ = ∀ ∈ . I i d J j , b i I 1

)0, ( δ∈

k

≤

−

0

)

( f x

T

T

k

k

k

k

k

=

−

−

+

+

−

k x t ( )

x

x

Dx

c

k x t ( )

x

( k f x t ( ) (

)

) ( D x t ( )

)

(

) (

)

1 2

T

k

( )

T v Dv

)

(

T

⇒ − + + ≤ 0 Dx c v 1 2

Kết hợp với

kDx

Tv Dv = ta được: ( 0

)

T

T

+ ≤ . Mặt khác, áp dụng kết quả c v 0

kDx

kDx

iii) của hệ quả (2.4) ta được (

)

)

k

ta có được phương trình (2.18).

+ + = . Chọn c v c v 0 ≥ . Suy ra, ( 0

x x=

∈

Ngược lại, giả sử tồn tại

và

sao cho (2.18) được

x

Sol P (

)

{ } ) \ 0

thỏa mãn. Ta cần chứng minh, bài toán có nghiệm tia. Thật vậy:

+

≥

∈ v Sol P 0(

. Với mỗi

và

nên:

Đặt

w

= :

x

tv t :

t > , vì 0

{

} 0

∈ ∈ x Sol P ( ) v ) Sol P 0(

+ = + ≥ tv Ax tAv b

) )

( A x ( C x

+ = + = tv Cx tCv d

và 0 là vectơ chấp nhận được của bài toán

Do đó, x

tv+ ∈ ∆ . Vì

Tv Dv ≤ . Nếu 0

Tv Dv < thì dẫn đến mâu thuẫn với kết quả của hệ quả

∈ v ) Sol P 0(

(P0) ta có

(2.4). Suy ra,

Tv Dv = . Kết hợp với điều kiện (2.18) ta được:

0

T

+

=

+

+

+

+

tv

x

tv

c

x

tv

( f x

)

(

)

T ( tv D x

)

(

)

T

=

+

+

+

+

=

( ).

T x Dx

T c x

c

v

2 T t v Dv

f x

( t Dx

)

1 2

  

1 2  1  2 

0

31

∈

Vì

nên

với mọi

t ≥ . Như vậy, ta đã chứng

0

x

Sol P (

)

x

+ ∈ tv

Sol P (

)

∈

∈

và

minh được nếu

v

x

Sol P (

)

Sol P không bị chặn thì tồn tại

(

)

{ } ) \ 0

Sol P 0(

=

+

≥

thỏa (2.18) và

là nghiệm tia của (P).

w

x

tv t :

{

} 0

Hiển nhiên, nếu bài toán (P) có nghiệm tia thì

Sol P không bị chặn. 

)

(

Từ định lý trên, ta trực tiếp có các kết quả sau:

Hệ quả 2.5 Nếu tập nghiệm

0(

n

m

s

×

Sol P bị chặn. Trường hợp,

(

)

bất kỳ ( ,

c b d ∈ × )

,

   thì tập nghiệm

Sol P là rỗng hoặc chỉ có một nghiệm là 0 với )

có chứa phần tử khác 0 và nếu:

T

+

>

Dx

c

v

0,

∀ ∈ x

Sol P (

),

∀ ∈ v

(

)

{ } ) \ 0

Sol P ( 0

thì tập nghiệm

Sol P bị chặn.

)

(

Sol P ) 0(

Định lý 2.4 Tập nghiệm

2.2.2. Tính đóng của tập nghiệm )

Sol P của bài toán quy hoạch toàn phương là tập

(

đóng.

Chứng minh

=

=

Ta có:

trong đó,

= ∈ ∆ x

v P (

)

inf

f x

( ) :

x

Sol P (

)

:

f x ( )

v P (

{

} )

{

} ∈ ∆ .

v P là giá trị hữu hạn, mà ∆ là tập đóng, f là hàm liên tục nên

)

• Nếu (

Sol P là tập đóng.

)

(

• Nếu (

v P = −∞ thì hiển nhiên

)

Sol P = ∅ nên là tập đóng. 

(

)

• Nếu (

v P = +∞ thì ∆ = ∅ . Suy ra, ) Sol P = ∅ nên ) ( Sol P đóng. ) (

Nhận xét: Tập nghiệm cực tiểu địa phương (

loc P ) của bài toán quy hoạch

(

)

toàn phương có thể không đóng.

2

(P1)

2 x 2

= − + = ∈ ≥ ≥ f x ( ) min : x ( ) , 0,  x x 1 2 x x , 1 2 x 1 x 2

Ví dụ: Xét bài toán: {

} 0 .

=

=

>

=

. Rõ ràng,

Ta có:

)

= ∅ ;

)

x

(

) :

0,

{

} 0

Sol P ( 1

loc P ( 1

x x , 1 2

x 1

x 2

1(

đóng nhưng

Sol P là tập )

1(

loc P là tập không đóng. )

32

2.2.3. Tính hữu hạn của tập nghiệm

Định lý 2.5

i) Nếu D là ma trận xác định dương và ∆ khác rỗng thì (P) có nghiệm duy

=

nhất. Khi đó, tập

.

Sol P (

)

loc P (

)

ii) Nếu D là ma trận xác định âm thì mỗi nghiệm cực tiểu địa phương của (P)

(nếu có) là một điểm cực biên của ∆ . Trong trường hợp này,

⊂

⊂

∆ . Khi đó, số nghiệm của bài toán (P) luôn nhỏ hơn

Sol P (

)

loc P (

)

extr

số điểm cực biên của ∆ .

Sol P là tập lồi đóng. Hơn nữa,

)

(

iii) Nếu D là ma trận nửa xác định dương thì

Sol P là hữu hạn thì

)

(

Sol P là )

(

nếu D là ma trận nửa xác định dương và

tập rỗng hoặc

Sol P chỉ có một phần tử.

)

(

Chứng minh

i) Giả

sử D

trận đối xứng xác định dương và

n

n

khác rỗng. Đặt

.

{ ∆ = ∈

{ T v Dv v

} 1

là ma }

2

n

ξ≥

Suy ra:

T x Dx

x

,

x

0x ∈ ∆ , ta có:

∀ ∈  . Cố định

T

T

0

0

0

0

0

−

=

−

−

+

+

−

)

( ) f x

( f x

x

x

x

Dx

c

x

x

(

)

( D x

)

(

) (

)

0

0

20

≥

−

−

+

−

ξ

.

.

x

x

Dx

c

x

x

1 2 1 2

0

Rõ ràng, vế trái của bất đẳng thức trên dần đến +∞ khi

= ∈ = > x ≥ Ax b Cx d ξ = : inf : , v 0 : : ,  

0

x x− → +∞ . Do đó, tồn

. Suy ra, bài toán (P) không thể

tại

) ( 0 B x γ

− f x ( ) f x ( ) 1, ≥ ∀ ∈ ∆ x \ , 0γ > sao cho

. Mặt khác,

có nghiệm trong

) ( 0 B x γ

) ( 0, B x γ

∈ ∆ ∩

x

,

min

f x

( ) :

có nghiệm x . Vì (P) không thể có nghiệm trong

} ) ( 0 B x γ

∆ ∆ ∩ ≠ ∅ nên bài toán \ ,

nên x cũng là nghiệm của bài toán (P). Ta chứng minh tính duy nhất

{ ) ( 0 B x γ

của nghiệm, giả

sử bài

toán có hai nghiệm

,x y và

x

y≠ . Vì

∆ \ ,

33

T

+

−

Dx

c

y

x

nên theo định lý (2.4) ta có, (

) (

) 0 ≥ . Mà

T

−

−

> . Mặt khác:

y

x

0

x

y≠ và D là ma trận xác định dương nên (

( ) x D y

)

T

T

=

−

=

−

−

+

+

−

> (vô lý)

0

0

( ) f x

y

x

Dx

c

y

x

)

(

) (

)

(

( ) x D y

( f y

)

1 2

Vậy, bài toán (P) có duy nhất nghiệm.

∈

ii) Giả sử D là ma trận xác định âm và

. Ta chứng minh x là điểm

x

loc P (

)

≠

∆ . Khi đó, tồn tại

cực biên của ∆ . Giả sử trái lại, x

extr

x

∈ ∆ ∈ ∆ ≠ và ,

y

x

y

,

− ∈ ∈ y ( ), Sol P ( ) x T x x ∆

sao cho

,

và

t ∈

+ . Vì x ∈ ∆ ,

x

= − (1

t x )

ty

(

)0,1

1

t

∇

−

−

. Ta có:

f x x ( ),

x

≥ và 0

y

− = − x

x

x

(

)

− t

1

t

−

∇

−

= ∇

−

f x x ( ),

x

f x y ( ),

x

≥ 0

− t

∇

−

∈

Suy ra:

= , kết hợp với dữ kiện

ta được

f x x ( ),

x

0

x

loc P (

)

T

−

−

x

x

) 0 ≥

(

( ) x D x

∆ .

Điều này trái với giả thiết D là ma trận xác định âm. Do đó, x

extr∈

iii) Ta có, D là ma trận nửa xác định dương. Theo định lý 1.12 thì f là hàm

lồi. Suy ra,

Sol P là tập lồi đóng. Hiển nhiên, nếu

)

(

Sol P có hữu hạn phần tử thì

)

(

Sol P hoặc là tập rỗng hoặc là chỉ có một phần tử (do

)

(

Sol P là tập lồi đóng). 

(

)

− ∈ − ∈ x y x T x∆ ( ) x T x∆ ( )

Ví dụ: Xét bài toán QHTP

)

(

2 x 1

2 x 2

{

} ≤ 1

là ma trận xác định âm.

Ta có:

= − − + = min f x ( ) 1: x − ≤ , 1 ≤ − ≤ 1, 1 x x , 1 2 x 1 x 2

=

=

− −

−

=

∆

Sol P (

)

loc P (

)

extr

{ } − (1;1),(1; 1),( 1;1),( 1; 1)

D − 2 =  0   0 − 2 

2.2.4. Tính lồi đa diện của tập nghiệm Xét bài toán quy hoạch toàn phương:

(

)

2 x 1

2 x 2

{

} ≤ 1

= − − + = min f x ( ) 1: x − ≤ , 1 ≤ − ≤ 1, 1 x x , 1 2 x 1 x 2

34

=

=

− −

−

Ta có:

. Suy ra:

Sol P (

)

loc P (

)

Sol P không phải là

)

(

{ } − (1;1),(1; 1),( 1;1),( 1; 1)

tập lồi. Do đó,

Sol P cũng không phải là tập lồi đa diện.

(

)

Nhận xét: Tập nghiệm của bài toán quy hoạch toàn phương có thể không

phải là tập lồi đa diện.

2.2.5. Tính chất của tập

Sol P ∩ ∆ )

int

(

2

=

Ví dụ 1: Xét bài toán QHTP

. Ta có,

{

} 1

min f x ( ) x : x ∈ − ≤ ≤ , 1 x 

và Q là ma trận xác định dương. Do đó, bài toán là Quy hoạch

toàn phương lồi. Mặt khác, ta tìm được

x = là một nghiệm của bài toán. Mà

0

x = 0

là một điểm trong của ∆ . Nên

Sol P ∩ ∆ ≠ ∅ . int

)

(

= α Q [1], c=0, =0

Ví dụ 2: Xét bài toán QHTP

(

)

2 x 1

2 x 2

{

} 1

= + = ≤ min f x ( ) : x − ≤ , 1 ≤ − ≤ 1, 1 x x , 1 2 x 1 x 2

Ta có:

. Suy ra, Q là ma trận xác định dương. Bài toán là

là nghiệm của bài toán và

Quy hoạch toàn phương lồi. Mặt khác,

(0;0)

* x =

* x ∈ ∆ . Nên

int

Sol P ∩ ∆ ≠ ∅ . int

(

)

= = α = Q , c 0, 0 2 0 0 2      

Nhận xét: Tập

Sol P ∩ ∆ có thể khác rỗng. Hơn nữa, nghiệm của bài

int

(

)

toán Quy hoạch toàn phương lồi có thể là điểm trong của tập ràng buộc ∆ .

35

Chương 3: PHƯƠNG PHÁP GIẢI BÀI TOÁN QUY HOẠCH TOÀN PHƯƠNG

3.1. Điều kiện Kuhn-Tucker

Xét bài toán:

f x min ( ) ≤

=

v d k g x . ( )

.

1,...,

m

i

=

≥

b i , i 0,

j

1,...,

n .

x

j

Để tìm điều kiện Kuhn-Tucker trước tiên ta chuyển các bất đẳng thức trong

hệ ràng buộc về dạng đẳng thức bằng cách cộng vào các biến bù

2 s i

20, t≥ j

đó ta được hệ:

+

=

=

v d k g x . ( )

.

1,...,

m

f x min ( ) 2 s i

b i , i

+

=

=

i −

x

t

0,

j

1,...,

n .

j

2 j

≥ . Khi 0

Đặt

. Lập hàm Lagrangian cho bài toán trên:

(

)

(

)

m

n

n

m

=

−

−

−

−

−

,

,

ˆ , , L x a s a t

( ) f x

t



(

)

( ) g x i

2 s i

j

2 j

( ˆ a b i i

( a x  j

)

)

∑

∑

= 1

= 1

j

i

= = s ,..., s , t ,..., t s 1 t 1

.

trong đó,

(

)

(

)

m

m

∇

=

. Do đó, ta tìm

ˆ, L x a s a t , ,

,

0

Điều kiện tối ưu bậc nhất của hàm L là:



(

)

ta được:

các đạo hàm riêng của hàm L theo các biến

ˆ, x a s a t , , ,

m

=

+

−

=

=

0,

1,...,

j

n

a 

ˆ a i

j

∑

∂ ( ) f x ∂ x

∂ ( ) g x i ∂ x

∂ L ∂ x

i

= 1

j

j

= −

−

−

=

=

0,

1,...,

i

m

b i

( ) g x i

2 s i

(

)

= −

=

=

0,

i

1,...,

m

ˆ2 a s i i

∂ L ∂ ˆ a ∂ L ∂ s

= ,..., , ,..., ˆ a ˆ a = a a  ˆ a 1 a  1

36

= −

−

=

=

x

t

j

n

0,

1,...,

j

2 j

(

)

= −

=

=

j

n

2

0,

1,...,

a t  j

j

(

)

∂ L ∂ a  ∂ L ∂ t

Từ phương trình thứ 3, suy ra ˆ

ia s = . Từ phương trình thứ 2, ta có: nếu

i

0

ia > thì ˆ 0

is = và 0

ia = thì ta có thể chọn

i

is ≥ suy ra

b= . Nếu ˆ 0 0 g x ( ) i

)

( ˆ a b i i

i

. Từ phương trình thứ 4, ta có: nếu

Từ phương trình thứ 5, suy ra

− = và 0 b≤ . Do đó, ta có thể viết thành điều kiện g x ( ) i g x ( ) i g x ( ) i b≤ . i

ja t = 

j

thì

thì ta có thể chọn

0

0

0

jt = và 0

jx ≥ . Do 0

ja >

jx = . Nếu 0

ja =

jt ≥ suy ra

đó, ta có thể viết thành điều kiện

và

0

ja x = 

j

jx ≥ . 0

Khi đó, điều kiện Kuhn-Tucker của bài toán min đã cho được phát biểu

dưới dạng như sau:

m

+

−

=

=

0,

1,...,

j

n

a 

ˆ a i

j

∑

∂ ( ) f x ∂ x

∂ ( ) g x i ∂ x

= 1

i

j

j

−

=

=

0,

1,...,

i

m

( ˆ a b i i

≤

=

,

1,...,

i

m

=

=

b i 0,

1,...,

j

n

j

≥

0.

) ( ) g x i ( ) g x i a x  j ˆ, , x a a 

Xét bài toán quy hoạch toàn phương:

+

T x Qx

T c x

= ≤

f x min ( ) v d k Ax b .

.

≥

x

0

n

m

× m n

∈

∈

∈

trong đó,

× m n Q

,

c

b

A

,

,

∈  là ma trận đối





 là ma trận cấp

× n n S

xứng cấp n n× .

Áp dụng điều kiện Kuhn-Tucker cho bài toán quy hoạch toàn phương trên ta

được:

0

T

+ ˆ c

T − = − Qx A a a 2  ) (

= − ˆ a b Ax 0

37

= ≥

0 0

≤ Ax b T a x  ˆ, x a a , 

Cộng biến bù y vào bất phương trình Ax b≤ ta được hệ sau:

+

ˆ

c

T − = − Qx A a a 2  + = y

Ax

b

=

(3.1)

0

=

0

≥

,

0.

T a x  T ˆ a y ˆ x y a a , , 

Ta có thể biểu diễn hệ trên bởi ma trận dạng khối như sau:

× n n

× n m

× n n

(3.2)

T A × n m 0

× m n

× m m

× m m

× m n

− − . c b 2 Q A 0 I I 0            

  x   y   =   ˆ a   a  

ˆ

và

.

trong đó

0

T a y

x y a a ≥ , , , 

T a x 

= = ˆ0, 0

3.2. Thuật toán giải quy hoạch toàn phương lồi

Xét bài toán quy hoạch toàn phương:

=

+

f x min ( )

T x Qx

T c x

≤

(3.3)

v d k Ax b .

.

≥

x

0

n

m

× m n

trong đó,

× m n Q

,

∈  là ma trận đối

× n n S

xứng cấp n n× .

Nếu Q là ma trận nửa xác định dương thì theo định lý 1.12 ta có f là hàm

lồi. Do đó, quy hoạch toàn phương đang xét là quy hoạch lồi hay còn gọi là quy

hoạch toàn phương lồi.

Trong phần 3.1 ta đã thiết lập được điều kiện Kuhn-Tucker cho bài toán quy

hoạch toàn phương (3.3):

∈ ∈ ∈ c b A , ,    là ma trận cấp

38

+

ˆ

c

(3.4)

Ax

b

,

0.

T − = − Qx A a a 2  + = y ≥ ˆ x y a a , , 

và

=

0

(3.5)

=

T a x  T ˆ a y

0

Đây là điều kiện cần để bài toán có nghiệm nhưng nếu f là hàm lồi thì bất

kỳ điểm

*x thỏa điều kiện Kuhn-Tucker cũng là nghiệm cực tiểu toàn cục của bài

toán hay

*x là nghiệm của bài toán.

Xét điều kiện Kuhn-Tucker ta thấy, điều kiện (3.4) là tuyến tính, điều kiện

(3.5) là phi tuyến. Do đó, ta có thể sử dụng các thuật toán giải quy hoạch tuyến tính

mở rộng cho quy hoạch toàn phương. Vì vậy, điều kiện Kuhn-Tucker là rất quan

trọng trong việc giải bài toán quy hoạch toàn phương và nó còn là cơ sở cho các

thuật toán giải quy hoạch toàn phương.

3.2.1. Thuật toán Wolfe

Xét bài toán quy hoạch toàn phương lồi (3.3) ( Q là ma trận nửa xác định

dương). Như ta đã biết, nếu f là hàm lồi thì bất kỳ điểm nào thỏa mãn điều kiện

Kuhn-Tucker cũng là nghiệm của bài toán. Để tìm điểm thỏa điều kiện Kuhn-

Tucker, P.Wolfe đề nghị cải tiến pha 1 của thuật toán đơn hình hai pha. Về bản

chất, cộng các biến giả vào tất cả các ràng buộc tuyến tính và thử tìm min của tổng

các biến giả. Để đảm bảo nghiệm cuối cùng thỏa mãn điều kiện phi tuyến

=

=

, Wolfe mở rộng phương pháp đơn hình theo hướng như sau:

ˆ0,

T a y

0

T a x 

• Khi thực hiện phép xoay không được cho các biến

pa và

px cùng trong một

cơ sở.

• Tương tự, các biến ˆ pa và

py không được ở trong cùng một cơ sở.

Thuật toán Wolfe được trình bày dưới hai hình thức: dạng ngắn và

dạng dài. Thuật toán Wolfe dạng ngắn đòi hỏi có điều kiện hoặc là

0

c = hoặc là Q

39

là ma trận xác định dương, trong khi thuật toán viết dưới dạng dài không yêu cầu

các điều kiện đó.

3.2.1.1. Thuật toán Wolfe dạng ngắn Để có nghiệm chấp nhận được ban đầu ta cộng vào các ràng buộc tuyến tính

(3.4),

biến giả:

n+ 2m

T

=

s

,...,

s

)

m

s 1

T

=

1 w

,...,

1 w n

T

2

=

w

,...,

2 w 1

2 w n

( ( 1 w 1 (

) )

Khi đó, hệ (3.4) được viết dưới dạng:

T

1

2

+ − = − ˆ Qx A a a w w 2 c − + 

(3.6)

1

2

+ + = Ax y s b

Ta cũng có thể viết dưới dạng ma trận khối như sau:

−

−

−

× n n

× n m

× n n

× n n

× n n

× n m

=

(3.7)

c b

T A × n m 0

I 0

I 0

I 0

2 Q A

0 I

0 I

  

  

× m n

× m m

× m m

× m n

× m n

× m n

× m m

  

x y ˆ a a  1 w

2

w

s

      .        

          

2

ˆ

.

trong đó,

,

,

,

,

0

1 x y a a w w s ≥ , ,



Một nghiệm chấp nhận được của bài toán (3.7) thỏa điều kiện (3.5) có thể

=

=

=

=

chứa m n+ biến có giá trị bằng 0:

x

ˆ0, a

0,

0,

y

0

và với mỗi j thì ít nhất

a 

một trong hai biến

≥ ˆ x y a a s w w , , , , , , 0. 

1 ,j

2 j

w w là bằng 0. Khi đó, trong cơ sở đầu chứa các biến

và với mỗi j ta chọn một trong hai biến

1 ,j

2 j

cách sau:

2

= = w w vào cơ sở theo 1,..., m s i b i , i

0

• Nếu

1 w j

j

jw = .

jc < thì chọn

c= − vào cơ sở, khi đó 0

40

1

vào cơ sở, khi đó

0

• Nếu

2 j

j

jw = .

jc > thì chọn

0

• Nếu

jc = thì có thể chọn bất kỳ một trong hai biến vào cơ sở.

Ta có bảng đơn hình xuất phát (được cho ở bảng sau). Trong đó,

=

= + ,

. Cột đầu tiên của bảng cho ta hệ số của biến cơ sở. Cột

M n m

N

+ n m 3 3

thứ hai cho ta biết biến cơ sở hiện tại. Cột thứ ba cho ta giá trị của biến cơ sở. Cột

+

+

+

cho ta các biến thực. Cột

cho ta biết

j

n

m

N

α = ,

j

1,..., 2

n

2

m

α = ,

2

2

1,...,

j

j

các biến giả và

. Các

t ∈

}1;2 {

ijα là hệ số các biến tương ứng. z trong hàng cuối

M

M

w c= 0

và

, trong đó

được tính bởi

1

jc = ứng với các

j

j

j

i

B i

∑

i

= 1

i

= 1

biến giả và bằng 0 đối với các biến khác.

− = z z c c − cα ij c x B B i = ∑

41

42

Sau đó tiến hành thuật toán đơn hình hai pha mở rộng (thuật toán

Wolfe) như sau:

• Pha 1 của thuật toán Wolfe dạng ngắn là tìm nghiệm tối ưu của bài toán

m

với miền ràng buộc (3.6) và ˆ

B i

∑

i

= 1

0

a a sẽ không được chọn vào cơ sở.

a =

. Do đó, ˆ ,i

j

m

Kết thúc pha 1, ta tìm được nghiệm cơ sở thỏa mãn

. Khi đó, các cột

= = ∀ = f s min ( ) , 1, i 1,..., m a = , 0 c s c B i i

i

= 1

0 =∑ s i

t j

T

1

2

=

sao cho

w

)

(

w 1,...,

w n

jw hoặc là

jw , việc chọn phụ thuộc vào

jw hoặc là

các biến cơ sở cuối cùng của pha 1. Đặt E là ma trận hệ số của vectơ

,w E là

ma trận đường chéo với các phần tử chéo là +1 hoặc –1 phụ thuộc vào

hoặc

. Vậy, kết thúc pha 1 ta tìm được nghiệm cơ sở chấp

, s w không nằm trong cơ sở ta có thể di chuyển ra khỏi bảng. Đặt i

j

1 w= j

j

2 j

nhận được của hệ:

T

+

= −

ˆ Qx A a a Ew 2

c

− +  + + =

(3.8)

y

b

Ax ≥

s = = ˆ a

x y s w , ,

,

0,

0.

a 

thỏa điều kiện phi tuyến (3.5). Kết thúc pha 1, ta chuyển sang pha 2.

• Pha 2 của thuật toán Wolfe dạng ngắn là tìm nghiệm tối ưu của bài toán

n

=

= ∀ =

với miền ràng buộc (3.8) thỏa điều

min (

,

1,

1,...,

) f w

j

n

c w c B j

B

j

j

∑

= 1

j

kiện (3.5). Sau đó tiến hành thuật toán đơn hình với nhận xét:

 Khi thực hiện phép xoay không được cho các biến

pa và

px cùng

trong một cơ sở.

 Tương tự, các biến ˆ pa và

py không được ở trong cùng một cơ sở.

n

Kết thúc pha 2, ta tìm được nghiệm cực tiểu của bài toán sao cho

.

0

j

=∑ w

j

= 1

Khi đó, nghiệm của (3.8) với

0w = vừa mới tìm cũng là nghiệm của (3.4),

w w w=

43

(3.5) và nó cũng là nghiệm của bài toán quy hoạch toàn phương ban đầu

(3.3).

Nếu ta không xét điều kiện

0

c = hoặc Q là ma trận xác định dương thì bài toán tìm

n

nghiệm tối ưu trong pha 2 có thể không tìm được vì

. Định lý sau đây cho

j

j

= 1

ta kết quả nếu

0

c = hoặc Q là ma trận xác định dương thì có thể tìm được nghiệm

n

tối ưu của bài toán trong pha 2 thỏa

.

0

j

=∑ w

j

= 1

Cho Bx là những biến trong cơ sở, nghiệm nhận được cuối cùng của pha 2 là

0 >∑ w

trong đó

là

(

)

N

Nx = . Đặt Ba là những thành phần bằng 0 trong a và Na

=

+

=

và

. Gọi

0

= x 0 x x ,B

những thành phần dương của a . Ta có,

T x a 

(

)

N

T x a  B B

T x a  N N

= a a a ,B  

,q d là n-vectơ hằng và R là ma trận cấp n n× . Khi đó ta có định lý

sau:

k là n-vectơ,

Định lý 3.1 Giả sử k là nghiệm của bài toán quy hoạch tuyến tính min Tq k

với miền ràng buộc:

T

+ = d ˆ Qx A a a Rk 2 − + 

= b Ax

N

=

=

=

.

Khi đó, tồn tại r là n-vectơ sao cho

0, Ar

Qr

0, T q k

T d r

≥ = ˆ x a a k w , , , , 0, 0.  a x ,  B

Chứng minh. Xem [6], trang 22-26.

Áp dụng định lý (3.1) cho hệ (3.8) của pha 2 với:

=

q

= k w ( ) T 1,...,1 = − = R E d

,

c .

Ta có nghiệm cuối cùng của pha 2 thỏa mãn các giả thiết của định lý (3.1), suy ra

T c r

tồn tại r n-vectơ với

. Do đó, nếu Q là ma trận xác định

j

= = − w Qr 0, min

dương thì

. Nếu

.

T c r

c = thì min

0

jw

j

∑ =∑ w

∑

= − = Qr = ⇒ = ⇒ r 0 min 0 0 0

44

3.2.1.2. Thuật toán Wolfe dạng dài Thuật toán Wolfe dạng dài bao gồm ba pha, hai pha đầu tương ứng với hai

pha của dạng ngắn. Vì vậy, dạng dài bắt đầu bằng cách áp dụng dạng ngắn với c

được thay thế bởi vectơ 0 và phương trình:

T

1

2

+

−

= −

ˆ

Qx A a a w w 2

c

− + 

được thay thế bởi

T

1

2

Bây giờ ta bắt đầu tiến hành pha 1, pha 2 giống như trong dạng ngắn. Kết

thúc của pha 2, biến w sẽ bị di chuyển ra khỏi bảng. Vậy, ta có nghiệm cơ sở của

hệ:

T

+

=

ˆ Qx A a a vc 2

(3.9)

0 b

ˆ

,

0.

− +  + = Ax y ≥ x y a a v , , , 

với

0

v = . Do đó, để tiện cho việc tính toán ta đưa biến v vào trước khi thực hiện

pha 1. Nghĩa là, hệ phương trình:

1

2

T

+

−

= −

ˆ

2 Qx A a a w w

c

− + 

được thay bởi hệ

1

2

T

− + = ˆ Qx A a a w w 2 0 − + 

Sau đó tiến hành pha 1, với chú ý rằng biến v không vào cơ sở trong suốt 2 pha

đầu, tức là

v = . Sau khi kết thúc pha 2, ta có nghiệm của hệ (3.9) với

0

v = thỏa 0

mãn (3.5). Để có được nghiệm của (3.4) thì v phải bằng 1 và (3.5) được thỏa mãn.

Để đạt được điều này, pha 3 của thuật toán Wolfe dạng dài áp dụng thuật toán đơn

hình tìm nghiệm tối ưu của bài toán: min v− với miền ràng buộc (3.9) và điều kiện

(3.5). Có hai trường hợp xảy ra:

v− không bị chặn dưới.

•

• Giá trị tối ưu của bài toán min v− là hữu hạn.

− + + = ˆ 0 − + Qx A a a w w vc 2 

45

Nếu trường hợp 2 xảy ra, tức giá trị tối ưu của bài toán là hữu hạn thì áp

dụng định lý (3.1) cho dạng dài với

0w = trong suốt pha 3, với

1n = . Ta có:

= −

= . Khi đó, theo định lý (3.1) ta có:

k

v q= ,

= − , 1

Tq k

= v R c d ,

,

0

=

− = v

T q k

T d r

min

= . 0

Suy ra: không có bước lặp đơn hình nào có thể thỏa mãn điều kiện (3.5). Trong

trường hợp hàm mục tiêu không bị chặn dưới và bài toán không có nghiệm.

j

j

j

j x a a v ,

Nếu trường hợp 1 xảy ra, nghĩa là v− không bị chặn dưới, thì do số biến cơ )

sở là hữu hạn nên dãy nghiệm cơ sở nhận được ở pha 3 là hữu hạn (

1

=

ˆ , , 

nhận được ở bảng đơn hình đầu tiên ở pha 3,

với

1 1 1 x a a v ,

j

1,...,

g

. Nghiệm (

)

ˆ , , 

trong đó tất cả

với

1 v

1 x

(

)

ix trong cơ sở có giá trị được giữ trên

1

. Nghiệm

1ˆ,a a

2

2

= = 0, ,..., x 1 x n

trong bảng đơn hình thứ hai cũng được xác định tương tự. Cứ tiếp

2 2 x a a v ,

bảng, các giá trị còn lại bằng 0. Áp dụng tương tự cho (

)

2

g

2

g

=

<

với

tục quá trình trên, sau hữu hạn bước ta có

0

1 v

v

< < ...

v

1 x x ,

ˆ , , 

nghiệm cơ sở.

Nghiệm nhận được với

1v = được kết hợp tuyến tính bởi hai nghiệm. Có hai

trường hợp sau:

j

1

j

. Ta có:

gv ≥ thì chọn chỉ số

v

< ≤ 1

v +

1

,1

≤ ≤ − sao cho 1

j

g

j

• Nếu

j

+ 1

j

j

j

+ 1

=

+

.

x

x

x

+ 1

− 1 + 1 j

j

v −

v j v

− 1 j − v

v

v

gv < thì 1

• Nếu

g

− 1

g

− 1

g

,..., x là

.

( + − 1

)

= x x v x

3.2.2. Ví dụ minh họa

Giả bài toán quy hoạch toàn phương sau:

46

+

−

−

=

+

4

6

3

f x min ( )

2 x 2

x x 1 2

x 1

x 2

3 ≤

1 ≤

4

2 x 2 1 + x 2 + x 3 2 ≥ 0.

v d k x . . 1 x 2 1 x x , 1 2

Giải

Ta có:

2 x 2

+ − − = + 4 6 3 f x min ( ) x x 1 2 x 1 x 2

3 ≤

2 x 2 1 + x 2 + x 3 2 ≥ 0.

1 ≤ 4

v d k x . . 1 x 2 1 x x , 1 2

Suy ra:

Do đó, Q là ma trận nửa xác định dương. Ta cộng các biến bù

= = = = c , 2 Q , A , b 4 4 4 6 1 1 2 3 − 6  − 3                  1   4  

2

ràng buộc. Khi đó, miền ràng buộc có thể được viết dưới dạng:

+

+

=

1

x 2

y 1

x 1 +

+

=

2

y

3

4

≥

,

,

0.

x x 1 2 2 x x y y , 1 2

1

2

Điều kiện Kuhn-Tucker cho bài toán được phát biểu dưới dạng:

+

ˆ

c

Ax

b

≥

,

0.

T − = − Qx A a a 2  + = y ˆ x y a a , , 

và

=

0

=

T a x  T ˆ a y

0

Để có được nghiệm cơ sở chấp nhận được ta cộng vào các điều kiện tuyến

tính các biến giả:

,y y vào các 1

47

T

=

s

(

)

2

T

=

1 w

T

2

=

w

2 2 , w w 1 2

, s s 1 ( 1 1 , w w 1 2 (

) )

và viết chúng dưới dạng ma trận như sau:

= . .

4 4 0 0 1 2 4 6 0 0 1 3 1 1 1 0 0 0 2 3 0 1 0 0 − 1 0 0 0 1 0 0 − 1 0 1 0 0 0 0 0 0 − 1 0 0 0 0 0 0 − 1 0 0 1 0 0 0 1 0 − 6 − 3 0 0               0   0     1   4  

Áp dụng thuật toán đơn hình hai pha mở rộng (thuật toán Wolfe dạng dài).

Ta có, bảng đơn hình xuất phát như sau:

B.V

v

Bx

1x

2x

1y

2y

1ˆa

2ˆa

1a

2a

1s

2s

2 1w

2 2w

Coeff. B.V.

0

0

4

4

0

0

1

2

-1

0

-1

0

0

0

-6

0

6

0

0

1

3

0

-1

0

-1

0

0

-3

0

4

1

1

1

1

0

0

0

0

0

0

0

1

0

0

1

4

2

3

0

1

0

0

0

0

0

0

0

1

0

1

5

3

4

1

1

0

0

0

0

0

0

1 1w 1 2w 1s 2s jz

x 1 x 2 y 1 y 2 ˆ a 1 ˆ a 2 a  1 a  2 1 w 1 1 w 2 2 w 1 2 w 2 s 1 s 2 v                                                

48

2

Trong pha 1 ta xét hàm mục tiêu

i

= 1

1

có được

2w là biến ra khỏi cơ sở. Sau đó thực hiện phép

2x là biến vào cơ sở và

không được vào cơ sở

xoay, ta được bảng đơn hình tiếp theo. Chú ý, các biến ˆ,

f s ( ) s i = ∑ . Từ bảng đơn hình đầu tiên ta

trong suốt pha 1. Sau 3 bước lặp sẽ kết thúc pha 1.

B.V

v

Bx

1x

2x

1y

2y

1ˆa

2ˆa

1a

2a

1s

2s

2 1w

2 2w

Coeff. B.V.

0

0

0

0

-1

-1

0

0

-4

0

0

1 1w

4 3

1 3

2 3

2 3

1

0

0

0

0

0

0

0

0

2x

1 6

2 3

1 − 6

1 − 6

1 2

1 − 2

0

0

1

0

1

1

0

1

0

1s

1 6

1 6

1 3

1 − 6

1 − 2

1 2

4

0

0

0

1

1

0

0

0

1

2s

1 − 2

3 − 2

1 2

1 2

3 2

5

0

1

1

0

0

jz

1 3

2 3

Tiếp đến

1y là biến vào cơ sở và 1s là biến ra khỏi cơ sở.

B.V

v

Bx

1x

2x

1y

2y

1ˆa

2ˆa

1a

2a

1s

2s

2 1w

2 2w

Coeff. B.V.

0

0

0

0

-1

-1

0

0

-4

0

0

1 1w

4 3

1 3

2 3

2 3

0

0

0

1

0

0

0

0

0

2x

1 6

2 3

1 − 6

1 − 6

1 2

1 − 2

0

1

0

0

1

0

1

0

0

1y

1 6

1 6

1 3

1 − 6

1 − 2

1 2

4

0

0

0

1

1

0

0

0

1

2s

1 − 2

3 − 2

1 2

1 2

3 2

4

0

0

0

0

1

jz

1 2

Sau bước này

2y là biến vào và 2s là biến ra khỏi cơ sở.

,a a v

49

B.V

v

Bx

1x

2x

1y

2y

1ˆa

2ˆa

1a

2a

1s

2s

2 1w

2 2w

Coeff. B.V.

0

0

0

0

-1

-1

0

0

-4

0

0

1 1w

1 3

4 3

2 3

2 3

1

0

0

0

0

0

0

0

0

2x

2 3

1 − 6

1 − 6

1 6

1 2

1 − 2

0

1

0

0

1

0

1

0

0

1y

1 3

1 − 6

1 6

1 6

1 − 2

1 2

4

0

0

0

1

0

0

0

0

1

2y

1 − 2

3 − 2

1 2

1 2

3 2

jz

Vì tất cả các

is đều rời khỏi cơ sở nên pha 1 kết thúc. Để tiến hành pha 2, ta

=

=

đặt

. Dựa vào bảng đơn hình cuối của pha 1, ta viết bảng đơn hình xuất

1 w w w 1 1

phát ở pha 2, với hàm mục tiêu đang xét là

.

B.V

v

Bx

1x

2x

1y

2y

1ˆa

2ˆa

1a

2a

Coeff. B.V.

0

0

0

0

-1

0

-4

1

1w

4 3

1 3

2 3

0

1

0

0

0

0

2x

2 3

1 6

1 − 6

1 − 2

1 2

1

0

1

0

0

0

1y

1 3

1 6

1 − 6

1 − 2

1 2

4

0

0

0

1

0

0

2y

1 − 2

3 − 2

3 2

1 2

0

-1

jz

4 3

=

=

Trong pha 2, ta chọn các biến vào cơ sở phải thỏa điều kiện

.

0,

T ˆ y a

0

T x a 

Do đó, ta chọn 1x là biến vào và

1w là biến ra khỏi cơ sở. Khi đó, ta có bảng đơn

hình sau:

f w ( ) w= 1

50

B.V

v

Bx

1x

2x

1y

2y

1ˆa

2ˆa

1a

2a

Coeff. B.V.

0

1

0

0

0

0

0

-3

1x

1 4

3 − 4

1 2

0

0

1

0

0

0

0

2x

1 2

1 2

1 − 2

3 2

1

0

0

1

0

0

0

1y

1 − 4

1 − 2

1 4

3 2

4

0

0

0

1

0

0

2y

1 − 2

3 − 2

1 2

3 2

jz

Vì biến

1w đã rời khỏi cơ sở nên pha 2 đã hoàn thành. Ta tiếp tục thực hiện

pha 3 với hàm mục tiêu là: min v− . Dựa vào bảng đơn hình cuối của pha 2, ta chọn

v là biến vào và

2x là biến ra, áp dụng thuật toán đơn hình ta được:

B.V

v

Bx

1x

2x

1y

2y

1ˆa

2ˆa

1a

2a

Coeff. B.V.

0

1

2

0

0

0

1

0

1x

1 4

1 4

1 − 2

0

0

0

0

0

1

-1

v

1 3

1 3

2 3

1 − 3

1

0

-1

1

0

0

-1

0

1y

1 2

1 − 4

1 − 4

4

0

-1

0

1

0

-2

1

0

2y

1 − 2

1 − 2

0

jz

1 3

Ta tiếp tục chọn

2a là biến vào và

1y là biến ra khỏi cơ sở.

51

B.V

v

Bx

1x

2x

1y

2y

1ˆa

2ˆa

1a

2a

Coeff. B.V.

1

1

1

1

0

0

0

0

0

0

0

1x

0

0

0

0

1

-1

v

1 − 6

1 − 3

1 6

2 3

2 3

2

0

-2

2

0

0

-2

1

0

2a

1 − 2

1 − 2

2

0

1

-2

1

0

0

0

0

0

0

2y

jz

1 6

2 − 3

Từ bảng đơn hình trên, suy ra thuật toán kết thúc với

gv =

nghiệm của bài toán có dạng:

g

− 1

g

g

− 1

< . Do đó, 1 2 3

(

)

( + − 1 + −

= = x x v x x x , 1 2

) (1 0).(1;0)

= (0;0)

= (1;0).

Suy ra: 1 x

tiêu tối ưu được tính bởi:

= là một nghiệm tối ưu của bài toán. Khi đó, giá trị mục 0 x= 21;

2 x 1

2 x 2

2

= + + − − f x ( ) 2 3 4 6 3 x x 1 2 x 1 x 2

+ + − − 3.0 4.1.0 6.1 3.0

2 2.1 4.

= = −

52

Kết Luận

Luận văn trình bày lại một số kết quả của bài toán Quy hoạch toàn phương

thông qua việc nghiên cứu các tài liệu [3], [5], [6]:

• Điều kiện tồn tại nghiệm của bài toán Quy hoạch toàn phương.

• Một số tính chất định tính của tập nghiệm của bài toán Quy hoạch toàn

phương: tính bị chặn, tính đóng, tính hữu hạn, tính lồi đa diện, tính chất tập

• Phương pháp giải bài toán Quy hoạch toàn phương lồi.

Đồng thời luận văn cũng đưa ra được một số ví dụ minh họa để làm rõ vấn

đề hơn. Nhân đây tôi cũng xin chân thành gửi lời cảm ơn đến các tác giả của các tài

liệu tham khảo đã cung cấp tài liệu quý để giúp tôi có thể hoàn thành luận văn này.

Sol P ∩ ∆ . int ) (

53

Tài Liệu Tham Khảo

[1]. Phan Quốc Khánh, Trần Huệ Nương (2003), Quy hoạch tuyến tính, NXB Giáo

dục.

[2]. Nguyễn Thị Bạch Kim (2008), Các phương pháp tối ưu – Lý thuyết và thuật

toán, NXB Bách khoa Hà Nội.

[3]. Gue Myung Lee, Nguyen Nang Tam, Nguyen Dong Yen (2005), Quadratic

programming and affine variational inequalities, Springer.

[4]. Hoang Tuy (1998), Convex analysis and global optimization, Kluwer.

[5]. Martina Vankova (2004), Algorithms for the solution of the quadratic

programming problem, University of Port Elizabeth.

[6]. Philip Wolfe (1959), The simplex method for quadratic programming.