CH số 11 - B1 - ĐH KTQD Chuyên Photocopy - Đánh máy - In Luận văn, Tiểu luận : 6.280.688
Lời mở đầu
TÊt c¶ c¸c ngµnh, c¸c lÜnh vùc dï ho¹t ®éng ë ph¬ng diÖn nµo th× môc
®Ých cuèi cïng còng lµ gi¶i c¸c bµi to¸n tèi u cña ®¬n vÞ m×nh. ViÖt Nam lµ
mét minh chøng.
Trong xu thÕ héi nhËp hiÖn nay, ®Æc biÖt sau kÝ kÕt hiÖp ®Þnh th¬ng m¹i thÕ
giíi WTO, ViÖt Nam ®ang ®øng tríc nhiÒu thö th¸ch míi. Vµ c¹nh tranh trªn
th¬ng trêng quèc tÕ lµ bµi to¸n hµng ®Çu ®èi víi c¸c doanh nghiÖp trong níc.
Do tÝnh cÊp thiÕt cña thùc tÕ nªn em ®· quyÕt ®Þnh chän ®Ò tµi: “ThuËt
to¸n Frank-Wolfe”- ®©y lµ thuËt to¸n gi¶i c¸c bµi to¸n quy ho¹ch låi víi
c¸c rµng buéc tuyÕn tÝnh. Em hi väng nã cã thÓ gãp mét phÇn lµm phong phó
h¬n kho tµng thuËt to¸n gi¶i c¸c bµi to¸n tèi u.
Bài viết của em gồm 3 phần lớn (ngoài phần mục lục và phần tài liệu tham
khảo):
Thứ nhất : Lời mở đầu
Thứ hai : Nội dung
Thứ ba
: Kết luận
Trong phần nội dung,em sẽ trình bày 4 vấn đề chính:
1. Tổng quan về quy hoạch phi tuyến
2. Thuật toán Frank-Wolfe
3. Thí dụ
4. Chương trình Gamside
Cuối cùng, em xin chân thành cảm ơn các thầy giáo,cô giáo khoa Toán
kinh tế đã tạo môi trường cho em được học tập và rèn luyện. Em hết sức biết
ơn thầy giáo Ngô Văn Mỹ đã giúp em hoàn thành đề án môn học này.
Nội dung:
1.
Tổng quan về quy hoạch phi tuyến
1.1. Giới thiệu chung về QHFT
1
CH số 11 - B1 - ĐH KTQD Chuyên Photocopy - Đánh máy - In Luận văn, Tiểu luận : 6.280.688
Bài toán QHFT sẽ nói ở dưới đây không phải là bài toán QHFT thực tổng
quát, mà ta chỉ xét lớp bài toán QHFT có hàm mục tiêu là hàm khả vi liên
tục( tới bậc tuỳ ý) trên tập mở bao tập phương án D; bản thân tập phương án
cũng được xác định bởi các hàm số trong các ràng buộc là các hàm khả vi
liên tục n biến. Cụ thể ta có bài toán tổng quát sau:
f ( x) min(max)
i
g ( x)(; ; ), bi (i 1, m)
(1)
là các hàm n biến
độc lập. Ngoài ra: trong các hàm f ( x ) và g ( x) i 1, m phải có ít nhất
một hàm phi tuyến; luôn giả thiết các hàm g ( x)i 1, m là các hàm liên
Trong đó:
x R n , bi R i 1, m ; f ( x) và g i ( x ) i 1, m
i
i
tục; hàm mục tiêu
f ( x)
khả vi liên tục trên tập mở bao tập phương án D.
Tuy bài toán QHFT đã được giới hạn như trên, nhưng tính phi tuyến của
bài toán luôn tạo ra những phức tạp đáng kể khi tiệm cận với nó. Với bài
toán QHFT người ta cũng sử dụng phương pháp tiệm cận giống như bài toán
cực trị có ràng buộc cổ điển trong giải tích-tức là tìm cách đưa bài toán cực
trị có ràng buộc về bài toán cực trị tự do rồi tìm cách đưa ra điều kiện KunhTucker. Víi mét nhãm ®iÒu kiÖn bæ sung ®ñ m¹nh th× ®iÒu kiÖn KunhTucker có thể trở thành điều kiện cần và đủ đối với lời giải của (1).
1.2. Bài toán QHFT
Bài toán tổng quát QHFT có dạng như (1); tuy nhiên đôi khi để thuận tiện
trong việc giải thích ý nghĩa kinh tế ta có thể biểu diễn các dạng cụ thể sau:
f ( x ) max
2
CH số 11 - B1 - ĐH KTQD Chuyên Photocopy - Đánh máy - In Luận văn, Tiểu luận : 6.280.688
g i ( x) bi
x j 0
(i 1, m)
( j 1, n)
(1.1)
f ( x ) min
g i ( x) bi
x j 0
(i 1, m)
( j 1, n)
(1.2)
Về mặt hình thức thì ba bài toán (1),(1.1), (1.2) khác nhau, song cũng giống
như QHTT ta có thể dùng các phép biến đổi tương đương để đưa bài toán
này về bài toán kia. Cụ thể như sau:
a.
f ( x ) max f 1 ( x ) f ( x ) min
b.
g i ( x ) bi g i ( x) bi
c.
i
g
(x) bi
i
g ( x) i i
g (x) bi
d.
i
g
(x) si bi
i
g (x) bi
si 0
e.
i
g
(x) si bi
i
g (x) bi
s i 0
1.3. Điều kiện Kuhn-Tucker
Trở lại bài toán tổng quát (1) ban đầu:
3
CH số 11 - B1 - ĐH KTQD Chuyên Photocopy - Đánh máy - In Luận văn, Tiểu luận : 6.280.688
f ( x) min(max)
i
g ( x)(; ; ), bi (i 1, m)
với các giả thiết đã có về
f ( x)
và g i ( x)i
, nếu cả m ràng buộc của
( x ) i 1, m là hệ hàm độc
1, m
(1) đều có dạng đẳng thức; mxk là phương án tối ưu và thuật toán kết thúc.
Thật vậy:
Khi bài toán QHFT thứ k có dạng:
(f ( x k ), x x k ) min
Ax b
x 0
theo giả thiết f(x) lồi khả vi nên ta có:
(f ( x k ), x x k ) f ( x k ) f ( x )(x D )
f ( x ) f ( x k ) (f ( x k ), x x k )
ˆk xk ) k 0
(f ( x k ), x
f ( x ) f ( x k )(x D
=> điều phải chứng minh.
Th2: nếu
k 0
=> xˆ k x k là phương giảm của f(x). Ta xét
x x k ( xˆ k x k )
0 1
k
k
k
Và k ( ) f ( x ( xˆ x ) min là hàm lồi theo và đặt:
x k 1 x k k ( xˆ k x k )
10
CH số 11 - B1 - ĐH KTQD Chuyên Photocopy - Đánh máy - In Luận văn, Tiểu luận : 6.280.688
Và cứ tiếp tục như vậy thì thuật toán hội tụ. Bởi tập xác định của nó là tập
lồi đa diện lồi.
Tuy nhiên có thể dừng lại ở một bước bất kỳ,và chấp nhận một sai số nào đó.
Qua nội dung của thụât toán ta thấy rằng bản chất của thuật toán FrankWolfe là biến bài toán quy hoạch phi tuyến thành bài toán quy hoạch tuyến
tính thông qua tuyến tính hoá từng điểm một.
3. Thí dụ
Giải bài toán quy hoạch lồi sau:
f ( x) ( x1 2) 2 ( x2 2) 2 min
2 x1 x2 2
x1 , x2 0
Lời giải:
x2
2
x*
0
f (x)
1
x1
2
Bước 0:
Với điểm xuất phát
x 0 (0,0)
ta có:
x x 0 ( x1 , x 2 )
f ( x) (2( x1 2),2( x 2 2))
x 0 (0,0) f ( x 0 ) ( 4,4)
f ( x 0 , x x 0 ) 4 x1 4 x 2 min
11
CH số 11 - B1 - ĐH KTQD Chuyên Photocopy - Đánh máy - In Luận văn, Tiểu luận : 6.280.688
Bài toán có dạng:
f ( x) 4 x1 4 x2 min
2 x1 x2 2
x , x 0
1 2
Vì
f ( x ) ( 4,4)
là hướng tăng, hướng ngược lại là hướng giảm nên
với tập ràng buộc trên ta có phương án tối ưu là xˆ 0 (0.2)
Khi đó:
xˆ 0 x 0 (0,2)
0 (f ( x 0 , xˆ 0 x 0 ) 8 0
x x 0 ( xˆ 0 x 0 )
(0, (0,2))
(0,2 )
0 f x 0 ( xˆ 0 x 0 )
4 ( 2 2) 2
42 8 8
với
0,1
. Khi đó để giải bài toán ban đầu ta giải bài toán đối với
Điều kiện cần:
0 ' ( ) 0
8 8 0
1
Ta thấy với
1 0,1 0 ( 0) 8
0 ( 1) 4
x 1 (0,2)
Bước 1:
x x 1 ( x1 , x 2 2)
f ( x 1 ) ( 2(0 2), 2( 2 2)) ( 4,0)
f ( x 1 , x x 1 ) 4 x1 min
12
CH số 11 - B1 - ĐH KTQD Chuyên Photocopy - Đánh máy - In Luận văn, Tiểu luận : 6.280.688
2 x1 x2 2
x1 , x2 0
với ràng buộc
xˆ 1 (1,0) xˆ 1 x 1 (1,2)
1 (f ( x 1 ), xˆ 1 x 1 )
(4,0) (1,2)
4 0
Khi đó xét
x x 1 ( xˆ 1 x 1 )
(0,2) (1,2)
( , 2 2 )
1 ( ) f ( x 1 ( xˆ 1 x 1 ))
52 4 4
, ( ) 10 4
với
2
0,1
5
2
5
có kết quả sau:
1 ( 0) 5 * 0 4 * 0 4 4
1 ( 2 / 5) 5 * 4 / 25 4 * 2 / 5 4 16 / 25
1 ( 1) 5
min 1 ( ) 16 / 25 2 / 5
2 6
x2 ( , )
5 5
Bước 2:
2
6
, x2 )
5
5
2
6
16
8
f ( x 2 ) ( 2( 2), 2( 2)) (
, )
5
5
5
5
x x 2 ( x1
2 (f ( x 2 ), x x 2 )
16
8
16
x1 x 2
5
5
5
Bài toán mới có dạng:
13
CH số 11 - B1 - ĐH KTQD Chuyên Photocopy - Đánh máy - In Luận văn, Tiểu luận : 6.280.688
16 8 16
x1 x2 min
5 5 5
2 x1 x2 2
x1 , x2 0
xˆ 2 (1,0)
3 6
xˆ 2 x 2 ( , )
5 5
2 0 0
Kết luận:
2 6
x* x 2 ( , )
5 5
4.
là PATƯ và
f
*
16
5
trị tối ưu.
Phần mềm hỗ trợ: GAMS
4.1. Khái quát về GAMS
Để hỗ trợ cho việc giải các bài toán tối ưu một cách nhanh nhất và các bài
toán có số bước giải lớn, ta có phần mềm hỗ trợ GAMS.
GAMS(General Algebraic Modeling System) là một hệ thống các chương
trình giải các bài toán quy hoạch toán học.GAMS bao gồm nhiều thủ tục
khác nhau trong đó xin giới thiệu một số thủ tục sau:
LP Tìm nghiệm đúng của bài toán quy hoạch tuyến tính
MIP Tìm nghiệm đúng của bài toán quy hoạch nguyên tuyến tính
….
Trong đó có thủ tục NLP( Nonlinear Programming) để giải các bài toán
QHFT các hàm trơn.
4.2. Các nguyên tắc khi làm việc với GAMS
GAMS yêu cầu phải khai báo chính xác cấu trúc của chương trình đầu
vào.
14
CH số 11 - B1 - ĐH KTQD Chuyên Photocopy - Đánh máy - In Luận văn, Tiểu luận : 6.280.688
Toàn bộ khai báo ghi thành một tệp với phần mở rộng .gms (ví dụ:
bt.gms).
Sau khi chạy chương trình, GAMS tạo ra tệp kết quả có cùng tên tệp
với phần mở rộng .list (ví dụ: bt.list).
Mỗi chương trình có thể chứa một hay nhiều mô hình và được giải
nhờ các dòng lệnh khác nhau.
Một chương trình đúng có thể chạy nhiều lần với các mô tả biến theo
những kích thước khác nhau.
GAMS không phân biệt chữ hoa và chữ thường.
4.3. Dòng lệnh của GAMS
Một dòng lệnh của GAMS có thể bắt đầu ở đầu dòng với một từ khoá
và kết thúc bởi dấu “;”. Mỗi dòng lệnh có thể gồm nhiều câu lệnh và
mỗi câu lệnh có thể viết trên nhiều dòng lệnh khác nhau.
Nếu một dòng lệnh bắt đầu từ dấu* hoặc $title sẽ được bỏ qua khi
thực hiện chương trình và máy coi đây là một chú thích.
Một đoạn văn bản nằm giữa cặp lệnh sau là đoạn văn bản chú thích:
$ontext..
$offtext
4.4.
Những nội dung cơ bản của một chương trình giải bằng GAMS
4.4.1.
Khai báo biến
Biến tự do được khai báo với từ khoá: variable tên biến nhãn biến;
Biến định dạng được khai biến với các từ khoá:
Free variable tên biến nhãn biến; (với biến liên tục không có ràng
buộc)
Positive variable tên biến nhãn biến;(với biến liên tục không âm)
Negative variable tên biến nhãn biến;(với biến nguyên không âm)
4.4.2. Khai báo các hàm mục tiêu và các ràng buộc
15
CH số 11 - B1 - ĐH KTQD Chuyên Photocopy - Đánh máy - In Luận văn, Tiểu luận : 6.280.688
Khai báo tên và nhãn với từ khoá:
Equation tên phương trình 1 nhãn,…,tên ràng buộc 1 nhãn,…;
Khai báo biểu thức xác định hàm và các ràng buộc với cấu trúc sau:
Tên phương trình 1… biểu thức xác định phương trình 1;
…………………………………………………………..
Tên ràng buộc 1… biểu thức xác định ràng buộc 1;
…………………………………………………………...
Dấu của các phương trình và bất phương trình trong GAMS:
dấu (=): =e=
dấu không lớn hơn(≤): =l=
dấu không nhỏ hơn(≤): =g=
Các phép toán cơ bản trong GAMS:
Phép cộng: +
Phép trừ:
-
Phép nhân: *
Phép chia: /
Phép lấy luỹ thừa: **
Các hàm thông dụng trong GAMS:
Exp(x):
ex
Log(x):
ln(x)
Log10(x):
log10(x)
Sqr(x):
x2
Sqrt(x):
x
Sin(x):
sin(x)
Cos(x):
cos(x)
Arctang(x):
arctg(x)
Power(x):
xn
16
CH số 11 - B1 - ĐH KTQD Chuyên Photocopy - Đánh máy - In Luận văn, Tiểu luận : 6.280.688
4.4.3. Đặt giá trị ban đầu cho các biến
Đây là giá trị tạm thời của biến, nó sẽ thay đổi khi chương trình thực
hiện.
Trong nhiều bài toán thuật toán sẽ tự động gán giá trị xuất phát cho
các biến, có thể là giá trị cận biên hoặc giá trị bằng không nếu chúng
thoả mãn hệ ràng buộc.
chắc chắn rằng trong mọi bài toán việc chủ động đặt cho các biến giá
trị ban đầu một cách hợp lý(nếu có thể) sẽ tránh được hiện tượng bài
toán xuất phát từ điểm không xác định hàm mục tiêu hoặc các véc tơ
gradient của hàm đó, khi đó thuật toán sẽ cho ta lời giải tốt nhất.
Ta có thể đặt giá trị ban đầu cho các biến bằng một trong ba cách sau:
Đặt giá trị đúng(=) cho biến: tên biến.l=…;
Đặt giá trị không thấp hơn(≥) cho biến: tên biến.lo=…;
Đặt giá trị không cao hơn(≤) cho biến: tên biến.up=…;
4.4.4. Đặt tên cho mô hình
Model tên mô hình/ all/;
4.4.5. Chỉ định thủ giải
Một bài toán QHPT viết trên GAMS phải được giải bằng thủ tục
NPL.Trong GAMS có ba thuật toán nào để giải bài toán QHPT đó là:
Conopt, Minos và Snopt.Việc sử dụng thuật toán nào để giải một bài
toán QHPT cụ thể tuỳ vào cấu trúc, đặc điểm của bài toán đó.
Nếu ta không chọn thuật toán để giải thì thuật toán được chỉ định là
Conopt.
Cấu trúc lệnh để chỉ thủ tục giải như sau:
Solve tên mô hình minizing(maximizing) tên hàm mục tiêu
using NPL-;
4.4.6. Khai báo hiển thị kết quả
17
CH số 11 - B1 - ĐH KTQD Chuyên Photocopy - Đánh máy - In Luận văn, Tiểu luận : 6.280.688
Nếu như việc giải bài toán cho ta lời giải đúng thì ta chọn cách hiển
thị kết quả đúng giá trị của lời giải bằng lệnh có cấu trúc như sau:
Display tên biến 1.l, tên biến 2.l,…,tên biến n.l;
Nếu như việc giải bài toán cho ta lời giải gần đúng thì ta có thể chọn
cách hiển thị kết quả thấp hơn hoặc cao hơn giá trị đúng của lời giải
bằng lệnh có cấu trúc như sau:
Display tên biến 1.lo, tên biến 2.lo,…,tên biến n.lo;(thấp hơn)
Display tên biến 1.up, tên biến 2.up,…,tên biến n.up;(cao hơn)
4.5.
Chạy và sửa lỗi mô hình
4.5.1. Chạy mô hình
Trước khi yêu cầu GAMS dịch chương trình ta cần ghi lại thành một
tệp chẳng hạn bt.gms.
Nhấn nút Run( biểu tượng mũi tên màu đỏ) trên thanh công cụ để chỉ
thị cho GAMS dịch chương trình và ghi lại kết quả với tệp bt.list.
Quá trình dịch nếu có lỗi GAMS sẽ báo lỗi chi tiết trong từng dòng
lệnh với dòng báo lỗi chữ đỏ và nếu click double vào dòng chữ đỏ
này dấu nhắc sẽ đặt tại dòng lệnh có lỗi trong cửa sổ chương trình.
4.5.2. Các lỗi và thông báo lỗi
Unkown symbol: một biến, một tập hợp,… không được khai báo
hoặc không được khai báo đúng quy cách.
Suffix is missing: toán tử đối với biến thiếu phần chỉ định(.l, .up,
.lo…).
No solution: mô hình sai hoặc sử dụng thủ tục không hợp lệ.
=l=, =e=, or =g=oprator expected: lỗi dấu phép toán.
Variable wrong type: biến ngoài giới hạn khai báo.
Log of negative number division by zero gardient too big: loga và
căn bậc hai của số âm, chia cho số không.
18
CH số 11 - B1 - ĐH KTQD Chuyên Photocopy - Đánh máy - In Luận văn, Tiểu luận : 6.280.688
Uncontrolled set: một ký hiệu không có trong các tập đã khai báo.
Endog arguments: mô hình có phần tử phi tuyến không tồn tại nhưng
có mặt trong chỉ định giải.
4.6.
Ứng dụng GAMS để giải ví dụ.
variable f bien ham muc tieu;
positive variable x1 bien x1 khong am
x2 bien khong am;
equation rb ten rang buoc la rb
hsmt ten ham so muc tieu la hsmt;
* Khai bao bieu thuc ham so muc tieu va rang buoc cua bai toan
rb..2*x1+x2=l=2;
hsmt..f=e=sqr(x1-2)+sqr(x2-2);
* Dat gia tri dung cho phuong an xuat phat
x1.l=0;
x2.l=0;
* Dat ten mo hinh la qhft
model qhft/all/;
* Lua chon thu tuc de giai
solve qhft minizing f using nlp;
* Lua chon cach thuc hien thi ket qua
Display x1.l,x2.l,f.l;
Kết quả:
18 VARIABLE x1.L
=
0.400 bien x1 khong am
VARIABLE x2.L
=
1.200 bien khong am
VARIABLE f.L
=
3.200 bien ham muc tieu
Như vậy kết quả chạy máy cũng cho ta kết quả giống giải bằng tay.
19
CH số 11 - B1 - ĐH KTQD Chuyên Photocopy - Đánh máy - In Luận văn, Tiểu luận : 6.280.688
Kết luận
Trên đây là một số nghiên cứu và tổng kết của em về thuật toán FrankWolfe. Qua nội dung trên, ta thấy thuật toán Frank-Wolfe đã đóng góp một
phần vào việc giải quyết các bài toán tối ưu. Đồng thời với phần mềm
chuyên dụng GAMS chúng ta đã mở rộng thêm được các bài toán QHFT, rút
ngắn thời gian giải bằng tay. Tuy nhiên với những giả thiết mà thuật toán
Frank-Wolfe đưa ra đặc biệt là giả thiết: “các ràng buộc phải là tuyến tính”;
20
- Xem thêm -