Giáo trình Tối ưu - Chương 14: Tối ưu hóa

Nội dung text: Giáo trình Tối ưu - Chương 14: Tối ưu hóa

1. Ch−ơng 14 : tối −u hoá Đ1.Ph−ơng pháp tỉ lệ vàng Trong ch−ơng 8 chúng ta đã xét bài toán tìm nghiệm của ph−ơng trình phi tuyến tức là tìm giá trị của x mà tại đó hàm triệt tiêu.Trong phần này chúng ta sẽ đặt vấn đề tìm giá trị của x mà tại đó hàm đạt giá trị cực trị(cực đại hay cực tiểu).Ph−ơng pháp tiết diện vàng là một ph−ơng pháp đơn giản và hiệu quả để tìm giá trị cực trị của hàm. Giả sử ta có hàm y = f(x) và cần tìm giá trị cực trị trong khoảng [a,b].Khi tìm nghiệm chỉ cần biết 2 giá trị của hàm là ta khẳng định đ−ợc nghiệm có nằm trong khoảng đã cho hay không bằng cách xét dấu của hàm.Khi tìm giá trị cực trị ta phải biết thêm một giá trị nữa của hàm trong khoảng [a,b] thì mới khẳng định đ−ợc hàm có đạt cực trị trong đoạn đã cho hay không.Sau đó ta chọn thêm một điểm thứ t− và xác định xem giá trị cực trị của hàm sẽ nằm trong đoạn nào. Theo hình vẽ,khi chọn điểm trung gian c ta có : l1 + l2 = l0 (1) và để tiện tính toán ta chọn : l l 1 = 2 (2) l l 0 1 Thay thế (1) vào (2) ta có : l l a c b 1 = 2 (3) l1 + l2 l1 l0 l1 l2 l Gọi r = 2 ,ta nhận đ−ợc ph−ơng trình : l1 1 1+ r = (4) r hay : r2 + r - 1 = 0 (5) Nghiệm của ph−ơng trình (5) là : −1+ 1− 4(−1) 5 −1 r = = = 0.61803 (6) 2 2 Giá trị này đã đ−ợc biết từ thời cổ đại và đ−ợc gọi là “tỉ lệ vàng”.Nh− trên đã nói,ph−ơng pháp tỉ lệ vàng đ−ợc bắt đầu bằng 2 giá trị đã cho của biến x là a và b.Sau đó ta chọn 2 điểm x1 và x bên trong khoảng [a,b] theo tỉ lệ vàng: 5 −1 d = = 0.61803 2 218
2. y y a x x x a x2 x1 b d 1 x2 d b x cũ x1 cũ 2 a b Ta tính giá trị của hàm tại các điểm bên trong đoạn [a,b].Kết quả có thể là một trong các khả năng sau : 1. Nếu,nh− tr−ờng hợp hình a,f(x1) > f(x2) thì giá trị cực trị của hàm nằm trong [x2,b] và x2 trở thành a và ta tính tiếp. 2. Nếu f(x1) #include #include float eps=1e-6; float f(float x) { float a=2*sin(x)-x*x/10; return(a); }; float max(float xlow,float xhigh) { float xl,xu,r,d,x1,x2,f1,f2,xopt,s; int lap; xl=xlow; xu=xhigh; lap=1; 219
3. r=(sqrt(5.0)-1.0)/2.0; d=r*(xu-xl); x1=xl+d; x2=xu-d; f1=f(x1); f2=f(x2); if (f1>f2) xopt=x1; else xopt=x2; do { d=r*d; if (f1>f2) { xl=x2; x2=x1; x1=xl+d; f2=f1; f1=f(x1); } else { xu=x1; x1=x2; x2=xu-d; f1=f2; f2=f(x2); } lap=lap+1; if (f1>f2) xopt=x1; else xopt=x2; if (xopt!=0) s=(1.0-r)*fabs((xu-xl)/xopt)*100; } while((s>eps)&&(lap<=20)); float k=xopt; return(k); } float min(float xlow,float xhigh) { float xl,xu,r,d,x1,x2,f1,f2,fx,xopt,s; int lap; xl=xlow; 220
4. xu=xhigh; lap=1; r=(sqrt(5.0)-1.0)/2,0; d=r*(xu-xl); x1=xl+d; x2=xu-d; f1=f(x1); f2=f(x2); if (f1 eps)&&(lap<=20)); float r1=xopt; return(r1); } void main() { float x,y,xlow,xhigh,eps; 221
5. clrscr(); printf("TIM CUC TRI CUA HAM BANG PHUONG PHAP TIET DIEN VANG\n"); printf("\n"); printf("Cho khoang can tim cuc tri\n"); printf("Cho can duoi a = "); scanf("%f",&xlow); printf("Cho can tren b = "); scanf("%f",&xhigh); if (f(xlow) 0.Ch−ơng trình sau mô tả thuật toán trên. 222
6. Ch−ơng trình 14-2 //Phuong phap New_ton; #include #include #include #include float f(float x) { float a=2*sin(x)-x*x/10; return(a); } float f1(float x) { float a=2*cos(x)-x/5.0; return(a); } float f2(float x) { float a=-2*sin(x)-1.0/5.0; return(a); } void main() { float a,eps,x[50],y1,t; clrscr(); printf("TINH CUC TRI BANG PHUONG PHAP NEWTON\n"); printf("\n"); printf("Cho diem bat dau tinh a = "); scanf("%f",&a); eps=1e-6; int i=1; x[i]=a; do { x[i+1]=x[i]-f1(x[i])/f2(x[i]); t=fabs(x[i+1]-x[i]); x[i]=x[i+1]; i++; if (i>1000) { printf("Khong hoi tu sau 1000 lan lap"); getch(); 223
7. exit(1); } } while (t>=eps); printf("\n"); y1=f2(x[i]); if (y1>0) printf("x cuc tieu = %10.5f y cuc tieu = %10.5f",x[i],f(x[i])); else printf("x cuc dai = %10.5f y cuc dai = %10.5f",x[i],f(x[i])); getch(); } Ta có kết quả x = 1.42755,y= 1.77573 Đ3.Ph−ơng pháp parabol Nội dung của ph−ơng pháp parabol là ta thay đ−ờng cong y = f(x) bằng một đ−ờng cong parabol mà ta dễ dàng tìm đ−ợc giá trị cực trị của nó.Nh− vậy trong khoảng [a,b] ta chọn thêm một điểm x bất kì và xấp xỉ hàm f(x) bằng parabol qua 3 điểm a,x,và b.Sau đó ta đạo hàm và cho nó bằng 0 để tìm ra điểm cực trị của parabol này.Giá trị đó đ−ợc tính bằng công thức: f(a)(x2 − b2 ) + f(x)(b2 − a 2 ) + f(b)(b2 − x2 ) x = 1 2f(a)(x − b) + 2f(x)(b − a) + 2f(b)(a − x) Sau đó t−ơng tự ph−ơng pháp tỉ lệ vàng ta loại trừ vùng không chứa giá trị cực trị và tiếp tục quá trình trên cho đến khi đạt độ chính xác mong muốn.Ch−ơng trình đ−ợc viết nh− sau: Ch−ơng trình 14-3 //phuong phap parabol #include #include #include float f(float x) { float f1=2*sin(x)-x*x/10; return(f1); } void main() { float a,b,x0,x1,x2,x3,f3; clrscr(); printf("TIM CUC TRI BANG PHUONG PHAP PARABOL\n"); printf("\n"); 224
8. printf("Cho doan can tim cuc tri [a,b]\n"); printf("Cho diem dau a = "); scanf("%f",&a); printf("Cho diem cuoi b = "); scanf("%f",&b); x0=a; x2=b; x1=(x0+x2)/4; do { x3=(f(x0)*(x1*x1-x2*x2)+f(x1)*(x2*x2-x0*x0)+f(x2)*(x0*x0-x1*x1)) /(2*f(x0)*(x1-x2)+2*f(x1)*(x2-x0)+2*f(x2)*(x0-x1)); f3=f(x3); if (x3>x1) x0=x1; else x2=x1; x1=x3; } while (fabs(x2-x0)>1e-5); printf("\n"); f3=(f(x2+0.01)-2*f(x2)+f(x2-0.01))/(0.01*0.01); if (f3<0) printf("x cuc dai = %10.5f y cuc dai = %10.5f",x2,f(x2)); else printf("x cuc tieu = %10.5f y cuc tieu = %10.5",x2,f(x2)); getch(); } Chạy ch−ơng trình này với a = 0 và b = 4 ta có x cực đại là 1.42755 và y cực đại là 1.77573. Đ4. Ph−ơng pháp đơn hình(simplex method) Trong thực tế nhiều bài toán kinh tế,vận tải có thể đ−ợc giải quyết nhờ ph−ơng pháp quy hoạch tuyến tính.Tr−ớc hết ta xét bài toán lập kế hoạch sản xuất sau: Một công ty muốn sản xuất 2 loại sản phảm mới là A và B bằng các nguyên liệu 1,2,và 3.Suất tiêu hao nguyên liệu để sản xuất các sản phảm cho ở bảng sau: Sản phẩm A Sản phẩm B Nguyên liệu 1 2 1 Nguyên liệu 2 1 2 Nguyên liệu 3 0 1 Số liệu này cho thấy để sản xuất một đơn vị sản phẩm A cần dùng 2 đơn vị nguyên liệu 1,một đơn vị nguyên liệu 2 và để sản xuất một đơn vị sản phẩm B cần dùng 1 đơn vị 225
9. nguyên liệu 1,hai đơn vị nguyên liệu 2,1 đơn vị nguyên liệu 3.Trong kho của nhà máy hiện có dự trữ 8 đơn vị nguyên liệu 1,7 đơn vị nguyên liệu 2 và 3 đơn vị nguyên liệu 3.Tiền lãi một đơn vị sản phảm A là 4.000.000 đ,một đơn vị sản phẩm B là 5.000.000đ.Lập kế hoạch sản xuất sao cho công ty thu đ−ợc tiền lãi lớn nhất. Bài toán này là bài toán tìm cực trị có điều kiện.Gọi x1 là l−ợng sản phẩm A và x2 là l−ợng sản phẩm B ta đi đến mô hình toán học: f(x) = 4x1 + 5x2 → max với các ràng buộc : 2x1 + x2 ≤ 8 (ràng buộc về nguyên liệu 1) x1 + 2x2 ≤ 7 (ràng buộc về nguyên liệu 2) x2 ≤ 3 (ràng buộc về nguyên liệu 3) x1 ≥ 0,x2 ≥ 0 Một cách tổng quát ta có bài toán đ−ợc phát biểu nh− sau : Cho hàm mục tiêu CTX → max với điều kiện ràng buộc AX ≤ B và X ≥ 0.Thuật toán để giải bài toán gồm hai giai đoạn - tìm một ph−ơng án cực biên một đỉnh - kiểm tra điều kiện tối −u đối với ph−ơng án tìm đ−ợc ở giai đoạn 1.Nếu điều kiện tối −u đ−ợc thoả mãn thì ph−ơng án đó là tối −u.Nếu không ta chuyển sang ph−ơng án mới. Ch−ơng trình giải bài toán đ−ợc viết nh− sau : Ch−ơng trình 14-4 //simplex; #include #include int m,n,n1,it,i,j,h1,h2,hi,m1,ps,pz,v,p; float bv[20]; float a[20][20]; float h,mi,x,z; void don_hinh() { int t; float hi; if (p!=2) for (i=1;i<=m;i++) bv[i]=n+i; if (p==2) { h1=n; h2=m; } else { h1=m; h2=n; 226
10. } for (i=1;i -0.00001) { z=a[m1][n1]; t=0; } mi=1e+20; pz=0; for (i=1;i<=m1-1;i++) { if (a[i][ps]<=0.0) continue; h=a[i][n1]/a[i][ps]; if (h<mi) { mi=h; pz=i; } } if (pz==0) { if (p==2) { printf("Khong ton tai nghiem\n"); t=0; 227
11. } else { printf("Nghiem khong bi gioi han\n"); t=0; } } if (p==1) bv[pz]=ps; hi=a[pz][ps]; for (j=1;j<=n1;j++) a[pz][j]=a[pz][j]/hi; if (pz!=1) for (i=1;i<=pz-1;i++) { hi=a[i][ps]; for (j=1;j<=n1;j++) a[i][j]=a[i][j]-hi*a[pz][j]; } for (i=pz+1;i<=m1;i++) { hi=a[i][ps]; for (j=1;j<=n1;j++) a[i][j]=a[i][j]-hi*a[pz][j]; } } else printf("Nghiem bat thuong"); } } void main() { clrscr(); printf("PHUONG PHAP DON HINH\n"); printf("\n"); flushall(); printf("Cho bai toan tim max(1) hay min(2)(1/2)? : "); scanf("%d",&p); printf("Cho so bien n = "); scanf("%d",&n); printf("Cho so dieu kien bien m = "); scanf("%d",&m); n1=n+m+1; if (p==2) m1=n+1; else 228
12. m1=m+1; printf("Cho ma tran cac dieu kien bien\n"); for (i=1;i<=m;i++) for (j=1;j<=n;j++) if (p==2) { printf("a[%d][%d] = ",i,j); scanf("%f",&a[j][i]); } else { printf("a[%d][%d] = ",i,j); scanf("%f",&a[i][j]); } printf("\n"); printf("Cho ma tran ve phai\n"); for (i=1;i<=m;i++) if (p==2) { printf("b[%d] = ",i); scanf("%f",&a[m1][i]); } else { printf("b[%d] = ",i); scanf("%f",&a[i][n1]); } printf("\n"); printf("Cho ham muc tieu\n"); for (j=1;j<=n;j++) if (p==2) { printf("z[%d] = ",j); scanf("%f",&a[j][n1]); } else { printf("z[%d] = ",j); scanf("%f",&a[m1][j]); } if (p==2) hi=m; else hi=n; for (j=1;j<=hi;j++) a[m1][j]=-a[m1][j]; a[m1][n1]=0.0; 229
13. don_hinh(); printf("\n"); printf("NGHIEM TOI UU HOA\n"); if (p==2) printf("Bai toan cuc tieu tieu chuan\n"); else printf("Bai toan cuc dai tieu chuan\n"); printf("sau %d buoc tinh",it); printf("\n"); for (j=1;j<=n;j++) { if (p==2) x=a[m1][m+j]; else { v=0; for (i=1;i<=m;i++) if (bv[i]==j) { v=i; i=m; } if (v==0) x=0.0; else x=a[v][n1]; } printf("x[%d] = %10.5f\n",j,x); } printf("\n"); printf("Gia tri toi uu cua ham muc tieu = %10.5f\n",z); getch(); } Dùng ch−ơng trình này giải bài toán có hàm mục tiêu : z = 80x1 + 56x2 + 48x3 → min với ràng buộc : 3x1 + 4x2 + 2x3 ≥ 15 2x1 + 3x2 + x3 ≥ 9 x1 + 2x2 + 6x3 ≥ 18 x2 + x3 ≥ 5 x1,x2,x3 ≥ 0 Ta cần nhập vào ch−ơng trình là tìm min,với số biến n =3,số điều kiện biên m = 4,các hệ số a[1,1] = 3 ; a[1,2] = 4 ; a[1,3] = 2 ; a[2,1] = 2; a[2,2] = 3 ; a[2,3] = 1 ; a[3,1] = 1 ; a[3,2] = 2 ; a[3,3] = 6 ; a[4,1] = 0 ; a[4,2] = 1 ; a[4,3] = 1 ; b[1] = 15 ; b[2] = 9 ; b[3] = 18; b[4] = 5 ; z[1] = 80 ; z[2] = 56 ; z[3] = 48 và nhận đ−ợc kết quả : x[1] = 0 ; x[2] = 2.5 ; x[3] =2.5 và trị của hàm mục tiêu là 260 230
14. Đ5.Ph−ơng pháp thế vị Trong vận tải ta th−ờng gặp bài toán vận tải phát biểu nh− sau : có n thùng hàng của một hãng xây dựng cần chuyển tới n địa điểm khác nhau.Giá vận tới tới mỗi địa điểm đã cho.Tìm ph−ơng án vận chuyển để giá thành là cực tiểu. Một cách tổng quát bài toán đ−ợc phát biểu : ∑a i p i → min Ví dụ : Cần vận chuyển 6 thùng hàng tới 6 địa điểm với giá thành cho ở bảng sau : Thùng 1 2 3 4 5 6 → địa điểm 1 ⎛60 35 28 53 29 26⎞ 2 ⎜ 81 43 37 23 36 45⎟ ⎜ ⎟ 3 42 42 33 47 43 51 4 ⎜29 70 42 53 48 37⎟ ⎜ 81 69 40 66 69 60⎟ 5 ⎜ ⎟ 6 ⎝10 21 32 31 24 27⎠ Để giả bài toán ta dùng thuật toán Hungary nh− sau : - trừ mỗi dòng cho số min của dòng đó ta có : ⎛34 9 2 27 3 0 ⎞ ⎜58 20 14 0 13 22⎟ ⎜ ⎟ 9 9 0 14 10 18 ⎜ 0 41 13 24 19 8 ⎟ ⎜ 41 29 0 26 29 20⎟ ⎜ ⎟ ⎝ 0 11 22 21 14 17⎠ - trừ mỗi cột cho số min của cột đó ⎛34 0 2 27 0 0 ⎞ ⎜58 11 14 0 10 22⎟ ⎜ ⎟ 9 0 0 14 7 12 ⎜ 0 32 13 24 16 8 ⎟ ⎜ 41 20 0 26 26 20⎟ ⎜ ⎟ ⎝ 0 2 22 21 11 17⎠ Mục tiêu của thuật toán Hungary là biến đổi ma trận giá thành sao cho có thể đọc giá trị tối −u từ ma trận.Điều này đ−ợc thực hiện khi mỗi hànhg và cột chứa ít nhất một số 0.Nếu ta vẽ một đoạn thẳng qua mỗi hàng và cột chứa số 0 thì khi đó số đoạn thẳng tối thiểu qua tất cả các số 0 phải là 6.Trong ma trận trên ta chỉ mới dùng 5 đoạn thẳng nghĩa là ch−a có giá trị tối −u.Để biến đổi tiếp tục ta tìm trị min của các phần tử ch−a nằm trên bất kì đoạn thẳng nào.Trị số đó là 7.Lấy các phần tử không nằm trên đoạn thẳng nào trừ đi 7 và công các phần tử nằm trên hai đoạn thẳng với 7 ta có ma trận : ⎛41 7 9 27 0 0 ⎞ ⎜65 18 21 0 10 22⎟ ⎜ ⎟ 9 0 0 7 0 5 ⎜ 0 32 13 17 9 1 ⎟ ⎜41 20 0 19 19 13⎟ ⎜ ⎟ ⎝ 0 2 22 14 4 10⎠ 231
15. Do số đoạn thẳng tối thiểu còn là 5 nên ta lặp lại b−ớc trên và nhận đ−ợc ma trận mới : ⎛42 7 10 28 0 0 ⎞ ⎜65 17 21 0 9 21⎟ ⎜ ⎟ 10 0 1 8 0 5 ⎜ 0 31 13 17 8 0 ⎟ ⎜ 41 19 0 19 18 12⎟ ⎜ ⎟ ⎝ 0 1 22 14 3 9 ⎠ Số đoạn thẳng cần để qua hết các số 0 là 6 nghĩa là ta đã tìm đ−ợc trị tối −u.Ta đánh dấu 6 số 0 sao cho mỗi hàng và mỗi cột chỉ có 1 số đ−ợc đánh dấu.Chỉ số các số 0 đ−ợc đánh dấu cho ta trị tối −u : a15 = 0 nghĩa là thùng 1 đ−ợc vận chuyển tới địa điểm 5 a24 = 0 nghĩa là thùng 2 đ−ợc vận chuyển tới địa điểm 4 a32 = 0 nghĩa là thùng 3 đ−ợc vận chuyển tới địa điểm 2 a46 = 0 nghĩa là thùng 4 đ−ợc vận chuyển tới địa điểm 6 a53 = 0 nghĩa là thùng 5 đ−ợc vận chuyển tới địa điểm 3 a61 = 0 nghĩa là thùng 6 đ−ợc vận chuyển tới địa điểm 1 Ch−ơng trình viết theo thuật toán trên nh− sau : Ch−ơng trình 14-5 // van_tru; #include #include void main() { int a[20][20],z[20][20],p[20][2]; float x[20][20],w[20][20]; float c[20],r[20]; int t,c1,i,j,k,k2,k3,k5,l,l1,m,n,r1,s; float m1,q; clrscr(); printf("Cho so an so n = "); scanf("%d",&n); printf("Cho cac he so cua ma tran x\n"); for (i=1;i<=n;i++) for (j=1;j<=n;j++) { printf("x[%d][%d] = ",i,j); scanf("%f",&x[i][j]); w[i][j]=x[i][j]; } for (i=1;i<=n;i++) { c[i]=0.0; 232
16. r[i]=0.0; p[i][1]=0.0; p[i][2]=0.0; a[i][1]=0.0; a[i][2]=0.0; } for (i=1;i n) continue; if (x[i][j]!=0) { j=j+1; goto mot; } else if (i==1) { 233
17. a[l][1]=i; a[l][2]=j; c[j]=1.0; l=l+1; } else { l1=l-1; for (k=1;k n) continue; else if ((x[i][j]!=0)||(c[j]!=0)||(r[i]!=0)) { j=j+1; goto ba; } else { p[m][1]=i; p[m][2]=j; m=m+1; for (k=1;k<=l;k++) if (a[k][1]!=i) continue; else { r[i]=1.0; 234
18. c[a[k][2]]=0.0; goto sau; } } } k2=m-1; r1=p[k2][1]; c1=p[k2][2]; k3=l; k=1; s=1; bon: if (k==1) { z[k][1]=r1; z[k][2]=c1; k=k+1; goto bon; } else { if (s==1) { for (j=1;j<=k3;j++) if (a[j][2]==c1) { r1=a[j][1]; s=2; z[k][1]=r1; z[k][2]=c1; k=k+1; goto bon; } k=k-1; } else { for (j=1;j<=k2;j++) if (p[j][1]==r1) { c1=p[j][2]; s=1; z[k][1]=r1; z[k][2]=c1; k=k+1; goto bon; } else 235
19. continue; k=k-1; } } k5=1; nam: if (k5==k) { l=l+1; a[l][1]=z[k][1]; a[l][2]=z[k][2]; if (l!=n) { for (i=1;i<=n;i++) { r[i]=0.0; c[i]=0.0; p[i][1]=0; p[i][2]=0; } for (i=1;i<=l;i++) c[a[i][2]]=1.0; m=1; goto hai; sau: m1=9999; for (i=1;i<=n;i++) if (r[i]==0.0) for (j=1;j<=n;j++) if (c[j]==0.0) if (x[i][j]<m1) m1=x[i][j]; for (i=1;i<=n;i++) for (j=1;j<=n;j++) { if ((r[i]!=0.0)||(c[j]!=0.0)) if ((r[i]!=1.0)||(c[j]!=1.0)) continue; else x[i][j]=x[i][j]+m1; else x[i][j]=x[i][j]-m1; } goto hai; } } else { for (i=1;i<=l;i++) 236
20. if ((a[i][1]==z[k5+1][1])) if ((a[i][2]==z[k5+1][2])) break; a[i][1]=z[k5][1]; a[i][2]=z[k5][2]; k5=k5+2; goto nam; } } q=0.0; for (i=1;i<=n;i++) q+=w[a[i][1]][a[i][2]]; printf("Gia thanh cuc tieu : %10.5f\n",q); printf("\n"); printf("Cuc tieu hoa\n"); for (i=1;i<=n;i++) printf("%d%10c%d\n",a[i][1],' ',a[i][2]); getch(); } Chạy ch−ơng trình ta nhận đ−ợc giá thành cực tiểu là 181 237