Chuyên đề Chương 3: Thuật toán gomory thứ nhất

ược bảng đơn hình: 0rij ,n rr i Q j NT x ∈ ∈= là chấp nhận được và l - chuẩn. 
 Chọn dòng đầu tiên ứng với thành phần không nguyên: 
k { }{ }min 1.. , không nguyênrioi i n x= ∈ 
và xây dựng lát cắt đúng: 
{ } { }( )( )r1 0 kj
1
1
0
 nguyên
r
n r jk
j Nr
n r
n r
x x x x
x
x
+ +
∈
+ +
+ +
 = − + − − ≥
∑
 (24) 
Bùi Thế Tâm III.9 Quy hoạch rời rạc 
Viết dòng thứ nhất của (24) vào cuối bảng đơn hình rT . Ta được bảng đơn hình 
không chấp nhận được (chỉ với 1n rx + + ) và l - chuẩn. Dùng l -phương pháp đối với 
bảng này, đồng thời sau khi đưa khỏi cơ sở 1n rx + + thì dòng tương ứng 1n r+ + bị 
xoá, sau khi đưa vào cơ sở lx ( 1l r≥ + ) thì dòng tương ứng không được khôi phục. 
Nếu cuối cùng ta nhận được bảng đơn hình ứng với bài toán quy hoạch tuyến tính 
không giải được thì bài toán 0( , )NL C cũng không giải được . 
 Nếu ta nhận được bảng 1rT + chấp nhận được và l - chuẩn thì kiểm tra tính nguyên 
của 1( , )rX L C+ . Nếu 1( , )rX L C+ thoả mãn điều kiện nguyên thì nó đồng thời là 
phương án tối ưu của bài toán 0( , )NL C , nếu không thoả mãn thì chuyển sang bước 
r+1. 
3. TÍNH HỮU HẠN CỦA THUẬT TOÁN GOMORY THỨ NHẤT 
Giả sử tập các phương án tối ưu của bài toán 0( , )L C là bị chặn. 
Định lý 4. Giả sử có các điều kiện sau: 
1) Tính nguyên của hàm mục tiêu 0x CX≡ được đảm bảo và 0x được xét khi 
chọn dòng xây dựng lát cắt đúng. 
2) Một trong các khẳng định sau là đúng: 
i) Hàm mục tiêu 0x bị chặn dưới trên 0L . 
ii) Bài toán 0( , )NL C có ít nhất một phương án 'X . 
 Khi đó thuật toán Gomory thứ nhất kết thúc sau một số hữu hạn bước lặp lớn. 
 Trước khi chứng minh định lý ta cần chứng minh ba bổ đề. Giả sử 
( , )rX L C 0 1( , ,..., )r r r rnX x x x≡ ≡ . Kí hiệu rX là giả phương án ứng với bảng rT nhận 
được từ bảng rT sau khi loại khỏi cơ sở 1n rx + + và xoá dòng tương ứng . 
 Bổ đề 1. Ta có: 1rr rX X X +> ≥ . 
 Bất đẳng thức đầu tiên suy ra từ công thức biến đổi bảng đơn hình và tính l - 
chuẩn của bảng đơn hình (cột đầu tiên của rT được tính theo công thức { }
{ }00
( )
. ,
( )
r
kr r r
l lr
kl
x
R R R
x
−− − có số đầu tiên khác 0 là dương). Bất đẳng thức thứ hai là do cột 
0 giảm khi dùng phương pháp đơn hình đối ngẫu từ vựng. 
 Bổ đề 2. Các số ( 0,1,..., )rix i n= bị chặn dưới. 
Chứng minh. Với i = 1, ..., n điều đó suy ra từ điều kiện không âm 
0jx ≥ ( 1,..., )j n= . Với 0i = điều đó suy ra từ điều kiện 2) của định lý 4. Thật vậy, 
nếu i) là đúng thì bổ đề 2 là hiển nhiên đúng. Nếu điều kiện ii) được thoả mãn thì 
'rX X≥ suy ra '0 0rx x≥ . 
 Bổ đề 3. Nếu rX không thoả mãn điều kiện nguyên và 0r rp px x≡ không nguyên 
thì: 
Bùi Thế Tâm III.10 Quy hoạch rời rạc 
[ ]0 1 1 0( , ,..., , ) ( ,..., )r r r r r rpp px x x x x x− ≥ . 
 Chứng minh 
Giả sử k { }{ }min 0,1,..., , không nguyênrioi i n x= ∈ , suy ra k p≤ . Giả sử 
 { } { } { }lex min , 0
rr
j rl
rr kjr
kl kj
RR
j N x
x x
   = ∈ ≠    
(dòng quay là lát cắt mới thêm) và { }{ }( ) min i i 0,1,...n ; 0r rl ilh R x= ∈ ≠ ( hàng đầu 
tiên của cột lR có hệ số 0≠ , cụ thể là 0rhlx > do 0rlR > ). 
 Vì { } 0 0 ( )r r rkl kl lx x h R k p≠ ⇒ ≠ ⇒ ≤ ≤ . Có hai khả năng xảy ra: 
1) ( )rlh R q p≡ < . 
2) ( )rlh R q p≡ = . 
 Trong trường hợp 1) theo quy tắc của l -phương pháp rrq qx x< vì 
{ }
{ }
0 (do 0)
r
r r r rr kq q qr ql ql
kl
x
x x x x x
x
= − , và bổ đề được chứng minh. 
 Trong trường hợp 2) ta có ( )rlh R k p= = . Vì vậy 00
rr
iix x= với ( )
r
li k h R< = 
(h là chỉ số đầu tiên rhlx khác không) và 
{ }
{ }
0
0 0
r
r rr k
rk k kl
kl
x
x x x
x
= − . 
 Vì rklx = 0
r
hlx > , nên { }r rkl klx x≥ . Từ đó ta có : 
 { } [ ]0 0 0 0r r rrk k k kx x x x≤ − = . 
Do k = p nên bổ đề được chứng minh. 
 Chứng minh định lý 4 
Giả sử dãy : 
 0 1, ,..., ,...rX X X vô hạn (25) 
Khi đó theo Bổ đề 1 và Bổ đề 2 tồn tại 0i , 00 i n≤ ≤ ; tồn tại 0 0r ≥ và một dãy vô 
hạn : 
1 2 1 0... ...( )r r r r rν< < < < ≥ (26) 
sao cho ta có : 
 1r riix x
+ = ; 0r r≥ ; 00 1i i≤ ≤ − (27) 
0 0
1r r
i ix xν ν
+ < ,(ν = 1,2,...) (28) 
 Từ Bổ đề 1 và (27) ta có 
 00
1
0,r riix x r r
+ ≤ ≥ (29) 
Bùi Thế Tâm III.11 Quy hoạch rời rạc 
 Từ (28), (29) và bổ đề 2 suy ra tồn tại số ' 0r r> và các số nguyên 0z và 0z +1 
sao cho: 
00 0 1
r
iz x z< < + , '( )r r≥ (30) 
 Từ (27), (30) và Bổ đề 3 suy ra: [ ]00 0
1
0
r rr
ii ix x x z
+ ≤ ≤ = . Điều này là mâu thuẫn 
với (30), định lý được chứng minh. 
4. GIẢI VÍ DỤ SỐ 
Giải bài toán sau bằng thuật toán Gomory thứ nhất: 
Max 3210 2 xxxx −+= 
82 321 ≤−+ xxx 
94 321 ≤++ xxx (31) 
322 321 ≤+−− xxx 
63 321 ≤−− xxx 
01 ≥x , 02 ≥x , 03 ≥x 
321 ,, xxx nguyên. 
Sau khi thêm biến bù bài toán viết lại thành: 
Max 3210 2 xxxx −+= 
 3214 28 xxxx +−−= 
 3215 49 xxxx −−−= (32) 
3216 223 xxxx −++= 
 3217 36 xxxx ++−= 
0,,,,, 7654321 ≥xxxxxxx , ; 
7654321 ,,,,, xxxxxxx nguyên. 
Từ đây ta có bảng đơn hình xuất phát. Vì bảng đơn hình xuất phát không là l- 
chuẩn ta phải thêm ràng buộc phụ: 100321 =≤++ gzxxx hay 
0100 3218 ≥−−−= xxxx và 08 ≥x và viết vào phía dưới bảng 1. 
Bảng đơn hình xuất phát sau khi thêm ràng buộc phụ: 
Bùi Thế Tâm III.12 Quy hoạch rời rạc 
 Bảng 1 
x8 100.00000 1.00000 1.00000* 1.00000 
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. 
 Bảng 2 
Tiếp tục dùng thuật toán đơn hình đối ngẫu từ vựng giải bài toán phụ quy hoạch 
tuyến tính cho đến tối ưu ta được các bảng 3, bảng 4, bảng 5, bảng 6. 
 Bảng 3 
 1 - x1 -x2 -x3 
x0 0.00000 -1.00000 -2.00000 1.00000 
x1 0.00000 -1.00000 0.00000 0.00000 
x2 0.00000 0.00000 -1.00000 0.00000 
x3 0.00000 0.00000 0.00000 -1.00000 
x4 8.00000 2.00000 1.00000 -1.00000 
x5 9.00000 1.00000 4.00000 1.00000 
x6 3.00000 -1.00000 -2.00000 2.00000 
x7 6.00000 3.00000 -1.00000 -1.00000 
 1 - x1 -x8 -x3 
x0 200.00000 1.00000 2.00000 3.00000 
x1 0.00000 -1.00000 - 0.00001 0.00000 
x2 100.00000 1.00000 1.00000 1.00000 
x3 0.00000 0.00000 -0.00001 -1.00000 
x4 -92.00000 1.00000 -1.00000 -2.00000* 
x5 -391.00000 -3.00000 -4.00000 -3.00000 
x6 203.00000 1.00000 2.00000 4.00000 
x7 106.00000 4.00000 1.00000 0.00000 
 1 - x1 -x8 -x4 
x0 62.00000 2.50000 0.50000 1.50000 
x1 0.00000 -1.00000 - 0.00001 0.00000 
x2 54.00000 1.50000 0.50000 0.50000 
x3 46.00000 -0.50000 0.50000 -0.50000 
x4 0.00000 0.00000 0.00000 -1.00000 
x5 -253.00000 -4.50000 -2.50000* -1.50000 
x6 19.00000 3.00000 0.00000 2.00000 
x7 106.00000 4.00000 1.00000 0.00000 
Bùi Thế Tâm III.13 Quy hoạch rời rạc 
 1 - x1 -x5 -x4 
x0 11.40000 1.60000 0.20000 1.20000 
x1 0.00000 -1.00000 - 0.00001 0.00000 
x2 3.40000 0.60000 0.20000 0.20000 
x3 -4.60000 -1.40000* 0.20000 - 0.80000 
x4 0.00000 -0.00001 0.00000 -1.00000 
x5 0.00000 0.00000 -1.00000 0.00000 
x6 19.00000 3.00000 0.00000 2.00000 
x7 4.80000 2.20000 0.40000 -0.60000 
 Bảng 4 
 Bảng 5 
Tám dòng đầu của bảng 6 là bảng đơn hình l- chuẩn và chấp nhận được. 
Do x0 lẻ nên từ dòng 0 sinh lát cắt ở dòng x9 theo công thức (24) và ta được bảng 6. 
Chọn dòng x9 làm dòng quay 
 Bảng 6 
x9 -0.76923 -0.38462 -0.53846 * -0.15385 
 1 - x3 -x5 -x4 
x0 6.14286 1.14286 0.42857 0.28571 
x1 3.28571 -0.71429 -0.14286 0.57143 
x2 1.42857 0.42857 0.28571 -0.14286 
x3 0.00000 -1.00000 0.00000 0.00000 
x4 0.00000 0.00000 0.00000 -1.00000 
x5 0.00000 0.00000 -1.00000 0.00000 
x6 9.14286 2.14286 0.42875 0.28571 
x7 -2.42857 1.57143 0.71429 -1.85714* 
 1 - x3 -x5 -x7 
x0 5.76923 1.38462 0.53846 0.15385 
x1 2.53846 -0.23077 0.07692 0.30769 
x2 1.61538 0.30769 0.23077 -0.07692 
x3 0.00000 -1.00000 0.00000 0.00000 
x4 1.30769 -0.84615 -0.38462 -0.53846 
x5 0.00000 0.00000 -1.00000 0.00000 
x6 8.76923 2.38462 0.53846 0.15385 
x7 0.00000 0.00000 0.00000 -1.00000 
Bùi Thế Tâm III.14 Quy hoạch rời rạc 
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 đơn 
hình l- chuẩn và chấp nhận được. Biến x1 lẻ nên từ dòng x1 sinh ra lát cắt ở dòng x10 . 
 Bảng 7 
x10 -0.42857 -0.71429 -0.14286 -0.28571 * 
 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 đơn 
hình l- chuẩn và chấp nhận được. Biến x2 lẻ nên từ dòng x2 sinh ra lát cắt ở dòng x11 . 
 Bảng 8 
x11 -0.50000 -0.50000 -0.50000 -0.50000* 
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 đơn 
hình l- chuẩn và chấp nhận được, có cột phương án là nguyên và quá trình lặp kết thúc. 
 1 - x3 -x9 -x7 
x0 5.00000 1.00000 1.00000 0.00000 
x1 2.42857 -0.28571 0.14286 0.28571 
x2 1.28571 0.14286 0.42857 -0.14286 
x3 0.00000 -1.00000 0.00000 0.00000 
x4 1.85714 -0.57143 -0.71429 -0.42857 
x5 1.42857 0.71429 -1.85714 0.28571 
x6 8.00000 2.00000 1.00000 0.00000 
x7 0.00000 0.00000 0.00000 -1.00000 
 1 - x3 -x9 -x10 
x0 5.00000 1.00000 1.00000 0.00000 
x1 2.00000 -1.00000 0.00000 1.00000 
x2 1.50000 0.50000 0.50000 -0.50000 
x3 0.00000 -1.00000 0.00000 0.00000 
x4 2.50000 0.50000 -0.50000 -1.50000 
x5 1.00000 0.00000 -2.00000 1.00000 
x6 8.00000 2.00000 1.00000 0.00000 
x7 1.50000 2.50000 0.50000 -3.50000 
Bùi Thế Tâm III.15 Quy hoạch rời rạc 
 Bảng 9 
Vậy phương án tối ưu là ( 1; 2; 0; 4; 0; 8; 5) với trị hàm mục tiêu x[0]=5 
5. 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 và nguyên , mj ,...,2,1= 
các b[i] có thể dương và âm, phương án xuất phát có thể không đối ngẫu chấp nhận 
được. Nếu bài toán giải 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 =−−+= ∑
=
+ 
 1 - x3 -x9 -x11 
x0 5.00000 1.00000 1.00000 0.00000 
x1 1.00000 -2.00000 -1.00000 2.00000 
x2 2.00000 1.00000 1.00