狠狠撸

218
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.
G?i
1
2
l
l
r = ,ta nh?n ???c ph??ng tr×nh :
r
1
r1 =+ (4)
hay : r2
+ r - 1 = 0 (5)
Nghi?m c?a ph??ng tr×nh (5) l? :
...61803.0
2
15
2
)1(411
r =
?
=
??+?
= (6)
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:
...61803.0
2
15
d =
?
=
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 :
1
2
0
1
l
l
l
l
= (2)
Thay th? (1) v?o (2) ta c? :
1
2
21
1
l
l
ll
l
=
+
(3)
a b
l0
l1 l2
c

219
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) < f(x2) th× th× gi? tr? cùc tr? c?a h?m n?m trong [a,x1] v? x1 tr? th?nh b
v? ta t?nh ti?p.
C?i l?i c?a ph??ng ph?p t? l? v?ng theo h×nh a l? gi? tr? x1 cò tr? th?nh gi? tr? x2 míi n?n gi?
tr? f(x2) míi ch?nh l? gi? tr? f(x1) cò n?n ta kh?ng c?n t?nh l?i n?.Ch??ng tr×nh m? t? thu?t
to?n tr?n nh? sau:
Ch??ng tr×nh 14-1
//tiet_dien_vang;
#include <conio.h>
#include <stdio.h>
#include <math.h>
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;
d
d
a x1
x2
b
x
y
a x1x2 b x
y
x2 cò x1 cò

220
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;

221
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<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 r1=xopt;
return(r1);
}
void main()
{
float x,y,xlow,xhigh,eps;

222
clrscr();
printf("TIM CUC TRI CUA HAM BANG PHUONG PHAP TIET DIEN VANGn");
printf("n");
printf("Cho khoang can tim cuc trin");
printf("Cho can duoi a = ");
scanf("%f",&xlow);
printf("Cho can tren b = ");
scanf("%f",&xhigh);
if (f(xlow)<f(xlow+0.1))
{
x=max(xlow,xhigh);
y=f(x);
printf("x cuc dai = %10.5fn",x);
printf("y cuc dai = %10.5fn",y);
}
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 :
)x(f
)x(f
xx
i
i
i1i
′
?=+
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? :
)x(f
)x(f
x
)x(g
)x(g
xx
i
i
i
i
i
i1i
′′
′
?=
′
?=+
C?c ??o h?m f′(xi) v? f″(xi) ???c x?c ??nh theo c?c c?ng th?c :
2
iii
i
ii
i
h
)hx(f)x(f2)hx(f
)x(f
h2
)hx(f)hx(f
)x(f
?+?+
=′′
??+
=′
T?i gi? tr? f′(x) = 0 h?m ??t gi? tr? cùc ??i n?u f″(x) < 0 v? cùc ti?u n?u f″(x) > 0.Ch??ng
tr×nh sau m? t? thu?t to?n tr?n.

223
Ch??ng tr×nh 14-2
//Phuong phap New_ton;
#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
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 NEWTONn");
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();

224
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:
)xa)(b(f2)ab)(x(f2)bx)(a(f2
)xb)(b(f)ab)(x(f)bx)(a(f
x
222222
1
?+?+?
?+?+?
=
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 <conio.h>
#include <stdio.h>
#include <math.h>
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 PARABOLn");
printf("n");

225
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?

226
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 CT
X →
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 <conio.h>
#include <stdio.h>
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 nghiemn");
t=0;

228
}
else
{
printf("Nghiem khong bi gioi hann");
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 HINHn");
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 bienn");
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 phain");
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 tieun");
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 HOAn");
if (p==2)
printf("Bai toan cuc tieu tieu chuann");
else
printf("Bai toan cuc dai tieu chuann");
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.5fn",j,x);
}
printf("n");
printf("Gia tri toi uu cua ham muc tieu = %10.5fn",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
Ch??ng tr×nh vi?t theo thu?t to?n tr?n nh? sau :
Ch??ng tr×nh 14-5
// van_tru;
#include <conio.h>
#include <stdio.h>
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 xn");
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.5fn",q);
printf("n");
printf("Cuc tieu hoan");
for (i=1;i<=n;i++)
printf("%d%10c%dn",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

狠狠撸

Chuong14

More Related Content

Chuong14