ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC SƯ PHẠM
——————————–

TRẦN XUÂN LỢI

ỨNG DỤNG PHƯƠNG PHÁP TỐI ƯU
GIẢI BÀI TỐN HÌNH HỌC PHỔ THÔNG

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

Đà Nẵng - 2019


ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC SƯ PHẠM
——————————–

TRẦN XUÂN LỢI

ỨNG DỤNG PHƯƠNG PHÁP TỐI ƯU
GIẢI BÀI TỐN HÌNH HỌC PHỔ THƠNG

Chun ngành: Phương pháp Tốn sơ cấp
Mã số: 8.46.01.13

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

Người hướng dẫn khoa học:
TS. HOÀNG QUANG TUYẾN

Đà Nẵng - 2019


LỜI CAM ĐOAN

Luận văn này là cơng trình nghiên cứu của riêng tơi và được hồn thành dưới sự
hướng dẫn của TS. HOÀNG QUANG TUYẾN. Luận văn chưa từng được cơng bố
trong các cơng trình của người khác. Tơi xin chịu trách nhiệm với những lời cam đoan
của mình.
Tác giả

¼�

Trần Xuân Lợi


TRANG THONG TIN LU�N VAN TH�C Si
Ten d� tai: Ap d1,mg plmong phap t6i U'U giai bai toan hlnh hQC ph6 thong.
Nganh: Phuo-ng phap Toan so· dp.
HQ va ten hQc vien: Tr!n Xuan LQ'i
Ng'oi hU'o'ng d§n khoa hQc: TS. Hoang Quang Tuyen
CO' SO' dao t�o: Dti hQc Ba N�ng - Trucmg Dti hQc Su phtm
Tom tit:
Cac bai toan qrc trj trong chu'O'ng trlnh ph6 thong thucmg la nhung bai toan kh6 nhung lii
ming den nhi€u j nghia trong th1,rc ti€n. Ngoai nhG'ng each giai bing phuong phap hlnh hQC thu!n tty,
ta con c6 th€ hlnh tht'c h6a lti va dung c6ng C\l giai tich t€ giai. Trong d6 m9t s6 cac phu'O'ng phap t6i
uu rrt h'u hi�u khi giai cac bai toan c1,rc tri hlnh hQc nay, nhu cac di€u ki�n t€ c6 nghi�m t6i uu,
phuo-ng phap nhan t:'.r Lagrange, dinh Ii Kuhn-Tucker.
Trong lu�n van nay trinh bay lti m9t s6 kien thrc v€ giai tfch 16i nhu: t�p 16i, ham 16i, cac dinh
Ii lien quan, mo hinh t>ng quat CUa m9t bai toan t6i U'U Va CaC phuo-ng phap d€ giai Chung.

Lu�n van t�p trung giai quy�t cac bai toan crc tri hinh h9c lien quan d�n cac y�u t6 nhu
khoang each, g6c, di�n tich, th€ tfch. Ngoai ra con dua vao m9t s6 bai toan t6i U'U thvc te kinh di€n
nlm: bai toan tlm du·o·ng di ngln nhtt, bai toan cit v�t li�u ti�t ki�m nhtt, cht'ng minh lii dinh lu�t
kh(1c xci anh sang theo phuong phap t6i uu.
Lu�n van du9·c chia lam hai chu'O'ng. Trong chu'O'ng 1, toi neu lti mo hlnh bai toan U'U, cac khai
ni�m lien quan Y€ giai tfch ]6i Cung nhU' dtra vao m9t S6 phU'O'ng phap va di€u ki�n t6i U'U d€ giai. )
clmo-ng 2 t6i t�p trung giai quy�t cac bai toan qrc tri hlnh h9c trong chu'O'ng trlnh pp6 thong cung nhu
giai quy�t m9t s6 bai toan hlnh hQC khac d1ra vao ph!n m€m Matlab.
Hy VQng ring cac k�t qua cua ]u�n van se dLl'Q'C mer r9ng, d6ng tho·i ]a tai li�u tham khao b6 ich
vao vi�c dty Va hQC Toan CJ b�c ph6 thong, cung nhu vi�c nghien Cl'U cua giang Vien sinh vien O' b�ic
Dti h9c.
Tir khoa: Giai tfch h6a bai toan qrc trf hlnh h9c, diiu kiin t5i uu, Nhan tir Lagrange, dfnh l£ Kuhn­
Tucker, CfC trf hlnh h9c.
Xac nhin c'

Ngl'o'i thvÃc hin d tai

ẳ

TrĐn Xuan LQ'i



MỤC LỤC

Mở đầu

1

CHƯƠNG 1. Những kiến thức liên quan


4

1.1. Một số bài toán tối ưu và ý nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1. Ví dụ bài tốn tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.2. Ý nghĩa thực tiễn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2. Mơ hình và phương pháp giải bài tốn tối ưu . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1. Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.2. Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.3. Tính chất cực trị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.4. Mơ hình bài tốn tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3. Những nguyên lí cơ bản của các phương pháp tối ưu . . . . . . . . . . . . . . 13
1.3.1. Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3.2. Đối ngẫu Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3.3. Định lý Kuhn-Tucker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
CHƯƠNG 2. Áp dụng phương pháp tối ưu giải các bài tốn cực trị hình
học phổ thơng

21

2.1. Áp dụng trong hình học phẳng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.1. Một số bài toán cực trị về khoảng cách . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.2. Một số bài toán cực trị về chu vi và diện tích . . . . . . . . . . . . . . . . . . . . . . . . 27


2.1.3. Một số bài tốn cực trị về góc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.2. Áp dụng trong hình học khơng gian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.2.1. Một số bài tốn cực trị về thể tích khối chóp . . . . . . . . . . . . . . . . . . . . . . . . 35
2.2.2. Một số bài toán cực trị về thể tích hình lăng trụ và hình nón . . . . . . . . 39
2.3. Áp dụng thuật tốn tối ưu giải bài tốn tìm đường đi ngắn nhất trên

mạng giao thông . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.3.1. Mơ hình tốn học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.3.2. Thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.3. Ví dụ cho thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.4. Giải bài tốn quy hoạch tuyến tính hai biến bằng phương pháp hình
học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.4.1. Mơ hình tốn học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.4.2. Thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.4.3. Ví dụ cho thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.5. Bài toán cắt vật liệu tiết kiệm nhất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.5.1. Mơ hình tốn học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.5.2. Thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.5.3. Ví dụ cho thuật tốn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2.5.4. Lập trình thuật toán giải bài toán trên Matlab . . . . . . . . . . . . . . . . . . . . . . 64
Kết luận

69

Tài liệu tham khảo

70


LỜI CẢM ƠN

Để hoàn thành đề tài luận văn thạc sĩ, bên cạnh sự nỗ lực cố gắng của bản thân
cịn có sự chỉ bảo nhiệt tình của q thầy cơ, cũng như sự động viên ủng hộ của gia
đình và bạn bè trong suốt thời gian học tập, nghiên cứu và thực hiện luận văn.
Trước hết, tôi xin gửi lời cảm ơn chân thành nhất tới thầy giáo – TS. Hồng Quang
Tuyến đã hết lịng quan tâm giúp đỡ, hướng dẫn tơi hồn thành luận văn này trong

thời gian qua.
Tơi cũng xin bày tỏ lịng biết ơn sâu sắc đến các quý Thầy, Cô giáo và Ban chủ
nhiệm Khoa Toán, Trường Đại Học Sư Phạm - Đại Học Đà Nẵng đã tận tình truyền
đạt những kiến thức quý báu và tạo điều kiện thuận lợi nhất cho tôi trong suốt quá
trình học tập nghiên cứu cho đến khi thực hiện đề tài luận văn.
Cảm ơn các anh, chị và các bạn trong lớp Cao Học Phương pháp Toán sơ cấp
Khóa 35 đã hỗ trợ tơi rất nhiều trong q trình học tập và nghiên cứu.
Do điều kiện thời gian cũng như kinh nghiệm còn hạn chế nên luận văn khơng thể
tránh khỏi những thiếu sót. Tơi rất mong nhận được sự chỉ bảo, đóng góp ý kiến của
các thầy cơ để tơi có thể bổ sung và hồn thiện luận văn một cách tốt hơn.
Tôi xin chân thành cảm ơn!
Đà Nẵng, ngày 30 tháng 9 năm 2019.
Tác giả

Trần Xuân Lợi


NHỮNG KÍ HIỆU DÙNG TRONG LUẬN VĂN

N

Tập hợp các số nguyên dương

R

Tập hợp các số thực

Rn

Không gian Euclid n chiều


x, y

Tích vơ hướng của x và y

x

Chuẩn Euclid của x

f ′ (x0 , d)

Đạo hàm theo hướng của hàm f theo hướng d tại x0

∇f (x)

Véc-tơ Gradient của hàm f tại điểm x

∇2 f (x)

Ma trận Hesse của hàm f tại điểm x

fx′ i

Đạo hàm riêng của f theo biến xi

[x, y]

Đoạn thẳng nối giữa hai điểm x và y

[ABC]


Diện tích tam giác ABC

L(x, λ)

Hàm Lagrange

AT

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

v.đ.k

với điều kiện


1

MỞ ĐẦU

1. Lý do chọn đề tài
Ngay từ thế kỉ XVII L. Euler đã viết: “Vì thế giới được thiết lập một cách hồn
hảo nhất và vì nó là sản phẩm của đấng sáng tạo tinh thông nhất, nên không thể tìm
thấy cái gì mà khơng mang theo tính chất cực đại hay cực tiểu nào đó ”. Điều đó cho
chúng ta thấy rằng, vấn đề cực trị trong cuộc sống và trong tốn học, ln là một
điều tất yếu. Ngay từ xa xưa, người ta cũng đã mong muốn tạo ra những cái lớn nhất,
nhanh nhất và tốt nhất nhưng lại tốn ít thời gian, cơng sức và của cải nhất. Chính
từ những nhu cầu đó mà bài tốn cực đại và cực tiểu nói chung hay là bài tốn cực
trị chiếm một vai trị rất lớn trong Tốn học cũng như trong cuộc sống.
Trong chương trình Tốn phổ thơng, bài tốn về cực trị nói chung hay về cực trị

hình học nói riêng ln là một trong những bài tốn khó, khó cho cả học sinh lẫn
giáo viên. Vì vậy trong luận văn này, chúng tơi sẽ trình bày lại một cách hệ thống về
các bài toán cực trị hình học trong chương trình tốn phổ thơng, và cách giải chúng
thơng qua các phương pháp tối ưu. Ngồi ra chúng tơi cũng sẽ trình bày thêm một
số bài tốn tối ưu hình học xuất phát từ thực tế và cách giải chúng với những thuật
tốn được lập trình trên phần mềm Mathlab, để giúp học sinh phổ thông cũng như
giáo viên dạy Tốn có cái nhìn mới mẻ hơn về việc giải quyết một vấn đề Toán học
bằng cơng cụ hỗ trợ là máy tính.
Với những lý do trên, dưới sự hỗ trợ của giáo viên hướng dẫn TS. Hồng Quang
Tuyến tơi quyết định lựa chọn đề tài: “Áp dụng phương pháp tối ưu giải bài tốn hình


2

học phổ thơng”.
2. Mục đích nghiên cứu
Mục đích của đề tài nhằm nghiên cứu và làm rõ các vấn đề: Các phương pháp tối
ưu, các bài toán cực trị trong hình học phẳng, hình học khơng gian,... Từ đó giải các
bài tốn cực trị hình học trong chương trình phổ thơng và một số bài tốn hình học
khác.
3. Đối tượng nghiên cứu
Mơ hình bài tốn tối ưu, các phương pháp giải bài tốn tối ưu, các bất đẳng thức
trong hình học phẳng, hình học khơng gian và các bài tốn cực trị hình học liên quan.
4. Phạm vi nghiên cứu
- Các phương pháp giải bài toán tối ưu.
- Các bài tốn cực trị hình học trong chương trình phổ thơng.
- Một số bài tốn tối ưu hình học thực tế.
- Lập trình giải tốn trên phần mềm Matlab.
5. Phương pháp nghiên cứu
Luận văn được nghiên cứu dựa trên các phương pháp:

- Tham khảo tài liệu liên quan đề tài từ: sách giáo khoa, sách giáo viên, giáo trình
giảng dạy cao học và từ mạng internet.
- Phân tích, nghiên cứu các tài liệu đã chọn lọc.
- Sử dụng phần mềm Matlab để lập trình tìm nghiệm của các bài tốn tối ưu.
- Trao đổi thảo luận với thầy giáo hướng dẫn.


3

6. Ý nghĩa khoa học và thực tiễn của đề tài
- Bổ sung thêm tài liệu trong việc giảng dạy tốn học phổ thơng.
- Làm tài liệu tham khảo trong việc áp dụng phương pháp tối ưu để giải các bài
toán thực tế.
- Giúp người đọc tiếp cận về việc giải tốn bằng lập trình trên phần mềm Matlab.
7. Cấu trúc luận văn
Ngoài phần mở đầu và kết luận, tài liệu tham khảo, luận văn gồm 02 chương:
• Chương 1: Kiến thức chuẩn bị

Chương này trình bày cơ đọng một số khái niệm cơ bản của giải tích lồi, mơ hình
bài tốn tối ưu và một số phương pháp giải bài toán tối ưu như: phương pháp
hướng chấp nhận được, định lý Kuhn-Tucker phương pháp nhân tử Lagrange.
• Chương 2: Áp dụng phương pháp tối ưu để giải các bài tốn cực trị

hình học
Chương này trình bày các bài tốn cực trị hình học, các yếu tố hình học về
khoảng cách, góc, diện tích, thể tích và sử dụng các phương pháp tối ưu để giải.
Ngồi ra cịn trình bày thêm các bai toán tối ưu khác như bài toán tìm đường
đi ngắn nhất, bài tốn cắt vật liệu tiết kiệm nhất cũng như cách giải trên phần
mềm Matlab.



4

CHƯƠNG 1

NHỮNG KIẾN THỨC LIÊN QUAN

Chương này nhắc lại một số khái niệm cơ bản về bài toán cực trị có hoặc khơng
có ràng buộc. Các khái niệm cơ bản về tập lồi, hàm lồi,... và các định lí liên quan đến
các khái niệm trên.

1.1. Một số bài toán tối ưu và ý nghĩa
1.1.1. Ví dụ bài tốn tối ưu

Bài tốn 1.1. Vẽ nội tiếp trong hình trịn với bán kính cho trước một hình chữ nhật
có diện tích lớn nhất.
Bài tốn 1.2. Cho tam giác ABC . Hãy tìm điểm E trên cạnh BC sao cho hình bình
hành ADEF , với D, F nằm trên AB và AC có diện tích lớn nhất.
Bài tốn 1.3. Người ta muốn xây một nhà kho để chứa hàng dạng hình hộp chữ
nhật. Cho trước một số lượng vật liệu nhất định, làm thế nào để xây được một nhà
kho có thể tích lớn nhất.
1.1.2. Ý nghĩa thực tiễn

Những bài toán trên là một vài ví dụ về bài tốn tối ưu trong lí thuyết thuần túy
hoặc trong thực tế. Để giải những bài tốn trên, ngồi phương pháp hình học thuần
túy ta có thể mơ hình hóa lại bài tốn dưới dạng giải tích.
Quay lại với Bài tốn 1.1. Ta có thể mơ hình hóa lại bài tốn trên dưới dạng giải
tích như sau:



5

Giả sử đường trịn được mơ tả bởi phương trình x2 + y 2 = r2 (r > 0 cho trước), vẽ
các trục Ox và Oy song song với các cạnh của hình chữ nhật.
Kí hiệu (x, y) là tọa độ của đỉnh hình chữ nhật tại góc phần tư thứ nhất (hình
1.1).

Hình 1.1

Khi đó diện tích hình chữ nhật bằng 4xy .
Từ đó ta có bài tốn: tìm cực đại của hàm hai biến f (x, y) = 4xy với các điều kiện:
i) g1 (x, y) = x2 + y 2 − r2 = 0;
ii) g2 (x, y) = x

0;

ii) g3 (x, y) = y

0.

Qua ví dụ trên ta có thể thấy những bài tốn hình học có thể được chuyển sang
ngơn ngữ giải tích, và trên thực tế có rất nhiều bài tốn khi hình thức hóa lại như


6

vậy ta sẽ có hướng tiếp cận và giải quyết dễ dàng bằng những công cụ khác. Một cách
tổng quát, bất kì bài tốn nào đã hình thức hóa cũng có thể được xây dựng theo cách
tương tự, bao gồm các yếu tố sau:
Phiếm hàm f : X → R ∪ {−∞; +∞} Trong đó f là phiếm hàm và ràng buộc D ⊂ X .

Như vậy, ta có thể phát biểu lại bài toán 1 theo cách như sau:
f : R2 → R
maxf (x, y):= max 4xy

Với ràng buộc x2 + y 2 = r2 , x

0, y

Ràng buộc ở đây là tập D = {(x; y) ∈ R2 : x2 + y 2 = r2 , x

0
0, y

0}.
r
2

Hình chữ nhật cần tìm trong bài tốn này chính là hình vng cạnh bằng √ ,
tương ứng với nghiệm (x; y) =

r
r
√ ,√
2 2

và fmax = 2r2 tương ứng diện tích hình chữ

nhật lớn nhất khi đó là 2r2 .

1.2. Mơ hình và phương pháp giải bài tốn tối ưu

Trước tiên ta nhắc lại một số định nghĩa và định lý quan trọng của giải tích lồi.
1.2.1. Tập lồi

Định nghĩa 1.4. Đường thẳng đi qua hai điểm a, b trong không gian Euclid n-chiều
Rn là tập hợp các điểm x ∈ R
x = λa + (1 − λ) b, λ ∈ R.

Định nghĩa 1.5. Đoạn thẳng nối hai điểm a, b trong Rn là tập hợp các điểm x ∈ R
có dạng
x = λa + (1 − λ) b, 0

λ

1.


7

Định nghĩa 1.6. Siêu phẳng trong Rn là tập
{x = (x1 , x2 , ...xn ) |x1 a1 + x2 a2 + ... + xn an = α, ai ∈ R, ∀i = 1..n, α ∈ R}.

Định nghĩa 1.7. (Tập lồi) Tập D ⊂ Rn được gọi là tập lồi nếu
∀a, b ∈ D và λ ∈ [0; 1] ta có λa + (1 − λ) b ∈ D.

Định nghĩa 1.8. (Nón lồi) Tập D ⊂ Rn được gọi là nón lồi nếu
∀a, b ∈ D thì x + y ∈ D và tx ∈ D, ∀t

0.

Định nghĩa 1.9. (Bao lồi) Bao lồi của tập A là tập lồi nhỏ nhất chứa A. Kí hiệu

CovA .

Định nghĩa 1.10. (Tổ hợp lồi của hai tập hợp)
Cho A ⊂ Rn , B ⊂ Rn , tổ hợp lồi của A và B là tập hợp các điểm thuộc Rn có dạng
x = λa + (1 − λ) b, a ∈ A, b ∈ B, 0

λ

1.

Định lý 1.1. Tập lồi là đóng với phép giao, phép cộng, phép nhân với một số và phép
lấy tổ hợp tuyến tính. Tức là nếu A, B là hai tập lồi trong Rn thì các tập sau đây
cũng lồi:
i) A ∩ B := {x|x ∈ A, x ∈ B}.
ii) αA + βB := {x = αa + βb|a ∈ A, b ∈ B, α, β ∈ R}.
1.2.2. Hàm lồi

Trong luận văn này chỉ xét các hàm số thực và nhận giá trị hữu hạn.
Định nghĩa 1.11. ∀x, y ∈ A, 0

λ

1

• Hàm số f xác định trên tập lồi A được gọi là hàm lồi trên A nếu:
f (λx + (1 − λ) y)

λf (x) + (1 − λ) f (y) , ∀x, y ∈ A, 0

λ


1.


8

• Hàm f được gọi là lồi chặt nếu :
f (λx + (1 − λ) y) < λf (x) + (1 − λ) f (y) , ∀x, y ∈ A, 0 < λ < 1.
• Hàm f được gọi là tựa lồi (quasi convex) trên A nếu:
∀λ ∈ R, tập mức {x ∈ A|f (x)

λ} là một tập lồi.

• Hàm f được gọi là tựa lõm (quasi concave) trên A nếu −f tựa lồi.

Định nghĩa 1.12. Các hàm λf , f + g và max (f, g) được định nghĩa như sau:

(λf ) := λf (x)
(f + g) (x) := f (x) + g (x)
max (f, g) := max{f (x) , g (x)}.

Định lý 1.2. Cho f là hàm lồi trên tập lồi A và g là hàm lồi trên tập lồi B . Lúc đó
trên A ∩ B các hàm sau là lồi:
i) λf + βg, ∀λ, β

0.

ii) max (f, g).
Định lý 1.3. Một hàm lồi xác định trên tập lồi A thì liên tục tại mọi điểm trong của
A.

• Chú ý: Hàm lồi xác định trên tập lồi thì liên tục tại mọi điểm trong, chưa chắc liên

tục trên điểm biên.
• Kí hiệu: f ′ (a) hoặc ∇f (a) là đạo hàm của f tại a.

Định lý 1.4.


9

1. Cho f : A → R là một hàm khả vi trên tập lồi mở A. Điều kiện cần và đủ để f lồi
trên A là:
f (x) + ∇f (x) , y − x

f (y) , ∀x, y ∈ A.

2. Nếu f khả vi hai lần thì f lồi trên A khi và chỉ khi ∀x ∈ A ma trận Hesse H (x)
của f tại x xác định không âm, tức là:
y T H (x) y

0, ∀x ∈ A, y ∈ Rn .

Chú ý: Tính khả vi của một hàm lồi giữ vai trò quan trọng bậc nhất trong tối ưu
hóa.
Định nghĩa 1.13. Ta gọi đạo hàm theo hướng d của một hàm số f (không nhất thiết
lồi) tại x là một đại lượng số:
f ′ (x, d) := lim+
λ→0

f (x + λd) − f (x)

λ

nếu giới hạn này tồn tại.
Định lý 1.5. Nếu f là một hàm lồi trên tập A thì ∀x ∈ A và ∀d ∈ Rn sao cho x+d ∈ A
đạo hàm theo hướng d của f tại x luôn tồn tại và nghiệm đúng
f ′ (x, d)

f (x + d) − f (x) .

Ngoài ra, với mỗi x cố định, f ′ (x, .) là một hàm lồi trên tập lồi {d : x + d ∈ A}.
Từ định lí trên ta rút ra được nhận xét:
• Nếu f khả vi thì f ′ (x, d) = ∇f (x) , d , ∀d.
• Hàm lồi chưa chắc khả vi tại mọi điểm.

Định nghĩa 1.14. Cho f là một hàm lồi trên tập lồi A. Một vector y ∗ ∈ Rn được gọi


10

là dưới vi phân tại x∗ ∈ A nếu
f (x∗ ) + y ∗ , x − x∗ , ∀x ∈ A.

f (x)

Tập các điểm y ∗ thỏa mãn bất đẳng thức này được kí hiệu ∂f (x∗ ).
Trường hợp ∂f (x∗ ) chỉ có một điểm ta nói f khả vi tại x∗ .
Nhận xét 1.1.
1. Tương tự trường hợp hàm một biến, bất đẳng thức
f (x)


f (x∗ ) + y ∗ , x − x∗ , ∀x ∈ A,

có nghĩa rằng siêu phẳng đi qua điểm (x∗ , f (x∗ )) nằm dưới đồ thị hàm số.
2. Tập ∂f (x∗ ) có thể rỗng, tuy nhiên với hàm lồi thì khác rỗng.
Định lý 1.6. Cho f là hàm lồi (hữu hạn) trên tập lồi A. Khi đó f có dưới vi phân
tại mọi điểm trong tương đối riA
Nhận xét 1.2. Nếu A ≡ Rn thì f có dưới vi phân tại mọi điểm vì riRn ≡ Rn .
1.2.3. Tính chất cực trị

Cho D ⊂ Rn , D = ∅ và hàm số f : D → R (không nhất thiết lồi).
Định nghĩa 1.15. Một điểm x∗ ∈ D được gọi là cực tiểu địa phương của f trên D
nếu tồn tại một lân cận mở U của x∗ sao cho f (x∗ )

f (x) với mọi x ∈ D ∩ U . Điểm

x∗ được gọi là cực tiểu tuyệt đối (toàn cục) của f trên D nếu:
f (x∗ )

f (x) , ∀x ∈ D.

Sau đây sẽ là hai tính chất cơ bản về cực trị của hàm lồi:
Định lý 1.7.
i) Mọi điểm cực tiểu địa phương của một hàm lồi trên một tập lồi đều là điểm cực


11

tiểu tuyệt đối.
ii) Nếu x∗ là điểm cực tiểu của hàm lồi f trên tập lồi D và x∗ ∈ intD thì 0 ∈ ∂f (x∗ ).
Định lý 1.8. Cực đại của hàm lồi (nếu có) trên tập lồi có điểm cực biên bao giờ cũng

đạt tại một điểm cực biên.
Định lý 1.9. (Định lí Weierstrass) Một hàm liên tục f trên D compact, khác
rỗng đạt cực tiểu và cực đại trên D.
Định lý 1.10. Nếu x ∈ Rn là một điểm cực tiểu địa phương của một hàm f (x) khả
vi trên Rn thì ∇2 f (x)

0 (ma trận ∇2 f (x)

0 nửa xác định dương).

Ngược lại, nếu x ∈ Rn là một điểm tại đó f (x) hai lần khả vi và
∇f (x) = 0, ∇2 f (x)

0 (ma trận ∇2 f (x) xác định dương),

thì x được gọi là một điểm cực tiểu địa phương chặt của f (x).
1.2.4. Mơ hình bài tốn tối ưu

Nhiều vấn đề thực tế trong các lĩnh vực đều có thể mơ tả dưới dạng một bài tốn
tối ưu. Ta có thể xét một vài ví dụ:
Ví dụ: Một nhà máy sản xuất n loại sản phẩm cần sử dụng m loại nguyên liệu
khác nhau.Gọi xj là số lượng sản phẩm thứ j (j = 1, n) và cj là lãi thu được của một
sản phẩm j . Biết rằng để sản xuất một sản phẩm loại j cần một lượng nguyên liệu
aij j = 1, m . Gọi bi là số lượng tối đa của nguyên liệu i mà xí nghiệp có.

Bài tốn ở đây là cần sản xuất mỗi loại sản phẩm với số lượng bao nhiêu để tổng
lợi nhuận thu được là lớn nhất.
Ta có thể mơ hình hóa toán học bài toán trên như sau:



12

n

max

cj xj
j=1

với điều kiện

n

aij xj

bi , i = 1, m

j=1

xj

0, j = 1, n.

Dạng tổng quát của bài toán tối ưu được mô tả như sau:
min f (x) với điều kiện x ∈ D;

hoặc
max f (x) với điều kiện x ∈ D.

Trong đó, D là một tập (có thể rỗng) trong một khơng gian nào đó, f là hàm số

thực xác định trên một tập chứa D. Thông thường D được mô tả như tập nghiệm
của hệ đẳng thức (bất đẳng thức), cũng có thể là tập nghiệm của hệ phương trình vi
phân (tích phân), D thường được gọi là tập phương án chấp nhận được.
Ngồi ra cịn có:
min{f (x) |x ∈ D} = − max{−f (x) |x ∈ D}.

Như vậy ta thấy có thể đưa bài tốn tìm cực đại về bài tốn tìm cực tiểu và ngược
lại.
Xét bài toán min f (x) với điều kiện x ∈ D, có những khả năng xảy ra đối với
nghiệm tối ưu (tuyệt đối):
1. D là một tập rỗng (khơng có phương án chấp nhận được).


13

2. Cực tiểu của f trên D bằng −∞.
3. Cực tiểu của f trên D hữu hạn nhưng không đạt trên D.
4. f đạt cực tiểu hữu hạn trên D, lúc đó điều kiện x ∈ D thường xuất hiện ở các dạng
sau (có thể cùng lúc ở cả 3 dạng):
- Ràng buộc đẳng thức : F (x) = 0 với F : X → Y .
- Ràng buộc bất đẳng thức fi (x)

0 với fi : X → R, i = 1, ..., m.

- Ràng buộc bao hàm thức x ∈ A, A ⊂ B với A cho trước.
5. Điểm x∗ tại đó f nhận giá trị tối ưu, tức là:
f (x∗ )

f (x) , ∀x ∈ D hay f (x∗ )


f (x) , ∀x ∈ D

được gọi là nghiệm tối ưu toàn cục.
7. Nếu D = X (X là một khơng gian nào đó) thì bài tốn tối ưu trên được gọi là bài
tốn tối ưu khơng ràng buộc, ngược lại gọi là bài toán tối ưu ràng buộc.
Để tổng quát, nhiều khi người ta còn thay inf cho min và sup cho max.

1.3. Những nguyên lí cơ bản của các phương pháp tối ưu
1.3.1. Điều kiện tối ưu

Định nghĩa 1.16. Một vector d = 0 được gọi là hướng chấp nhận được của D tại
x∗ ∈ D nếu tồn tại số thực λ > 0 sao cho:
x∗ + λd ∈ D với mọi 0 < λ

λ.

Tập các hướng chấp nhận được của D tại x∗ được ký hiệu là D(x∗ ) và bao đóng là
D(x∗ ).


14

Định lý 1.11. Giả sử f khả vi trong một tập mở chứa D. Nếu x∗ là cực tiểu địa
phương trên D thì dT ∇f (x∗ )

0 với mọi d ∈ D(x∗ ).

Định nghĩa 1.17. Một vector x∗ ∈ D được gọi là điểm dừng của f trên D nếu
dT ∇f (x∗ )


0 với mọi d ∈ D(x∗ ).

Nhận xét 1.3.
1. Nếu x∗ ∈ int(D) thì D(x∗ ) = Rn và ∇f (x∗ ) = 0.
2. Từ Định lí 1.10 nếu x∗ là cực tiểu địa phương thì x∗ là điểm dừng. Tuy nhiên điều
ngược lại khơng đúng. Ví dụ: 0 là điểm dừng của f (x) = x3 nhưng nó khơng phải
là cực tiểu trên đoạn [a; b] chứa điểm 0 nào. Tuy vậy, với quy hoạch lồi điểm dừng
chính là điểm cực tiểu.
Định lý 1.12. Giả sử D là một tập lồi, f là một hàm lồi khả vi trên tập mở chứa D.
Lúc đó, điều kiện cần và đủ cho x∗ làm hàm f đạt cực tiểu trên D là x∗ là điểm dừng
của f trên D.
Ta xét thêm một số điều kiện mở rộng đảm bảo cho bài tốn có nghiệm tối ưu.
Định nghĩa 1.18. Hàm f : D → R được gọi là nửa liên tục dưới tại điểm x ∈ D nếu
với mỗi ǫ > 0 có một δ > 0 sao cho f (x − ǫ

f (x) với mọi x ∈ D, |x − x| < δ . Hàm f

nửa liên tục trên trên D khi và chỉ khi −f nửa liên tục dưới trên D. Hàm f được gọi
là liên tục trên D nếu nó vừa nửa liên tục dưới, vừa nửa liên tục trên D.
Định lý 1.13. Một hàm f (x) nửa liên tục dưới trên một tập compact D = ∅ phải
đạt cực tiểu trên D. Tương tự, một hàm f (x) nửa liên tục trên trên một tập compact
D = ∅ phải đạt cực đại trên D.

Nếu tập D chỉ đóng mà khơng bị chặn thì một hàm nửa liên tục dưới (nửa liên


15

tục trên) trên D có thể khơng đạt cực tiểu (cực đại) trên D. Tuy vậy ta có:
Định lý 1.14.

i. Một hàm f : D → R nửa liên tục dưới trên một tập đóng D = ∅ mà bức trên D,
(f (x) → +∞ khi x ∈ D thì x → +∞) thì f phải có cực tiểu trên D.

ii. Một hàm f : D → R nửa liên tục trên trên một tập đóng D = ∅ mà −f bức trên D,
(f (x) → −∞ khi x ∈ D thì x → +∞) thì f phải có cực đại trên D.
1.3.2. Đối ngẫu Lagrange

Trong mục này ta sẽ trình bày phương pháp nhân tử Lagrange để tìm điểm cực trị
của những bài toán tối ưu, với ràng buộc đẳng thức và được đưa về dưới dạng hàm
Lagrange.
Định nghĩa 1.19. Xét bài toán
min f0 (x) v.đ.k x ∈ D

D = {x | fi (x) = 0, i = 1, ..., n, fi : Rn → R}.

Gọi
m

L (x, λ0 , λ1 , ..., λm ) =

λi fi (x) là hàm Lagrange.

i=0

Ta có định lí sau:
Định lý 1.15. (Quy tắc nhân tử Lagrange) Cho fi , i = 0, ..., m khả vi liên tục trong
lân cận V ⊂ Rn của x∗ . Nếu x∗ là nghiệm cực tiểu địa phương của bài tốn trên thì
tồn tại các nhân tử Lagrange λi

0, i = 0, 1, ..., m sao cho chúng không cùng triệt tiêu



16

và thỏa mãn
m
′

′

∗

λi fi (x∗ ) = 0.

L (x , λ0 , λ1 , ..., λm ) :=
i=0

Nếu f1 (x∗ ), f2 (x∗ ), ..., fm (x∗ ) độc lập tuyến tính thì λ0 = 0 và có thể chọn bằng 1.
′

′

′

Đề hiểu rõ hơn định lí trên ta xét ví dụ sau:
Ví dụ: Cho hai số thực x, y thỏa mãn điều kiện x + y = 10. Tìm giá trị nhỏ nhất
của biểu thức:
f (x; y) = x2 + y 2 .

Giải:

Bước 1: Thiết lập bài toán cực tiểu đối với hàm f (x; y) = x2 + y 2 thỏa mãn điều
kiện φ(x; y) = x + y − 10 = 0.
Bước 2: Thiết lập hàm Lagrange
L(x; y; λ) = x2 + y 2 + λ(x + y − 10).

Bước 3: Tính các đạo hàm riêng của hàm f và cho bằng 0
−λ
∂f
= 2x + λ = 0 ⇔ x =
.
∂x
2
−λ
∂f
= 2y + λ = 0 ⇔ y =
.
∂y
2
∂f
−λ
= x + y − 10 = 0 ⇒
.2 = 10 ⇔ λ = −10.
∂λ
2

Tìm được điểm dừng có tọa độ (5; 5; −10).
Suy ra fmin = f (5; 5) = 52 + 52 = 50.
Qua ví dụ trên phần nào ta đa nắm được ý tưởng của phương pháp thiết lập hàm
Lagrange để tìm cực trị, bây giờ ta quay lại với Bài tốn 1.
Sau khi đã mơ hình hóa lại bài tốn về dạng giải tích, để giải bài tốn ta sẽ đi tìm