40
Chương III
BÀI TOÁN QUY HOẠCH PHI TUYẾN

1. PHƯƠNG PHÁP RST2ANU GIẢI BÀI TOÁN TỐI ƯU
PHI TUYẾN TOÀN CỤC HỖN HỢP NGUYÊN
1.1. Đặt vấn đề
Dạng chính tắc của bài toán tối ưu một mục tiêu được biểu diễn như sau:
Min (Max) f(X) , X = (x
1
, x
2
, …, x
n
)
∈
R
n
, với các điều kiện ràng buộc
(i) g
j
(X) ≤ 0,

j = 1, 2, …, k,
(ii) g
j
(X) = 0, j = k+1, k+2, …, .m.
Trong các bài toán thực tế có thể bổ sung thêm các ràng buộc
(iii) a
i

≤ f(X). Trong trường hợp f(X
*
) ≤ f(X) chỉ đúng với
∀X∈D trong một lân cận nào đó của X
*
thì X
*
được gọi là phương án tối ưu địa
phương. Một cách tương tự, ta có thể định nghĩa khái niệm phương án tối ưu toàn cục /
địa phương cho bài toán cực đại hoá. Nếu chúng ta chỉ quan tâm tới việc tìm kiếm
phương án tối ưu toàn cục thì ta có
bài toán tối ưu toàn cục.
Các phương pháp giải bài toán tối ưu toàn cục phi tuyến đơn mục tiêu được
phân ra thành hai lớp: phương pháp tất định và phương pháp ngẫu nhiên (
deterministic
and stochastic methods
). Phương pháp tất định sử dụng các tính chất giải tích của hàm
mục tiêu và các hàm ràng buộc. Một số dạng bài toán tối ưu toàn cục với những tính
chất giải tích nhất định của hàm mục tiêu và các hàm ràng buộc có thể giải được bằng
các phương pháp tất định thích hợp, chẳng hạn như phương pháp quy hoạch toàn
phương, quy hoạch tách, quy hoạch lồi, quy hoạch d.c… Trong các trường hợp đó
phương án tố
i ưu toàn cục có thể tìm được sau một số hữu hạn bước tính toán với độ
chính xác chọn trước.
Tuy nhiên, đối với nhiều lớp bài toán tối ưu toàn cục phương pháp tất định tỏ ra
không có hiệu quả. Trong khi đó, các phương pháp ngẫu nhiên như: phương pháp đa
khởi tạo (
multistart), mô phỏng tôi (simulated annealing), thuật giải di truyền (genetic

41

được được phát sinh ra một cách ngẫu nhiên và lưu trữ trong mảng có tên A. Đánh dấu
hai điểm có giá trị hàm mục tiêu lớn nhất và nhỏ nhất tương ứng là M và L.
Trong pha địa phương, các phương án được xử lý nhằm thu được giá trị ước
lượng tốt hơn của hàm mục tiêu. Trong pha này, thuật giải xác định X* là điểm được
nội suy bậc hai dựa trên phương án L và hai phương án khác được chọn ngẫu nhiên
trong mảng A. Nếu như X* chấp nhận được thì với f(X*) ≤ f(M), M sẽ được thay thế
bởi X* trong mảng A, còn với f(X*)>f(M) M sẽ được thay thế bởi X* với xác suất
p=
exp(-β(f(X*)-f(M))/(f(X*)-f(L))) , trong đó β >0 là tham số được lựa chọn thích hợp.
Nếu X* không phải là phương án chấp nhận được, bỏ qua X* và chọn hai phương án
khác trong A một cách ngẫu nhiên rồi cùng với L tiếp tục sinh ra phương án mới. Quá
trình cứ thế tiếp diễn như vậy cho tới khi tập hợp các phương án trong A sẽ có xu hướng
co cụm lại xung quanh một phương án tối ưu toàn cục.
Lưu đồ thuật giải RST2AN được thể hiệ
n trên hình minh hoạ, trong đó:
• n, f(X), g(j), a
i
, b
i
, … là các đầu vào.

42
• A = RandomNSolution (N) phát sinh N phương án ngẫu nhiên chấp nhận
được, đồng thời tính giá trị của hàm mục tiêu và trả về kết quả cho mảng A.
Như vậy, mảng A chứa luôn cả giá trị hàm mục tiêu tương ứng với từng
phương án.

Lưu đồ thuật giải RST2ANU
• Arrange(A) sắp xếp mảng A theo thứ tự tăng dần của hàm mục tiêu.
r = random(0,1)

Phần mềm tính toán khoa học RST2ANU đã được thiết kế và xây dựng có thể sử
dụng để giải quyết nhiều mô hình tối ưu phát sinh trong lĩnh vực nông nghiệp, hỗ trợ
cho giảng dạy và nghiên cứu khoa học nông nghiệp cũng như trong các lĩnh vực khác.
Phần mềm này đã được nâng cấp có tính thân thiện với người sử dụng và tránh
được sao chép, có thể được phổ cập có bản quyền mộ
t cách rộng rãi. Việc tạo ra các
giao diện thân thiện cho phép dễ dàng nhập các hàm mục tiêu và ràng buộc của nhiều
dạng bài toán tối ưu phi tuyến là một vấn đề khá phức tạp đã được giải quyết thành công
trong phần mềm này.
Trong tình hình hiện tại, khi các phần mềm tối ưu phi tuyến không có sẵn trên
thị trường trong và ngoài nước, phần mềm RST2ANU nên được triển khai sử dụng để
giải quyết các bài toán tối
ưu trong các lĩnh vực khác nhau, bao gồm cả các bài toán
nguyên và hỗn hợp nguyên. Các nghiên cứu cần tiếp tục được triển khai và được hỗ trợ

44
về mặt tài chính để tích hợp RST2ANU vào các gói phần mềm trong điều khiển tự động
hóa hay trong các hệ hỗ trợ ra quyết định.

2. MỘT SỐ VÍ DỤ ÁP DỤNG RST2ANU
2.1. Bài 1: Bài toán xác định tham số sàng phân loại
Sau đây là cách viết chương trình con tính giá trị hàm mục tiêu và kiểm tra tính
khả thi của phương án đã được phát sinh khi thực hiện chương trình máy tính
RST2ANU.
float f()
{ float fv, g;
g= 0.05*cos(0+3.1417/18)+0.3*cos(x[0])+0.15*cos(x[1])+0.5*cos(x[2])-
0.365;
g=1000*g*g;
fv=g;

**crs2.c
n=4,nc=0,nint=4,epsilon=0.000001,eps1=0.000001,iterlast=10000
ifailast=2000,imlast=0,islast=2000,iprint=0,id=0,imp=1,ipat=0
noninteger variables are:
x[0] x[1] x[2] x[3]
guess=0,nguess=0,lppatt=0
lower and upper bounds of coordinates:
xmin[0]=0.000000,xmax[0]=3.141700
xmin[1]=0.000000,xmax[1]=3.141700
xmin[2]=0.000000,xmax[2]=3.141700
xmin[3]=0.000000,xmax[3]=3.141700
itnlast=3,istnlast=3,eps2=0.010000
***CRS
SOLUTION FOR NLPP by type 1 as usually
**case 1 na=50
seed[0]=*, s*,f=0.000000,fm=0.000001,iter=763,ifun=1664,t1=0
*, s*,f=0.000000,fm=0.000001,iter=1069,ifun=1619,t1=0
*, s*,f=0.000000,fm=0.000001,iter=1026,ifun=1557,t1=0
*,f*,f=4.300038,fm=4.300157,iter=1941,ifun=25813,t1=0
t*, f= 0.000000,iter2=4799 ifun2=30653,t2=0
fopt=0.000000
0.198735,0.550661,1.784750,1.670850,
seed[1]=*,f*,f=4.300035,fm=4.300137,iter=1891,ifun=32299,t1=0
*,f*,f=4.300043,fm=4.300156,iter=1705,ifun=31407,t1=0
*,f*,f=4.300050,fm=4.300186,iter=967,ifun=21132,t1=1
*, s*,f=0.000000,fm=0.000001,iter=938,ifun=1481,t1=0
t*, f= 0.000000,iter2=5501 ifun2=20783,t2=1
fopt=0.000000
0.198752,0.550653,1.784751,1.670846,
seed[2]=*,f*,f=4.300051,fm=4.300158,iter=1168,ifun=-27879,t1=0

return(fv);
}
int feas()
{ int flag=1;
float g;
g=x[0]+x[1]+x[2]+x[3]+x[4];
if(g>50)
{ flag=0;
goto LAST;
}
g=x[5]+x[6];
if(g>1)
{ flag=0;
goto LAST;
}
LAST:
if(flag==0) {return(0);}

47
else {return(1);}

File vào CUONG1.IN
1 7 2 5 0.001 0.001
10000 2000 0 2000
0 0 0 0 0 0 0
0 1 2 3 4
0 50 0 50 0 50 0 50 0 50
0 1 0 1
123 234 345 456 567
0 0 0.01

21.514578,9.515970,8.769965,5.103930,5.095558,1.000000,0.000000,
seed[2]=0*, s*,f=-88.360855,fm=-88.272774,iter=588,ifun=14737,t1=1
t*, f= -88.360855,iter2=588 ifun2=14737,t2=1
fopt=-88.360855

48
21.570715,9.461304,8.736217,5.097508,5.134254,1.000000,0.000000,
seed[3]=0*, s*,f=-88.359039,fm=-88.270882,iter=691,ifun=17550,t1=0
t*, f= -88.359039,iter2=691 ifun2=17550,t2=0
fopt=-88.359039
21.375309,9.651163,8.772411,5.121580,5.079536,1.000000,0.000000,
seed[4]=0*, s*,f=-88.360451,fm=-88.273888,iter=691,ifun=16477,t1=0
t*, f= -88.360451,iter2=691 ifun2=16477,t2=0
fopt=-88.360451
21.518408,9.449259,8.761295,5.180042,5.090996,1.000000,0.000000,
***t3=0/1***
***b1=547,b2=2840,***
***a1=547,a2=2840,***

3. TÍCH HỢP RST2ANU VỚI MATLAB
Trong Matlab không có lệnh nhảy vô điều kiện goto. Để xử lí vấn đề này cần lập
trình theo từng khối tuần tự, kết hợp với cách sử dụng các lời gọi hàm thông qua các file
chương trình, khối lệnh khác nhau.
Chương trình RST2ANU gồm nhiều file, mỗi file có thể là một chương trình
con, cũng có thể là một khối lệnh. Chương trình hoàn chỉnh được chứa trong thư mục
RST2ANU, file CRS là file chính và cũng là lệnh gọi chương trình từ
Matlab.
Nhập / lưu bài toán và các dữ kiện
Chạy chương trình bằng cách dùng lệnh crs từ dòng lệnh của Matlab. Khi chạy
sẽ thấy xuất hiện:

với các ràng buộc:
x
2
− 3x
1
− 3x
4
= 0; x
3
− 2x
2
− 2x
5
= 0;
4x
4
– x
6
= 0; x
1
+ 2x
4
≤ 4;
x
2
+ x
5
≤ 4; x
3
+ x

5
, x
6
là các biến nguyên.
Your choice: 1

49
Sau đó lần lượt xuất hiện các dòng nhắc nhập dữ liệu đầu vào, ta lần lượt nhập
như sau:
+++++ THE PROBLEM +++++
Number of variables (N):6
Array to describe integer variables:[0 0 0 1 1 1]
Goal function f(x)=(X(1)^0.6)+(X(2)^0.6)+(X(3)^0.4)+2*X(4)+5*X(5)-4*X(3)-
X(6)
Feasible conditions: (Leave blank for none)
1. X(1)=(X(2)-3*X(4))/3
2. X(3)=2*(X(2)+X(5))
3. X(6)=4*X(4)
4. X(2)-3*X(1)-3*X(4)==0
5. X(3)-2*X(2)-2*X(5)==0
6. 4*X(4)-X(6)==0
7. X(1)+2*X(4)<=4
8. X(2)+X(5)<=4
9. X(3)+X(6)<=6
10.
Number of feasible conditions entered: 9
Array to describe min values of X: [0 0 0 0 0 0]
Array to describe max values of X: [3 4 4 1 2 6]
+++++ CONDITIONS FOR ALGORITHM +++++
Limit Random Trying to find one feasible solution to (1000): 1000

))*exp(0.066*X(7))
1. X(5)=50-(X(1)+X(2)+X(3)+X(4));
2. X(6)+X(7)==1
3. X(1)+X(2)+X(3)+X(4)+X(5)==50
0 <= X(1) <= 50 real
0 <= X(2) <= 50 real
0 <= X(3) <= 50 real
0 <= X(4) <= 50 real
0 <= X(5) <= 50 real
0 <= X(6) <= 1 integer
0 <= X(7) <= 1 integer
Epsilon approximately: 0.0001%
Searching. Be patient
Searching completed.
===== Here is the result =====
Stop with epsilon approximately.
X* =
Columns 1 through 6
21.0902 9.4856 9.2223 5.0966 5.1052 1.0000
Column 7
0

51
f(X*)= -88.3465 ± 8.8346e-005
Total time:
5.217 second(s)
Source: p01_50.mat
Results saved to res.txt
End.
Chú ý: