Chuyên đề Chương 4: Thuật toán gomory thứ hai

ed long far *t; long int t1,t2; 
char *s1,*s2; FILE *f1,*f2; 
int ktnguyen(double x); 
int cotquay(); 
void biendoi(); 
void inbang(int cuoi); 
int dhdoingau(); 
void main() 
{clrscr(); 
t= (unsigned long far *)MK_FP(0,0X46C); t1=*t; 
printf("\nCo in trung gian hay khong 1/0 ? "); 
scanf("%d%*c",&tg); 
 // Nhap du lieu 
printf("\nVao ten tep so lieu : "); gets(s1); 
f1=fopen(s1,"r"); 
fscanf(f1,"%d%d%lf%d%d%d",&n,&m,&gz,&n1,&x0,&ss); 
for (i=0;i<=n;i++) for (j=0; j<=m;j++) 
 { fscanf(f1,"%lf",&r); s[i][j]=r; } 
for (i=0; i<=n;i++) fscanf(f1,"%d",&cs[i]) ; 
Bùi Thế Tâm IV.14 Quy hoạch rời rạc 
for (j=1; j<=m; j++) fscanf(f1,"%d",&nc[j]); 
fclose(f1); sb=1; blap=0; 
 // In du lieu nhap de kiem tra 
printf("\nn,m,gz,n1,x0,ss=%d %d %13.5lf %d %d%d",n,m,gz,n1,x0,ss); 
if (tg==1){ printf("\nVao ten tep chua ket qua : "); 
gets(s2); 
f2=fopen(s2,"w"); 
fprintf(f2,"\nn,m,gz,n1,x0,ss=%d%d%13.5lf%d%d%d",n,m,gz,n1,x0,ss); 
 } 
printf("\nBang 1, so lieu ban dau"); 
if (tg==1) fprintf(f2,"\nBang 1, so lieu ban dau"); inbang(0); 
if (ss==1){ 
printf("\nBang 1, so lieu ban dau, l- chuan, chap nhan duoc"); 
if (tg==1) 
fprintf(f2,"\nBang 1, so lieu ban dau, l- chuan, chap nhan duoc"); 
lc = n; goto Lap1;} 
if (ss==2){ 
printf("\nBang1,ban dau,l-chuan,khong chap nhan duoc,chay DHDN"); 
if (tg==1) 
fprintf(f2,"\nBang 1,ban dau,l- chuan, 
khong chap nhan duoc,chay DHDN"); 
 lc = n; goto L1;} 
 // Them rang buoc phu 
sb=1; cs[n+1]=n+1; s[n+1][0]=gz; 
for (j=1;j<=m; j++) s[n+1][j]=1; 
printf("\nBang 1, so lieu ban dau them rang buoc phu"); 
if (tg==1) 
fprintf(f2,"\nBang 1,so lieu ban dau them rang buoc phu"); 
inbang(1); 
l=n+1; // dong quay la dong cuoi cung 
 // Xac dinh cot quay 
cmin=1; 
for (j=2;j<=m;j++) 
 { for (i=0; i<=n;i++) 
 { if (s[i][cmin] > s[i][j]) {cmin=j; break;} 
 if (s[i][cmin] < s[i][j]) break; 
Bùi Thế Tâm IV.15 Quy hoạch rời rạc 
 } } 
printf("\nDong quay= %d, Cot quay= %d, Phan tu quay =%13.5lf", 
l,cmin,s[l][cmin]); 
if (tg==1) { 
fprintf(f2,"\nDong quay= %d, Cot quay= %d, Phan tu quay= %13.5lf", 
l,cmin,s[l][cmin]); } 
biendoi(); sb++; 
printf("\nBang %d, l- chuan dau tien",sb); 
if (tg==1) fprintf(f2,"\nBang %d, l- chuan dau tien",sb); 
inbang(0); lc = n+1; 
L1: kgd2= dhdoingau(); 
if (kgd2==1) { 
 printf("\nBai toan phu khong giai duoc, STOP"); 
 if (tg==1) fprintf(f2,"\nBai toan phu khong giai duoc,STOP"); 
 getch(); getch(); return; } 
 // Tim xong bang l- chuan + chap nhan duoc, sang Buoc lap lon 
Lap1: blap = blap+1; 
printf("\n------------------------------------------------"); 
printf("\n\nBUOC LAP LON THU %d: ",blap); 
if (tg==1) 
 { fprintf(f2,"\n---------------------------------------"); 
 fprintf(f2,"\n\nBUOC LAP LON THU %d: ",blap);} 
 // Kiem tra loi giai toi uu bai toan phu co nguyen khong 
le=-1; 
for(i=x0;i<=n1;i++) if(ktnguyen(s[i][0])==0){le = i; break; } 
printf("\nThanh phan le thuoc dong = %d",le); 
if (tg==1) fprintf(f2,"\nThanh phan le thuoc dong = %d",le); 
if (le==-1) { printf("\nPHUONG AN TOI UU QHTT NGUYEN: "); 
if (tg==1) 
 fprintf(f2,"\nPHUONG AN TOI UU QHTT NGUYEN: "); 
 for (i=0; i<=n;i++) 
 printf("\nx[%2d] = %13.5lf",cs[i],s[i][0]); 
 printf("\nSo luong lat cat: %d lat cat",blap-1); 
 printf("\nSo bang don hinh da lap : %d bang",sb); 
 if (tg==1) 
 { for (i=0; i<=n;i++) 
Bùi Thế Tâm IV.16 Quy hoạch rời rạc 
 fprintf(f2,"\nx[%2d] = %13.5lf",cs[i],s[i][0]); 
 fprintf(f2,"\nSo luong lat cat: %d lat cat",blap-1); 
 fprintf(f2,"\nSo bang don hinh da lap : %d bang",sb); 
 } 
 t= (unsigned long far *)MK_FP(0,0X46C); 
 t2=*t; printf("\nThoi gian chay chuong trinh: %ld giay", 
 (long int)((t2-t1)/18.21)); 
 if (tg==1) 
 fprintf(f2,"\nThoi gian chay chuong trinh:%ld giay", 
(long int)((t2-t1)/18.21)); 
 fclose(f2); getch(); 
 return; 
 } 
 // Tao lat cat moi va ghi vao cuoi bang 
lc++; cs[n+1]=lc; s[n+1][0]= -(s[le][0]- floor(s[le][0])); 
for (j=1; j<=m; j++) 
if (nc[j]<=n1) { // khi xj <= n1 
 if (ktnguyen(s[le][j])) s[n+1][j]=0; 
 else { if ((s[le][j]-floor(s[le][j]))<=fabs(s[n+1][0])) 
 s[n+1][j]=-(s[le][j]-floor(s[le][j]) ); 
 else s[n+1][j]=-(fabs(s[n+1][0])/(1-fabs(s[n+1][0]))) 
 *(1-(s[le][j]-floor(s[le][j]))); 
 } 
 } // khi xj > n1 
else { if (s[le][j]<0) s[n+1][j]=-(fabs(s[n+1][0])/(1-fabs(s[n+1][0]))) 
 *(-s[le][j]); 
 else s[n+1][j]=-s[le][j]; 
 } 
printf("\nBang %d, sau khi them lat cat",sb); 
if (tg==1) fprintf(f2,"\nBang %d, sau khi them lat cat",sb); 
inbang(1); 
 // Xac dinh dong quay va cot quay 
l=n+1 ; printf("\nDong quay = %d",l); 
if (tg==1) fprintf(f2,"\nDong quay = %d",l); 
cotquay(); 
printf("\nCot quay = %d, Phan tu quay = %13.5lf",cmin,s[l][cmin]); 
Bùi Thế Tâm IV.17 Quy hoạch rời rạc 
if (tg==1) 
fprintf(f2,"\nCot quay=%d,Phan tu quay=%13.5lf",cmin,s[l][cmin]); 
 // Bien doi bang don hinh 
biendoi(); sb++; 
printf("\nBang %d, bang dau tien bai toan phu",sb); 
if (tg==1) 
 fprintf(f2,"\nBang %d, bang dau tien bai toan phu",sb); 
inbang(0); kgd2= dhdoingau(); 
if (kgd2==1) { printf("\nBai toan phu khong giai duoc"); 
 if (tg==1) 
 fprintf(f2,"\nBai toan phu khong giai duoc, STOP"); 
 getch(); getch(); return; } 
goto Lap1; 
} 
int ktnguyen(double x) 
{ long int h; double z; z=fabs(x); h=(int)(z+0.5); 
if (fabs(z-h)<=0.0001) return 1; else return 0; 
} 
int cotquay() 
{ k=0; 
for (j=1; j<=m; j++) if (s[l][j]<-0.000001) { k=j; break;} 
if (k==0) return 1; 
cmin=k; 
for (j=k+1;j<=m;j++) if (s[l][j]< -0.000001) 
 { for (i=0; i<=n;i++) 
 {t4=s[i][cmin]/fabs(s[l][cmin]);t5=s[i][j]/fabs(s[l][j]); 
 if (t4 > t5) {cmin=j; break;} 
 if (t4 < t5) break; 
 } 
 } 
return 0; 
} 
void biendoi() 
{ for (j=0;j<=m;j++) if (j!= cmin) 
 { for (i=0;i<=n;i++) if (i!=l) 
 s[i][j]=s[i][j]-(s[l][j]/s[l][cmin])*s[i][cmin]; 
Bùi Thế Tâm IV.18 Quy hoạch rời rạc 
 s[l][j]=0; } 
for (i=0;i<=n;i++) 
if (i!=l) s[i][cmin]=-s[i][cmin]/s[l][cmin]; 
s[l][cmin]=-1; 
nc[cmin]=cs[l]; 
} 
void inbang(int cuoi) 
{ int n1; if (cuoi==1) n1=n+1; else n1=n; 
printf("\nCo so : "); 
for (i=0; i<=n1;i++) printf("%d ",cs[i]) ; printf("\n"); 
printf("Phi co so : "); 
for (j=1; j<=m; j++) printf("%d ",nc[j]);printf("\n"); 
for (i=0;i<=n1;i++) { for (j=0; j<=m;j++) 
 printf(" %10.5lf ",s[i][j]); 
 printf("\n"); } 
if (tg==1) 
{fprintf(f2,"\nCo so : "); 
for (i=0; i<=n1;i++) fprintf(f2,"%d ",cs[i]); 
fprintf(f2,"\n"); fprintf(f2,"Phi co so : "); 
for (j=1; j<=m; j++) 
fprintf(f2,"%d ",nc[j]);fprintf(f2,"\n"); 
for (i=0;i<=n1;i++) { for (j=0; j<=m;j++) 
 fprintf(f2," %13.5lf ",s[i][j]); 
 fprintf(f2,"\n"); 
 } 
 } 
getch(); 
} 
int dhdoingau() 
{ blap2 =0;Lap2: blap2++; 
printf("\nBuoc lap Don hinh doi ngau thu %d : ",blap2); 
if (tg==1) 
fprintf(f2,"\nBuoc lap Don hinh doi ngau thu %d :",blap2); 
l=-1; 
for (i=1;i<=n;i++) if (s[i][0]<0) {l=i; break;} 
printf("\nDong quay %d ",l); 
Bùi Thế Tâm IV.19 Quy hoạch rời rạc 
if (tg==1) fprintf(f2,"\nDong quay = %d",l); 
if (l==-1) { 
 printf("\nBang tren ung phuong an toi uu cua bai toan phu"); 
 if (tg==1) fprintf(f2,"\nBang tren ung phuong an toi uu bai toan phu"); 
 return 0; 
 } 
else { kgd=cotquay(); 
 if (kgd==1) return 1; 
 printf("\nCot quay=%d, Phan tu quay=%13lf",cmin,s[l][cmin]); 
 if (tg==1) 
fprintf(f2,"\nCot quay = %d, Phan tu quay =%13.5lf", 
cmin,s[l][cmin]); 
 biendoi(); sb++; 
 printf("\nBang %d, DHDN",sb); 
 if (tg==1) fprintf(f2,"\nBang %d, DHDN",sb); 
 inbang(0); 
 goto Lap2; 
 } 
} 
• Sau khi chạy chương trình ta nhận được lời giải tối ưu của bài toán trên là: 
x[ 0] = 27.00000 
x[ 1] = 7.00000 
x[ 2] = 0.00000 
x[ 3] = 1.50000 
x[ 4] = 62.00000 
x[ 5] = 0.00000 
x[ 6] = 57.50000 
x[ 7] = 2.00000 
Số lượng lát cắt: 3 lát cắt 
Số bảng đơn hình đã lập : 9 bảng 
3. THUẬT TOÁN DALTON VÀ LLEWELLYN 
 3.1. Dalton cải tiến thuật toán Gomory thứ hai cho bài toán qui hoạch tuyến tính 
rời rạc bộ phận sau: 
Bùi Thế Tâm IV.20 Quy hoạch rời rạc 
{ }
0
1
ij
1
1 2 1 1
1 2 1
Max (22)
1,..., (23)
0 1,..., (24)
, ,... , 1,..., ; (25)
0 ... , 1,...,
j
j
n
j j
j
n
j i
j
j
j
j j j jq
j j jq
x c x
a x b i m
x j n
x A A A A j n n n
A A A j n
=
=
=
= =
≥ =
∈ ≡ = ≤
= < < < =
∑
∑
 Nếu cần ta bổ sung bất đẳng thức 
 1, 1,...,jj jqx A j n≤ = (26) 
vào điều kiện (23), khi đó phương án X của bài toán (L0,C) (22) – (24) thoả mãn điều 
kiện 
10 , 1,...,jj jqx A j n≤ ≤ = . 
 3.2. Định lý 1. Giả sử ( ), rrX L C X≡ là phương án tựa tối ưu của bài toán 
( ),rL C và rijrT x= là bảng đơn hình tương ứng, 
1
0 , 1
1
r
i i i
i n
A x Aυ υ+
≤ ≤
< < 
Khi đó bất đẳng thức 
 0
r
j j
j N
xγ γ
∈
≥∑ (27) 
hay viết lại là 
0 (28)
0 (29)
r
j j
j N
Z x
Z
γ γ
∈
= − +
≥
∑
là một lát cắt đúng, trong đó: 
( )
0 0
0
, 1 0
(30)
0
(31)
0
r
i i
r r
ij ij
r
j r ri i
ij ijr
i i
x A
x x
x A x x
A x
υ
υ
υ
γ
γ
+
= −
 ≥=  − − < −
 Chứng minh định lý. Kiểm tra tính cắt: 
0 00
r
r r
j j i i
j N
x x Aυγ γ
∈
= < = −∑ (do 0rjx = ). 
 Kiểm tra tính đúng. Giả sử X là phương án của bài toán rời rạc, với i đã chọn, biểu 
diễn xi qua các biến phi cơ sở như sau: 
 ( )r0 ij
r
r
i i j
j N
x x x x
∈
= + −∑ (32) 
 Có 2 khả năng: 
Bùi Thế Tâm IV.21 Quy hoạch rời rạc 
 1) , 1i ix A υ+≥ (33) 
 2) i ix Aυ≤ (34) 
 Ta đưa vào các ký hiệu: 
( ){ } { }
( ){ } { }
( )
( )
r r
ij ij
r r
ij ij
r
ij
r
ij
, 0 , 0
, 0 , 0
r
r
r r r
r r r
j
j N
j
j N
N j j N x j j N x
N j j N x j j N x
S x x
S x x
−
+
−
+
−
∈
+
∈
= ∈ − ≤ = ∈ ≥
= ∈ − > = ∈ <
= −
= −
∑
∑
 Từ (32) ta có 
0 (35)
0 (36)
0 (37)
r
i ix x S S
S
S
− +
−
+
= + +
≤
≥
 Xét Trường hợp 1, tức là , 1i ix A υ+≥ . Từ (33) và (35) ta có 
0 , 1
r
i ix S S A υ
− +
++ + ≥ , 
suy ra ( ) ( ), 1 0 , 1 0 (do 0)r ri i i iS A x S A