Bùi Thế Tâm V.1 Quy hoạch rời rạc

Chương 5
THUẬT TOÁN GOMORY THỨ BA
Chương này trình bày thuật toán Gomory thứ ba nhằm xây dựng các lát cắt đảm
bảo tất cả các Bảng đơn hình ở mỗi bước đều có tất cả các phần tử là nguyên
1. ẢNH HƯỞNG CỦA SAI SỐ LÀM TRÒN VÀ TƯ TƯỞNG CỦA
THUẬT TOÁN GOMORY THỨ BA
1.1.
Ảnh hưởng của sai số làm tròn có thể dẫn đến lời giải sai khi dùng phương
pháp đơn hình giải bài toán quy hoạch tuyến tính. Khi giải bài toán quy hoạch tuyến
tính nguyên ảnh hưởng sai số làm tròn tăng mạnh do các nguyên nhân sau :
- Tăng khối lượng tính toán vì dùng nhiều lần
l - phương pháp.
- Khả năng mắc sai khi xử lý các số kiểu phần thập phân 0,999999 ≈ 1,000000
- Khả năng nhận lời giải không đúng vì số nguyên có thể nhận là không nguyên.
Để tránh sai số làm tròn, Gomory đưa ra thuật toán thứ ba để giải bài toán quy
hoạch tuyến tính nguyên toàn phần :

0
1
n
ij
j=1
ax (1)
a , 1, 2, , (2)
0 , 1, 2, , (3)
ên , 1, 2, , (4)
n
jj

l
- chuẩn T
0
, T
1
, , T
s
mà cái cuối cùng là chấp nhận được.
Giả sử bảng xuất phát T
0
là nguyên hoàn toàn (tất cả các phần tử là số nguyên).
Các bảng tiếp theo có thể không nguyên là do: ngoài các phép toán + , - , * khi chuyển
từ T
ν
sang T
ν+1
, ta còn dùng phép tính chia trên phần tử quay. Nếu phần tử quay trên tất
cả các bước là (-1) thì các bảng T
1
, T
2
, vẫn là nguyên khi T
0
- nguyên, cuối cùng
phương án tối ưu X
s
của bài toán (L
s
,C) ứng với T
s



Bùi Thế Tâm V.2 Quy hoạch rời rạc

ứng với T' không là phương án mở rộng. Cần xây dựng một hàm tuyến tính :

0
() ( )
jj
jN
Z
Xr rx
∈
=
+−
∑
(5)
thỏa mãn các điều kiện sau :
I. Điều kiện nguyên :
r
j
- nguyên ,
0
j
N∀∈
(6)
II. Điều kiện cắt :
Z(X') = r
0
< 0 ,




=




#
với
j
N∈ là cột của ma trận T' và

j
jN,r 0
ex min
j
l
l
j
R
R
l
r
r
∈<
= (9)
thì
1
l

là không chấp nhận được thì xây dựng lát cắt đúng nguyên thỏa mãn (5) -
(10). Viết dòng tương ứng ngay dưới bảng T
r
và lấy nó làm dòng quay. Sau đó, thực
hiện một bước lặp của
l
- phương pháp để nhận được bảng mới T
r+1
nguyên và
l
-
chuẩn.

Bùi Thế Tâm V.3 Quy hoạch rời rạc

2. XÂY DỰNG LÁT CẮT ĐÚNG NGUYÊN, THUẬT TOÁN
GOMORY THỨ BA
2.1.
Cơ sở xây dựng lát cắt đúng nguyên :
Định lý 1. Giả sử 0
λ
>

00
()
jj
jT
yd dy
∈
=+ −

j
- nguyên , jT
∈
.
Khi đó : z ≥ 0
z - nguyên.
Chứng minh. Tính nguyên của z trực tiếp suy ra từ định nghĩa phần nguyên và
tính nguyên của y
j
( jT∈ ).
Để chứng minh z ≥ 0 ta dùng phản chứng, giả sử z < 0. Từ tính nguyên của z suy
ra
z ≤ -1. (11)
Mặt khác:
00
()
j
j
jT
d
yd
y
λλ λ
∈
=+ −
∑
, như vậy

00 0
() ()



=+ −




∑

suy ra
00
()
j
j
jT
d
yd
yz
λλ λ
∈


=+ −+
 


∑
, hay

00

}
0, 0
j
yjT≥∈∪ (theo giả thiết),
0
λ
>

và định nghĩa phần lẻ
,
j
d
jT
λ

∈


. Do vậy , 0z ≥ . Định lý được chứng minh.

Bùi Thế Tâm V.4 Quy hoạch rời rạc

2.2. Từ định lý trên ta xây dựng lát cắt đúng nguyên thỏa mãn (5) - (10). Giả sử
cho bảng
0
ij
,
n
iQ jN
Tx

k
jj
jkj
dx jN
yx
yx jN
md mx
λ
∈∈
=∈
=
=∈
==

Như vậy:
0, 0
1, 0
j
j
j
d
d
d
λ
≥



=



−



∑2.3. Trong phần này ta sẽ chỉ ra trong một số trường hợp cụ thể nhận được bảng
T
0
nguyên,
l
- chuẩn :
Xét bài toán :

0
1
n
ij
j=1
ax (13)
a , 1,2, , (14)
0 , 1, 2, , (15)
ên , 1,2, , (16)
n
jj
j
ji
j

n
ij
j=1
ax ( )( )
a ( ), 1,2, ,
0, 1, 2, , , 1, ,
ên , 1, 2, , , 1, ,
n
jj
j
ni i j
j
j
mx cx
xb xi m
xj nnnm
x nguy j n n n m
=
+
≡−−
=+ − =
≥= ++
−=++
∑
∑

Ta có các biến x
1
, , x
n

x
2
0 0 -1 0 0
#

#

#

###

x
n
0 0 0 0 -1
x
n+1
b
1
a
11
a
12
a
1j

x
n+i
b
i
a
i1
a
i2
a
ij
a
in

# # # #

#

#
x
n+m
b
m
a
n1
a
m2
a
mj
a
mn

n
j
j=1
x
∑
với ràng buộc
(14)-(15) và tìm được:
n
j
j=1
ax x 'mM=
∑

Rõ ràng, với mọi phương án của bài toán (13) - (16) ta đều có :
[]
n
j
j=1
x'
M
M
≤
≡
∑

Vì vậy, từ bài toán này ta có thể đưa vào biến mới :

Bùi Thế Tâm V.6 Quy hoạch rời rạc
1, ,
ex min
lj
jn
Rl R
∈
=
(
'
j
R
- là cột của
'
0
T ứng với biến phi cơ sở
( 1, , )
j
x
jn
=
).
Thực hiện một bước lặp của
l - phương pháp, xóa dòng x
n+m+1
(dòng cuối của
bảng
'
0
T
) và nhận được bảng T

Xxxx xxx==


là phương án tối ưu mở rộng của bài toán (L
N
,C) và thuật toán dừng. Nếu T
0
không
chấp nhận được thì chuyển tới bước lặp đầu tiên.
Bước lặp p (p ≥ 1). Cho bảng
0
1
P-1
1ij
,
n
P
P
iQ jN
Tx
−
−
∈∈
= - nguyên , l - chuẩn nhưng
không chấp nhận được. Chọn k là chỉ số đầu tiên vi phạm tính chấp nhận được
{
}
{
}
1

thì ta chọn cột cột quay l theo công thức :

1
11
,0
ex min
Pkj
PP
lj
jN x
Rl R
−
−−
∈<
= (20)
và xây dựng lát cắt đúng nguyên (dòng quay) :

1
1
1
0
( ) (21)
0 (22)
ên
P
P
P
kj
k
nP j

Viết dòng (21) vào cuối bảng T
P-1
và lấy làm dòng quay. Thực hiện một bước lặp
của
l - phương pháp (loại x
n+P
khỏi cơ sở, đưa x
l
vào cơ sở), xóa dòng x
n+P
. Nếu l ≥ n+1
thì dòng x
l
không khôi phục nữa, ta sẽ nhận được bảng

Bùi Thế Tâm V.7 Quy hoạch rời rạc

0
P
ij
,
n
P
P
iQ jN
Tx
∈∈
=
là nguyên và
l - chuẩn, trong đó :

P
không châp nhận được thì chuyển tới bước
(p+1).
2.5. Quy tắc chọn số λ . Số λ được chọn theo ba điều kiện sau

I. Phần tử quay bằng (-1) : 1
1
P
kl
x
λ
−

=
−


(24)
II. Bảng T
P
phải là l - chuẩn : 1
11
0
P

R
phải là lexmin : 1
11
0
00
ex min
P
PP P
k
l
x
RR R l
λ
−
−−

=+ →


(26)

Chú ý :

1)
1
1
0

10
P
kl
x
λ
−
−
≤<,
do
0
λ
>
nên ta có :

1P
kl
x
λ
−
≥− (24')
b) Điều kiện (25) có thể đơn giản hóa bằng cách sau.
Nếu
1
0
P
kj
x
−
≥ thì
1

0
P
kj
x
−
<
.

Bùi Thế Tâm V.8 Quy hoạch rời rạc

Với mỗi
1P
j
N
−
∈ , ta đặt :
{
}
() min | 0.
p-1
ij
hj ix=>
Từ (20) suy ra
P-1
P-1 kj
( ) ax{h(j)|j N , x <0}hl m=∈
. Rõ ràng, nếu h(j) < h(l) thì
với bất kỳ
λ
ta có :

0
P
kj
x
−
<
và h(j) = h(l).
Khi đó, điều kiện (25) được viết lại là :

1
11'
1
0,
P
kj
PP P
jj l P
x
R
RRjN
λ
−
−−
−

=+ >∀∈



(25')

ta có thể tìm được số tự nhiên z
j
sao
cho :

1111
(1) 0
PPPP
jjl jjl
R
zR RzR
−−−−
−+ << − (27)

Chú ý rằng
11PP
jl
R
zR
−−
≠ với z bất kỳ, vì nếu
11PP
jl
R
zR
−
−
= thì
01
P-1

j
= 1 thì (27) thỏa mãn.
2)
11
() ()
PP
hl j hll
x
qx r
−−
=
+ trong đó q, r là các số tự nhiên,
1
()
P
hll
rx
−
< . Khi đó nếu chọn
chọn z
j
= q thì (27) được thỏa mãn.
3)
11PP
ij il
x
qx
−−
= , i = h(l) , h(l) + 1 , , h(l) + t ≡ s - 1, và


Từ (27) và (25') suy ra cần chọn số λ thỏa mãn:
1
'
1
,
P
kj
jP
x
zjN
λ
−
−

−≤ ∀∈



, hay
1P
kj
j
x
z
λ
−
≥− , suy ra
1P
kj
j

trong đó z
j
- được chọn theo 4 khả năng đã trình bày ở trên.
c) Xét điều kiện (26). Vì λ > 0 ,
11
0
0, 0
PP
kl
xR
−−
<
>
nên điều kiện (26) được viết lại
như sau :

min
λ
→
(26')

Cuối cùng từ (24') , (25'') , (26') ta có :

{
}
P-1
kl
ax -x ,m
λ
θ

xxx
xxxx
xxxx
4- 8-
8

4321
,,, xxxx nguyên.
Sau khi thêm biến bù bài toán viết lại thành
Max
43210
3663 xxxxx
−
−
+
=

43215
92245 xxxxx
+
+
+
−
=
43216
66729 xxxxx
+
+
+
+

100 xxxxx −−−−= - và 0
9
≥x và viết vào phía dưới bảng 1. Chọn dòng x
9

làm dòng quay.
1 -x
1
-x
2
-x
3
-x
4
x
0
0 -3 -6 6 3
x
1
0 -1 0 0 0
x
2
0 0 -1 0 0
x
3
0 0 0 -1 0
x
4
0 0 0 0 -1
x


Bảng 2
x
10
-66 -1* -1 -2 -1

Tiếp tục dùng thuật toán đơn hình đối ngẫu từ vựng ta được bảng 3 là l- chuẩn và
không chấp nhận được. Vì x
5
<0 nên sinh ra lát cắt x
11
và chọn nó làm dòng quay.
1 -x
1
-x
9
-x
3
-x
4
x
0
600 3 6 12 9
x
1
0 -1 0 0 0
x
2
100 1 1 1 1
x

0
402 3 3 6 6
x
1
66 -1 1 2 1
x
2
34 1 0 -1 0
x
3
0 0 0 -1 0
x
4
0 0 0 0 -1
x
5
-191 6 -4 -12 -13
x
6
361 5 2 -9 -4
x
7
0 -12 4 7 4
x
8
531 -8 8 16 4
Bảng 3
x
11
-15 0 -1* -1 -1

5
131 6 -4 -8 -9
x
6
331 5 2 -11 -6
x
7
-60 -12 4 3 0
x
8
441 -8 8 8 -4
Bảng 4
x
12
-15 0 -1 -1 -1*

Tiếp tục dùng thuật toán đơn hình đối ngẫu từ vựng ta được bảng 5 là l- chuẩn và
không chấp nhận được. Vì x
7
<0 nên sinh ra lát cắt x
13
và chọn nó làm dòng quay.

Bùi Thế Tâm V.12 Quy hoạch rời rạc 1 -x
10
-x
11

471 -8 12 12 -4
Bảng 5
x
13
-5 -1* 0 0 0
Tiếp tục dùng thuật toán đơn hình đối ngẫu từ vựng ta được bảng 6 là l- chuẩn và
không chấp nhận được. Vì x
5
<0 nên sinh ra lát cắt x
14
và chọn nó làm dòng quay.
1 -x
13
-x
11
-x
3
-x
12
x
0
297 3 0 0 3
x
1
56 -1 1 1 0
x
2
29 1 0 -1 0
x
3

11
-x
3
-x
14
x
0
288 3 0 0 3
x
1
56 -1 1 1 0
x
2
29 1 0 -1 0
x
3
0 0 0 -1 0
x
4
18 0 1 1 -1
x
5
1 6 5 1 -9
x
6
414 5 8 -5 -6
x
7
0 -12 4 3 0
x

p
7
x
p
8

λ

1 600 0 100 0 0 205 691 -792 3 12
2 402 66 34 0 0 -191 361 0 531 13
3 357 51 34 0 0 -131 331 -60 411 9
4 312 51 34 0 15 4 421 -60 471 12
5 297 56 29 0 15 -26 396 0 511 9
6 288 56 29 0 18 1 414 0 523

Vậy phương án tối ưu là (56, 29, 0, 18, 1, 414, 0, 523) với trị hàm mục tiêu là
x[0]=288.
3. CHƯƠNG TRÌNH MÁY TÍNH
• Thuật toán này dùng để giải bài toán quy hoạch tuyến tính nguyên hoàn toàn ,
có dạng:
max
1
0
→=
∑
=
j
m
j
j

j
ij
bxa =
∑
=1
thì ta thay thế bằng hai
bất đẳng thức:
ii
m
j
ij
bxa ≤
∑
=1
và
ii
m
j
ij
bxa ≥
∑
=1
.

Sau khi thêm biến bù bài toán trên có thể viết ở dạng:
max))((
1
0
→−−=
∑

j
x nguyên. ., ,2,1
p
m
j
+
=

• Trong chương trình sử dụng các biến và mảng sau:
- m: số biến chính, n: số biến chính và biến bù của bài toán (n=m+p), gz là một
số dương đủ lớn và thường lấy bằng
},,{max
jiij
cba .
- ss = 1 nếu bảng đơn hình s ban đầu là l- chuẩn, =2 nếu bảng không là l - chuẩn
- Mảng s gồm n + 2 dòng và m+1 cột lúc đầu ghi dữ liệu của bài toán sau đó lưu
bảng đơn hình ở mỗi bước. Dòng n+1 để chứa ràng buộc phụ.
- s[0][0] hàm mục tiêu, cột 0 là cột phương án, dòng 0 là các ước lượng
- cs : các biến ở bên trái bảng đơn hình, nc : các biến phi cơ sở
•
Cách nhập dữ liệu
Dữ liệu ban đầu của bài toán được ghi trong một tệp văn bản, gồm có:
- n, m, gz, ss.
- Mảng s dữ liệu ban đầu bố trí dạng (ở dưới) và được ghi vào tệp dữ liệu theo
từng dòng :
Bùi Thế Tâm V.15 Quy hoạch rời rạc


• Văn bản chương trình
#include <stdio.h>
#include <conio.h>
#include <math.h>
-x
1
-x
2
. . . . . . . . . –x
m
0 -c
1
-c
2
. . . . . . . . –c
m
x
0
x
1
x
2
#

x
m
0
0
#
0

#define N 30
long int s[N+2][M+1],gz,t1,t2,lamda; double r;
int sb,cmin,m,n,i,j,k,l,lc,tg,cs[N+2],nc[M+1], np[M+1];
int ka,blap,hl,hj,trong,zj[M+1],q,is,ss;
unsigned long far *t; char *s1,*s2;
FILE *f1,*f2;
void biendoi();
void inbang(int cuoi);
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 ban dau
printf("\nVao ten tep so lieu : "); gets(s1);
f1= fopen(s1,"r"); fscanf(f1,"%d%d%ld%d",&n,&m,&gz,&ss);
for(i=0;i<=n;i++)for(j=0;j<=m;j++) fscanf(f1,"%ld",&s[i][j]);
for (i=0; i<=n;i++) fscanf(f1,"%d",&cs[i]) ;
for (j=1; j<=m; j++) fscanf(f1,"%d",&nc[j]);
fclose(f1);
sb=1; blap=0;
// In kiem tra ket qua nhap
printf("\n n,m,gz,ss = %d %d %10ld %d",n,m,gz,ss);
if (tg==1){ printf("\nVao ten tep chua ket qua : "); gets(s2);
f2=fopen(s2,"w");
fprintf(f2,"\n n,m,gz,ss = %d %d %10ld %d",n,m,gz,ss);
}
printf("\nBang 1, so lieu ban dau:");
if (tg==1) fprintf(f2,"\nBang 1, so lieu ban dau:");
inbang(0);

printf("\nBang %d, khong ke dong n+1, l - chuan",sb);
if (tg==1)
fprintf(f2,"\nBang %d, khong ke dong n+1, l- chuan",sb);
inbang(0); lc=n+1;
//Bat dau buoc lap lon, da tim duoc bang xuat phat l- chuan
Lap1: blap++; 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 cot phuong an con thanh phan am khong
ka=-1;
for (i=1; i<=n; i++) if (s[i][0]<0) {ka = i; break; }

Bùi Thế Tâm V.18 Quy hoạch rời rạc

printf("\nPhan tu am cua phuong an ung voi dong %d",ka);
if (tg==1)
fprintf(f2,"\nPhan tu am cua phuong an ung voi dong %d",ka);
// Bang don hinh la toi uu
if (ka==-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] = %13ld",cs[i],s[i][0]);
printf("\nSo luong lat cat: %d lat cat",blap-1);
printf("\nSo bang da lap : %d bang",sb);
if (tg==1)
{ for (i=0; i<=n;i++)

}
}
printf("\nCot quay = %d",cmin);
if (tg==1) fprintf(f2,"\nCot quay = %d ",cmin);
// Xay dung lat cat
lamda = -s[ka][cmin];
printf("\nlamda = %10ld",lamda);
if (tg==1) fprintf(f2,"\nlamda = %10ld",lamda);
for (j=1;j<=m;j++) np[j]=0;
for (j=1;j<=m; j++) if (s[ka][j]<0) np[j]=1; np[cmin]=0;
printf("\nMang NP : ");
for (j=1;j<=m;j++) printf("%d ",np[j]); printf("\n");
if (tg==1) {
fprintf(f2,"\nMang NP : ");
for(j=1;j<=m;j++) fprintf(f2,"%d ",np[j]); fprintf(f2,"\n"); }
// Xet np co trong hay khong
trong=1;
for (j=1; j<=m; j++) if (np[j]==1) {trong=0; break;}
if (trong==1) goto L2;
// Truong hop np khac trong, tim hl
for (i=0;i<=n;i++) if (s[i][cmin]>0) {hl=i; break;}
printf("\nh[%d] = %d",cmin,hl);
if (tg==1) fprintf(f2,"\nh[%d] = %d",cmin,hl);
// Tim cac hj ung voi cac cot ma np[j]=1
for (j=1;j<=m;j++)
if (np[j]==1)
{ for (i=0;i<=n;i++) if (s[i][j]>0) {hj=i; break;}
printf("\nh[%d] = %d",j,hj);
if (tg==1) fprintf(f2,"\nh[%d] = %d",j,hj);
if (hj != hl) np[j]=0; // np chi xet voi j ma hj=hl

fprintf(f2,"\nMang ZJ : ");
for(j=1;j<=m;j++) fprintf(f2,"%d ",zj[j]); fprintf(f2,"\n"); }
// Tinh lai lamda
for (j=1;j<=m;j++) if (np[j]==1)
{ if ((-s[ka][j])%zj[j]==0) q= (-s[ka][j])/zj[j];
else q= (-s[ka][j])/zj[j]+1;
if (q>lamda) lamda=q; }
// Da tinh xong lamda, xay dung lat cat
L2: printf("\nlamda cuoi cung = %ld",lamda);
if (tg==1) fprintf(f2,"\nlamda cuoi cung = %ld",lamda);

Bùi Thế Tâm V.21 Quy hoạch rời rạc

lc++; cs[n+1]=lc;
for (j=0; j<=m; j++)
{ if (s[ka][j]>=0) s[n+1][j]=s[ka][j]/lamda;
else
{ if ((-s[ka][j])%lamda==0) s[n+1][j]=s[ka][j]/lamda;
else s[n+1][j]=s[ka][j]/lamda-1; }
}
printf("\nBang %d, sau khi them lat cat moi",sb);
if (tg==1)
fprintf(f2,"\nBang %d, sau khi them lat cat moi",sb);
inbang(1);
// Bien doi bang don hinh
l=n+1 ; printf("\nDong quay = %d",l);
if (tg==1) fprintf(f2,"\nDong quay = %d",l);
biendoi(); sb++;
printf("\nBang %d, khong ke dong n+1",sb);
if (tg==1) fprintf(f2,"\nBang %d, khong ke dong n+1",sb);

fprintf(f2," %10ld ",s[i][j]);
fprintf(f2,"\n"); }
}
getch();
}
• 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] = 288
x[ 1] = 56
x[ 2] = 29
x[ 3] = 0
x[ 4] = 18
x[ 5] = 1
x[ 6] = 414
x[ 7] = 0
x[ 8] = 523
Số lượng lát cắt: 5 lát cắt
Số bảng đã lập : 7 bảng
BÀI TẬP
Giải các bài toán quy hoạch tuyến tính nguyên sau bằng thuật toán Gomory thứ
ba:
Bài 1. Max x0 = x1 + x2
3 * x1 + 2 * x2 <= 5
x2 <= 2
x1, x2 => 0 và nguyên
Đáp số : (x0, x1, x2, x3, x4) = (2; 1; 1; 0; 1)
Bài 2. Max x0 = 3 * x1 – 4 * x2
- 2 * x1 + x2 <= 3
x1 – 2 * x2 <= 3
2 * x1 + x2 <= 10


j
=1, ,5
j
j
mx xx
xxx
xxx
xxx
xj
xnguy
≡ +
++=
− ++=
− +=
≥ =
−

Đáp số : ( x0, x1, x2, x3, x4, x5) = (5; 3; 2; 4; 2; 3)
Bài 6. Max
43210
252 xxxxx
+
+
−
=

6557
4321
≤
−

43210
,,,, xxxxx
nguyên.
Đáp số: phương án tối ưu mở rộng (294, 26, 0, 40, 34, 10, 1, 192, 655, 26)