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

g đó : 
{ }( ) { }1 \P PN N l n p−= ∪ + 
Nếu TP là chấp nhận được thì ( ) ( )0 1 00 10 0, ,..., , ,...,P P P P P P Pn nX x x x x x x= = là phương án 
tối ưu mở rộng của bài toán (LN,C) . Nếu TP 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
klx
λ
−  = −  
 (24) 
 II. Bảng TP phải là l - chuẩn : 
1
1 1 0
P
kjP P P
j j l
x
R R Rλ
−
− − = + >   
 , (25) 
 { }( )1\ \{ }P Pj N n p N l−∀ ∈ + = 
 III. Cột 0
PR phải là lexmin : 
1
1 10
0 0 ex min
P
P P Pk
l
xR R R lλ
−
− − = + →  
 (26) 
Chú ý : 
1) 
1
1 0
1
P
P Pl
n P l
RR R
−
−
+
−= = >− suy ra bất đẳng thức (25) đúng với j = n + p rồi. 
2) Từ (24) và 1 0Pklx
− 
2.6. Xác định λ thỏa mãn (24) - (26) 
a) Điều kiện (24) có thể viết thành : 
1
1 0
P
klx
λ
−
− ≤ < , 
do 0λ > nên ta có : 
 1Pklxλ −≥ − (24') 
b) Điều kiện (25) có thể đơn giản hóa bằng cách sau. 
Nếu 1 0Pkjx
− ≥ thì 
1
1 0
P
kj P
l
x
Rλ
−
−  ≥   
 và điều kiện (25) đúng với bất kỳ 0λ > . Do 
vậy, chỉ cần xét điều kiện (25) với : 
1 \{ }Pj N l−∈ mà 1 0Pkjx − < . 
Bùi Thế Tâm V.8 Quy hoạch rời rạc 
Với mỗi 1Pj N −∈ , ta đặt : 
{ }( ) min | 0 .p-1ijh j i x= > 
Từ (20) suy ra P-1P-1 kj( ) ax{h(j)|j N , x <0}h l m= ∈ . Rõ ràng, nếu h(j) < h(l) thì 
với bất kỳλ ta có : 
1
1 1 0
P
kjP P P
j j l
x
R R Rλ
−
− − = + >   
Do đó, trường hợp này (25) cũng đúng. 
Như vậy, chỉ cần xét (25) với : 
1 \{ }Pj N l−∈ mà 1 0Pkjx − < và h(j) = h(l). 
Khi đó, điều kiện (25) được viết lại là : 
1
1 1 '
10 ,
P
kjP P P
j j l P
x
R R R j Nλ
−
− −
−
 = + > ∀ ∈   
 (25') 
{ }' P-11 1 kj| \{ } , x 0 , ( ) ( )P PN j j N l h j h l− −= ∈ < = 
 Nếu ' 1PN − = ∅ thì (25') không cần thêm bất cứ điều kiện nào trên số 0λ > . Bây 
giờ giả sử ' 1PN − ≠ ∅ . Khi đó đối với mỗi ' 1Pj N −∈ ta có thể tìm được số tự nhiên zj sao 
cho : 
 1 1 1 1( 1) 0P P P Pj j l j j lR z R R z R
− − − −− + < < − (27) 
Chú ý rằng 1 1P Pj lR zR
− −≠ với z bất kỳ, vì nếu 1 1P Pj lR zR− −= thì 
0 1
P-1
ij ,
det 0
Pi N j N
x
−∈ ∈
= , điều này là không thể. Do đó 1 1à P Pj lR v R− − là không tỉ lệ với 
nhau. 
Có 4 khả năng : 
1) 1 1( ) ( )
P P
h l j h l lx x
− −= . Khi đó nếu chọn zj = 1 thì (27) thỏa mãn. 
2) 1 1( ) ( )
P P
h l j h l lx qx r
− −= + trong đó q, r là các số tự nhiên, 1( )Ph l lr x −< . Khi đó nếu chọn 
chọn zj = q thì (27) được thỏa mãn. 
3) 1 1P Pij ilx qx
− −= , i = h(l) , h(l) + 1 , ... , h(l) + t ≡ s - 1, và 
 1 1P Psj slx qx
− −> trong đó q là số tự nhiên ≥2. 
Khi đó, nếu ta chọn zj = q thì (27) đúng. 
4) 1 1P Pij ilx qx
− −= , i = h(l) , h(l) + 1 , ... , h(l) + t ≡ s - 1, và 
1 1P P
sj slx qx
− −< , trong đó q là số tự nhiên ≥ 2. 
Khi đó, ta chọn zj = q - 1 thì (27) đúng. 
Bùi Thế Tâm V.9 Quy hoạch rời rạc 
Từ (27) và (25') suy ra cần chọn số λ thỏa mãn: 
1
'
1,
P
kj
j P
x
z j Nλ
−
−
 − ≤ ∀ ∈   
, hay 
1P
kj
j
x
zλ
−
≥ − , suy ra 
1P
kj
j
x
z
λ
−
≥ − . Vậy điều kiện (25') chuyển thành điều kiện sau: 
P-1
kj '
1
j
x
ax -
z P
m j Nλ θ −
  ≥ ≡ ∈   
 (25'') 
trong đó zj - được chọn theo 4 khả năng đã trình bày ở trên. 
c) Xét điều kiện (26). Vì λ > 0 , 1 10 0, 0
P P
k lx R
− − 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-1klax -x ,mλ θ= (28) 
2.7. Giải ví dụ bằng số 
Giải bài toán quy hoạch nguyên sau: 
Max 43210 3663 xxxxx −−+= 
3
984
96672
59224
41
321
4321
4321
≤
≤−+−
≥+++
≤−−−
xx
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 ++++−= 
3217 9848 xxxx +−+= 
418 483 xxx ++= 
876543210 ,,,,,,,, xxxxxxxxx nguyên 
Bùi Thế Tâm V.10 Quy hoạch rời rạc 
Từ đây ta có bảng đơn hình xuất phát (Bảng 1). Vì bảng đơn hình không là l- 
chuẩn nên ta phải thêm ràng buộc phụ 1004321 =≤+++ gzxxxx hay 
43219 100 xxxxx −−−−= - và 09 ≥x và viết vào phía dưới bảng 1. Chọn dòng x9 
làm dòng quay. 
 1 -x1 -x2 -x3 -x4 
x0 0 -3 -6 6 3 
x1 0 -1 0 0 0 
x2 0 0 -1 0 0 
x3 0 0 0 -1 0 
x4 0 0 0 0 -1 
x5 5 4 -2 -2 -9 
x6 -9 -2 -7 -6 -6 
x7 8 -4 8 -9 0 
x8 3 -8 0 0 -4 
 Bảng 1 
x9 100 1 1* 1 1 
Thực hiện một bước của đơn hình đối ngẫu từ vựng ta được bảng 2 là l-chuẩn. Vì 
x7 <0 nên sinh ra lát cắt x10 và chọn nó làm dòng quay. 
 Bảng 2 
x10 -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ì x5 <0 nên sinh ra lát cắt x11 và chọn nó làm dòng quay. 
 1 -x1 -x9 -x3 -x4 
x0 600 3 6 12 9 
x1 0 -1 0 0 0 
x2 100 1 1 1 1 
x3 0 0 0 -1 0 
x4 0 0 0 0 -1 
x5 205 6 2 0 -7 
x6 691 5 7 1 1 
x7 -792 -12 -8 -17 -8 
x8 3 -8 0 0 -4 
Bùi Thế Tâm V.11 Quy hoạch rời rạc 
 1 -x10 -x9 -x3 -x4 
x0 402 3 3 6 6 
x1 66 -1 1 2 1 
x2 34 1 0 -1 0 
x3 0 0 0 -1 0 
x4 0 0 0 0 -1 
x5 -191 6 -4 -12 -13 
x6 361 5 2 -9 -4 
x7 0 -12 4 7 4 
x8 531 -8 8 16 4 
 Bảng 3 
x11 -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 4 là l- chuẩn và 
không chấp nhận được. Vì x7 <0 nên sinh ra lát cắt x12 và chọn nó làm dòng quay. 
 1 -x10 -x11 -x3 -x4 
x0 357 3 3 3 3 
x1 51 -1 1 1 0 
x2 34 1 0 -1 0 
x3 0 0 0 -1 0 
x4 0 0 0 0 -1 
x5 131 6 -4 -8 -9 
x6 331 5 2 -11 -6 
x7 -60 -12 4 3 0 
x8 441 -8 8 8 -4 
 Bảng 4 
x12 -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ì x7 <0 nên sinh ra lát cắt x13 và chọn nó làm dòng quay. 
Bùi Thế Tâm V.12 Quy hoạch rời rạc 
 1 -x10 -x11 -x3 -x12 
x0 312 3 0 0 3 
x1 51 -1 1 1 0 
x2 34 1 0 -1 0 
x3 0 0 0 -1 0 
x4 15 0 1 1 -1 
x5 4 6 5 1 -9 
x6 421 5 8 -5 -6 
x7 -60 -12 4 3 0 
x8 471 -8 12 12 -4 
 Bảng 5 
x13 -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ì x5 <0 nên sinh ra lát cắt x14 và chọn nó làm dòng quay. 
 1 -x13 -x11 -x3 -x12 
x0 297 3 0 0 3 
x1 56 -1 1 1 0 
x2 29 1 0 -1 0 
x3 0 0 0 -1 0 
x4 15 0 1 1 -1 
x5 -26 6 5 1 -9 
x6 396 5 8 -5 -6 
x7 0 -12 4 3 0 
x8 511 -8 12 12 -4 
 Bảng 6 
x14 -3 0 0 0 -1* 
Thực hiện một bước của thuật toán đơn hình đối ngẫu từ vựng ta được bảng l- 
chuẩn chấp nhận được có cột phương án là nguyên và quá trình lặp kết thúc. 
Bùi Thế Tâm V.13 Quy hoạch rời rạc 
 1 -x13 -x11 -x3 -x14 
x0 288 3 0 0 3 
x1 56 -1 1 1 0 
x2 29 1 0 -1 0 
x3 0 0 0 -1 0 
x4 18 0 1 1 -1 
x5 1 6 5 1 -9 
x6 414 5 8 -5 -6 
x7 0 -12 4 3 0 
x8 523 -8 12 12 -4 
 Bảng 7 
Bảng tổng hợp :(Phương án và giá trị λ ở mỗi bước) 
P 
x p0 x
p
1 x
p
2 x
p
3 x
p
4 x
p
5 x
p
6 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 xcx 
ij
m
j
ij bxa ≤∑
=1
, pi ,...,1= 
0≥jx , mj ,...,2,1= 
jx nguyên. 
Bùi Thế Tâm V.14 Quy hoạch rời rạc 
các b[i] có thể dương và âm, phương án xuất phát không đối ngẫu chấp nhận được. 
Nếu bài toán có ràng buộc đẳng thức dạng: ii
m
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 →−−=∑
=
m
j
jj xcx 
mjxx jj ,...,2,1))(1( =−−= 
.,...,2,1))((
1
pixabx j
m
j
ijiim =−−+= ∑
=
+ 
.,...,2,10 pmjx j +=≥ 
jx nguyên. .,...,2,1 pmj += 
• 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 
- Tiếp đến là mảng cs: nhập các số từ 0, 1, 2,, n 
- Cuối cùng là mảng nc: nhập các số từ 1, 2,, m 
•Với dữ liệu bài toán trên thì ta có tệp dữ liệu VDG3.CPPcó dạng: 
8 4 100 2 
 0 -3 -6 6 3 
 0 -1 0 0 0 
 0 0 -1 0 0 
 0 0 0 -1 0 
 0 0 0 0 -1 
 5 4 -2 -2 -9 
 -9 -2 -7 -6 -6 
 8 -4 8 -9 0 
 3 -8 0 0 -4 
 0 1 2 3 4 5 6 7 8 
 1 2 3 4 
•Văn bản chương trình 
#include 
#include 
#include 
 -x1 -x2 . . . . . . . . . –xm 
0 -c1 -c2 . . . . . . . . –cm x0 
x1 
x2 
# 
xm 
0 
0 
# 
0 
-1 0 . . . . . . . . . . 0 
 0 -1 . . . . . . . . . 0 
# # % # 
0 0 . . . . . . . . . . -1 
xm+1 
# 
xn 
b1 
# 
bp 
-a11 . . . . . . . . . - a1m 
# # # 
-ap1 . . . . . . . . . .-ap,m 
Bùi Thế Tâm V.16 Quy hoạch rời rạc 
#include 
#define M 30 
#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 : "