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

) 
 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; 
227
 } 
 for (i=1;i<=m1;i++) 
 for (j=1;j<=h1;j++) 
 { 
 a[i][h2+j]=0.0; 
 if (i==j) 
 a[i][h2+j]=1.0; 
 } 
 it=0; 
 t=1; 
 while (t) 
 { 
 it=it+1; 
 if (it<(m*n*5)) 
 { 
 mi=a[m1][1]; 
 ps=1; 
 for (j=2;j<=n1-1;j++) 
 if (a[m1][j]<mi) 
 { 
 mi=a[m1][j]; 
 ps=j; 
 } 
 if (mi>-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; 
228
 } 
 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 
229
 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; 
230
 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 
231
Đ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 : 
 ∑ → minpa ii 
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 : 
 1 2 3 4 5 6 → địa điểm 
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
272431322110
606966406981
374853427029
514347334242
453623374381
262953283560
Để 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ó : 
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
17142122110
20292602941
8192413410
181014099
22130142058
03272934
- trừ mỗi cột cho số min của cột đó 
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
1711212220
20262602041
8162413320
12714009
22100141158
00272034
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 : 
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
104142220
13191902041
191713320
507009
22100211865
00279741
Thùng 
1
2
3
4
5
6
232
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 : 
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
93142210
12181901941
081713310
5081010
2190211765
002810742
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; 
233
 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<=2*n;i++) 
 { 
 z[i][1]=0.0; 
 z[i][2]=0.0; 
 } 
 for (i=1;i<=n;i++) 
 { 
 m1=9999.0; 
 for (j=1;j<=n;j++) 
 if (x[i][j]<m1) 
 m1=x[i][j]; 
 for (j=1;j<=n;j++) 
 x[i][j]=x[i][j]-m1; 
 } 
 for (j=1;j<=n;j++) 
 { 
 m1=9999.0; 
 for (i=1;i<=n;i++) 
 if (x[i][j]<m1) 
 m1=x[i][j]; 
 for (i=1;i<=n;i++) 
 x[i][j]=x[i][j]-m1; 
 } 
 l=1; 
 for (i=1;i<=n;i++) 
 { 
 j=1; 
mot: if (j>n) 
 continue; 
 if (x[i][j]!=0) 
 { 
 j=j+1; 
 goto mot; 
 } 
 else 
 if (i==1) 
 { 
234
 a[l][1]=i; 
 a[l][2]=j; 
 c[j]=1.0; 
 l=l+1; 
 } 
 else 
 { 
 l1=l-1; 
 for (k=1;k<=l1;k++) 
 { 
 if (a[k][2]!=j) 
 continue; 
 else 
 { 
 j=j+1; 
 goto mot; 
 } 
 } 
 } 
 } 
 l=l-1; 
 if (l!=n) 
 { 
 m=1; 
hai: for (i=1;i<=n;i++) 
 { 
 j=1; 
ba: if (j>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; 
235
 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 
236
 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++) 
237
 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