Giáo trình Turbo C nâng cao và C++ (Phần 2)

 } 
 else 
 { 
 x=min(xlow,xhigh); 
 y=f(x); 
 printf("x cuc tieu = %10.5f y cuc tieu = %10.5f",x,y); 
 } 
 getch(); 
 } 
 Trong ch−ơng trình này ta cho a = 0 ; b =4 và tìm đ−ợc giá trị cực đại y = 1.7757 tại 
x = 1.4276 
 Đ2.Ph−ơng pháp Newton 
 Khi tính nghiệm của ph−ơng trình f(x) = 0 ta dùng công thức lặp Newton-Raphson : 
 f(xi )
 xi+1 = xi − 
 f′(xi )
Một cách t−ơng tự,để tìm giá trị cực trị của hàm f(x) ta đặt g(x)=f′(x).Nh− vậy ta cần tìm giá 
trị của x để g(x) = 0.Nh− vậy công thức lặp Newton-Raphson sẽ là : 
 g(xi ) f′(xi )
 xi+1 = xi − = xi − 
 g′(xi ) f′′(xi )
Các đạo hàm f′(xi) và f″(xi) đ−ợc xác định theo các công thức : 
 f(xi + h) − f(xi − h)
 f′(xi ) =
 2h 
 f(xi + h) − 2f(xi ) + f(xi − h)
 f′′(xi ) =
 h 2
Tại giá trị f′(x) = 0 hàm đạt giá trị cực đại nếu f″(x) 0.Ch−ơng 
trình sau mô tả thuật toán trên. 
222
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
 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
 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
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
 } 
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; 
 227
 } 
 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
 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
 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
 Đ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
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
 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) 
 { 
 233
 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; 
234
 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
 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
 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