B ộ■ GIÁO DỤC
* VÀ ĐÀO TẠO
•
TRƯỜNG ĐẠI
HỌC
s
ư
PHẠM
HÀ
NỘI
•
•
•
• 2
= = = 8 dBŨIg8 ===

BÙI THỊ BÍCH PHƯƠNG

CÁC ĐIÈU KIỆN TỐI ƯU TRONG BÀI TOÁN
QUY HOẠCH HAI CẤP TUYỂN TÍNH
Chuyên ngành: Toán Giải tích
Mã số: 60 46 01 02

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

Người hướng dẫn khoa học: PGS. TS. NGUYỄN QUANG HUY


Hà Nội, ngày 16 tháng 07 năm 2015
Tác giả

Bùi Thị Bích Phương


B Ả N G K Ý H IỆ U

R

tập số thực

Rn

không gian Euclide n — chiều

0

tập rỗng

I

x

\

giá trị tuyệt đối của i ễ K "

grphF


convíỉ

bao lồi của

(x,y)

tích vô hướng của X và y

d f(x )

dưới vi phân giới hạn
(dưới vi phân Mordukhovich) của / tại X

v/(z)

g r a d ie n t c ủ a / t ạ i X

rgA

hạng của ma trận A

E

ma trận đơn vị có số chiều tương ứng

ep = ( 1 , ••• , 1 )T e

vectơ p chiều có các tọa độ bằng một
t ậ p n g h iệ m c ủ a b à i t o á n c ấ p d ư ớ i tu y ế n tín h

1.1

Mồ hình và ví dụ

3

1 .2

Tính chất hình học của quy hoạch hai cấp tuyến tính

7

2

3

S ự tồ n tạ i n gh iệm tro n g tố i ưu h ai cấp tu y ến tín h

12

2 .1

Sư tồn tai n gh iêm ..................................................................

12

2 .2

Mối liên hệ với các bài toán quy hoạch toán học khác


3.2.1

Trường hợp optimistic

31

3.2.2

Trường hợp pessimistic

34

K ế t lu ận

40
iv


T à i liệu th a m khảo


1

MỞ ĐẦU
1. Lý do chọn đề tài
Bài toán quy hoạch hai cấp được phát biểu lần đầu tiên bởi H. V.
Stackelberg năm 1934 trong cuốn chuyên khảo về kinh tế thị trường. Một
dạng đặc biệt của các bài toán quy hoạch hai cấp là trò chơi Stackelberg
đã được xem xét nhiều trong lý thuyết trò chơi kinh tế. Các bài toán
quy hoạch hai cấp được giới thiệu tới cộng đồng tối ưu hóa trong những

tại nghiệm và các điều kiện tối ưu.

5. Phương pháp nghiên cứu
Sử dụng các phương pháp nghiên cứu trong đại số tuyến tính, giải
tích đa trị, giải tích lồi và lý thuyết tối ưu.

6. Đ óng góp củ a luận văn
Trình bày tổng quan về lý thuyết quy hoạch hai cấp tuyến tính, sự
tồn tại nghiệm, mối quan hệ giữa bài toán quy hoạch hai cấp tuyến tính
và các bài toán quy hoạch toán học khác, điều kiện cần và đủ tối ưu
trong các bài toán quy hoạch hai cấp tuyến tính.


3

Chương 1

B ài toán tối líu hai cấp
tuyến tính
Trong chương này ta sẽ trình bày mô hình, ví dụ và tính chất hình
học của bài toán tối ưu hai cấp tuyến tính.

1.1

M ô hình và ví dụ
Bài toán tối ưu hai cấp tổng quát là một bài toán tối ưu trong đó

g ồ m h a i b iế n X v à y v ớ i X đ ư ợ c c h ọ n là m ộ t n g h iệ m c ủ a b à i t o á n th ứ

hai chứa tham số y. Do đó đây là bài toán có cấp bậc theo ý nghĩa các


h : Mn X R m

h (X, у) = (/li (X, y ) , . . . , h q (X, y))T ,

có tập nghiệm kí hiệu là ф(у) với cố định у e Mn và Ф được gọi là ánh
xạ đa trị từ R m vào

kí hiệu là Ф : Mm —> 2 к",ф (у) = ffo/fll.ip =


4
A rgm in{/ (a:, y) : g (x, y ) < 0 , h (x, y) = 0}
X

= {x

y G Mm,

a G

J41 G Mpxn,

€ Mpxm,

c G Mn.

Chú ý rằng sự mô tả của bài toán tối ưu tuyến tính phụ thuộc tham số
ở trên không thực sự hạn chế trong trường hợp tổng quát miễn là chúng
ta chỉ nhiễu tuyến tính vế phải. Trường hợp hàm mục tiêu của bài toán
cấp dưới phụ thuộc tham số cũng như trường hợp khi cả vế phải và hàm
mục tiêu là nhiễu tuyến tính có thể giải quyết bằng cách tương tự. Kí
hiệu
{y) — Argmin {
: A l x < a — A2y, X > o}

X

là tập các nghiệm tối ưu của bài toán (1.3). Khi đó, bài toán quy hoạch
h ai cấ p có d ạn g :

m in {


—X : X

+ y


8

, 2x + y < 13} .

X

Tập tất cả các cặp (x,y) thỏa mãn các ràng buộc cả cấp trên và
cấp dưới kí hiệu là M , tương tự các hướng cực tiểu của hàm mục tiêu
của cả các bài toán cấp trên và cấp dưới kí hiệu bởi các mũi tên và được
minh họa trong Hình Ịl.lỊ
Tập chấp nhận được của bài toán cấp dưới với mỗi giá trị cố định
y là giao của tập M với tập tất cả các điểm nằm trên trục Oy. Bây giờ,
nếu hàm f ( x , y) = —X là cực tiểu trên tập này, thì ta vẽ một đường nét
đậm biểu thị nghiệm tối ưu của bài toán cấp dưới:

x(y) =


Hình 1.1: Bài toán quy hoạch hai cấp tuyến tính.


7
ưu là 12.
Từ Hình h l ta thấy, kể cả trường hợp đơn giản nhất là các hàm
tuyến tính, bài toán quy hoạch hai cấp là một bài toán tối ưu không lồi
và không khả vi. Vì vậy, khi tìm nghiệm tối ưu hay là tìm các điểm dừng
của các bài toán này có thể gặp rất nhiều khó khăn.

1.2

Tính ch ất hình học củ a quy hoạch hai
cấp tuyến tính
Hình 1A gợi ý rằng tập chấp nhận được của bài toán quyhoạch hai

cấp tuyến tính có biểu diễn dưới dạng hợp các mặt của

tập M . Chúng

ta sẽ chỉ ra rằng tính chất đúng cho lớp bài toán hai cấp tuyến tính tổng
quát.
Đ ịn h n g h ĩa 1 .1 . Một ánh xạ r :—»•2Rq được gọi là đa diện nếu đồ
thị của nó
grphr := { ( x , y ) e M9 X

: X e r(y )}

(1-5)


J c { 1 , . . . ,p } xét tập nghiệm M (/, J )

của hệ đẳng thức (bất đẳng thức) tuyến tính
(A1X + A2y — a)i = 0, ỉ E J, (A 1X + A 2 T/ — a)i < , i Ệ J,
Xj — ũ ,j Ệ I , Xj > 0, j £ I , Ằị = 0, ỉ Ệ J, Ằị > 0, ỉ G J,
(A1TX + c)j = 0 , j € / , ( ^ 1TA + c)j > 0, j ị I.
Khi đó, điều kiện (1.6) được thỏa mãn. Tập M ự , J ) là đa diện và hình
chiếu của nó cũng là đa diện trên Mn X Mm. Từ đồ thị của

là hợp

của các tập M ự , J ) , ta có các khẳng định sau. Nếu một tập M ự , J ) là
khác rỗng thì hình chiếu của nó trên không gian Mn X Mm bằng tập tất
cả các nghiệm của hệ:
(.Al x + A2y - a ) j = 0 ,ỉG J , (Á í x + A2y — à)i < 0, i Ệ J,
= 0, j Ệ I,X j > 0, j e I.
Tập này xác định một mặt của tập lồi đa diện { ( x ,y ) : A 1X + A2y
0 }. Mặt khác, nếu một số điểm trong (x , y ) của một mặt của tập
{ (íCj y) '•

X ~ị~ A

^ ữj X ^ 0 } lcL chap nliâĩi điiơc, thi X G

ra tất cả các mặt có tính chất này.

suy
□


< 5 và
X

X

+ y


8

, 2x + y < 1 3 ,2x — 7y < 0}.

Hình L2 minh họa tập chấp nhận được của ví dụ này. Nghiệm tối
ưu của bài toán cấp dưới là
3 ,5
X (y)

6
8

với

bài toán cấp trên lại không liên thông và bằng tập các điểm (x (y ),y ) với
3 ,5 y
x (y ) = < 5
8

v ó i^ < y < f,
với

—y

Y

< y < 3,

với 3 < y

m in
y

{ < d1, X > + < d2, y > : A3y = b,y > 0, X

e

^fL (y)\ .

Trong trường hợp tổng quát hơn ta xét bài toán quy hoạch hai cấp được
thay thế bởi
^ L(y) = ArgminKi/1, x) : A l x + A2y2 < a,

> 0 },

(2.1)

A 1 £ R pxn,

A2 £

X

X

với y = {y \ y 2)T e Mn+m,
Mpxm,

X


m ịn{(d 1 ,a;( 2/)) + (d2,y) : A 3y = b , y > 0 },
y

( 2 .2 )

với định nghĩa cực tiểu tốt tương ứng với y. Bài toán tối ưu này là liên
tục nhưng không khả vi. Sử dụng Định lý Weierstrass ta có
Đ ịn h lý

2 .1

. (S ự tồ n tạ i n gh iệm củ a b à i to á n tố i ưu h ai cấp

tu y ế n tín h )P , Theorem 3.2] Nếu tập M := {y > 0 : Azy = b} là khác
rỗng và compact, bài toán cấp dưới ( 2 . 1 ) có nhiều nhất m ột nghiệm tối
ưu với m ọi y £ M và tập chấp nhận được của bài toán (1.4) là khác
rỗng, thì bài toán này có ít nhất m ột nghiệm tối ưu.
Như vậy nghiệm tối ưu (toàn cục) và tất cả các nghiệm tối ưu địa
phương có thể tìm thấy tại các đỉnh của một số các tập đa diện. Các
tập này là hình chiếu của tập nghiệm mỗi một hệ đẳng thức (bất đẳng
thức) tuyến tính sau lên Mn X Mm. Mỗi hệ này tương ứng với hai tập chỉ
số I c { 1 , . . . , n } , J c { 1 , . . . ,p } và được xác định như sau
( A 1x + A 2y 2 — à ) i =

0,

( A 1x + A 2y 2 — à )ị < 0 ,

Ằị >


6}

tương tự với kết quả

của Hệ quả (1.1).
Giả sử tính đơn trị của Định lý |2.l| không thỏa mãn trường hợp các
bài toán tối ưu cấp dưới tuyến tính có một tham số trong hàm mục tiêu


14
nhưng không tham số hóa tập chấp nhận được trừ khi nghiệm tối ưu là
hằng số trên tập M . Khi đó, từ lựa chọn y không thể kiểm tra được lựa
chọn X, điều này đánh giá độ khó của giá trị hàm mục tiêu trước khi
biết cách chọn của bài toán cấp dưới. Trong nhiều cách giải, mỗi cách
cần một số giả

th iế t

về mối liên hệ giữa

X

và

y.

Ta sẽ nghiên cứu hai

mối liên hệ sau.
Thứ nhất, giả sử lựa chọn

(2.5)

ở đó
¥o{y) = min{ ( d 1^ ) : X e ^ i ( y ) } .
X

Thứ hai, nếu lựa chọn y không thể ảnh hưởng đến lựa chọn X trong
trường hợp bài toán tối ưu không biết trước kết quả. Ta thu được bài
toán được gọi là bài toán hai cấp pessimistic:
min{ipp(y) + (d2,y) : A3y = b , y > 0},
y

(2.6)

ở đó
ípp(y) = m ax{(d 1 ,a;) : X e ^ ( 2/)}.
X

Một nghiệm tối ưu pessimistic của bài toán quy hoạch hai cấp (1.4)
(2 . 1 ) được định nghĩa là một nghiệm tối ưu của bài toán ( 2 .6 ).


15
Với bài toán hai cấp optimistic ta có thể sử dụng tính đa diện của
ánh xạ í ri(-) để nghiên cứu sự tồn tại của các nghiệm tối ưu. Suy ra quy
hoạch hai cấp optimistic có thể được thay cho một số hữu hạn các bài
toán tối ưu tuyến tính có nghiệm tối ưu tốt nhất để giải bài toán gốc.
Suy ra
Đ ịn h lý



-X ị+X 2



Hình 2.1: Tập chấp nhận được cấp dưới và các hướng cực tiểu hóa.


17
ở đó M (0,0) kí hiệu là tập chấp nhận được của bài toán cấp dưới . Do
đ ó , v ớ i 7/2 > Vị , lim

k—
>oc

yị

=

lim

fc—>00

yị

=

1 t a có

lim 00
fc-»oo
Từ

£2


a

Bài toán quy hoạch hai cấp có mối quan hệ gần gũi với các bài toán
khác trong quy hoạch toán học. ở đây ta sẽ đưa ra hai mối liên hệ. Đó
là liên hệ giữa bài toán quy hoạch hai cấp với bài toán tối ưu đa mục
tiêu và bài toán quy hoạch

2.2.1

0 -1

tuyến tính.

Tối ưu đa mục tiều

Trong mục này ta nghiên cứu mối liên hệ của bài toán tối ưu hai
cấp (1.3), (1.4) với bài toán tối ưu hai mục tiêu, ta thấy được mối liên
hệ này như trong Hình 1A, ở đây, các điểm nằm trên đường thẳng AB


18
tạo nên tập tất cả các điểm tối ưu Pareto của bài toán
“m in”

: Á^x + A2y < a, A3y = b ,x ,y > 0

các kí hiệu tương tự như đã sử dụng trong công thức flo p , (Ị1.4Ị). Tuy
nhiên, chỉ có điểm hữu hiệu chấp nhận được với bài toán quy hoạch hai
cấp là điểm Ả điểm này có giá trị hàm xấu nhất trong hàm mục tiêu
cấp trên. Do đó, trong tổng quát không thể

(Ị+y)\ '

v)
với 0 < y < 3. Thay vào hàm mục tiêu cấp trên suy ra
2x2 — y = 2y — y = y

min : 0 < y < 3.


19
Do đó,
y* =
y

0

,x ĩ = ^ - , x * 2 =
’ 1
100
2

0

là nghiệm tối ưu (toàn cục) duy nhất của bài toán quy hoạch hai cấp
tuyến tính. Mặt khác, nghiệm này không là hữu hiệu (tối ưu Pareto) và
cũng không là hữu hiệu optimistic với bài toán tối ưu hai mục tiêu
f2x2 - y \
„
Ị
) ->• “m in”,

2*2

- ỳ\ =

Ta có
'1x\ -

y*\ =

V. ~X1 J

/ 0 \

(2

x2

-y \

Vĩõõ/

\ X1 /

=

/-3

+ 3e'

V 100 *