ĐẠI HỌC QUỐC GIA TP. HCM

TRƯỜNG ĐẠI HỌC BÁCH KHOA
—————————————

NGUYỄN NGỌC BẢO

ỨNG DỤNG LÝ THUYẾT TỐI ƯU
VÀ LÝ THUYẾT TRÒ CHƠI VÀO
BÀI TOÁN THỦY ĐIỆN

CHUYÊN NGÀNH: TOÁN ỨNG DỤNG
Mã số: 60 46 01 12

LUẬN VĂN THẠC SĨ

TP. Hồ Chí Minh, tháng 6 năm 2015


Cơng trình được hồn thành tại: Trường Đại Học Bách Khoa - ĐHQG.TPHCM
Cán bộ hướng dẫn khoa học: TS.Lê Xuân Đại
........................................................................................
........................................................................................
........................................................................................
Cán bộ chấm nhận xét 1: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
........................................................................................
........................................................................................
........................................................................................
Cán bộ chấm nhận xét 2: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
........................................................................................
........................................................................................

........................................................................................
Luận văn thạc sĩ được bảo vệ tại Trường Đại học Bách Khoa, ĐHQG Tp. HCM ngày 01
tháng 8 năm 2015.
Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm:
1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Xác nhận của Chủ tịch Hội đồng đánh giá luận văn và Trưởng Khoa quản lý chuyên
ngành sau khi luận văn đã được sữa chữa (nếu có)
CHỦ TỊCH HỘI ĐỒNG

TRƯỞNG KHOA KHOA HỌC ỨNG DỤNG

PGS.TS. Huỳnh Quang Linh


ĐẠI HỌC QUỐC GIA TP.HCM
ĐẠI HỌC BÁCH KHOA
—————————–

CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập - Tự do - Hạnh phúc
—————————–

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ tên học viên: Nguyễn Ngọc Bảo
Ngày, tháng, năm sinh: 17/11/1984
Chuyên ngành: Toán ứng dụng


MSHV: 13240280
Nơi sinh: Lâm Đồng
Mã số: 60 46 01 12

I. TÊN ĐỀ TÀI: ỨNG DỤNG LÝ THUYẾT TỐI ƯU VÀ LÝ THUYẾT TRỊ CHƠI VÀO
BÀI TỐN THỦY ĐIỆN
NHIỆM VỤ VÀ NỘI DUNG:
• Mơ tả bài tốn điều tiết tối ưu nhà máy thủy điện.
• Mơ hình hóa và giải số bài tốn tối ưu hóa cơng suất phát điện, tối ưu hóa doanh thu
của Nhà máy thủy điện Đại Ninh ngắn hạn và dài hạn.
• Chiến lược chào giá điện của nhà máy thủy điện và phương pháp phân bổ tối ưu công
suất cho các nhà máy điện theo Lý thuyết trị chơi.
II. NGÀY GIAO NHIỆM VỤ: 19/01/2015
III. NGÀY HỒN THÀNH NHIỆM VỤ: 14/06/2015
IV. CÁN BỘ HƯỚNG DẪN: TS.Lê Xuân Đại

CÁN BỘ HƯỚNG DẪN

TS. Lê Xuân Đại

Tp. HCM, ngày · · · tháng · · · năm 2015
CHỦ NHIỆM BỘ MƠN ĐÀO TẠO

PGS.TS. Nguyễn Đình Huy
TRƯỞNG KHOA

PGS.TS. Huỳnh Quang Linh



LỜI CẢM ƠN
Tơi xin bày tỏ lịng biết ơn sâu sắc của mình với Thầy hướng dẫn,
TS. Lê Xuân Đại. Thầy đã ln truyền đạt kiến thức, động viên, khuyến
khích, giúp đỡ tơi hồn thành luận văn tốt nghiệp.
Tơi xin chân thành cảm ơn tất cả quý thầy cô Bộ mơn Tốn Ứng DụngKhoa Khoa học Ứng Dụng đã tận tình dạy dỗ, truyền đạt kiến thức, kỹ
năng cho tơi trong suốt khóa học và xin cảm ơn Phịng đào tạo sau Đại
học đã luôn tạo điều kiện thuận lợi cho tôi.
Tôi xin cảm ơn Trường THPT Chu Văn An, nơi tôi công tác đã tạo điều
kiện cho tôi tham gia khóa học theo Chương trình hợp tác đào tạo, chuyển
giao khoa học công nghệ giữa Trường Đại Học Bách Khoa TP.HCM và
UBND tỉnh Lâm Đồng.
Cuối cùng tôi xin gửi lời cảm ơn đến gia đình, những người đã gần gũi,
khích lệ tơi trong thời gian qua.


TĨM TẮT LUẬN VĂN
TĨM TẮT
Luận văn trình bày kết quả ứng dụng lý thuyết tối ưu giải quyết một
trong những bài toán thực tế được quan tâm hiện nay: Tối ưu hóa vận
hành nhà máy thủy điện để cơng suất phát điện, doanh thu của nhà máy
lớn nhất. Vấn đề được giải quyết bằng cách áp dụng kết quả từ lý thuyết
tối ưu và giải số bằng phần mềm Matlab. Luận văn cũng trình bày kết
quả ứng dụng lý thuyết trò chơi vào việc chào giá điện trong thị trường
điện cạnh tranh.
ABSTRACT
This thesis presents the results of application optimization theory to solve
a practical problem of concern nowadays: Optimized operating hydropower
plants to achieve maximum electricity generation capacity and profits. The
problem is solved by applying the outcomes from optimization theory and
Matlab software. The study also presents the issue of the application of

game theory to the pricing capability in the competitive electricity market.


LỜI CAM ĐOAN
Tơi xin cam đoan đây là cơng trình nghiên cứu của riêng tôi.
Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được
ai cơng bố trong bất kỳ cơng trình nào khác.
Tác giả

Nguyễn Ngọc Bảo


Mục lục

DANH MỤC HÌNH

9

LỜI NĨI ĐẦU

10

1 CƠ SỞ LÝ THUYẾT
1.1 Bài toán tối ưu . . . . . . . . . . . . . . . . . .
1.1.1 Các khái niệm cơ bản . . . . . . . . . . .
1.1.2 Điều kiện tồn tại nghiệm . . . . . . . . .
1.1.3 Phân loại bài toán tối ưu . . . . . . . . .
1.2 Hàm lồi . . . . . . . . . . . . . . . . . . . . . .
1.2.1 Hàm lồi . . . . . . . . . . . . . . . . . .
1.2.2 Các phép toán về hàm lồi . . . . . . . .

1.2.3 Tính liên tục của hàm lồi . . . . . . . .
1.2.4 Đạo hàm theo hướng của hàm lồi . . . .
1.2.5 Tiêu chuẩn nhận biết hàm lồi khả vi . .
1.3 Bài tốn quy hoạch phi tuyến khơng ràng buộc
1.4 Bài tốn quy hoạch phi tuyến có ràng buộc . . .
1.4.1 Điều kiện tối ưu . . . . . . . . . . . . . .
1.4.2 Bài tốn Quy hoạch tồn phương . . . .

13
13
13
14
15
16
16
17
17
17
18
19
21
21
23

.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

2 ĐIỀU TIẾT TỐI ƯU HỒ THỦY ĐIỆN ĐẠI NINH
2.1 Giới thiệu nhà máy thủy điện Đại Ninh . . . . . . . . . . .
2.2 Tính tốn xác định chế độ vận hành tối ưu nhà máy thủy
điện Đại Ninh ngắn hạn . . . . . . . . . . . . . . . . . . .
2.2.1 Mơ hình tốn . . . . . . . . . . . . . . . . . . . . .
2.2.2 Kết quả tính toán . . . . . . . . . . . . . . . . . . .

2.3 Tính tốn xác định chế độ vận hành tối ưu nhà máy thủy
điện Đại Ninh dài hạn . . . . . . . . . . . . . . . . . . . .
2.3.1 Mơ hình tốn . . . . . . . . . . . . . . . . . . . . .
2.3.2 Kết quả tính tốn . . . . . . . . . . . . . . . . . . .
7

25
25
27
27
32
35
35
36


Trang 8

Luận văn thạc sĩ

3 LÝ THUYẾT TRÒ CHƠI VÀ ỨNG DỤNG VÀO VIỆC
CHÀO GIÁ CỦA NHÀ MÁY THỦY ĐIỆN
3.1 Giới thiệu lý thuyết trò chơi . . . . . . . . . . . . . . . . .
3.2 Cân bằng Nash . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Vài nét về thị trường điện cạnh tranh ở Việt Nam . . . . .
3.4 Áp dụng lý thuyết trò chơi trong chào giá điện . . . . . . .
3.4.1 Hàm chi phí phát điện, chi phí biên, hàm mục tiêu
3.4.2 Áp dụng lý thuyết trò chơi vào việc chào giá điện .

39

39
40
41
43
43
43

TÀI LIỆU THAM KHẢO

52

PHỤ LỤC

54

Nguyễn Ngọc Bảo - Cao học khóa 2013. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Trang 8


Luận văn thạc sĩ - Chuyên ngành Toán Ứng Dụng

Trang 9

DANH MỤC HÌNH
Hình
Hình
Hình
Hình
Hình
Hình
Hình

Hình
Hình

2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9

Cửa xả tràn nhà máy thủy điện Đại Ninh .............................25
Biểu đồ điều phối hồ chứa thủy điện Đại Ninh .....................26
Sơ đồ nhà máy thủy điện .......................................................27
Biểu đồ tối ưu lưu lượng nước cho Bài toán 2.1.....................33
Biểu đồ tối ưu dung tích hồ chứa cho Bài tốn 2.1 ...............34
Biểu đồ doanh thu của nhà máy thủy điện Đại Ninh ............34
Biểu đồ điều khiển tối ưu thủy điện Đại Ninh năm 2011 ......36
Biểu đồ điều khiển tối ưu thủy điện Đại Ninh năm 2012 ......37
Biểu đồ điều khiển tối ưu thủy điện Đại Ninh năm 2013 ......38

Nguyễn Ngọc Bảo - Cao học khóa 2013. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Trang 9


LỜI NĨI ĐẦU
Lý do chọn đề tài
• Điều tiết hoạt động của nhà máy thủy điện nói riêng và các nhà máy
điện nói chung là vấn đề quan trọng, ảnh hưởng đến nền kinh tế và

an ninh năng lượng của mỗi quốc gia. Bộ Cơng thương có Cục điều
tiết để quản lý về vấn đề này.
• Bản thân tơi được cơ quan và địa phương tạo điều kiện học tập trong
khuôn khổ Hợp tác đào tạo và chuyển giao khoa học công nghệ giữa
trường Đại học Bách Khoa TPHCM và UBND tỉnh Lâm Đồng nên tôi
chọn hướng nghiên cứu mang tính ứng dụng thực tế cho địa phương,
nhằm phát huy hơn nữa lợi ích của việc vận hành nhà máy thủy điện
Đại Ninh nằm trên địa bàn hai tỉnh Lâm Đồng và Bình Thuận.
• Sản lượng điện của nhà máy thủy điện Đại Ninh hiện đạt chỉ tiêu
được giao tuy nhiên cịn thấp so với thiết kế và có thể đạt hiệu quả
cao hơn nếu vận dụng lý thuyết tối ưu để vận hành nhà máy và đạt
lợi nhuận cao hơn nếu áp dụng lý thuyết trò chơi vào việc chào giá
trong thị trường phát điện cạnh tranh.
• Điều tiết tối ưu nhà máy thủy điện và phân bố công suất phát điện
cho các nhà máy một cách tối ưu là góp phần vào việc ổn định giá
điện và sử dụng tài nguyên hợp lý.
• Phương pháp điều khiển nhà máy thủy điện Đại Ninh nói riêng và các
nhà máy thủy điện nói chung hiện nay thiên về phương án an toàn,
theo kinh nghiệm mà chưa cải tiến theo hướng tối ưu.
Mục đích nghiên cứu
• Dựa trên cơ sở lý thuyết tối ưu để đưa ra quỹ đạo tối ưu mực nước hồ
và lưu lượng nước qua turbin theo thời gian để công suất phát điện
lớn nhất, lượng nước xả bỏ nhỏ nhất và vẫn đảm bảo nước cho thủy
lợi, xả nước cho dịng chảy sinh thái và mơi trường hạ du đập thủy
điện. Giải số bài toán: tối đa hóa cơng suất phát điện trong thời gian
ngắn và dài hạn.
10


Luận văn thạc sĩ - Chuyên ngành Toán Ứng Dụng


Trang 11

• Áp dụng lý thuyết trị chơi trong việc chào giá ở thị trường phát điện
cạnh tranh nhằm đảm bảo doanh thu cho doanh nghiệp, tiết kiệm chi
phí phát điện trên tồn hệ thống và hài hịa lợi ích giữa các nhà máy
điện và người sử dụng điện.
Đối tượng và phạm vi nghiên cứu
• Việc vận hành tối ưu nhà máy thủy điện Đại Ninh.
• Hàm chi phí và bảng chào giá của nhà máy thủy điện Đại Ninh.
Phương pháp nghiên cứu
• Nghiên cứu tài liệu có liên quan đến đề tài.
• Sử dụng phần mềm Matlab để tính tốn và mô phỏng quỹ đạo tối ưu
mực nước hồ thủy điện Đại Ninh và lưu lượng nước qua turbin, lưu
lượng nước chảy tràn.
• Áp dụng Lý thuyết trị chơi, Lý thuyết chi phí cận biên của kinh tế
học để đưa ra chiến lược chào giá cho nhà máy thủy điện Đại Ninh
trên thị trường điện cạnh tranh để tăng lợi nhuận cho nhà máy.
Ý nghĩa của đề tài
• Ý nghĩa khoa học: Ứng dụng tốn học cùng với cơng nghệ thơng tin
để giải quyết bài tốn trong kinh tế và kỹ thuật.
• Ý nghĩa thực tế: Có ý nghĩa về kinh tế và góp phần vào việc sử dụng
hợp lý tài nguyên nước của quốc gia. Các nhà máy thủy điện có thể
sử dụng kết quả của đề tài để đưa ra phương án vận hành tối ưu và
phương pháp chào giá điện, hạn chế sự phụ thuộc vào các cơng ty tư
vấn về điện.
Tình hình nghiên cứu trong và ngồi nước
Hiện nay ở trong và ngồi nước có nhiều nghiên cứu liên quan, có thể
kể đến một số nghiên cứu sau:
• Sau khi lý thuyết tối ưu ra đời, cùng với sự phát triển của máy tính,

nhiều nhà nghiên cứu ở các nước đã áp dụng vào vấn đề điều khiển
tối ưu các nhà máy thủy điện cụ thể, tuy nhiên thường không công
bố code.
Nguyễn Ngọc Bảo - Cao học khóa 2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Trang 11


Trang 12

Luận văn thạc sĩ

• GS.VS Hồng Xn Phú nghiên cứu về lý thuyết điều khiển, lý thuyết
tối ưu, giải tích số và các ứng dụng, trong đó có bài tốn tối ưu cơng
suất nhà máy thủy điện.
• Tác giả Lê Hùng, trường Đại học Bách Khoa Đà Nẵng giải bài toán
tối ưu vận hành điều tiết hồ thủy điện bậc thang Sông Bung 2 và
Sông Bung 4 bằng ngôn ngữ lập trình Delphi.
• Nhóm tác giả Trần Đình Long, Đàm Xuân Hiệp, Đặng Quốc Thống,
Nguyễn Minh Thắng nghiên cứu chiến lược chào giá cho các nhà máy
thủy điện trong thị trường điện cạnh tranh.
• Các cơng ty tư vấn về điện ra đời, có các phần mềm trợ giúp cho việc
điều khiển tối ưu nhà máy và phương pháp chào giá điện.
Những vấn đề luận văn sẽ thực hiện
• Mơ hình hóa và sử dụng phần mềm Matlab để giải bài tốn tối ưu
cơng suất phát điện của nhà máy thủy điện Đại Ninh ngắn hạn và
dài hạn.
• Áp dụng lý thuyết trị chơi và lý thuyết chi phí cận biên của kinh tế
học để đưa ra phương pháp chào giá của nhà máy thủy điện Đại Ninh
trong thị trường điện cạnh tranh.

Nguyễn Ngọc Bảo - Cao học khóa 2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Trang 12



Chương 1
CƠ SỞ LÝ THUYẾT
1.1
1.1.1

Bài toán tối ưu
Các khái niệm cơ bản

Bài toán tối ưu tổng quát được phát biểu như sau:
min f (x), với điều kiện x ∈ D

(P1 )

max f (x), với điều kiện x ∈ D

(P2 )

hoặc

trong đó D ⊂ Rn được gọi là tập nghiệm chấp nhận được hay tập ràng
buộc và f 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.
Điểm x∗ ∈ D mà f (x∗ ) ≤ f (x), ∀x ∈ D được gọi là nghiệm tối ưu, hoặc
nghiệm tối ưu toàn cục, hoặc nghiệm cực tiểu toàn cục, hay đơn giản là
nghiệm của bài toán (P1 ).
Điểm x∗ ∈ D được gọi là nghiệm cực tiểu toàn cục chặt nếu f (x∗ ) <
f (x), ∀x ∈ D và x = x∗ .
Khơng phải bài tốn (P1 ) nào cũng có nghiệm cực tiểu tồn cục và nếu bài

tốn có nghiệm cực tiểu tồn cục thì chưa chắc có nghiệm cực tiểu tồn
cục chặt.
Giá trị tối ưu (hay giá trị cực tiểu) của bài toán (P1 ) được kí hiệu là
min f (x) hoặc min{f (x)|x ∈ D}.
x∈D

Đ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 (P1 ) nếu tồn tại ε -lân cận B(x∗ , ε)
của điểm x∗ ∈ D sao cho f (x∗ ) ≤ f (x), ∀x ∈ B(x∗ , ε) ∩ D, trong đó
B(x∗ , ε) := {x ∈ Rn | ||x − x∗ || < ε}.
13


Trang 14

Luận văn thạc sĩ

Điểm x∗ ∈ D được gọi là nghiệm tối ưu địa phương chặt, hoặc nghiệm
cực tiểu địa phương chặt của bài toán (P1 ) nếu tồn tại ε -lân cận B(x∗ , ε)
của điểm x∗ ∈ D sao cho f (x∗ ) < f (x), ∀x ∈ B(x∗ , ε) ∩ D và x = x∗ .
Các khái niệm tương tự cũng được định nghĩa cho bài toán (P2 ).
Nhận xét: Bài toán (P1 ) tương đương với bài toán max −f (x), với điều
kiện x ∈ D theo nghĩa tập nghiệm tối ưu của hai bài toán này là trùng
nhau và giá trị tối ưu ngược dấu.

1.1.2

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

Mục đích của Quy hoạch tốn học là nghiên cứu các tính chất của tập

nghiệm và xây dựng các thuật tốn để tìm nghiệm của bài toán tối ưu. Câu
hỏi đầu tiên đặt ra là "bài tốn cần giải có nghiệm tối ưu hay khơng?".
Xét bài toán tối ưu:
min f (x), với điều kiện x ∈ D

(P1 )

trong đó D ⊂ Rn và f (x) là một hàm thực xác định trên một tập mở chứa
D. Khi đó một trong bốn khả năng sau có thể xảy ra:
- Bài tốn (P1 ) khơng có phương án chấp nhận được, tức là D = ∅;
- Bài tốn có nghiệm tối ưu;
- Bài tốn khơng có nghiệm tối ưu và giá trị hàm mục tiêu giảm vô hạn
trên tập chấp nhận được D, tức là giá trị tối ưu inf{f (x)|x ∈ D} = −∞;
- Bài toán khơng có nghiệm tối ưu và giá trị tối ưu inf{f (x)|x ∈ D} là
hữu hạn.
Như vậy, trừ trường hợp tập chấp nhận được bằng rỗng, giá trị tối ưu của
bài tốn (P1 ) ln tồn tại nhưng nghiệm tối ưu thì khơng nhất thiết tồn
tại. Việc tìm kiếm điều kiện đảm bảo để bài tốn có nghiệm tối ưu là quan
trọng.
Cho hàm số f xác định trên tập mở X ⊂ Rn .
Hàm f được gọi là liên tục tại điểm x0 ∈ X nếu với mỗi ε > 0 cho
trước, tồn tại δ > 0 sao cho f (x) − f (x0 ) < ε với mọi x0 ∈ X thỏa mãn
x − x0 < δ. Nói cách khác hàm f liên tục tại x0 ∈ X nếu với mọi dãy
xk ⊂ X hội tụ đến x0 , ta có f (xk ) → f (x0 ).
Hàm f được gọi là nửa liên tục dưới (tương ứng, nửa liên tục trên)
tại điểm x0 ∈ X nếu với mỗi ε > 0 cho trước, tồn tại δ > 0 sao cho
f (x) ≥ f (x0 ) − ε (tương ứng, f (x) ≤ f (x0 ) + ε) với mọi x0 ∈ X thỏa mãn
x − x0 < δ.
Nhận xét: Nếu f nửa liên tục dưới tại x0 thì −f nửa liên tục trên tại x0 .
Nguyễn Ngọc Bảo - Cao học khóa 2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Trang 14



Luận văn thạc sĩ - Chuyên ngành Toán Ứng Dụng

Trang 15

Hàm f vừa nửa liên tục trên, vừa nửa liên tục dưới tại x0 thì liên tục tại
điểm đó.
Hàm f được gọi là liên tục (tương ứng, nửa liên tục dưới, nửa liên tục
trên) trên X nếu nó liên tục (tương ứng, nửa liên tục dưới, nửa liên tục
trên) tại mọi điểm của X.
Định lý 1.1. ([10] trang 20) Cho D là tập compact khác rỗng. Khi đó:
i) Nếu hàm f nửa liên tục dưới trên D thì bài tốn (P1 ) có nghiệm tối ưu,
ii) Nếu hàm f nửa liên tục trên trên D thì bài tốn (P2 ) có nghiệm tối ưu,
Chứng minh.
Do tính tương tự, ta chỉ cần chứng minh (i). Giả sử giá trị tối ưu của
bài toán (P1 ) là t0 = inf f (D) . Theo định nghĩa
(x) ≥ t0 , ∀x ∈ D

(1.1)

và tồn tại dãy xk ⊂ D sao cho lim f (xk ) = t0 .
k→∞

Do D là tập compact nên có một dãy con của dãy xk hội tụ đến một
điểm x0 ∈ D. Để đơn giản, ta có thể giả thiết rằng lim xk = x0 ∈ D. Do
k→∞

f nửa liên tục dưới tại x0 ∈ D nên f (x0 ) ≤ lim f (xk ) = t0 . Kết hợp điều
k→∞


này với (1.1) ta có: t0 = inf f (D) = f (x0 ), chứng tỏ rằng x0 là nghiệm tối
ưu của bài toán (P1 ).
Hệ quả 1.1. (Định lý Weierstrass) Nếu tập D compact và hàm f liên
tục trên D thì cả hai bài tốn (P1 ) và (P2 ) đều có nghiệm tối ưu.
Chứng minh. Hàm liên tục là hàm nửa liên tục trên và nửa liên tục dưới.
Kết luận của Hệ quả được suy trực tiếp từ Định lý 1.1.

1.1.3

Phân loại bài toán tối ưu

Để tiện cho việc nghiên cứu, người ta thường chia các bài tốn tối ưu thành
một số lớp dựa trên tính chất của hàm mục tiêu và tập chấp nhận được.
• Quy hoạch tuyến tính: Hàm mục tiêu f (x) là hàm tuyến tính và tập
chấp nhận được là tập lồi đa diện.
• Quy hoạch ngun: Tập chấp nhận được có cấu trúc rời rạc
• Quy hoạch phi tuyến: Hàm mục tiêu hoặc một trong các hàm ràng
buộc không phải là hàm afin. Trong các bài toán tối ưu phi tuyến có
hai lớp đặc biệt quan trọng, đó là Quy hoạch lồi và Quy hoạch lõm.
Nguyễn Ngọc Bảo - Cao học khóa 2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Trang 15


Trang 16

Luận văn thạc sĩ

• Quy hoạch động: Bài tốn Quy hoạch động xét các đối tượng là các
quá trình có thể chia ra thành nhiều giai đoạn hoặc các q trình
phát triển theo thời gian. Nhiều bài tốn quy hoạch động có thể đưa

về bài tốn quy hoạch tuyến tính cỡ lớn.
• Quy hoạch đa mục tiêu: Bài tốn có có nhiều hàm mục tiêu mà ta
phải cực tiểu hóa (cực đại hóa) đồng thời.
• Ngồi ra cịn có Quy hoạch ngẫu nhiên, Quy hoạch tham số...

1.2

Hàm lồi

1.2.1

Hàm lồi

Định nghĩa 1.1. Cho x1 , x2 là hai điểm trong Rn . Đường thẳng qua x1 và
x2 là tập các điểm x = λx1 + (1 − λ) x2 = x2 + λ(x1 − x2 ) với λ ∈ R. Tập
M ⊂ Rn được gọi là tập afin nếu M chứa trọn cả đường thẳng đi qua hai
điểm bất kì của M, nghĩa là ∀x1 , x2 ∈ M, λ ∈ R ⇒ λx1 + (1 − λ)x2 ∈ M .
Định nghĩa 1.2. Tập M ⊂ Rn được gọi là tập lồi nếu M chứa trọn đoạn
thẳng nối hai điểm bất kì thuộc nó, tức là ∀x1 , x2 ∈ M, λ ∈ [0; 1] ⇒
λx1 + (1 − λ)x2 ∈ M .
Định nghĩa 1.3. Hàm số có dạng f (x) = c, x +α, trong đó vectơ c ∈ Rn
và α ∈ R cho trước được gọi là hàm afin.
Định nghĩa 1.4. Cho hàm f xác định trên tập lồi X ⊆ Rn . Ta gọi f
là hàm lồi nếu f (λx1 + (1 − λ)x2 )
λf (x1 ) + (1 − λ)f (x2 ) với bất kì
x1 , x2 ∈ X và số thực λ ∈ [0; 1]. Hàm f được gọi là hàm lồi chặt nếu
f (λx1 + (1 − λ)x2 ) < λf (x1 ) + (1 − λ)f (x2 ) với bất kì x1 , x2 ∈ X, x1 = x2
và λ ∈ (0; 1).
Miền xác định hữu hiệu của hàm f là domf := {x ∈ X|f (x) < +∞}.
Epigraph (tương ứng Hypograp) của hàm f, kí hiệu epi(f ) (tương ứng

hypo(f )) được định nghĩa như sau:
epi(f ) := {(x, ξ) ∈ X × R|ξ
hypo(f ) := {(x, ζ) ∈ X × R|ζ

f (x)} ⊂ Rn+1
f (x)} ⊂ Rn+1 .

Hàm f : X → R ∪ {+∞} có thể được mở rộng thành một hàm lồi trên
tốn khơng gian Rn bằng cách đặt f (x) = +∞ nếu x ∈
/ domf . Vì vậy để
n
đơn giản ta thường xét f là hàm lồi trên R .
Hàm f được gọi là hàm lõm (tương ứng, hàm lõm chặt) trên tập lồi X
nếu −f là hàm lồi (tương ứng, hàm lồi chặt).
Mệnh đề 1.1.([10] trang 200) Cho hàm số f xác định trên tập lồi khác
rỗng X ⊆ Rn . Khi đó:
Nguyễn Ngọc Bảo - Cao học khóa 2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Trang 16


Luận văn thạc sĩ - Chuyên ngành Toán Ứng Dụng

Trang 17

i) Hàm f là hàm lồi khi và chỉ khi epi(f ) là tập lồi.
ii) hàm f là hàm lõm khi và chỉ khi hypo(f ) là tập lồi.
Mệnh đề 1.2. ([10] trang 201)
i) Nếu hàm số f xác định trên tập lồi X ⊆ Rn là hàm lồi thì tập mức
dưới Lα (f ) := {x ∈ X|f (x) α} là tập lồi với mọi α ∈ R.
ii) Nếu hàm số f xác định trên tập lồi X ⊆ Rn là hàm lõm thì tập mức
trên Lα (g) := {x ∈ X|g(x) α} là tập lồi với mọi α ∈ R.

1.2.2

Các phép toán về hàm lồi

Định nghĩa 1.5. Cho hàm số f1 xác định trên tập lồi X1 ⊆ Rn , hàm
số f2 xác định trên tập lồi X2 ⊆ Rn và số thực λ
0. Các phép toán
λf1 , f1 + f 2 , max{f1 , f 2 } được định nghĩa như sau:
(λf1 )(x) := λ f1 (x), x ∈ X1 ;
(f1 + f2 )(x) := f1 (x) + f2 (x), x ∈ X1 ∩ X2 ;
max{f1 , f2 }(x) := max{f1 (x), f2 (x)}, x ∈ X1 ∩ X2 .
Mệnh đề 1.3.([10] trang 202) Cho hàm số f1 xác định trên tập lồi X1 ⊆
Rn , hàm số f2 xác định trên tập lồi X2 ⊆ Rn và các số thực α > 0, β > 0.
Khi đó các hàm λf1 , f1 + f 2 , max{f1 , f 2 } là lồi trên X1 ∩ X2 .
1.2.3

Tính liên tục của hàm lồi

Một hàm lồi f xác định trên tập lồi X ⊆ Rn không nhất thiết là hàm
liên tục. Tuy nhiên khi X là tập lồi mở ta có kết quả sau:
Định lý 1.2. ([10] trang 202)Nếu f là hàm lồi xác định trên tập lồi mở
X ⊆ Rn thì f liên tục trên tập X.
Nhận xét 1.1.([10] trang 202) Sự gián đoạn của hàm lồi chỉ có thể xảy
ra tại biên của tập xác định.
1.2.4

Đạo hàm theo hướng của hàm lồi

Định nghĩa 1.6. Cho hàm f xác định trên Rn và một vectơ d ∈ Rn \{0}.
(x0 )

Giới hạn lim+ f (x0 +td)−f
nếu tồn tại (hữu hạn hoặc vô cùng) được gọi
t
t→0

là đạo hàm theo hướng d của hàm f tại điểm x0 ∈ Rn , và kí hiệu là
(x0 )
f (x0 , d). Nếu vectơ d = ei trong đó ei = (0, ..., 1 , ..., 0)T thì ∂f∂x
=
i
i

Nguyễn Ngọc Bảo - Cao học khóa 2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Trang 17


Trang 18

Luận văn thạc sĩ

lim+ f (x0 +teti )−f (x0 ) = f (x0 , ei ). .

t→0

(x0 )
Dễ thấy nếu f(x) là hàm một biến thì (x0 , 1) = lim+ f (x0 +t)−f
=
t
t→0

f+ (x0 ) trong đó f+ (x0 ) là đạo hàm phải của f tại x0 và f (x0 , −1) =

(x0 )
(x0 )
lim+ f (x0 +t.(−1))−f
= lim− f (x0 +t)−f
= −f− (x0 ) với f− (x0 ) là đạo hàm
t
−t

t→0

t→0

trái của f tại x0 .
Mệnh đề 1.4.([10] trang 203) Cho hàm số f xác định trên Rn và điểm
x0 ∈ Rn . Nếu f khả vi tại x0 thì f (x0 , d) = ∇f (x0 ), d , ∀d ∈ Rn \{0}.
Nhận xét 1.2. Đạo hàm theo hướng của hàm f phản ảnh tốc độ biến
thiên của hàm f tại x0 theo hướng đó.
Định lý 1.3.([10] trang 204)Nếu f : X → R ∪ {+∞} là một hàm lồi xác
định trên tập lồi X ⊆ Rn thì nó có đạo hàm theo mọi hướng d ∈ Rn \{0}
tại mọi điểm x0 ∈ domf và f (x0 , d) f (x0 + d) − f (x0 ).
Hệ quả 1.2. Nếu f là hàm lồi khả vi xác định trên tập lồi mở X thì
f có đạo hàm theo mọi hướng d ∈ Rn \{0} tại mọi điểm x0 ∈ domf và
∇f (x0 ), d = f (x0 , d) f (x0 + d) − f (x0 ).
1.2.5

Tiêu chuẩn nhận biết hàm lồi khả vi

Định lý 1.4.([10] trang 205) Cho f là một hàm khả vi xác định trên tập
lồi mở X ⊆ Rn , khi đó:
i) Hàm f là hàm lồi trên X khi và chỉ khi f (y) − f (x)

∀x, y ∈ X.

∇f (x), y − x ,

ii) Hàm f là hàm lõm trên X khi và chỉ khi f (y)−f (x)
∀x, y ∈ X

∇f (x), y − x ,

Với hàm một biến f xác định trên tập lồi X ⊆ Rn ta đã biết: f là
hàm lồi trên X khi và chỉ khi f (x) 0 với mọi x ∈ X. Ví dụ như hàm
f (x) = ex lồi trên R. Tương tự ta có:
Định lý 1.5.([10] trang 205) Cho f là một hàm khả vi hai lần trên tập
lồi mở X ⊆ Rn , khi đó:
i) Hàm f là hàm lồi trên X khi và chỉ khi ma trận Hesse ∇2 f (x) là nửa
xác định dương trên X, tức với mỗi x ∈ X, y T ∇2 f (x)y 0, ∀y ∈ Rn .
Hàm f là hàm lồi chặt trên X khi và chỉ khi ma trận Hesse ∇2 f (x)
là xác định dương trên X, tức là:
x ∈ X, y T ∇2 f (x)y > 0, ∀y ∈ Rn \{0} .
ii) Hàm f là hàm lõm trên X khi và chỉ khi ma trận Hesse ∇2 f (x) là nửa
xác định âm trên X, tức với mỗi x ∈ X, y T ∇2 f (x)y 0, ∀y ∈ Rn .
Nguyễn Ngọc Bảo - Cao học khóa 2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Trang 18


Luận văn thạc sĩ - Chuyên ngành Toán Ứng Dụng

Trang 19

Hàm f là hàm lõm chặt trên X khi và chỉ khi ma trận Hesse ∇2 f (x)
là xác định âm trên X, tức là:

x ∈ X, y T ∇2 f (x)y < 0, ∀y ∈ Rn \{0} .
Hệ quả 1.3.([10] trang 206) Cho hàm toàn phương f (x) = 21 x, Qx +
x, a + α, trong đó Q là ma trận đối xứng cấp n × n. Khi đó:
i) Hàm f là hàm lồi (tương ứng, lồi chặt) trên Rn nếu Q là ma trận nửa
xác định dương (tương ứng, xác định dương) ;
ii) Hàm f là hàm lõm (tương ứng, lõm chặt) trên Rn nếu Q là ma trận
nửa xác định âm (tương ứng, xác định âm).
Ví dụ 1.1. Cho f (x1 , x2 ) = 2x21 + 4x1 x2 + 3x22 . Ta có:
∇f (x) =
∇2 f (x) =

f x1
f x2

=

f x1 x1

f x1 x2

f x2 x1

f x2 x2

4x1 + 4x2
4x1 + 6x2
=

4 4
4 6


Vì ma trận Hesse ∇2 f (x) xác định dương nên hàm f đã cho là hàm lồi
chặt trên R2 .

1.3

Bài toán quy hoạch phi tuyến khơng ràng buộc

Bài tốn quy hoạch phi tuyến không ràng buộc được phát biểu như sau:
min f (x) với điều kiện x ∈ Rn (B krb )
trong đó f : Rn → R là hàm phi tuyến.
Định lý 1.6.([10] trang 208) (Điều kiện bậc nhất) Cho hàm f xác định,
khả vi trên Rn . Nếu x∗ ∈ Rn là nghiệm cực tiểu địa phương của bài tốn
(B krb ) thì ∇f (x∗ ) = 0.
Định lý 1.7.([10] trang 209) Cho f là hàm lồi khả vi trên Rn . Khi đó
x∗ ∈ Rn là nghiệm cực tiểu tồn cục của bài tốn (B krb ) khi và chỉ khi
∇f (x∗ ) = 0.
Nhận xét 1.3. Nếu A là ma trận cấp n × n đối xứng, nửa xác định dương,
b ∈ Rn và c ∈ R thì hàm tồn phương f (x) = 21 xT Ax − bT x + c là hàm lồi
khả vi. Trong trường hợp này, vì ∇f (x) = Ax − b nên theo định lý 1.6 việc
giải bài toán quy hoạch lồi min{f (x)|x ∈ Rn } tương đương tìm nghiệm
Nguyễn Ngọc Bảo - Cao học khóa 2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Trang 19


Trang 20

Luận văn thạc sĩ

của một hệ phương trình tuyến tính Ax = b
Định lý 1.8. ([10] trang 209)(Điều kiện bậc 2) Giả sử hàm số f liên tục

khả vi hai lần trên Rn
i) Nếu x∗ ∈ Rn là điểm cực tiểu địa phương của f trên Rn thì ∇f (x∗ ) = 0
và ∇2 f (x∗ ) nửa xác định dương
ii) Ngược lại nếu ∇f (x∗ ) = 0 và ∇2 f (x∗ ) xác định dương thì x∗ là điểm
cực tiểu địa phương chặt của f trên Rn .
Ví dụ 1.2. Tìm điểm cực tiểu địa phương của hàm số:
f (x1 , x2 ) = x31 + x22 − 6x1 − 2x2 + 12
Giải.
3x21 − 6
2x2 − 2

6x1 0
.
0
2
√
√
2
−
2
Giải hệ ∇f (x) = 0 ta được hai điểm dừng x1 =
và x2 =
.
1
1
√
√
6
2
0

−6
2 0
Ta có: ∇2 f (x1 ) =
và ∇2 f (x2 ) =
.
0
2
0
2
√
6
2 0
Vì ∇2 f (x1 ) =
là ma trận xác định dương nên x1 là điểm cực
0
2
tiểu địa phương chặt của hàm f trên R2 . Do ∇2 f (x2 ) không là ma trận
nửa xác định dương cũng không là ma trận nửa xác định âm nên x2 không
là điểm cực đại địa phương, cũng không là điểm cực tiểu địa phương của
hàm f trên R2 .
Ví dụ 1.3. Giải bài tốn tối ưu không ràng buộc (B krb ) với hàm mục tiêu
f (x1 , x2 ) = x21 + x1 x2 + x22 + 2(x1 + x2 − 3).
Giải.
2x1 + x2 + 2
Ta có: ∇f (x) =
.
x1 + 2x2 + 2


−2

2 1


Giải hệ ∇f (x) = 0 ta được điểm dừng x∗ =  3 . Vì ∇2 f (x) =
−2
1 2
3
2 1
là ma trận đối xứng, xác định dương nên ∇2 f (x) =
là hàm lồi
1 2
chặt, điểm dừng x∗ là nghiệm cực tiểu của bài tốn.
Ta có: ∇f (x) =

và ∇2 f (x) =

Nguyễn Ngọc Bảo - Cao học khóa 2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Trang 20


Luận văn thạc sĩ - Chuyên ngành Toán Ứng Dụng

1.4

Trang 21

Bài tốn quy hoạch phi tuyến có ràng buộc

Bài tốn quy hoạch phi tuyến có ràng buộc được phát biểu như sau:
min f (x) với điều kiện x ∈ X (B rb )
trong đó X ⊂ Rn và hàm số f xác định trên X.

1.4.1

Điều kiện tối ưu

Định nghĩa 1.7. Cho dãy {xq } ⊂ Rn hội tụ đến x0 ∈ Rn . Ta nói dãy {xq }
v
hội tụ đến x0 theo hướng v ∈ Rn , kí hiệu {xq } →
− x0 , nếu tồn tại dãy số
dương {tq } , lim tq = 0 sao cho xq = x0 + tq v + o(tq ).
v
Nói cách khác {xq } →
− x0 , nếu tồn tại dãy số dương {tq } , lim tq = 0 sao
q
0
cho lim x t−x
= v.
q
Định nghĩa 1.8 Cho X ⊂ Rn . Tập tất cả các hướng v ∈ Rn , sao cho có
một dãy {xq } ⊂ X hội tụ đến x0 ∈ Rn theo hướng v ∈ Rn tạo thành một
nón. Ta gọi đó là nón tiếp xúc với X tại x0 ∈ X, kí hiệu là T (X, x0 ), cụ
v
thể T (X, x0 ) := {v ∈ Rn |∃{xq } ⊂ X sao cho {xq } →
− x0 }.
Định lý 1.9. ([10] trang 245)
i) Giả sử f khả vi trên một tập mở chứa X. Nếu x∗ ∈ X là nghiệm
cực tiểu địa phương của bài toán (B rb ) thì ∇f (x∗ ), v
0, ∀v ∈
∗
T (X, x );
ii) Ngược lại nếu x∗ ∈ X thỏa điều kiện ∇f (x∗ ), v > 0, ∀v ∈ T (X, x∗ )\{0}

thì x∗ là nghiệm tối ưu địa phương chặt của bài tốn (B rb ).
Ví dụ 1.4 Xét bài toán min{f (x1 , x2 ) = x21 − 4x22 |x21 + x22 1}.
Tập chấp nhận được của bài toán là hình trịn đóng B(0, 1) có tâm O và
bán kính 1.
Ta có: ∇f (x) = (2x1 −8x2 )T , điểm dừng x0 = (0, 0)T . Vì x0 ∈ int B(0, 1)
nên T (B(0, 1), x0 ) = R2 và ∇f (x0 ), v = 0, v ∈ T (B(0, 1), x0 ).
Tuy
0
nhiên x không phải nghiệm cực tiểu địa phương của bài tốn vì f (0, ±ε) =
−ε2 < 0, ∀ε.
Hệ quả 1.4. ([10] trang 246) Giả sử x∗ ∈ int X và x∗ là điểm cực tiểu địa
phương của bài tốn (B rb ). Khi đó ∇f (x∗ ) = 0.
Định lý 1.10.([10] trang 247) Cho f là một hàm lồi khả vi trên một mở
chứa tập lồi X ⊂ Rn . Điều kiện cần và đủ để x∗ ∈ X là điểm cực tiểu
toàn cục của bài toán quy hoạch lồi min{f (x)|x ∈ X} là ∇f (x∗ ), v
0, ∀v ∈ T (X, x∗ ).
Hệ quả 1.5.([10] trang 247) Cho f là một hàm lồi khả vi trên một tập
Nguyễn Ngọc Bảo - Cao học khóa 2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Trang 21


Trang 22

Luận văn thạc sĩ

mở chứa tập lồi X ⊂ Rn . Điểm x∗ ∈ X là điểm cực tiểu tồn cục của bài
tốn quy hoạch lồi min{f (x)|x ∈ X} khi và chỉ khi ∇f (x∗ ), x − x∗
0, ∀x ∈ X.
Xét bài toán quy hoạch phi tuyến minf (x) với điều kiện x ∈ X(B1rb )
gi (x) 0, i = 1, ..., m
trong đó X ⊂ Rn là tập nghiệm của hệ

hj (x) = 0, j = 1, ..., k
với f, gi , hj là các hàm khả vi trên Rn
Nhận xét 1.4.
i) Nếu gi (x), i = 1, ..., m là các hàm lồi và hj (x), j = 1, ..., k là các hàm
afin thì X là tập lồi, đóng. Nếu thêm điều kiện f là hàm lồi thì bài
tốn (B1rb ) là bài tốn quy hoạch lồi
ii) Do mọi hàm afin đều là hàm lồi nên quy hoạch tuyến tính là một
trường hợp riêng của quy hoạch lồi.
Cho x0 ∈ X là một nghiệm chấp nhận được của bài toán (B1rb ). Đặt
I(x0 ) := {i ∈ {1, ..., m}|gi (x0 ) = 0} là tập các chỉ số của các ràng buộc
gi (x) = 0, i = 1, ..., m thỏa mãn chặt tại x0 .
Kí hiệu S(x0 ) là tập hợp các vectơ v thỏa mãn hệ tuyến tính sau:
∇hj (x0 ), v = 0, j = 1, ..., k
∇gi (x0 ), v ≤ 0, i ∈ I(x0 )
Nhận xét 1.5. Với mọi x0 ∈ X, ta có T (X, x0 ) ⊆ S(x0 )
Định nghĩa 1.9. Ta nói điều kiện chính quy (regular condition) được thỏa
mãn tại x0 nếu T (X, x0 ) = S(x0 )
Định lý 1.11.([10] trang 250) Ta nói điều kiện chính quy được thỏa mãn
tại x0 nếu có một trong các điều kiện sau:
i) Các hàm hj (x), j = 1, ..., k và gi (x), i = 1, ..., m đều là các hàm afin
ii) Các hàm hj (x), j = 1, ..., k là afin; các hàm gi (x), i = 1, ..., m là lồi
và điều kiện Slater sau đây thỏa:
∃x ∈ Rn : gi (x) < 0, i = 1, ..., m và hj (x), j = 1, ..., k
iii) Các vectơ {∇gi (x0 ), i ∈ I(x0 )} và {∇hj (x0 ), j = 1, ..., k} độc lập
tuyến tính.
Điều kiện thứ nhất hoặc thức 2 của Định lý 1.10 đảm bảo điều kiện
chính quy thỏa mãn tại mọi điểm chấp nhận được của bài tốn đang
xét mà khơng cần chỉ rõ điểm x0 nào, còn điều kiện thứ ba đòi hỏi
phải biết điểm x0


Nguyễn Ngọc Bảo - Cao học khóa 2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Trang 22


Luận văn thạc sĩ - Chuyên ngành Toán Ứng Dụng

Trang 23

Định lý 1.12.([10] trang 250) (Định lý Karush-Kuhn-Tucker ) Cho các
hàm f, gi , i = 1, ..., m và hj , j = 1, ..., k là các hàm khả vi liên tục trên
một tập mở chứa X. Giả sử x∗ là nghiệm cực tiểu địa phương của bài
toán (B1rb ) và điều kiện chính quy được thỏa mãn tại x∗ . Khi đó điều kiện
Karush-Kuhn-Tucker (điều kiện KKT) sau đúng:
i) gi (x∗ )

0, i = 1, ..., m và hj (x∗ ) = 0, j = 1, ..., k

ii) Tồn tại các số λi
∇f (x∗ ) +

m
i=1

0, i = 1, ..., m và các số µj , j = 1, ..., k sao cho

λi ∇gi (x∗ ) +

k

µj ∇hj (x∗ ) = 0


j=1

iii) λi gi (x∗ ) = 0, ∀i = 1, ..., m (Điều kiện bù)
Ví dụ 1.5. Xét bài toán min{−(x21 + 4x22 )|x1 1}
Bài toán này có m = 1, k = 0 và hàm mục tiêu f (x) = −(x21 + 4x22 ) là
hàm lõm chặt. Vì g1 = x1 − 1 là hàm afin nên điều kiện chính quy được
thỏa mãn tại mọi điểm chấp nhận được.
−2x1
1
Ta có ∇f (x) =
và ∇g1 (x) =
−8x2
0
Điều kiện KTT tương ứng của bài toán này là:



x1 − 1 0


g
(x)
=
x
−
1
0


1

1




 −2x1 + λ1 = 0
 ∇f (x) + λ ∇g (x) = 0
1
1
⇔ −8x2 = 0


λ
g
(x)
=
0
1
1




λ1 (x1 − 1) = 0




λ1 0
λ

0
1
Giải hệ này ta được hai điểm KTT là (0, 0) ứng với λ1 = 0 và (1, 0) ứng
với λ2 = 2. (0, 0) là nghiệm cực đại tồn cục và (1, 0) khơng là điểm cực
đại hay cực tiểu địa phương.
1.4.2

Bài toán Quy hoạch tồn phương

Bài tốn Quy hoạch tồn phương được phát biểu như sau:
min f (x) = 21 xT Qx + cT x, với điều kiện Ax b.
Trong đó: Q là ma trận cấp n × n đối xứng và nửa xác định dương, A là
ma trận m × n ; b ∈ Rm ; c, x ∈ Rn .


Ax b



 Qx + c + AT λ = 0
Theo Định lý 1.11, thay vì giải bài tốn này, ta giải hệ KKT
.

λ 0



 λT (Ax − b) = 0
Nguyễn Ngọc Bảo - Cao học khóa 2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Trang 23



Trang 24

Luận văn thạc sĩ

Ví dụ 1.6. Giải bài tốn min f, f (x) = 21 x21 + 5x1 + 4x2 . Với các ràng
buộc x1 0; x2 0; x1 + 2x2 13; 2x1 + 5x2 100; 3x1 + 4x2 80.
Giải.
T
T
x
1
0
x
5
x1
1
1
Bài toán được viết lại: min 21
+
.
x2
0 0
x2
4
x2





−1 − 2
−13
0

 x1


Với:  2
5 
x.
 100  .;
x2
0
3
4
80
Sử dụng Matlab:
H = diag([1;0]);
f = [5;4];
A = [-1 -2; 2 5; 3 4];
b=[-13; 100; 80];
L= zeros(2,1);
options=optimset(’Algorithm’,’interrior-point-convex’);
[x, f val]=quadrog(H,f,A,b,[ ],[ ], options)
Sau khi chạy phần mềm, ta được kết quả (0; 6.5), f val = 26.

Nguyễn Ngọc Bảo - Cao học khóa 2013 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Trang 24


Chương 2

ĐIỀU TIẾT TỐI ƯU HỒ THỦY
ĐIỆN ĐẠI NINH
2.1

Giới thiệu nhà máy thủy điện Đại Ninh

Nhà máy thủy điện Đại Ninh nằm trên địa bàn 2 tỉnh Lâm Đồng và
Bình Thuận, bắt đầu hoạt động từ năm 2008, là nhà máy thủy điện có
cơng suất phát điện đứng thứ 5 ở Việt Nam.

Hình 2.1: Cửa xả tràn nhà máy thủy điện Đại Ninh
Phân loại nhà máy thủy điện:
Nhà máy thủy điện gồm các loại: nhà máy thủy điện chiến lược đa mục
tiêu; nhà máy thủy điện bậc thang; nhà máy thủy điện có hồ chứa điều
tiết trên 1 tuần; nhà máy thủy điện có hồ chứa điều tiết từ 2 ngày đến 1
tuần; nhà máy thủy điện có hồ chứa điều tiết dưới 2 ngày.
25