<||V/(x0)||.
Do đó, đạo hàm theo hướng của hàm / tại điểm x° đã cho là lớn nhất khi hướng à = ỊỊv/^A WỈL nhỏ nhất khi d = -ị^ịfí)]ịị hay giá trị hàm tăng nhanh nhất theo hướng gradient và giảm nhanh nhất theo hướng ngược với gradient.
1.2.10 Hàm tuyến tính, hàm afin
Mừt hàm số /(x) xác định trên R" đuợc gọi là tuyến tính nếu
f(Xx1 + fix2) = XỊ{xl) + nf{x2)
với mọi ì1, ì2 € R" và vói mọi A, ụ. 6 R. Mừt hàm tuyến tính xác định trên R" luôn có dạng /(x) = (c, ì), trong đó véc tơ c € R" cho trước.
Hàm tuyến tính có các tính chất rất đặc sắc và hữu ích sau đây:
Mệnh đề 1.3. ì) Các mật mồc cùa hàm tuyến tính song song với nhau; ii) Gradient cùa hàm tuyến tính f(x) = (c, x) tại mọi điểm là như nhau và bằng chính véc tơ c. Véc tơ c cũng chính là véc tơ pháp tuyến cùa các mặt mồc.
Ví dụ 1.8. Xét hàm hai biến f{x) = 3xi + 5x2. Ta có v/(i) = (3,5)T là véc tơ pháp tuyến cùa mỏi đường mức
L(Q, f) = {xe R21 3ii + 5x2 = a} với a 6 1.
Với bất kỳ ai Ỷ a2, L(auf) và L(a2, ỉ) là hai đường thẳng song song với nhau.
Hàm số có dạng f(x) = (c, x) + a, trong đó véc tơ c € R" và a Ễ M cho trước, được gọi là hàm afìn hay hàm tuyến tính afìn. Dễ thấy, nếu f(x) là afin thì
Vx, y € R", VA, ụ. e R mà A + n = Ì ta có /(ÁI + uy) = Xf{x) + nf{y).
16 Các phương pháp tối ưu
1.3 Tập lồi
LU Tậpaíin
Cho x\x2 là hai điểm trong R". Đường thẳng qua ì 1 và ì 2 là tập các điểm I = AX1 + (1-A)I2 = I2 + A(I1-X2) vớiA€K.
Tập M CRn đượ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, tức là
Vi1,!2 € M, A € R =* Ai1 + (Ì - À)i2 € M.
Nói cách khác M là tập afin nếu nó chứa tổ hợp tuyến tính của hai điểm bất kỳ thuừc M với tổng các hệ số bằng 1. Ta gọi mừt điểm X 6 R" có dạng
•
k k
x = Y í ^ x i với Ai,---,Ak eR và 52Ai = Ì
i=l i=l
là /lọp ạ^n của các điểm x\ X2, • • • , xk € Kn. Nếu M c !n là mừt tập afin và 1° G M thì tập
L = M - x° = {x - x° I X £ M)
là mừt không gian con, tức nếu 0, b e L thì mọi điểm c = Xa + ụb với A, ụ. 6 R cũng thuừc L (L đóng với phép cừng và phép nhân vô hướng). Vì vây, mừt tập afin có thể được biểu diễn bởi
M = x° + L = {x° + v\veL},
trong đó 1° e M và L là không gian con. Không gian con L tương ứng vói tập afin M không phụ thuừc vào cách chọn x°, tức x° là điểm bất kỳ thuừc M. Hơn nữa, không gian con L này xác định duy nhất (Bài tập). Ta gọi L là không gian con song song vói M. Thồ nguyên (dimension) hay còn gọi là số chiều của tập afin M là thứ nguyên cùa không gian con song song với nó.
Bao afin (affine hull) của mừt tập E c Rn là giao của tất cả các tập afin chúa E. Đó là tập afin nhỏ nhất chứa E, ký hiệu là aSE.
Ví dụ 1.9. Tập nghiệm M cùa hệ phương trình tuyến tính Ax = b, trong đó Ả là ma trận cấp m X n và véc tơ 6 € K m, là mừt tập afin. Thật vậy, với hai điểm tùy ý X1, X2 £ ử, và số thực bất kỳ A € R ta có
^(Ax1 + (Ì - A)x2) = XAx1 + (Ì - Ằ)Ar2
= A6 + (Ì - À)6
= 6.
Chương 1. Một sổ khái niệm và kết quà cơ bàn từ giải tích lồi 17
Điêu đó chúng tỏ Xx1 + (Ì - À)i 2 e M. Theo định nghĩa, M là mừt tập afin. Không gian con song song vói M là L = KerA := {x e Kn I Ax = 0}. Vì vậy, thứ nguyên của tập M bằng thứ nguyên của không gian con L = KeiA và bằng n - rankẠ trong đố ranL4 là hạng của ma trân Ả.
Ví dụ 1.10. i) Bao afin của tập Ei = {a, b} gồm hai điểm phân biệt 0, b G R3 là đường thẳng đi qua a và b, tức aSEi = {x é R31 X = Xa + (Ì - X)b, X € R}; li) Bao afín của tập EĩỊ = {x e ũ3 ị 0 < Xi < Ì, 0 < Xa < Ì, Xi = 0} là cả mặt phăng chứa hình vuông E2, cụ thể aff£2 = {x G R31 Xỉ = 0}; iii) Bao afin của hình cầu E3 = {x € K31 II&II < 1} là cả không gian K3.
13.2 SỐ chiều và điểm trong tương đối
Số chiều (hay thồ nguyên) của mừt tập M c Ì" là số chiều của bạo afin của nó, ký hiệu là dimM. Cho tập M c R" có dimM < ri. Mừt điểm o € M được gọi là điểm trong tương đối (relative interior point) cùa M nếu tổn tại hình cầu mở B(a, È) sao cho
Ị %e)naffM ) c M.
Phẩn trong tương đối của tập M, ký hiệu là ÚM, là tập chứa tất cả các điểm trong tương đối cùa M. Mừt tập M c Ì " được gọi là có thồ nguyên đầy đủ nếu dimM = n. Dễ thấy rằng tập M có phẩn trong khác rỗng (intM 7^ 0) khi và chỉ khi nó có thứ nguyên đầy đủ.
Ví dụ 1.11. Xét tập Eu E2, E3 như ở Ví dụ 1.10. Ta có:
i) int£i = 0 , úEi = 0, dimEỉ = i ;
ii) intiá = 0, ĨÍẼ2 = {x € K3I 0 < Xi < Ì, 0 < Xi < Ì, I 3 = 0} và dimÉ2 = 2;
iii) int£3 = {x G R3I ||i| | < 1}, dim£3 = 3, tức tập E3 có thứ nguyên đầy đủ.
1.33 Tập lồi và điểm cực biên
Cho hai điểm ì 1 và ì 2 thuừc R". Tập tất cả các điểm có dạng
X = Ai1 + (Ì - A)i2 = X2 + A(x1 - X2) với 0 < A < Ì,
được gọi là đoạn thẳng nôi X1 và ì2, ký hiệu là [ì1, ì2].
Tập MCE " được gọi là tập lồi (convex sét) nếu nó chứa trọn đoạn thẳng nối hai điểm bất kỳ thuừc nó, tức với mọi X1, ĩ2 ỊE M vào < A < Ì ta có Ai 1 + (Ì - \)x2 G M. Hình ỉ 5 cho Ta mừt sổ vi du đơn gìải ỡ K Ĩ Si và tập không lồi.
•mỉ
18 Các phương pháp tối ưu
Hình 1.5. (a), (b), (e) - Tập lói; (c), (ả) - Tập không lài
Từ định nghĩa dễ thấy rằng giao của mừt họ bất kỳ các tập lồi là tập lới. Tuy nhiên, hợp của các tập lồi chưa chắc là tập lồi.
Ta gọi điểm X e Rn có dạng
k le
X = 2 J Aji' vói Ai, • • • , \ k > ọ và Ai = Ị
i=i Í=1
là tổ hợp lồi của các điểm x\ X2, • • • , xk € Rn. Nếu Ai > 0 với mọi i = Ì, • • • ,k thì ta nói X là tổ hợp lồi chặt cùa X1, X2, • • • , xk e R".
Mệnh đề 1.4. Một tập M c K" là lồi khi và chỉ khi nó chồa tất cả các tổ hợp lồi cùa những phán tử thuộc nó.
Mệnh đề 1.5. i) Nếu M c R" là tập lồi và số thực a 6 R thi ãM = {ỵ ị y = ai, xe M} cũng là tập lồi;
li) Nếu Mu M2C R" là hai tập lồi thì Mi + M2 = {x ị X = X1 + X2, X1 € Mi, X2 6 M2 } cũng là tập lồi.
Bao lồi (convex hull) của tập E c Rn là giao của tất cả các tệp lồi chứa E và được ký hiệu là convE. Đó là tập lồi nhỏ nhất chứa E. Hai ví dụ về bao tói được minh họa ở Hình 1.6.
Chương Ì. Một sổ khái niệm và kết quà cơ bán từ giải tích lói 19 convE
comE
Hình 1.6. Ví dụ về bao lói
ĩ
Mệnh đề 1.6. Bao lồi của tập £cR " chồa tất cả các tổ hợp lồi của các phần tủ thuộc nó.
Cho tập lồi M c R". Mừt điểm XEM được gọi là điểm cực biên (extreme point) của M nếu X không thể biểu diễn đuợ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, tức
/By,z e M,y ^ z sao cho X = Xy + (Ì - \)z vói 0 < A < 1.
Theo định nghĩa, mừt điểm cực biên không thể là điểm trong của tập lồi. Vì vậy, tất cả các điểm cực biên đều là các điểm biên. Nếu tập hợp không chứa biên thì nó không có điểm cực biên.
(a) (b)
Hình 1.7. ịa) - Hình vuông có 4 điểm cực biên; (b) • Hình tròn có vô số điểm cực biên
Nhận xét 1.3. Số điểm cực biên của tập lồi có thể hữu hạn hoặc vô hạn (xem Hình 1.7). Khi tập lồi có hữu hạn điểm cực biên tíu chúng thường được gọi là các đỉnh. Chú ý rằng ta không nói về điểm cực biên của các tập không lói.
Mệnh đề 1.7. Một tập lồi đóng khác rỗng McR" có điểm cực biên khi và chi khi nó không chồa trọn một đường thẳng nào.
20 Các phương pháp tối ưu
Mừt đặc trung rất quan trọng của tập lồi đóng và bị chặn là
Định lý 1.2. (Krein6-Milman7) Một tập lồi đóng, bị chặn trong R" là bao lồi của các điềm cực biên của nó.
1.3.4 Siêu phảng, nửa không gian
Cho 0 € R" \ {0} và a € R. Tập
H := {xeW\ (a,x) = a}
được gọi là mừt siêu phang (hyperplane). Đó là mừt tập afin có số chiều bằng n -1, Ta gọi véc tơ a là véc tơ pháp tuyến của siêu phăng này.
Hình ỈA. Siêu phảng trong R2 với véc tơ pháp tuyến a và một điểm x° thuộc siêu phàng. Véc tx-x° (véc tơ in đậm) vuông góc với a, trong đó xía một điểm tùy ý thuộc siêu phảng
Ta gọi tập
{x € ÍT I (o, x) < ũ} (hoặc {x € Rn I (o, x) > a})
với a € R" \ {0} và a € R là nửa không gian đóng và tập
{ì e Rn I (o, x) < à) (hoặc {x e R" I (o, x) > á})
là nửa không gian mở xác định bời siêu phăng {x € M" I (a, x) = a}.
6Mark Grigorievich KREIN (1907 - 1989): Nhà toán học Xô Viít gốc Do Thái.
7David Pinhusovich MILMAN (1912 - 1982): Nhà toán học người Ukraina.
Chương 1. Một số khêu niệm và tít quà ca bàn từ giải tích lồi 21 (a, x) > a
Hình 1.9. Siêu phồng {x e R2|(a,x) = (a,i°) = ữ} xác định hai nửa không gian: i) nửa không gian {x e R2|(a, ì) > a} nằm vé phía theo hướng véc tơ a; ữ) nửa không gian {x 6 R21 (a, ì) < a} nằm vé phía ngược hướng véc tơ a
Cho tập M c R", véc tơ a € R"\{0} và số thực a. Ta gọi siêu phảng ^ = {i€Rn|(o,i)=a}
là siêu phồng tựa (supportìng hypeiplane) của M tại 1° € M nếu 1° G H\ằM nằm trọn toong nửa không gian đóng xác định bởi H, tức
(o, 1°) = a và (a, ì) < a với mọi X € Ai.
Xem minh họa ờ Hình 1.10. Tập {x G Rn I (o, ì) < (a, X0)} được gọi là nửa không gian tựa của M tại 1°.
a
Hình 1.10. Siêu phàng {ì I (a, ì) = (a, ì 0)} tó nôi phảng tựa cùa M tại 1°
Khi có mừt siêu phảng tựa của M tại 1° 6 M thì 1° phải là mừt điểm biên của Ai. Nguợc lại,
22 Các phương pháp tối ưu
Định lý 13. Qua mỏi điểm biên x° của tập lồi M c Rn tổn tại ít nhất một siêu phang tựa của M tại x°.
Định lý 1.4. Một tập lồi đóng khác rỗng M c R" là giao cùa họ các nửa không gian tựa cùa nó.
1.3.5 Nón
Tập McR " được gọi là nón (cone) nếu
X € M, A > 0 =*• Ax G M.
Mừt nón luôn chứa điểm gốc 0 € Rn. Tập Aícl " được gọi là nón lồi nếu M vừa là nón vừa là tập lồi, nghĩa là với bất kỳ x\ X2 e M và Ai, A2 > 0 ta có
XỊX1 + \2X2 € M.
Hình 1.11. (a)-nón lồi; (b) • nón không lồi
Mệnh đề 1.8. Tập M cũ" là nón lồi khi và chỉ khi nó chồa tất cả các tổ hợp tuyến tính không âm của các phần tử của nó.
Cho tập h véc tơ {vl, ••• ,vk}c Rn. Tập
k
coneK-.. ,vk} := {v 6 Kn I V = £ V , Ai > 0, ĩ = Ì,.. . ,jfc} i=J
được gọi là nón sinh bởi tập {v\ ••• , vkị Véc tơ vh £ {v\ • • • , vk} là không thiết yếu (non essential) nếu
cone{v\.-- ,vh-\vh+\--- , vk} = coneịv1, • • • ,vk}.
Xem minh họa ờ Hình 1.12.
Chương Ì. Một số khái niệm và kết quà cơ bản từ giãi tích lối 23
1.3.6 Phương lùi xa, phương cực biên
Cho tập lồi khác rỗng D c Rn. Véc tơ ã Ỷ 0 được gọi là phương lùi xa (recession direction) của D nếu
{x + Xd ị A > 0} c D với mỗi X 6 D.
Mọi nửa (toàng thẳng song song với mừt phương lùi xa ả xuất phát từ mừt điểm bất kỳ của D đều nằm trọn trong D. Rõ ràng rằng tập D không bị chặn khi và chỉ khi D 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 ỠCR" cùng véc tơ 0 tạo thành mừt nón lồi (Bài tập). Nón lồi đó được gọi đó là nón lùi xa của tập D và ký hiệu là recl). Ta nói hai phương d1 và đ2 là khác biệt (distinct) nếu d1 Ỷ oà 2 với Oi > 0. Phương lùi xa d của tập D được gọi là phương cực biên (extreme dừectìon) của D nếu không tồn tại các phương lùi xa khác biệt d1 và d2 của D sao cho ã = Ai á 1 + \2 0.
Ví dụ UI Xét tập
D := {x e ũ2 ị -x:+x2< 5,1! + 2x2 > 10,X! > 0,x2 > 3}.
Ta có ĩecD = cone{(l, 1)T, (1,0)T}; véc tơ d1 = (Ì, 1)T và đ2 = (1,0)T là hai phương cực biên của D. Véc tơ d3 = (2,1)T là mừt phương lùi xa nhưng không phải là phương cực biên cùa D. Xem minh họa ở Hình 1.13.
24 Các phương pháp tối ưu
Hình 1.13. Tập D và nón lùi xa lecD
13.7 Các định lý tách tập lồi
Đây là những định lý cơ bản nhất của giải tích lồi, là công cụ hữu hiệu của lý thuyết tối ưu.
Cho hai tập c, De Rn và siêu phang H = {x € R* ị (o, ì) = a} với a e M" \ {0} và a € 1. Ta nói siêu phăng H tách hai tập c và D nếu
(a,x).
Định lý 1.5. (Định lý tách ì) Nếu hai tập lồi c, DcR " không rỗng và rời nhau thì có một siêu phang tách chúng.
Định lý 1.6. (Định lý tách li) Nếu hai tập lồi đóng c, D c Rn không rỗng, rời nhau và một trong hai tập ấy là compac thì có một siêu phang tách hẳn chúng.
Chú ý 1.3. Nếu thiếu giả thiết "mừt trong hai tập là compac" thì Định lý 1.6 không còn đúng. Ví dụ c = {{xux2) e ả 21 x2 > e 1 1 } và D = {(xux2) 0 với mọi X thỏa mãn Ax > 0
khi và chỉ khi
3 y 6 = {y G R m I y > 0} sao cho a = ATy.
Chương 1. Một số khái mèm và kết quả cơ bản từ giải tích lồi 25
Bổ đè Farkas có rất nhiều ứng dụng. về mặt hình học, bổ đề này chỉ ra rằng: nón K = {x 6 Rn\Ax > 0} nằm hẳn trong nửa không gian {x € Kn|(o, x) > 0} khi và chỉ khi véc tơ pháp tuyến của siêu phảng {x e Rn|(o, x) = 0} nằm trong nón sinh bởi các hàng của ma trân A.
Hỉnh 1.14. (a) • Hai tập lồi c và D được tách hàn bởi một siêu phang; (b) - Hai tập lồi c và Dđược tách bả siêu phàng {x e K2 |x2 = 0} nhưng không tách hẳn được; (c) - Tập c và D giao nhau bằng rỗng nhung không thể tách được vì D không phái tập lồi
13.8 Tập lồi đa diện
Tập lồi đa diện p c R" là giao của mừt số hữu hạn nửa không gian đóng. Nói cách khác nó là tập nghiệm của mừt hệ hữu hạn các bất đẳng thức tuyến tính
(oi,x)>6j, i = Ì,•••,£, (1.4)
Mỗi bất đẳng thức trong hệ (1.4) được gọi là một ràng buộc. Ràng buừc k & {!,••• ,i}ìầ ràng buộc thùa nếu
{x|(a<,x)>6i)i = l,---,£} = {a:|(o<ìx)>6i)ie{l)--- ,i}\{k}}.
Nếu ta kí hiệu Ả là ma trận cấp ixn với các hàng lào' = (an, • • • ,Oj„),z = Ì, • • • ,i; véc tơ 6 = (6i, • • • , b()T e R(, X = (li, • • • , xn)T 6 w thi hệ (1.4) được viết dưới dạng ma trân như sau
Ax>b.
Vì mừt phương trình tuyến tính có thể biểu diễn tương đương với hai bất phương trình tuyến tính nên tập nghiệm của hệ phương trình và bất phương trình tuyến tính
ỉ = li+ !,••• ,i.
cũng là mừt tập lồi đa diện.
Dễ thấy rằng tập lồi đa diện là mừt tập lói, đóng. Mừt tập lồi đa diện bị chặn được gọi là đa diện lồi hay gọi tắt là đa diện.
26 Các phương pháp tối tíu
Hình 1.15. Đa diện này là giao của 5 nửa không gian {x\{a',x) > bi,i = Ì, • • • ,5} Cho tập lồi đa diện p xác định bởi (1.4). Nếu điểm x° € p thỏa mãn (0*0,1°) = 6^, to € {Ì, •••,*}
thì ta nói điểm x° thỏa mãn chặt ràng buừc lo. Tập
I(x°) := {ie{l,2ì--,t}\(ai,x°)=hi)
là tập hợp các chỉ số của những ràng buộc thỏa mãn chặt tại 1° 6 p. Mỗi điểm cực biên của tập lồi đa diện được gọi là mừt đinh của nó. Mừt 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 trong tương đối của mừt đoạn thẳng nào đó thuừc p thì F chứa tron cả đoạn thẳng đố, nghĩa là
y € p, z e p, X = Xy + (Ì - \)z e F với 0 < A < Ì =• y€F,zeF.
Mệnh đề 1.9. Cho tập lồi đa diện p xác định bởi hệ (1.4). Khi đó, tập con lồi khác rỗng F c p là một diện cùa p khi và chỉ khi tồn tại một tập chỉ số ì c {Ì, 2, • • • ,t) sao cho F là tập nghiệm cùa hệ
(a\ x)-bị, i e /
(a>-,x)>6j, je{l,2,---,*}\/.
Hơn nữa, ta có dimF = 71- rank{a', i € /}.
Nhắc lại rằng rank{a', i € /} bằng số véc tơ đừc lập tuyến tính lớn nhất trong bừ véc tơ ịa', ỉ Ì /} .
Đỉnh cùa tập lồi đa diện p là mừt diện có thứ nguyên bằng 0. Cạnh của p là mừt diên có thứ nguyên bằng 1. Mỗi cạnh vô hạn của tập lồi đa diện p tương ứng với mừt phương cực biên cùa nó.
Chương 1. Một sổ khái niệm và tót quả cơ bấn từ giải tích lôi 27
Hệ quả L I Cho tập lồi đa diện p xác định bởi hệ (1.4).
i) Một điểm x° €Plà đỉnh của p khi và chỉ khi x° thoa mãn chặt TI ràng buộc độc lập tuyến tính của hệ (1.4);
li) Một đoạn thẳng (hoặc nửa đường thẳng, hoặc đường thẳng) r c p là một cạnh của p khỉ và chỉ khi nó là tập các điểm của p thoa mãn chặt (n - 1) ràng buộc độc lập tuyến tính của hệ (ỈA).
Hệ quả 13. Một diện của tập lồi đa diện p cũng là một tập lồi đa diện. Hơn nữa mỗi đỉnh cùa một diện của p cũng là một đỉnh của p.
Cho 1° là mừt đỉnh của tập lói đa diện p xác định bởi hệ (1.4). Đỉnh x° được gọi là đỉnh không suy biến nếu nó thỏa mãn chặt đúng n ràng buừc của hệ (1.4), tức = rỉ. Ta nói x° là đỉnh suy biến nếu > n. Hai đỉnh X1 và X2 đuợe gọi là kề nhau nếu đoạn thẳng nối chúng là mừt cạnh.
Ví dụ 1.13. i) Đa diện p cũ3 à Hình 1.16(a) là giao của 5 nửa không gian, có dimP = 3, có mừt đỉnh suy biến và bốn đỉnh không suy biến;
li) Tam giác (phần gạch chéo) ở Hình 1.16(b) là đa diện xác định bởi hệ Xi + Xi + x3 = Ì, li > 0, 12 > 0, x3 > 0.
Tam giác này có thứ nguyên là 2 và ba đỉnh không suy biến;
iii) Đa diện xác định bởi hệ
Xi + Xí + X3 = Ì
Xi + Xi = 1
l i > 0, Xỉ > 0, X3 > 0
chính là đoạn thẳng nối điểm (l,0,0)r và (0, l,0)r (xem Hình 1.16(c)). Đa diện này có thứ nguyên bằng Ì và cả hai đỉnh của nó đều suy biến.
28 Các phương pháp tối ưu
V
Hình 1.16. Đinh suy biến và không suy biến
Định lý 1.7. (Định lý biểu diễn tập lồi đa diện) Giả sủ{v\- - ,VN} là tập các đinh và {dl, • • • ,dM} là tập các phương cực biên của tập lồi đa diện p. Khi đó, mỗi điểm X € p đêu có thể biểu diễn dưới dạng
N M
1=1 j=i
trongđó Ai > 0, i = l,---,N, Hi> 0, j = Ì,-.. ,M và ỵif=lXi = l.
Nhận xét 1.4. Nếu p là đa diên lồi thì tập các phương cực biên bằng ròng. Do đó trong (1.5) chỉ còn lại tổng thứ nhất, tức là mõi điểm của p đều được biểu diễn bằng tổ hợp lồi của các đỉnh của nó.
1.3.9 Đơn hình
Ta nói k + ì điểm (hay véc tơ) v°, v\ •• • , vk e R" là độc lập afìn (affinely inde pendent) nếu k véc tơ í'1 — L'°, • • • , vk — Ư° là đừc lập tuyến tính. Bao lối của k + Ì điểm đừc lập afin tong Rn được gọi là đơn hình k chiêu hay k-đơn hình. Tập
n
s = {x€ Rn ị Y^Xj < Ì, Xj>0, j = Ì, • • • ,n}
được gọi là đơn hình chuẩn trong R".
Chuông ì. Một số khái niệm và tét quả cơ bản từ giải tích lồi 29
Ví dụ 1.14. Mừt điểm là O-đơn hình, đoạn thẳng là Ì-dơn hình, tam giác là 2-đơn hình và tứ diện là 3-đơn hình (xem Hình 1.17). Đơn hình chuẩn trong E3 là tứ diện vớií 4 đỉnh là (0,0,0)r, (Ì, 0,0)T, (0, l,0)T và (0,0,1)T.
o-đơn hình ỉ-đan hình 2-đơn hình 3-đơn hình Hình 1.17. Các đơn hình trong R3
1.4 Hàm lồ i
1.4.1 Định nghĩa
Hàm / được gọi là hàm lồi (convex íunction) xác định tiến tập lồi X c R" nếu f(Xxl + (Ì - A)i2) < Xf(xl) + (Ì - A)/(x2)
với bất kỳ X1, X2 e X và số thực A G [0,1]. Ta gọi / là hàm lồi chặt (strictly convex íiinction) trên tập lồi X nếu
/(Ax1 + (Ì - A)x2) < Xf(xl) + (Ì - A)/(x2)
với bất kỳ ì1, X2 € X, X1 Ỷ X2 và 0 < A < L Miền xác định hữu hiệu của hàm / là dom/ := {x e x\ f(x) < +oo}.
Epigraph của hàm lồi / là tập
epi(/) -{(i,()eXxR|í>/(i)}cRn+1.
Hàm lồi / : X -» R u {+txj} có thè được mở rừng thành mừt hàm lói trên toàn không gian Ì " bằng cách đặt f(x) = +00 nếu X ị dom/. Vì vậy, để đơn giản, ta thường xét / là hàm lồi trên Rn.
Hàm / được gọi là hàm lõm (concave tiinction) (tư., hàm lõm chặt (strictly concave íunction)) nếu - / là hàm lồi (t.ư., hàm lồi chặt).
30 Các phương pháp tối ưu /(Ail + (1-A)i 2)
f(Xxl + (Ì - X)ệ
ì1 Ai 1 + (Ì - A)i 2 (a)
X1 Aii + a-A)! 2 Ị 2 (b)
Hình 1.18. (a)-Hàm lồi; (b) - Hàm lõm
Dê chúng minh rằng / là hàm lồi trên tập lồi X c K" khi và chi khi với mọi điểm x° G X và mọi hướng ti € R", hàm mừt biến tp(t) := /(ì 0+ tỵ) là hàm lồi trên tập lỗi ụ € R I x° + ív € X} c R (Bài tập). Tinh chất này rất hữu ích. Nó cho phép ta kiểm tra mừt hàm có phải là hàm lồi hay không bằng việc hạn chế xét nó trên mừt đường thẳng.
Mệnh đề 1.10. i) Hàm số Ị xác định trên tập lồi khác rỗng X c K" là hàm lồi khi và chỉ khi epi(f) là tập lồi;
ti) Hàm số g xác định trên tập lồi khác rỗng X c R" là hàm lõm khi và chỉ khi tập hypograph cùa nó
hypo(s) :={(I, 0 6XXR|Í/í* 1) * 6 >/(**)• (1.6)
Với mọi 0 < A < Ì, ta có
/(Ax1 + (Ì - A)x2) < A/tx1) + (Ì - X)f(x2) (do / là hàm tói) < A6 + (Ì - A)£2 (do (1.6)).
Suy ra
(\xl + (Ì - A)i 2, ÁC, + (Ì - xỵ2) = Ằ(x\eo + (Ì - A)(i 2,6) € epi(/)
Chương Ì. Một số khái mèm và tót quả cơ bản từ giải tích lồi 31
(<=) Ngược lại, giả sử epi(/) là tập lới. Vì (ì1, /(ì1)) và (ì2, /(ì2)) đều thuừc spi(/) nên với mọi 0 < A < ì,
A(x1,/(x1))+(l-A)(i2,/(a;2)) =
= ịxx1 + (Ì - À)*2, A/tx1) + (Ì - A)/(x2)) € epi(/).
Theo định nghĩa ta cố
/(Ai1 + (Ì - A)x2) < Xỉix1) + (Ì - A)/(x2) vo < A < 1.
Điều đó chứng tỏ / là hàm tói. •
(a) (b)
Hình 1.19. (a) - Epigraph cùa một hàm lài (b) - Hypograph cùa một hàm lõm
Mệnh đề 1.11. ì) Nếu hàm số ỉ xác định trên tập lồi X c Ì" là hàm lồi thì tập mồc dưới L a ( f ) := {x £ X ị f(x) < a} là tập lồi với mọi Oi € K; xì) Nếu ọ là hàm lõm xác định trên tập lồi khác rông X CRn thỉ tập mồc Kên :La{g) :={x€X\ g(x) > a} là tập lồi với mọi a e R.
Chồng minh: Ta chỉ cần chứng minh i). Lấy bất kỳ X1,!2 € La(Ị) và 0 < À < 1. Khi đó
/(Ai1 + (Ì - A)x2) < Xỉix') + (Ì - X)f{x2) (do / là hàm lồi)
< A Q + (1-A) Q {àox\xteLa{f))
= a.
Suy ra Ai1 + (Ì - A)i2 € Laự). Vậy La{f) là mừt tập lồi. •
32 Các phương pháp tối ưu
Chú ý 1.4. Mệnh đề 1.11 chỉ là điều kiện cần, không phải là điêu kiện đù. Nga là nếu tập mức dưới L a ( f ) của hàm / là tập tói với mọi ữ € R thì hàm / chua chắc đã là hàm lồi. Nếu tập mức trên La(g) của hàm g là tập tói với mọi a G R thì hèn g chưa chắc đã là hàm lõm.
Mừt hàm mà mọi tập mức dưới là tập tói đuợc gọi là mừt hàm tựa lói. Tương tự, mừt hàm mà mọi tập mức trên là tập lồi được gọi là mừt hàm tựa lõm.
Ví dụ 1.15. Hàm mừt biến f(x) = X3 có tập mức dưới Lai!) = {ì e K| X3 < ế) là tập lồi với mọi a G R và tập mức trên ừ {Ị) = {x € Rị X3 > 0} là tập lồi vá mọi p e R, nhưng f(x) không phải là hàm lồi cũng không phải hàm lõm trên R. Đó là hàm vừa tựa lồi, vừa tựa lõm.
1.4.2 Các phép toán về hàm lồi
Cho hàm lồi Ịi xác định trên tập lỏi Xi c Kn, hàm lồi /2 xác định trên tập lồi Xì c R" và số thực Á > 0. Các phép toán A/i, ỈI + /2, max{/i, /2} được định nghĩa như sau:
(Xf})(x) := xụxị x€X i ;
(/1 + /a)(«) := /1(1) + /2(1), X € X1 n x 2;
max{/j, fì}(x) := max{/i(i), /2(1)}, X 6 Xi n x2.
Kết quả sau dễ dàng suy ra từ định nghĩa
Mệnh đề 1.12. Cho /1 là hàm lồi trên tập lồi Xì, /2 là hàm lồi trên tập tói Xỉ Ví các số thực ũ > 0, p > 0. Khi đó các hàm afị + 0/2 và max{/!, /2} /à tó/ rréí Xinx 2.
1.4.3 Tính liên tục của hàm lồi
Mừt hàm lồi / xác định trên tập lồi X c R" không nhất thiết là hàm liên tục. Túi nhiên, khi X là tập lồi mở ta có
Định lý 1.8. Nêu ĩ là hàm lỗi xác định trên tập lồi mở X c R" thì Ị tiên tục trên X.
Chồng minh. Xem [28], trang 62 - 63. ũ
Nhận xét 1.5. Sụ gián đoạn cùa hàm lồi chi có thể xảy ra tại biên của tập xác định. Ví dụ 1.16. Xét hàm mừt biến
trên tập X = (-00,1].
Dễ thấy epi(/) c R2 là tập lồi. Do đó, theo Mênh đè 1.10, / là hàm lói trên X, Hàm / là liên tục trên X \ {ì}. Tại X = Ì, hàm / là nửa liên tục trên.
Chương 1. Một số khái niệm và kết quả cơ bản từ giải tích lỗi 33
1.4.4 Đạo hàm theo hướng của hàm lồi
Định lý 1.9. Nếu Ị : X -> R là một hàm lồi xác định trên tập lồi X c Rn thì nó có đạo hàm theo mọi hướng d€Rn\ {0} tại mọi điểm x° £ dom/ và
f'(x0,d) 0 mà x° + tả ị dom/ thì ta có
/(x° + tả) = 0 để x° + tả e dom/ thì với mọi Í! mà 0 < í Ì < t ta có * < ! Và ^ í + H)o .
Vì p là hàm lồi nên
?(íi)< jrtt)+(l-£)v(0).
Suy ra
0 ta luôn có
í
>lp'+(0) = f'(xũ,d).
Lấy í = Ì ta có p(l) - v(0) = /(ì 0 + d) - /(x°) > /'(x°, d). • Sau đây là hệ quả trực tiếp của Mệnh đề 1.2 và Định lý 1.9.
Hệ quả 1.4. Nếu Ị là hàm lồi khả vi xác định trên tập lồi mở X thì Ị cố đạo hàm theo mọi hướng ả € Ì " \ {0} tại mọi điểm x° € dom/ và
(Vf(xữU) = f'(xữ,đ)(vf(x),y-x) V*,!/€*;
ii) Hàm Ị là hàm lõm trên X khi và chỉ khi
ỉ(y)-f(x)<(vf(xịy-x) Vx.yeX.
Chồng minh. Xem [28], trang 83-85. ũ
Với hàm mừt biến / xác định trên tập lồi X c R ta đã biết: f là hàm lồi trài X khi và chỉ khỉ f"{x) > 0 với mọi X € X. Chẳng hạn: i) Hàm /(ì) = e1 là lỗi trôn R; li) Hàm g{x) = -h ư là lồi trôn (0, +oo); iii) Hàm h{x) = sin X không lồi, không lõm tiền K. Tương tự, với hàm n biến ta có
Định lý 1.11. Cho Ị là hàm khả vi hai lẩn trên tập lồi mở X C R». Khi đó, i) Hàm ỉ là hàm lồi trẽn X khi và chỉ khi ma trận Hesse v2/(i ) là nửa xà định dương trên X, tồc với mỏi X € X,
yTV2ỉ{x)y>0 VyeRn.
Hàm Ị là hàm lồi chặt trên X nếu v2/(i) xác định dương trên X, tồc với mỗi X € X
yTV2f(x)y>0 Vy€M n\{0} ;
ti) Hàm Ị là hàm lõm trên X khi và chỉ khi ma trận Hesse v2/(i ) là nửa xác định âm trên X, tồc với mỗi X 6 X,
yTV2ỉ{x)y<0 Vị/GR".
Hàm Ị là hàm lõm chặt trên X nếu v2/(i) xác định âm trên X, tồc với mỗi xeX, yrv2/(x)y<0 Vy€Rn\{0}.
Chồng minh. Xem [28], trang 90-91. ũ
Hệ quả 1.5. Cho hàm toàn phương
ỉ{x) = -(x,Qx) + (x,a) + a,
trong đó Q là ma trận đối xồng cấp nxn. Khi đó:
i) / là hàm lồi (tư., lồi chặt) trên Rnnếu Q là ma trận nửa xác định dươnị (t.ư., xác định dương);
ú) ỉ là lõm ịt.ư., lõm chặt) trên Rnnếu Q là ma trận nửa xác định ám (t.ư., xả định ăm).
Chương Ì. Một số khái niệm và tót quả cơ bản từ giải tích lồi
35
Ví dụ 1.17. Cho /(%, %) = 3xỊ + 2X1*2 + 4aị Ta có
6 2>
2 87" v2f(x ) = Ợầxi ĩ r ) =
\Jx2Xl •'1212/
Vì ma trận Hesse v2/(x ) xác định dương nên hàm / đã cho là hàm lồi chặt trên R2.
Bài tập Chương Ì
1. Cho tập E c Rn. Chứng minh rằng
k k
xeaữE » x = Ỵ^Xixi; x\x2,---,xk € E, ^A í = i . i=i i=i
2. Chứng minh rằng không gian con song song với tập afin M là xác định duy nhất.
3. Chứng minh rằng: i) giao của mừt họ hữu hạn các tập lồi là tập lồi; li) hợp của hai tập lồi chưa chắc đã là tập lồi, cho ví dụ cụ thể.
4. Cho Ả là ma trận cấp m X n và b e Rm. Chứng minh rằng, tập M = {x € R»|ÃĨ = b, X > 0} là tập lồi.
5. Cho {d1, • • • , dk} là các hưóng lùi xa của tập
D = {xeW \Ax = btx>0},
với A là ma trận cấp ro X TI và b G Km. Chứng minh rằng véc tơ
k
0 ^ d = ^ữid i vớiữi>0
i=l
cũng là mừt hướng lùi xa cùa D.
6. Cho p = {xe ầ.n\Ax - b, X > 0}. Chứng minh rằng nếu ả í 0 thỏa mãn Ad = Q và d>0
thì ả là mừt hướng lùi xa của tập p.
36 Các phương pháp tối ưu
7. Cho p ^ 0 là mừt hướng lùi xa của tập
£> = {z€Rn| Az = 6,i>0}
với A là ma trận cấp m X n và 6 6 R m. Chứng minh rằng -p không thể là mừi hướng lùi xa của D.
8. Cho tập M = {ì e K21 Xi +12 > 1; -li +12 < 2; Xi,x2 > 0}. Tun các
phương cực biên của M và xác định nón lùi xa recM.
9. Cho ví dụ: i) tập lồi không cố điểm cực biên; li) tập lồi có hữu hạn điểm cục biên; iii) tập lồi có vô hạn điểm cực biên; iv) Chúng minh rằng tập D = {x Ệ Rn\Ax < b} không có mừt điểm cực biên nào.
10. Cho tập lồi đa diện p = {x e ầ.6\Ax = b, X > 0}, trong đó
A =
Điểm X = (Ì, Ì, Ì, 0,0,0)T có phải là điểm cực biên của p không? Giải thích.
li. ChotậpP = {xeR2|-3ii + 2i2<30, -2x1 + x2<12, Ii,i2>0}.
i) Vẽ tập P; ii) Xác định các điểm cục biên và chỉ ra hai hướng lùi xa đừc lập tuyến tính cùa p.
12. Cho hàm số
f(xi,x2) = ^xị + -rxị + 2xỵx2 + ^xị - XỊ + 9
và điểm x° = (Ì, 2)T. Hãy viết khai triển Taylor bậc nhất của hàm số này tại điểm x°.
13. Hãy biểu diễn điểm (2,2)T như mừt tổ hợp lồi của ba điểm (0,0)T, (Ì, 4)r và (3,1)T.
14. Vẽ bao lồi của tập các điểm sau: (0,0)T, (1,0)T, (-1,2) T, (3,l)r, (2,6)T, (~2) Ì) 7. (-3, -2)T, (3,3)T. Chi rõ các điểm cực biên và các điểm trong của bao lồi này.
15. Cho gi, í = Ì, • • • , m là các hàm lồi và hj, ị = Ì, • • • , k là các hàm tuyến tính afin xác định ưên Rn. Chứng minh rằng tập hợp sau đây là lồi
M = {i€K n| ổ iW<0, i = l,---,m; hj{x) = 0, j = !,...,*} .
Chương ỉ. Một số khái mèm và kết quả cơ bản từ giải tích lồi 37
16. Các hàm số sau có phải hàm lồi khổng? Hãy giải thích bằng ít nhất hai cách: i) f[x) = \x\ với X € R;
li) f(x) = ex + Ì + 5x với X € R;
ỉỉỉ> f(x) = -ìax + 3i 3 với 0 < X < +oo;
iv) /(ì) = arctgx với 0 < X < +oo;
17. Trong các hàm số sau, hàm nào là hàm lỏi, hàm lõm hay không lồi, không lõm. Vì sao?
li) f(xi, 12) = xị + 2x\X2 - 10xi + 5x2;
iii) f(Xịt 12) = -xị - 5xị + 2xiX2 + 9xi - 8x2;
iv)f(xi,x2,13) = X1X2 + 2x\ + xị + 2xị - 6x1X3 + 3x2 x3;
v) f(xi,X2,x3) = -xỊ - 3xị - 2xị + 4xix2 + 2iiX3 + ix2x3;
vi) f(xi,x2, x3) = xị + 2xiX2 + 4xiX2 + 3xị + X2X3 + Gxị
vú) f{xi,X2, x3) = xỊ + 4xiX2 + 4X2 + + 4x2X3.
18. Chúng minh rằng hàm tuyến tính afin bị chặn trên (hay bị chăn dưới) trên mừt tập afin thì chì có thể đồng nhất bằng hằng số.
19. Chứng minh rằng hàm / : Mn -» Ì là hàm afin khi và chỉ khi / vừa là hàm lồi, vừa là hàm lõm.
20. Cho tập lồi khác rông D c Rn và hàm số / : D -> R. Chứng minh rằng: i) / là hàm lõm khi và chỉ khi hypo(/) là tập lói;
ii) Nếu / là hàm lõm thì tập L°(f) = {xe Dị f{x) > à), với a e B, là tập lồi.
21. Hãy xác định siêu phảng đi qua các điểm (Ì, Ì, Ì, 1) T, (2,0, Ì, 0) T, (0,2,0, l f và (Ì, í , -Ĩ0) T thuừc ầ4.
22. Cho c là tập lồi đóng và y ị c. Chồng minh rằng X* e c là điểm gần y nhất khi và chi khi (ì - y, ì - ý) > ||x* - Ị/ll2 với mọi X thuừc c.
23. Cho Ci và c2 là hai tập lồi trong Kn. Chứng minh rằng tồn tại mừt siêu phảng tách chạt Ci và c 2 khi và chỉ khi
ÌDỈ{||x-y|| li 6 Cu y € c 2 } > 0.
38 Các phương pháp tối ưu
24. Cho A là ma trận cấp m X n và c € Rn \ {0}. Chúng minh ràng có mừt và dì mừt hừ phương trình trong hai hừ phương trình sau có nghiêm
i) AI = c;
iiM Ty = 0, (c,y) = l .
25. Cho s là tập lồi khác rỗng trong R". Chúng minh rằng hàm / được định nghĩa như sau
f(y) :=inf{||y-i| | \x G S)
là hàm tói.
Chươn g 2
B à i toá n tố i ư u
Nừi dung chính của chương này là giới thiệu mô hình toán học của bài toán tối ưu và điều kiện tổn tại nghiệm. Trước hết, ta xét mừt số bài toán thực tế có thể đưa về bài toán tối ưu.
2.1 Mừt số ví dụ
Ví dụ 2.1. (Bài toán thuê lạc đà1)
Mừt đoàn lữ hành cẩn thuê nhũng con lạc đà mừt bướu và hai bướu để chở hàng từ Baghdad đến Mecca. Mỗi con lạc đà hai bướu có thể chở được 1000 lbs2 hàng và mỗi con lạc đà mừt bướu có thể chở được 500 lbs hàng. Trong chuyến đi, mỗi con lạc đà hai bướu dùng 3 bó cỏ khô và 100 galon3 nước, còn mỗi con lạc đà mừt buớu dùng 4 bó cỏ khô và 80 galon nước. Chỉ có 1600 galon nuóc và 60 bó cỏ khô được dự trữ sẩn ở các ốc đảo trên dọc đường đi. Mỗi con lạc đà hai bướu thuê với giá là 11$, mỗi con lạc đà mừt bướu thuê với giá là 5$. Nếu đoàn lữ hành này phải chở ít nhất là 10000 lbs hàng hóa từ Baghdad đến Mecca thì cần bao nhiêu lạc đà mừt bướu và bao nhiêu lạc đà hai bướu để số tiền thuê là ít nhất.
Gọi Xi > 0 là số lạc đà mừt bướu và X2 > 0 là số lạc đà hai bướu mà đoàn lữ hành cần thuê. Để thuê số lạc đà này người ta phải mất số tiền là:
f(x) = 5xi + 11X2.
Số lạc đà được thuê phải chờ được ít nhất 10000 lbs hàng, tức 500X1 + 1000x2 > 10000.
Nước và cỏ khô không được sử dụng quá trữ lượng dự trữ trong các ốc đảo nên
(cỏ khô)
(nước).
'theo [4], trang 182.
2lkg = 2.205 lbs.
3lgalon = 3.79 lít.
4xi + 3x2 < 60 80ii + 100X2 < 1600
40 Các phương pháp tối ưu
Và bài toán được phát biểu như sau:
min f(x) = 5xi + llx a
với điểu kiện 50ŨI1+ 1000i2 > 10000
4xj + 3 i 2 < 60
8O11+ 100x2< 1600
Xi,Xỉ > 0.
Ví dụ 2.2. (Bài toán lập kế hoạch sản xuất)
Mừt xí nghiệp dự định sản xuất n loại sản phẩm từ m loại nguyên liệu. Bài toán đặt ra là xí nghiệp nên sản xuất bao nhiêu đơn vị sản phẩm mỗi loại để doanh thu lớn nhất. Biết rằng: Lượng nguyên liệu loại í cần thiết để sản xuất mừt đơn vị sản phẩm loại ị là ày, i = Ì, • • • ,m, j = Ì, • • • ,n; Trữ lượng nguyên liệu loại í mà xí nghiệp
có là bị, i = Ì, • • • , m; Giá bán mừt đơn vị sản phẩm loại ị là Cj, j = Ì, • • • , n. Gọi Xj là số đơn vị sản phẩm loại ị mà xí nghiệp sẽ sản xuất, ị = Ì, • • • ,n. Hiển nhiên là Xj > 0 với mọi ị. Doanh thu của xí nghiệp là
f{x) = CỊXÌ + ••• + CnXn.
Tổng chi phí nguyên liệu loại ì mà xí nghiệp sẽ sử dụng để sản xuất không dược vượt quá trữ lượng, tức
OiiíCi H + ainxn < bị, i = Ì, • • • ,m.
Sau đây là mô hình toán học của bài toán lập kế hoạch sản xuất
n
max
v.đ.k.
n
J=1
Xi > 0, ị n.
trong đó "v.đ.k." là viết tắt của cụm từ "với điều kiên".
Ví dụ 23. (Bài toán lập kế hoạch sàn xuất hai mục tiêu)
Ta xét bài toán lập kế hoạch sản xuất với các số liệu được cho như ờ Ví du 2.2. Giả sử ngoài mục tiêu cực đại doanh thu, nguôi ta còn muốn cục đại số lượng sản
Chương 2. Bài toán tối ưu 41
phẩm sản xuất được. Khi đố, bài toán trở thành
n
max ^2 CịXị (doanh thu)
j=i
ti
max /,X j (tổng sản phẩm)
j=i
n
v.đ.k. ^ 0yZj < bi, i = Ì, • • • , m
Xj>0, ị = !,••• ,n
Ví dụ 2.4. toán xác địn/t khẩu phần thồc ăn)
Mừt nông bương chăn nuôi cần mua n loại thức ăn cho gia súc. Người ta cần xác định khẩu phần lẻ nhất cho gia súc mà vẫn đảm bảo được yêu cầu vẻ ra loại chất dinh dưỡng cho bữa ăn của chúng. Biết rằng: Trong khẩu phần thức ăn của gia súc phải có ít nhất bị đơn vị chất dinh dưỡng loại i, i = Ì, • • • , m; Lượng chất dinh
dưỡng loại i có trong mừt đơn vị khối lượng thức ăn loại ì là Oiị, í = Ì, • • •, ro, ị = Ì, • • • , n; Giá mừt đơn vị thức ăn loại ị là Pj, j = !,••• ,n. Gọi Xj > 0 là lượng thức ăn loại ị trong khẩu phẩn của gia súc, j = Ì, • • • ,n. Mô hình toán học cùa bài toán này là
n
min Y,PixJ
n
v.đ.k. ^2 aijxi * = !>••• I m
ề$ > 0, j = ì,-- - ,n.
Với mỗi i € {Ì, • • • , m}, ràng buừc 53"_J aịjXj > bị nghĩa là lượng chất dinh dưỡng loại i có trong khẩu phần thức ăn của gia súc phải đảm bảo không ít hơn yêu cầu tối thiểu.
Ví dụ 2.5. (Bài toán vận tài)
Người ta cần vận chuyển mừt loại hàng hóa từ m kho chứa hàng (gọi là điểm phát) đến n điểm tiêu thụ (gọi là điểm thu). Biết rằng: Diêm phát thứ í chứa dị đơn vị hàng, í = Ì, • • • , m; Điểm thu thứ ị cần bị đơn vị hàng, ị = Ì, • • , n. Chi phí vân chuyển mừt đơn vị hàng từ điểm phát i đến điểm thu j là dị, ì = Ì, • • • , m, j = Ì, • • , n. Vấn đề đặt ra là cẩn xác định lượng hàng cần chuyển từ mỗi điểm phát đến từng điểm tiêu thụ như thế nào để chi phí vân chuyển là cực tiểu.
42 Các phương pháp tối lùi
Ký hiệu Xịj là số lượng hàng cần vân chuyển từ điểm phát thứ í đến điểm thu thí ị, ì = Ì, • • • ,m, 3 = Ì, • • • ,n. Các đại lượng l y tạo thành ma trận phán phối hàiiỊ hóa
0, i = Ì,••• "ỉ, j = Ì, • • • n.
Như sẽ chúng minh chạt chẽ trong Chương 4 (Định lý 4.1), điểu kiện cân bằng diu phát chính là điều kiên cần và đủ để bài toán vận tải có nghiệm tối ưu.
Ví dụ 2.6. (Bài toán cắt gọt kim loại)
Giả sử cố m máy gia công cắt gọt kim loại. Mỗi máy này cố thể thực hiện được n công việc khác nhau (chẳng hạn: tiện, phay, bào...) và cố nhiệm vụ gia công mừt loạt phôi để sản xuất các chi tiết máy. Gọi l y là thời gian máy i thực hiện công việc
j,i= Ì, • • • , m, j = Ì, • • • , TI. Bài toán đặt ra là phải phân phối thòi gian cho từng máy làm cống việc nào để hiệu quả chung của sản xuất là cực đại. Biết: i) Wịj là hiệu quả (tính bằng tiền) của máy thứ i thực hiện cổng việc thứ j, chẳng hạn tính trong mừt giờ, và được cho dưới dạng ma trận năng suất
li) Mỗi máy ị, i € {Ì, • • • , m}, trong thời gian mà toàn bừ quá trình được xem xét (mừt ngày đêm chẳng hạn) có mừt thòi gian công tác cục đại là dị. Như vậy, tổng thời gian công tác cùa máy i để thực hiên các công việc j, í = Ì, • • • , Tí phải bằng dị, túc
Nếu được phép không sử dụng hết thời gian làm việc (công tác) tối đa của máy thì ta có thể thay thế các phương trình trên bởi các bất phương trình
ri
2^afy 0, í = Ì, • • • , m, j = Ì, • • •, n.
Mô hình toán học này cũng có thể áp dụng cho các bài toán thực tế khác, chẳng hạn bài toán phân phối diện tích đất đai có đừ phì nhiêu khác nhau để trồng các loại cây khác nhau như: lúa, ngô, cà chua, sán, khoai tây...
Ví dụ 2.7. (Bài toán người du lịch (ĩravelling Saỉesman Problem))
Giả sử mừt người du lịch muốn đi thăm n thành phố, đánh số từ Ì đến n. Cho biết chi phí đi từ thành phố í đến thành phố j là Cụ. Người du lịch xuất phát từ mừt trong n thành phố này, chẳng hạn thành phố Ì, để đi đến thăm n - Ì thành phố còn lại, mỗi nơi chỉ đến đúng mừt lần, sau đó lại quay về noi xuất phát Như vậy, nếu coi mỗi thành phố là mừt đỉnh của mừt đồ thị vô hướng thì mỗi hanh trình của nguôi du lịch là phải là mừt chu tình Hamilton4. Bài toán đặt ra là tìm mừt hành trình sao cho tổng chi phí là nhỏ nhất. Giả thiết rằng Cy > 0 với mọi i ệ j, Cị, = oe với mọi i và có thể Cý" Ỷ Cji
Đặt
Ì nếu người du lịch đi từ i đến j
0 nếu người du lịch không đi từ ĩ đến j , *' 3 = l ì ' ' ' 'n' (2-^
"Mừt dường di khép kín (chu Dinh) trong mừt đổ thị vô huống liên thông được gọi là mừt chu trinh Hamiltníu nó di qua mọi đinh của đổ thị, môi đinh đúng mừt lẩn.
Chương ĩ. Bài toán tối ưu 45
Điểu kiện người du lịch đi (tói mọi điểm và mỗi điểm chỉ đi qua đúng mừt lần có nghĩa là
(2.2)
3-1
(2.3)
i=l
5
(a)
Hình 2.1
Hình 2.1 minh họa hai cách đi đều thỏa mãn điều kiện (2.1)-(2.3) trong trường hợp có n = 6 thành phố nhưng cách đi như ở Hình 2. Ì (b) không thỏa mãn yêu cầu của bài toán. Vì vậy, điều kiện sau đây được đua vào để đảm bảo cho mỗi hành trình của người du lịch chỉ chúa mừt chu trình duy nhất
Ui - Uj + nXij < n - Ì, 2 < í ệ- ì < n, (2.4)
trong đó các biến Ui, Uj nhận các giá trị nguyên hay thực. Thật vậy, nếu trong hành trình nào đó của người du lịch thỏa mãn (2.1)-(2.3) có chứa nhiều chu trình con (Hình 2.1(b)) thì phải có mừt chu trình con không đi qua thành phố Ì (nếu cẩn thì ta
đánh số lại). Giả sử đó là chu trình đi qua các thành phố ú, i 2 , • • • , t'r, iu trong đó ik > Ì với mọi k = ì, • • • , r. Do đó
*Ì1Í2 — •^Í2»3 —•••—£ tru = 1.
Từ (2.4) ta CÓ
Ui, - ui 2 + nxixi2 < n - Ì
^12 — UÌ3 + ft£i2t3 < n — Ì
"ir - «<1 + nxiril < n - 1.
Lấy tổng các bất đẳng thức này, ta sẽ nhận được điều mâu thuẫn là nr < rịn - lị Vậy mỗi hành trình thỏa mãn (2.1)-(2.4) chỉ chứa đúng mừt chu trình duy nhất. Mặt khác, mọi hành trình gồm đúng mừt chu trình duy nhất đều thỏa mãn điều kiện (2.4).
46 Các phương pháp tối ưu
Thật vậy, xét mừt hành trình như thế. Đạt Ui = t nếu thành phố í được đi tới ở bu* thứ í (đánh số theo thứ tự cách đi) trong hành trình, í = 2,3, • , n. Ta có
Ui - u3ì < n - Ì V
Do đó điều kiện (2.4) được thỏa mãn với mọi ly = 0. Với Xịị = Ì, điểu kiện (2.4) trở thành đẳng thúc vì
Ui - Uj + nXịj = í - (í + 1) + n = n - 1.
Vậy, bài toán người du lịch được phát biểu nhu sau
n ti
min V ^2 dixiỉ 04 Phí củ a n8ười d u
1=1 j=i
n
v.đ.k. ^ l y = Ì, Ì = Ì, • • • , n
n
Ị ^ i y = Ì, j = Ì,••• ,n
i=l
lý 6 {0,1} ị = Ì,•• • ,n, j = Ì,• • • ,n
Ui - ụ, + nxy < n - Ì, 2 < i ^ j < n,
trong đó các biến Ui nhận các giá trị nguyên hay thực.
Từ nhũng năm 80 của thế kỷ 20, bài toán này đã trờ thành bài toán thường ngày trong công nghệ sản xuất vi mạch với số điểm phải đi qua lên tới mấy chục vạn, thâm chí cả triệu. Còn nhiều bài toán thực tế có mô hình toán học là bài toán này. Chẳng hạn: bài toán tìm hành trình tối ưu cho việc phân phối hay thu gom sàn phẩm (thư từ, báo chí, thu tiền dịch vụ nào đó...), bài toán lập trình tự kiểm tra định kỳ
máy móc, lập bình tự gia công các chi tiết máy...
Ví dụ 2.8. (Bài toán ba lô (Knapsack Problem))
Có mừt tập hợp gồm n loại đồ vật khác nhau. Đồ vật ị có dọng lượng là dị và có giá tri sử dụng là Cị, ị = Ì, • • • , Tì. Bài toán đặt ra là cần lựa chọn mừt tập con các đổ vật để cho vào mừt cái ba lô sao cho tổng giá trị sử dụng của chúng là lòn nhất và tổng trọng lượng không được vượt quá tải trọng 6 cho trước của ba lô. Sau đây là mừt số dạng bài toán ba lô thường gặp.
0 Bài toán ba lô 0 - 1: Nếu mỗi loại đổ vật ị chi có thể lựa chọn hoặc mang theo hoặc không mang theo thì đặt biến số
_ ị Ì nếu đồ vật j được chọn mang theo
i' ~ Ị 0 nếu đồ vật ì không được chọn mang theo.
Chương ĩ. Bài toán tối ưu 47
Khi đó, bài toán ba lô cố thể diễn đạt thành
n
max f(x) = jT CịXị
j=i
ti
v.đ.k. djXj < b
*j6{0,l}, j = l,2,-",n.
0 Bài toán ba lô nguyên bị chặn: Nếu đổ vật ị có thể chọn với số lượng tối đa là Thị thì bài toán trở thành
ti
max f(x) = ^2 c ixj
j=i
n
v.đ.k. ^2 aixi ^ ^
j=l
Xj e {0,Ì,• • • ,m,j}, j = 1,2,- - ,n,
trong đó Xj là số lượng đồ vật loại j được chọn xếp vào ba lô để được giá trị hàm mục tiêu lớn nhất.
0 Bài toán ba lô nguyên không bị chặn: Trong bài toán mỗi đổ vật cố thể chọn với số lượng không hạn chế. Cụ thể, bài toán được phát biểu là
max Ị{x) = ỵềcixj
n
v.đ.k. 2 ^ àịXị < b
Xj > 0 và nguyên, ị = Ì, 2, • • • , n.
Vì trọng lượng của mừt đổ vật loại ị là dj > 0 nên biến nguyên Xj nào của bài toán này cũng sẽ bị chặn bồi tải trọng b của ba lô.
0 Một số dạng khác: Ngoài các dạng vừa trình bày, còn mừt vài dạng khác của bài toán ba lô như: Bài toán ba lô đa lựa chọn (chọn đồ vật ị trong mừt nhóm ai nào đó) hay Bài toán tổng trên tập con (chọn mừt tập con của tập các số Oi, 02, • • • , an sao cho tổng các số thuừc tập con được chọn là lớn nhất, miên là không vượt quá 6 cho trước)...
0 Phạm vi ồng dụng: Bất chấp tên gọi, nhũng ứng dụng thực tiễn của bài toán ba lô không bị hạn chế trong phạm vi các vấn đề sắp xếp. Chẳng hạn, bài toán đổi tiền:
48 Các phương pháp tối ưu
"Mừt thủ quỹ phải trả lại số tiền 6 cho khách hàng bằng cách dùng mừt số lượng à nhất các tờ giấy bạc với trị giá lần lượt là Oi, a2, • • • Ôn" cũng có mô hình toán học là bài toán ba lô 0 - Ì
n
min Ị{x) = Ỵ j X j
n
v.đ.k. >J aixi ~ b
3=1
tị > 0 và nguyên, ị = Ì, 2, • • • ,n,
trong đó ạ, là trị giá tờ bạc loại ị, Xj là số tờ giấy bạc loại ì cần sử dụng.
Rất nhiều vấn đề nảy sinh trong mừt số ngành công nghiệp như: xếp dỡ hàng hóa lên tàu, pha cắt nguyên liệu, điều khiển ngân sách, quản lý tài chính... đều có thể diên đạt như bài toán ba lô ở dạng này hay dạng khác.
Ngoài ra, bài toán ba lô xuất hiện nhu bài toán con trong bài toán phân việc mà rừng (bài toán được dùng thuồng xuyên khi giải các bài toán tìm hành trình tối liu cho các loại xe cừ) trong các bài toán xếp lịch bay cho hàng không, trong các bải toán lập ke hoạch sản xuất, bài toán gừp và tách trên đồ thị, trong thiết kế mừt số vi mạch điện tử...
Ví dụ 2.9. (Bài toán phân bổ tài nguyên)
Cần phân phối mừt loại tài nguyên nào đó vói trữ lượng b cho Tì nhà máy. Biết rằng nếu phân phối cho nhà máy thứ ị mừt lượng tài nguyên là Xj thì hiệu quả mang lại là 3 + Wị
v.đ.k. tui = VÕ* - lo) 2 + (ỉfc - yo)2, • = 1,2,3,4
(xi-l) 2 + (yi-4) 2< 4
te - 9) 2 + (y2 - 5) 2 < Ì
6 < x3 < 8
- 2 < y3 < 2
2 < 14 < 4
- 3 < Vi <-l .
Chương 2. Bài toán tối ưu 51
Ví dụ 2.12. (Tim tâm cụm)
Cho tập hợp k điểm {a \ • • •, a*} c R". Tim điểm X* € Ì " sao cho tổng khoảng cách từ mỗi a*, i = Ì, • • • , k, đến X* là nhỏ nhất.
Mở hình toán học của bài toán này như sau
min f(x), v.đ.k. ì € w,
trong đố
/(z) = ||z-a 1|| + ..- + ||x-af c ||
là hàm tổng khoảng cách.
Nếu ta coi mỗi a' là mừt trung tâm dân cư còn X* là địa điểm cần xây dụng mừt cơ sờ dịch vụ (trường học, siêu thị, bệnh viện, v.v...) thì đây là bài toán lựa chọn địa điểm xây dụng mừt cơ sở dịch vụ sao cho tổng đừ dài các đường đi từ mỗi khu dân cu đến cơ sở dịch vụ đó là ngắn nhất cố thể.
2.2 Bài toán tối ưu và 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.đ.k. X e D, (Pi)
hoặc
max f{x) v.đ.k. xe D, (P2)
trong đó D c R" được gọi là tập nghiệm chấp nhận được hay tập ràng buộc và / : D -* E là hàm mục tiêu. Mỗi điểm ĩ G 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 (có thể gọi tắt là một phương án). Điểm ì* € D mà
/(x*) < f(x) Vx G 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 (global minimizer), hoặc chỉ đơn giản là nghiệm của bài toán (Pi). Người ta còn gọi mừt nghiêm tối ưu là mừt phương án tối ưu hay lời giải của bài toán đã cho. Điểm X* G D được gọi là nghiệm cực tiểu toàn cục chặt (strictly global minimứer) nếu
/(x*) < ỉ(x) Vx G D và X ệ X*.
Không phải bài toán (Pi) nào cũng có nghiêm cực tiêu toàn cục và nếu bài toán có nghiêm cực tiểu toàn cục thì cũng chưa chắc có nghiệm cực tiêu toàn cục chặt. Xem minh họa ở Hình 2.3 (trường hợp hàm mục tiêu /(x j là hàm mừt biến).
52 Các phương pháp tối ưu
Nghiệm cực tiểu Không có nghiệm Nghiệm cực tiểu toàn cục chặt cục tiểu toàn cục toàn cục không chặt
Hình 23
Giá trị tối ưu (hay giá trị cực tiểu) của bài toán (Pị) được kí kiêu là min f(x) hoặc min{/(x) I X G D}.
Nếu bài toán (Pi) có nghiêm tối ưu là ì* tíu
Ịự) = min{/(x) I X e Dị
Ta ký hiệu Argmin{/(x)|i G D} là tập nghiệm tối ưu của bài toán (Pi). Nếu bài toán chỉ có mừt nghiệm tối uu X* thì có thè viết x' = argmin{/(i)|i € 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 (PĨ) nếu tổn tại mừt e-lân cận B(x*,e) của điểm ì* 6 í) sao cho
/(!*)< f(x) VxeB(x*,e)nD.
Điểm X* e 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 (Pi) nếu tổn tại mừt e-lân cận B(x',e) của điểm X* e D sao cho
f{x') min hoác min/(x).
v.đ.k. X 6 D
Tương tự, bài toán (P2) cũng thường được phát biểu dưới dạng
max{/(i) I X € D} hoác Ị(x)—• max hoác max/(i).
v.đ.k. xeD
Các khái niệm tương tự cũng được định nghĩa cho bài toán (P2). Cụ thể, nếu tồn tại mừt e-lân cận B(x*, e) cùa điểm X* e D sao cho
fự)>f{x) VxeB{x\e)nD
thì X* được gọi là nghiêm tối ưu địa phương hay nghiệm cực đại địa phương của bài toán (P2). Nếu tồn tại mừt e-lân cận B(x*, ế) của điểm ĩ'£ Ũ sao cho
f{x') > f{x) Vi € Bự, é) n D và X ệ X*
thì X* được gọi là nghiệm tối ưu địa phương chặt hay nghiệm cực đại địa phương chặt của bài toán (F2 ).
Điểm X* € D thỏa mãn f(x*) > f(x) với mọi 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 đại toàn cục (gĩobal măximừer) hoặc chỉ đơn giản là nghiệm của bài toán (p2 ). Nếu X* e D thỏa mãn
/(ì*) > /(ì) Vx € í) và X Ỷ X*
54 Các phung pháp tất ưu
thì ta gọi X* là nghiệm tối ưu toàn cục chặt (strictly global maximứer) của bài toán (P2). Giá trị tối ưu (hay giá trị cực đại) cùa bài toán (Pĩ) được kí kiệu là
max{/(x) I X € D} hoặc max /(ì).
xeo
Tương tự như đối với bài toán (Pi), ta ký hiệu Argmax{/(x)|x € D) là tập nghiệm tối ưu của bài toán (P2). Truông hợp bài toán đà có mừt nghiệm tối ưu ì* thì ta cũng có thể viết ì* = argmax{/(x)|x G £>}.
Chú ý 2.1. i) Bài toán (Pi) tương đương với bài toán
max -f{x) v.đ.k. xeD
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 của chúng thì ngược dấu, tức
min{/(i) \x€D} = - max{-/(x) I X 6 D).
Vì vậy, không giảm tổng quát, ta chỉ cần xét bài toán (Pi) hoặc bài toán (P2).
ii) Nếu D = Rnthì ta nói (Pi) là bài toán tối ưu không ràng buộc. Ngược lại, nếu Ó c Rnthì ta nói (Pi) là bài toán tối ưu có ràng buộc. Trong các bài toán tó ưu có ràng buừc, tập D thường được xác định bôi
í) := {x € R" U(x) < 0, i = Ì, •••,?}, (2.5)
với gùi = Ì, ••• ,p, là các hàm thục xác định trên tập A D D (thông thường A = Rn). Ta gọi gi(x), i = Ì, • • • ,m, là các hàm ràng buộc. Mỏi hệ thúc 0i(x) < 0, i 6 {Ì, • • • ,p}, được gọi là mừt ràng buộc của bài toán. Vì ràng buừc
9i{x)>0 0
và
5i(x =0 & ỉ _f\^n [-9i{x)<0
nên rõ ràng biêu diễn (2.5) bao gồm hết các loại ràng buừc.
Chú ý 2.2. Nghiêm tối ưu toàn cục cũng là nghiệm tối ưu địa phương nhung điêu ngược lại chua chắc đúng. Tuy nhiên, nếu D là tập lồi và f{x) là hàm lồi thì nghiệm tối ưu địa phương của bài toán (Pi) cũng là nghiệm tối ưu toàn cục. Cụ thể,
Mệnh đề 2.1. Cho hàm lồi ỉ : Rn -> Ì vò tập lồi khác rỗng D c R". Yét bài toán mm{f{x)\xeD}.Khiđó:
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à nghiệm tối ưu địa phương chặt hoặc Ị là hàm lồi chặt thì x' là nghiệm tôi ưu toàn cục duy nhất của bài toán.
Chương ĩ. Bài toán tối ưu 55
Chồng minh. i) Giả sử X* e D là mừt nghiêm tối ưu địa phương của bài toán min{/(i)\x e D). Theo định nghĩa, tổn tại mừt e-lân cận B(x', e) của điểm ì* e D sao cho
fự) 0+. Ta có thể chọn được XA G B(x',e) n D với mừt e > 0. Điều này và (2.6) mâu thuẫn với giả thiết ì* là nghiêm tối ưu địa phương chặt. Vì vậy X* phải là nghiệm tối ưu toàn cục duy nhất.
Cuối cùng, giả sử rằng X* là nghiêm tối ưu địa phương và hàm mục tiêu / là lồi chặt. Vì hàm lồi chặt là hàm lồi nên từ i) ta có X* là nghiêm tối ưu toàn cục. Ta cũng giả thiết phản chúng rằng X* không phải là nghiệm tối ưu toàn cục duy nhất, tức tồn tạ xe Ó, xệ X* và Ị (ì) = f(x*). Do / là hàm lồi chặt nên
Do D là tập lồi nên {\ĩ + ịx*) € D và bất đẳng thức trên mâu thuẫn với giả thiết X* là nghiệm tối ưu toàn cục của bài toán, chứng tỏ X* là nghiệm tối ưu toàn cục duy nhất. •
Chú ý 2.3. Nếu bài toán (Pi) không có nghiệm tối ưu thì giá trị tối ưu của bài toán này, ký hiệu là inf Ị(D), là cân dưới lớn nhất (hay giá trị iníimum) hàm / trên D. Giả sử to - inf f(Ó) với to € R u {-oo} Khi đó,
f{x) >t0 Vi G D và 3{xn} c D sao cho lim /(xn) = í0.
T\rctog tự, nếu bài toán (P2) không có nghiệm tối ưu thì giá trị tối ưu của bài toán này, ký hiệu là súp/(£>), là cận trên nhỏ nhất (hay giá trị supremum) hàm / trên D. Nêu u = sup/(£>), í. € Ru {+00} thì
f(x) < í. Vi € D và 3{in} c D sao cho lim f(xn) = í..
56 Các phương pháp tối ưu
Ví dụ 2.13. i) Cho f(x) = cos X, D = R. Khi đó, bài toán (Pi) tuông ứng có vổ số nghiệm tối ưu toàn cục,
Argmin{cos X ị X 6 R} = {ĩ = {2k + l)ir, fc = 0, ±1, ±2, • • •}
và giá trị tói ưu là min{cosx I X € ầ) = -1.
Tập nghiệm tối uu của bài toán (P2) tương ứng là:
Argmax{cosx I X € K} = {ỉ = 2kn, k = ữ,±1,±2,-• •}
và giá trị tối ưu là max{cos 11 X € R} = 1.
ii)Cho
f(x) = \x\ nếu X < Ì
(i-2) 2- l nếui>l,D = R.
Đồ thị của hàm này được minh họa ở Hình 2.5(a). Dễ thấy X = 2 là nghiệm cực tiếu toàn cục duy nhất. Điểm X = 0 là nghiệm cực tiểu địa phương của / trên D. Giá trị tối ưu min{/(x)|x Ẽ Ũ } = /(2) = - 1 .
Điểm X = Ì là nghiệm cực đại địa phương. Khống tổn tại nghiệm cực đại toàn cục của / trên D và súpỊ(D) = +00.
JT/2
Ũ
-ff/'2
(b)
Hình 2£
iii) Cho f{x) = arctgx và D = R. Dê thấy, trẽn R, hàm / không có mừt nghiêm cực tiểu địa phương, cực đại địa phương, cực tiểu toàn cục hoặc cục đại toàn cục nào. Và ta có inf Ị{D) = - § và súp/(5) = +ị; (xem Hình 2.5(b)j.
iv) Cho f(x) = Xi và
D = {x € R21 lị + xị < 4, x\ > 1}.
Hình 2.6(a) biểu diễn tập D (phẩn gạch chéo). Hàm / có mừt nghiêm cục tiểu toàn cục trên D là X = -2.0) T và vô số nghiêm cực tiểu địa phương, đó là cả đoạn
Chương 2. Bài toán tối ưu 57
thẳng nối (Ì, y/3)T và (Ì, -y/ĩ)T: Giá toi tối ưu của bài toán (Pi) tương úng là mOxeD f(x) = -2.
T\iơng tạ, X = (2,0)r là nghiệm cục đại toàn cục duy nhất của bài toán (P2) tuông úng; tất cả những điểm nằm trên đoạn thẳng nối (-1 , \/3) T và (-1,-y/Z) T đêu là nghiêm cực đại địa phương và giá trị tối ưu maxie£ ) f(x) = 2.
v) Cho ỉ{x) = li và D = {x G R2 I XịXi < 0} (xem Hình 2.6(b)). Khi đó, bài toán (Pi) tương úng cố vổ số nghiêm cực tiểu địa phương, đố là tập các điểm {x € K21 Xi = 0, x2 < 0}; không có nghiệm cực tiểu toàn cục và inf f(D) = -00.
Bài toán (P2) tương úng có vổ số nghiệm cực đại địa phương, đó là tập các điểm {x 6 K21 l i = 0, Xi > 0}; không có nghiệm cực đại toàn cục và súp f(D) = +00.
Hình 2.6
2.3 Các 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 toá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 /(ì) là hàm tuyến tính và tập chấp nhận được D c R" là tập lồi đa diện (tức các hàm ràng buừc 9i{x), ì = Ì, • • • , m là các hàm afin).
• Quy hoạch nguyên (hay Tối ưu rời rạc (tổ hợp)): tập chấp nhận được DcR" có cấu tníc rời rạc. Mừt trưòng hợp riêng quan trọng của quy hoạch nguyên là bài toán quy hoạch tuyến tính nguyên, đó là bài toán quy hoạch tuyến tính mà các biến số chỉ lấy giá trị nguyên.
• Quy hoạch phi tuyến: hàm mục tiêu f(x) hoặc mừt trong các hàm ràng buừc Jj(x), i = Ì, • • • , m không phải 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à:
58 Các phung pháp tối ưu
+ Quy hoạch lồi: là bài toán cực tiểu mừt hàm mục tiêu /(x) là hàm lồi trên tạp chấp nhấn được D c Rn là tập lồi (hay cục đại mừt hàm lom trên tập lồi). Theo Mênh đề 2.1, các bài toán quy hoạch lồi có mừt tính chất rất đẹp là nghiêm tối un địa phương (nếu có) cũng là nghiệm tối ưu toàn cục.
+ Quy hoạch lõm: là bài toán cực tiểu mừt hàm mục tiêu /(x) là hàm lõm Mi tập chấp nhận được D c M" là tập tói. Đây là lớp bài toán tiêu biểu của Quy hoạch toàn cục. Mừt bài toán là bài toán quy hoạch toàn cục nếu nghiêm tối ưu địa phuong của nó chua chắc là nghiệm tối ưu toàn cục.
• Quy hoạch động: bài toá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 quá trình phát triển theo thời gian. Trong nhiều truồng hợp, người ta đua bài toán quy hoạch đừng về dạng bài toán quy hoạch tuyến tính với kích thước lớn.
• Quy hoạch đa mục tiêu: bài toán này không phải chỉ có mừt hàm mục tiêu duy nhất như bài toán (Pi) (hoặc (P2)) mà ta phải cực tiểu (hoặc cực đại) đồng thòi p (với p > 2) hàm mục tiêu trên tập chấp nhân được khác rỗng D c R" và các mục tiêu này có thể không tương thích với nhau.
• Ngoài ra còn có Quy hoạch d.c (hàm mục tiêu hay các hàm ràng buừc là hiệu của hai hàm lồi), Quy hoạch ngẫu nhiên (các tham số của bài toán không có giá bị xác định mà nó được mô tả bời các phân phối xác suất), Quy hoạch tham số (các hệ số của hàm mục tiêu hay hàm ràng buừc phụ thuừc vào mừt hay nhiều tham số)...
Trong giáo trình này, chúng ta trình bày cơ sở lý thuyết và mừt số phương pháp giải các bài toán thuừc:
- Quy hoạch tuyến tính (Chương 3) và mừt trường hợp riêng quan trọng của nó là Bài toán vận tải (Chương 4);
- Quy hoạch nguyên (Chương 5);
- Quy hoạch phi tuyến, bao hàm cả bài toán tối liu không có ràng buừc, bài toán tôi ưu có ràng buừc và quy hoạch lồi (Chương 6).
2.4 Điều kiện tồn tại nghiệm
Mục đích của Quy hoạch toá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 toán để tìm nghiêm của bài toán tối ưu. Câu hỏi đầu tiên đặt la là "bài toá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, (Pi)
ương đó D c R" và Ị(x) là mừt hàm thực xác định trên mừt tập mờ chúa D. Khi đó, có mừt trong bốn khả năng sau có thể xảy ra:
i) Bài toán (PỊ) không có phương án chấp nhân (toạc, tức D = 0;
Chương 2. Bỉu toán tối ưu 59
ii) Bài toán có nghiệm tối liu, túc tồn tại X* € D sao cho
/(«•) f(x), với xeD}
đống và có một cận dưới hữu hạn.
Chồng minh. (=>) Giả sử 1° là nghiệm tối ưu của bài toán (Pi). Khi đó, ta có
/(ì0) = min/(ì) và /(0)+ = [/(x°),+oo).
xíu
Hiên nhiên f(D)+ là tập đóng và nhận f{x°) là mừt cận dưới.
(•*=) Ngược lại, nếu tập /(£>)+ có mừt cận dưới hữu hạn thì cận đuôi lớn nhất (hay iníĩmum) của tập này là hữu hạn và ta ký hiệu nó là to. Theo định nghĩa của infimum, í > to vói mọi t e /(£>)+ và tổn tại mừt dãy {í„} c /(£>)+ hừi tụ đến to. Vì /(£))+ la tập đóng nên í 0 € /(£>)+. Theo định nghĩa của tập /(£>)+, tồn tại 1° € Ó sao cho ío > f(x°). Hiển nhiên là /(x°) cũng thuừc /(£>)+ và vì í 0 là cận dưới lớn nhất của tập f{D)+ nên ta có /(í 0) > t0. Suy ra, to = /(ì 0). Điều đó chúng tò x° là nghiệm tối ưu của bài toán (Pi). •
Định lý 2.1. Cho D là tập compac khác rỗng. Khi đó:
i) Nếu hàm Ị nửa liên tục dưới trên D thì bài toán (Pi) có nghiệm tối ưu; li) Nếu hàm Ị nửa liên tục trên trên D thì bài toán (P2) có nghiệm tối ưu.
Chồng minh. Do tính tương tự, ta chỉ cần chứng minh phần (i). Giả sử giá trị tối ưu của bài toán (Pi) là to ='mĩf(D). Theo định nghĩa,
f{x)>t0VxeD (2.7)
và
3 dãy { i n} c D sao cho lim /(xn) = í 0 -
60 Các phương pháp tối ưu
Do D là tập compac nên có mừt dãy con của dãy {ì"} hừi tụ đối mừt điểm x° € D. Để đon gian, ta có thể giả thiết luôn ràng lim*!*, ì " = x° € D. Do / nửa liên tục dưới tại 1° € D nen f(x°) < lim^oo /(> ) = to. Kít hợp sự kiện này với (2.7) ta
to = inf/(D) = /(*»),
chứng tỏ 1° là nghiêm tối ưu của bài toán (À). ũ.
Hệ quả 2.1. (Định lý Weierstrass7) M?H tập D là compac và hàm Ị liên tục trên D thì cả hai bài toán (Pi) VÀ (P2) đều có nghiệm tối ưu.
Chồng minh. Hàm liên tục là hàm vừa nửa liên tục trên vừa 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ý 2. Ì. ũ
Nếu tập khác rông D chỉ đóng mà không bị chăn và hàm / nửa liên tục dưới tròi D đù, nói chung, có thể hàm / không đạt cực tiêu trên D, tức bài toán (Pi) không có nghiệm tối liu. Tuy nhiên,
Định lý 2.2. Cho tập đóng khác rỗng D c R". Nếu hàm Ị là nửa liên tục dưới trên D và thỏa mãn điều kiện bồc (coercive) trên D,
f(x) -* +00 khi X 6 D, và \\x\\ -> +00
thì bài toán (Pi) có nghiệm tối ưu.
Chồng minh. Lấy mừt điểm bất kỳ x° € D. Trước hết, ta chứng minh rằng tập múc dưới
D = {xeD\f(x)<ỉ(x°)}
là tập compac. Thật vậy, do / là nửa liên tục dirới trên D nên với mồi dãy {ì71} c D, {x11} -> ĩ mà dãy {/(xn)} hừi tụ, ta có
/(x)< lim/(*")<
n-»oo
Suy ra ĩ € ồ, chúng tỏ D là tập đóng. Hơn nữa, nếu ồ không bị chặn thì phải tổn tại mừt dãy (xk) c ỗ , tức /(í*) < /(ì 0), sao cho |Ịxfc|| -> +00. Do điều kiên bức nên f(xk) -» +00, mâu thuẫn với sự kiện {xk} c D. Vậy ữ là tập cơmpac. Tko Định lý 2.1(i), hàm / đạt cực tiểu ttên ỏ, tức tồn tại ì* € D sao cho /(ì*) < /(ì) với mọi ì G D. Dễ ửiấy, ì* cũng chính là nghiệm cục tiểu của bài toán (Pj). ũ
7Karl Theodor VVilhelm WEIERSTRASS (1815 - 1897): Nhà toán học Đức. Ông nổl ù&Dong các chúng minh toán học và được mệnh danh lì "cha đè CÙI Giải tích hiện đại', ông là người phra khái niệm hừi tụ đều và giải thích mừt cách chặt chẽ các khái niệm hàm số, cục trị, đạo hàm, và đặc biệt làkhái niệm giới hạn.
Chương 2. Bài toán tối ưu 61
Bài tập Chuông 2
1. Cho ví dụ về hàm số / và tập D c Rn sao cho: i) Hàm / có mừt cực tiểu địa phương nhung không cố cực tiểu toàn cục trên D; li) Hàm / khổng có cả cực tiểu địa phương và cực tiểu toàn cục trên D; xà) Hàm / có các điểm cực tiểu địa phương và mừt điểm cực tiểu toàn cục với giá trị hàm mục tiêu khác nhau trên D; iv) Hàm / có nhiều điểm cực tiểu toàn cục trên D. Đặt câu hỏi tương tự cho cực dại.
2. Xét mừt bài toán tối ưu có tập chấp nhạn được xác định bởi các ràng buừc Ì - x\ - xị > 0, Ì - Xi - Xì > 0, Xì > 0.
Xác định trong các điểm sau đây, điểm nào là không chấp nhận được, điểm nào là chấp nhận được và nếu là điểm chấp nhận được thì đó là điểm bong hay điểm biên:'xa = (ị,ị)T,xb = (1,1)',*e = (-1,0)',I d = H,0) T và
3. Cho hàm mừt biến
f(x) = ì4- 6x3 + 3 i 2+ lũi.
i) Vẽ đổ thị của hàm số này?
ii) Xác định nghiệm tối ưu địa phương và nghiệm tối ưu toàn cục của bài toán {min f{x)\x € R}.
4. Xét bài toán
min Xi v.đ.k. (li - Ì)2 + xị = l, (li + Ì)2 + xị = l.
ì) Vẽ tập chấp nhân được;
li) Có hay không cực tiểu địa phương và cực tiểu toàn cục ?
5. Cho / là hàm lồi (tu., hàm lõm) trên tập đa diện D. Chúng minh rằng hàm / đạt cục đại (tư., cục tiểu) toàn cục tại ít nhất mừt đỉnh của D.
6. Giải bài toán sau
max{xỉ + Z21 3ii +x2 < 15, 2%1 -312 < 6, I2 < lo, 11,12 > 0}. (Gợi ý: Xem bài tập 5)
7. Xét bài toán min {/(ì) ị X e D}, trong đó D là tập các số nguyên. Chứng minh rằng môi điểm X e D đều là nghiêm cực tiểu địa phương.
8. Cho X = [a, 6] c Ì và / là hàm thực xác định trên X. Chứng minh rằng: i) Nếu / đạt cực tiêu địa phương tại X = a và tồn tại /+'(a) thì /ị(a) > 0; li) Nếu / đạt cục tiêu địa phương tại X = b và tồn tại /Ì (6) thì f'_ (6) < 0.
62 Các phương pháp tối ưu
9. Diêm (0,0)T có phải là nghiệm cực tiểu địa phương, nghiêm cực tiểu toàn cục của bài toán min{/(i)|x € R2} khổng, toong đó
i)f{xi,x2) = y/xị + xị;
ú) f{xux2) = xi + xị{2 - Tị)3.
Giải thích?
10. Mừt xí nghiệp có thể sử dụng tối đa 550 giờ máy cán, 430 giờ máy tiên và 200 giờ máy mài để sản xuất ba loại sản phẩm. Biết rằng: Để sản xuất mừt đơn vị sản phẩm loại thú nhất cần 9 giờ máy cán, 5 giờ máy tiện và Ì giờ máy mài. Để sản xuất mừt đem vị sản phẩm loại thứ ba cần 8 giờ máy cán, 3 giờ máy tiện và 3 giờ máy mài. Mất 5 giờ máy cán và 3 giờ máy tiện để sàn xuất mừt đơn vị sản phẩm loại thứ hai. Giá bán mỏi sản phẩm loại thứ nhít, thứ hai và thứ ba tương ứng là 100$, 120$ và 55$. Xí nghiệp cần quyết định san xuất mỗi loại sản phẩm bao nhiêu đơn vị để doanh thu lốn nhất. Hãy thiết lập mô hình toán học cho bài toán trên?
Chươn g 3
Q u y hoạc h tuyế n tín h
Năm 1939, nhà xuất bản của Đại học Leningrad đã in cuốn sách [14] của Kan torovich1 với tựa đè: "Phương pháp toán học về tổ chồc và ké'hoạch hóa sản xuất", trong đó tập trung vào xây dụng công thức của các vái đẻ kinh tế cơ bản, những biểu thức toán học của chúng, mừt phác thảo về phương pháp giải và thảo luận về ý nghĩa kinh tế của nó. về thực chất, nó chứa đụng những ý tưởng chính về lý thuyết và thuật toán giải quy hoạch tuyến tính. Tuy nhiên, phương Tây đã không biết đến công trình này trong nhiêu năm. Sau đó, năm 1947, Dantàg2 và các cừng sự phát hiện lại mô hình quy hoạch tuyến tính khi nghiên cứu bài toán lập kế hoạch cho không quân Mỹ. Cùng năm 1947, Dantãg đã công bố thuật toán đơn hình (simplex algorithm) nổi tiếng để giải bài toán quy hoạch tuyến tính.
Quy hoạch tuyến tính là mừt bừ phân quan trọng của quy hoạch toán học. Theo bản tin của Liên đoàn Toán học thế giới 1/2005: Mừt trong các thành tựu vĩ đại của thế kỷ XX là đã phát minh và phát triển lý thuyết quy hoạch tuyến tính. Đây là mô hình toán của nhiều bài toán thực tế thuừc các lĩnh vực khác nhau như kinh tế, viễn thông, xây dựng... Hiệu quả của việc úng dụng quy hoạch tuyến tính giải quyết các bài toán trong kinh tế đã được ghi nhận bằng sự kiện L.v. Kantorovich và T. c. Koopmans được nhận giải thuồng Nobel dành cho khoa học kinh tế (1975). Hơn nữa quy hoạch tuyến tính là mừt mô hình toán đơn giản và dễ giải. Các thuật toán giải quy hoạch tuyến tính còn là công cụ để giải các bài toán phức tạp hơn như tối ưu phi tuyến, tối ưu đa mục tiêu...
'Ltonid Vitaliyevich KANTOROVICH (19/1/1912 - 7/4/1986): Nhà toán học và kinh tế học người Nga. Cùng với Tjalling Koopmans, ông dược nhận giãi thưởng Nobel dành cho Khoa học Kinh tế năm 1975 "vì những đóng góp của họ cho lý thuyết phân bố lối ưu các nguồn lục."
JGeogrc Bernard DANTZIG (8/11/1914 - 13/5/2005): Nhà toán học người Mỹ. Năm 1975, ông là nguời đầu tiên được nhạn giải thưởng mang tên nhà toán học John von Neumann vì đóng góp quan tọng cho lý thuyết vận trù học (operations research) và khoa học quàn trị (management sciences).
63
64 Các phương pháp tối ưu
3.1 Định nghĩa quy hoạch tuyến tính
Bài toán quy hoạch tuyến tinh tổng quát được phát biểu như sau: min{/(x) = (c,x) |x€D}, {LI)
trong dó c = (ci, ca, • • • . Cnf € Ì" và D c Rn là tập lồi đa diện được xác định bài hệ phương trình và bất phương trình tuyến tính
OiiX\ + ai2X2 + • • • + Oinin = bị, te Li
OiiXi + aaX2 + • • • + ainxn < bị, te Lì
di\Xi + ai2X2 + ••• + ainx„ >bị, í e LỊ
trong đó Li u L2 u Lì = {1,2, ••• ,1} là tập các chỉ số, các hệ số thị và bị, ị = Ì, • • • ,i, ì = Ì, • • • ,n là các hằng số cho trước.
Nhắc lại rằng, trong bài toán trên, ta gọi
/(ì) = (c, ì) = CịXi + ••• + CnXn là hàm mục tiêu;
Cj, j = Ì, • • •, n là các /lệ số của hàm mục tiêu;
Xj, j = !,••• ,n là các biến;
{cồ, x) = (<,>) bị i = Ì, • • • , i là các ràng buộc;
Tập lồi đa diện D được gọi là tập nghiệm chấp nhận được hay tập ràng buộc. Mỗi điểm ĩ 6 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 (có thể gọi tắt là phương án). Điểm X* € D mà
/(x*) = (c, ì*) < /(ì) = (c, x) vói mọi xe D
được gọi là nghiệm tối ưu hoặc phương án tối ưu hay /ới giải của bài toán. Giá trị tối ưu của bài toán này được ký hiệu là min{(c, x)\xe D}.
Ta nói phương án ĩ = (li,-- ' ,xn)T thỏa mãn chặt ràng buộc lo, lo G {Ì, • • • ,1} nếu
n
j=i
Mừt phương án thỏa mãn chặt n ràng buừc đừc lập tuyến tính được gọi là mừt phương án cực biên. Như vậy, phương án cực biên chính là mừt đỉnh của tập lồi đa diện chấp nhận được (xem Mục 1.3.8, Chương 1). Phương án cực biên thỏa mãn chặt đúng n ràng buừc được gọi là phương án cực biên không suy biến; thỏa mãn chặt hơn n ràng buừc gọi là phương án cực biên suy biến.
Khi nghiên cứu quy hoạch tuyến tính cũng như khi áp dụng nó, người ta thường dùng hai dạng đặc thù sau:
Chương 3. Quy hoạch tuyến tinh 65
3.1.1 Dạng chuẩn tắc
min f(x) = CịXị+ 1- CnXn
n
v.đ.k. OịịXị >bi, i = Ì, • • • , m,
Zj > 0, j = !,••• ,n.
Mỗi ràng buừc OiịXị > bi, i 6 {Ì, • • • , ra} được gọi là mừt ràng buộc chính. Ràng buừc Xị > 0, j e {Ì, • • • , n} được gọi là rông ÍMíổc ítáw. Đặt A là ma trận cấp m X n với các hàng là o' = (an,oi 2 ,•••,oi n ), i = Ì,• • •,m; véc tơ 6 = (ti, • • • I M r £ K m. Bài toán quy hoạch tuyến tính chuẩn tắc được viết lại dưới dạng ma trận như sau
min f(x) =(c,x)
v.đ.k. Ax > b
x>0.
3.12 Dạng chính tác
min /(ì) = C\X\+ —I - CnXn
n
v.đ.k. 2 OỳXj = bi, í = Ì, • • •, ro,
Zj>0, j = l,-",n.
1\rong tự như dạng chuẩn tắc, ta gọi ràng buừc £"=1 fl 0, j € {Ì, • • • ,n} là ràng buừc dấu. Dạng ma trận của bài toán quy hoạch tuyến tính chính tắc là
min f(x) =(c,x)
v.đ.k. Ax = b
x>0,
trong đó ma trận A và véc tơ 6 được định nghĩa tương tự như ở dạng chuẩn tắc. Tuy nhiên, cần chú ý rằng, trong bài toán quy hoạch tuyến tính dạng chính tắc ta luôn viết các ràng buừc chinh ờ dạng sao cho 6 =(&!,••• , bm)T > 0, tức bị > 0 với mọi í = ĩ, • - ,m. Nếu tổn tại bỳ, < 0 với to € {Ì,---, m} thì ta nhân hai vế của ràng buừc chính £" = 1 a^i; = bia với -Ì ,
66 Các phương pháp tối ưu
Ví dụ 3.1. Bài toán
min f(x) = 5ii - 6x2 + 3i3
v.đJc 8x1 + 6x2 + 613 = 5
3ii - 2i 2 + 7i 3 = 7
xu Xì, 13 > 0
là mừt bài toán quy hoạch tuyến tính chính tắc, trong đó
Bài toán này có n = 3 biến và TU = ĩ ràng buừc chính.
Chú ý 3.1. Trong bài toán quy hoạch tuyến tính dạng chuẩn tắc và chính tắc, tài cả các biến đêu không âm. Do đó tập chấp nhận được của bài toán khống chứa mừt đường thẳng nào. Theo Mênh đề 1.7, tập chấp nhân được của bài toán quy hoạch tuyến tính dạng chuẩn tắc và chính tắc luôn có ít nhất mừt đỉnh.
3.13 Chuyển bài toán quy hoạch tuyến tính bát kỳ về dạng chuẩn tác hay chính tác
Mọi bài toán quy hoạch tuyến tính đều có thể đua về bài toán quy hoạch tuyến tính dạng chính tắc hoặc chuẩn tắc bằng các phép biến đổi sơ cấp sau:
0 Mừt biến Xj không bị ràng buừc dấu có thể thay bởi hiệu của hai biến không âm bằng cách đặt Xj = ĩ j - Xj với Xj > 0 và ĩ j > 0;
0 Thay biến Xj < 0 bởi biến Xj = -Tị > 0;
0 Mỗi ràng buừc bất đẳng thức
)Ẩ ũijXj < bị hoặc dịịXị > bị
có thể chuyển về ràng buừc đẳng thức nhờ đưa thêm vào mừt biến phụ xn+i > 0:
2 aiixi+ Xn+i = b< ho^c XI aý'xj ~ = bi>
0 Mỏi ràng buừc aijxj < bị có thổ viết lại thành - £ OiịXị > -bị',
0 Mỗi ràng buừc đẳng thức 2 OịịXị = bị có ứié thay bằng hai ràng buừc bất đẳng thức
y]o bị và - ^Ojji j > -bị,
0 Bài toán tìm cực đại
max{/(i) I X e D}
Chương 3. Quy hoạch tuyến tính 67
được đua vẻ bài toán tìm cục tiểu tuông đương là
min{-/(i) I X € D}
theo nghĩa: tập nghiệm tối ưu của hai bài toán này là như nhau nhưng giá trị tối ƯU trái dấu nhau,
max{/(x) I X e D} = - min{-/(x) I X € D}.
Ví dụ 32. Xét bài toán quy hoạch tuyến tính
min f(x) = ĨXị + 5i2 - 4X3
v.đ.k. 3xi - 5i2 + 3X3 < 5,
2xi + 4X2 + 6x3 = 8,
-4xi - 9X2 + 4x3 < -4,
Si > -2, 0 < x2 < 4, £3 tự do.
Để chuyển bài toán quy hoạch tuyến tính này về dạng chính tắc, trước hết thực hiện: - Nhân hai vế của ràng buừc chính thứ ba với - 1 ta được
Axi + 9x2 - ix3 > 4;
- Đổi biến Xi thành ĩ Ì với
Xi := li + 2 > 0 Xi = Xi - 2;
- Ràng buừc cận trên cùa biến thứ hai x2 < 4 được xem như ràng buừc chính thứ tin
- Biến thứ ba được đổi thành
13 = Ĩ3 - h với x3 > 0, 13 > 0.
Sau khi thay thế các biển đổi trên vào bài toán ban đầu ta nhận được bài toán
min 2 = 3ĩi + 5i2-4Ĩ3 + 4I3 - 6
v.&k. 3ĩi - 5i 2+3ĩ 3 - 3I3 < l i ,
2ĩi + 4x2+6ĩ 3 - 6I3 = 12,
4ĩi + 9i 2 -4x3 + 4 I 3 > 12,
*2 < 4,
Xì, 22, Xì, Xì > 0.
68 Các phương pháp tối ưu
Cuối cùng, sau khi bỏ hằng số -6 ở hàm mục tiêu và thèm các biến pin Xi, xi, Xe > 0 lần lượt vào các ràng buừc chính thứ nhất, thứ ba, thứ tư của bài toán này ta nhận được bài toán quy hoạch tuyến tính dạng chính tắc sau
min f'(x) = 3ĩi + 5i2 - 4Ĩ3 + 413
v.đ.k. 3ĩi - 5X2 + 3x3 - 3x3 + Xi 2ĩi + 4i2 + 6*3 - 6Ề3
4fÌ + 9 i 2 - 4ĩ 3 + 4 i 3 - 1 5
x2 + Xe
Xi, X2, Xì, h, Xi,'xẵ, XỆ
= 11, = 12, = 12,
= 4, > 0.
Giả sử (Sĩ, xỉ, ỈJ, Sỉ, Ij, i|, x;)T là nghiệm tối ưu của bài toán quy hoạch tuyến tính chính tắc này. Khi đó nghiệm tối ưu của bài toán ban đầu là X0* = {xf , xỹ, x ỹ f và giá trị tôi ưu là /(>* ) = 3i f + 5i f - 4if , trong đó ì f = ĩ j - 2, ì * = ì; và x f = ĩỉ -1| .
3.2 Sự tồn tại nghiệm và tính chất tập nghiệm của quy hoạch tuyến tính
Xét bài toán quy hoạch tuyến tính tổng quát
min{{c,i) \xeD}, {LP)
trong đó c € Rn và D c Kn là tập lồi đa diện khác rỗng.
3.2.1 Sự tồn tại nghiệm
Định lý 3.1. Nếu tập nghiệm chấp nhận được D khác rỗng và bị chặn thì bài toán quy hoạch tuyến tính (LP) luôn có nghiệm tối ưu.
Chồng minh. Theo định nghĩa, tập lồi đa diên là tập đóng. Thêm tính bị chăn nên ta có D là tập compac. Hàm tuyến tính là hàm liên tục. Theo Định lý Weierstrass (Hệ quả 2. Ì) ta có điều phải chứng minh. •
Trong trường hợp tập nghiệm chấp nhận được D khác rỗng và không bị chặn, bài toán (LP) có thể không có nghiệm. Tuy nhiên, nếu hàm mục tiêu /(ì) = (c,i) bị chặn dưới trên D thì bài toán (LP) luôn có nghiệm tối ưu.
Định lý 3.2. Nếu tập chấp nhận được D khác rỗng và hàm mục tiêu f(x) = (c, x) bị chặn dưới trên D thì bài toán quy hoạch tuyến tính (LP) luôn có nghiệm tôi ưu.