Giáo trình C++ - Chương 14: Tối ưu hóa
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 :
l1 l2
=
(2)
l0 l1
Thay thÕ (1) vµo (2) ta cã :
a
c
b
l1
l2
=
(3)
l0
l1 + l2 l1
l2
l1
l2
Gäi r = ,ta nhËn ®−îc ph−¬ng tr×nh :
l1
1
1+ r =
r
(4)
(5)
hay :
r2 + r - 1 = 0
NghiÖm cña ph−¬ng tr×nh (5) lµ :
−1+ 1− 4(−1)
5 −1
2
r =
=
= 0.61803...
(6)
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
2
d =
= 0.61803...
218
y
y
x
x
a
a
x2 x1 b
x1 cò
x1
d
d
b
x2
x2 cò
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;
219
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
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;
221
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)<f(xlow+0.1))
{
x=max(xlow,xhigh);
y=f(x);
printf("x cuc dai = %10.5f\n",x);
printf("y cuc dai = %10.5f\n",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 :
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 −
′
′′
f (xi )
g (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 ) =
h2
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.
222
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 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 − a2 ) + f(b)(b2 − x2 )
x1 =
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 <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 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
Nguyªn liÖu 2
Nguyªn liÖu 3
2
1
0
1
2
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 <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;
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 p → min
∑
i
i
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
2
3
4
5
60 35 28 53 29 26
81 43 37 23 36 45
42 42 33 47 43 51
29 70 42 53 48 37
81 69 40 66 69 60
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
0
3
0
⎛
⎜
⎞
⎟
58 20 14
13 22
⎜
⎜
⎜
⎟
⎟
⎟
9
0
9
0
14 10 18
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
0
⎛
⎜
⎞
⎟
58 11 14
10 22
⎜
⎜
⎜
⎟
⎟
⎟
9
0
0
0
14
7
12
8
32 13 24 16
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
0
7
0
9
5
1
32 13 17
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
21
5
⎛
⎞
⎜
⎟
65 17 21
0
8
9
0
8
⎜
⎜
⎜
⎟
⎟
⎟
10
0
1
0
31 13 17
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 <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 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
20 trang
10840
Free
Bạn đang xem tài liệu "Giáo trình C++ - Chương 14: Tối ưu hóa", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_c_chuong_14_toi_uu_hoa.pdf
