100
– Nhập cj, aj, ∀j = 1, 2, …, n và b. Đặt k := 0.
– Nếu ràng buộc dạng ≤ thì đặt F0(y) = 0, ∀y = 0, b .
– Nếu ràng buộc dạng = thì đặt F0(0) = 0 và F0(y) = – ∞, ∀y = 1, b .
Các bước lặp
Bước 1: Đặt k := k + 1.
Bước 2: ∀y = 0, b
i) Tính Fk(y) theo hệ thức truy toán:
Fk(y) =
{}
−
∈+−
kk
kk k1 kk
xJ cx F (y a x )
Max trong đó Jk = {0, 1, …[y/ak]}
hoặc theo hệ thức Dantzig:
{
}
k1 k k k k
k
k1 k
Max F (y),c F (y a ) ,y a
F(y) F(y),ya.
−
−
⎧+− ≥
⎪
=⎨<
⎪
⎩
ii) Tính jk(y):
Khi k = 1 thì j1(y) = 0 nếu F1(y) = 0 và j1(y) = 1 nếu F1(y) ≠ 0.
Còn với k > 1 thì k1 k1 k
k
k1 k
j
(y) khi F (y) F (y)
j(y) kkhiF (y) F(y).
−−
−
=
⎧
⎪
=⎨≠
⎪
⎩
Bước 3: Nếu k < n thì quay về bước 1.
Bước kết thúc
i) zmax = Fn(b). Giả sử jn(b) = m ≤ n và m > 0, thì có n
x
∗
= n1
x∗
−
= … = m1
x∗
+= 0.
Đặt b/ := b, i := m.
ii) Nếu gọi s là số nguyên không âm sao cho:
j
n(b/) = jn(b – ai) = jn(b – 2ai) = … = jn(b – s×ai)
j
n(b – s×ai) ≠ jn(b – (s+1)×ai
thì i
x∗= 1 + s.
iii) Đặt b/ := b – (s+1)×ai, i := jn(b/). Nếu i > 0 thì quay về bước ii), còn nếu trái lại thì in /
lưu trữ kết quả và dừng.
3.5. Hợp nhất hóa các ràng buộc của bài toán quy hoạch tuyến tính nguyên
Ví dụ 6. Xét BTQHTT nguyên với miền ràng buộc cho bởi
12
12
12
12
3210
411
3313
,0
+≤
⎧
⎪+≤
⎪
⎨+≤
⎪
⎪≥
⎩
xx
xx
xx
xx
⇒
123
124
125
12 5
32 10
411
33 13
, ,...., 0
+
+=
⎧
⎪++=
⎪
⎨
+
+=
⎪
⎪≥
⎩
xxx
xxx
xxx
xx x
(4.7)
(4.8)
(4.9)
(4.10)
và nguyên.
và nguyên.
101
Hệ ràng buộc trên có ba ràng buộc dạng đẳng thức (không kể điều kiện nguyên không âm
của các biến). Để đưa BTQHTT nguyên trên đây về bài toán cái túi, chúng ta cần hợp nhất hóa
các ràng buộc này thành một ràng buộc dạng đẳng thức. Trước hết chúng ta xét cách hợp nhất hóa
hai đẳng thức.
Định lý 1. Xét hệ hai phương trình
n
1j j 1
j1
n
2j j 2
j1
ax b,
ax b.
=
=
⎧=
⎪
⎪
⎨
⎪=
⎪
⎩
∑
∑
(4.11)
Trong đó, các hệ số aij ≥ 0, bi > 0, ∀j = 1, n và ∀i = 1, 2 .
Nếu t1 và t2 thỏa mãn các điều kiện:
– t1, t2 ∈ N+ và (t1, t2) = 1 (4.12)
– t1 không là ước của b2 (4.13)
– t2 không là ước của b1 (4.14)
– t1 > b2 – amin, t2 > b1 – amin, (4.15)
trong đó amin = Min {aij , ∀ j = 1, n và i =1, 2}.
thì tập nghiệm nguyên không âm của hệ (4.11) sẽ trùng với tập nghiệm nguyên không âm của
phương trình
()
n
11j 22j j 11 22
j1
ta ta x tb tb
=
+=+
∑ . (4.16)
Chứng minh
Rõ ràng mọi phương án nguyên không âm của (4.11) cũng là phương án nguyên không âm
của (4.16). Chúng ta sẽ đi chứng minh chiều ngược lại: mọi phương án nguyên không âm của
(4.16) cũng là phương án nguyên không âm của (4.11).
Giả sử x* = ( 1
x∗, 2
x∗, …, n
x
∗
) là phương án nguyên không âm của (4.16) (cần chú ý rằng
lúc đó luôn tồn tại chỉ số k sao cho k
x
∗
> 0). Đặt
n
iijji
j1
yaxb,i1,2.
∗∗
=
=−=
∑ Dễ dàng kiểm tra
được 1
y∗ và 2
y∗ là các nghiệm nguyên của phương trình t1y1 + t2y2 = 0. Từ đó, theo giả thiết (4.12)
của định lý suy ra: 1
y∗ = –( 2
y∗/t1)t2 = – qt2 , với q là một số nguyên. Do đó 2
y∗ = –( 1
y∗/t2)t1 = qt1.
Chúng ta sẽ chỉ ra q = 0. Thật vậy, nếu q ≥ 1 thì:
– t2 ≥ – t2q = 1
y∗ ⇒ t2 ≤
n
11 1jj
j1
yb ax
∗
∗
=
−= −
∑ ⇒ t2 ≤
n
21 1jj
j1
qt b a x∗
=
=−
∑.
Mặt khác:
n
12 1jj
j1
bqt ax 0
∗
=
−
=≠
∑ (do giả thiết (4.14))
⇒
n
1j j min
j1
ax a
∗
=
≥
∑ (do tồn tại chỉ số k sao cho k
x
∗
> 0)
102
⇒ t2 ≤
n
11jj1min
j1
baxba
∗
=
−≤−
∑ mâu thuẫn với (4.15).
Còn nếu q ≤ –1 thì t1 ≤ – 2
y∗ và dẫn tới t1 ≤ b2 – amin cũng mâu thuẫn với giả thiết (4.15).
Vậy q = 0, nên 1
y∗ = 2
y∗ = 0, tức là
n
1j j 1
j1
n
2j j 2
j1
ax b
ax b.
∗
=
∗
=
⎧=
⎪
⎪
⎨
⎪=
⎪
⎩
∑
∑
Chúng ta đã hoàn thành việc chứng minh định lý 1.
Quay lại ví dụ 6, để hợp nhất hóa các ràng buộc (4.7), (4.8) và (4.9) chúng ta tiến hành
như sau:
Trước hết chúng ta hợp nhất hóa hai phương trình đầu bằng cách nhân (4.7) với t1 = 12 và
nhân (4.8) với t2 = 11 (các số này thỏa mãn điều kiện nêu trong định lý) và cộng các kết quả lại để
có: 47x1 + 68x2 + 12x3 + 11x4 = 241. Lúc đó hệ các ràng buộc trong ví dụ 6 là tương đương với
hệ sau:
1234
125
12345
47 68 12 11 241
33 13
,,,, 0
+++=
⎧
⎪++=
⎨
⎪≥
⎩
xxxx
xxx
xxxx x
(4.17)
(4.9)
(4.10)
Từ đó, nhân (4.13) với 15 và (4.9) với 242 rồi cộng lại, theo định lý nêu trên chúng ta thu
được hệ ràng buộc tương tương:
12345
12345
1431 1746 180 165 242 6761
,,,, 0
++++=
⎧
⎨≥
⎩
xxxxx
xxxx x
Quá trình hợp nhất hóa các ràng buộc đã hoàn thành.
Nhận xét. Việc hợp nhất hóa các ràng buộc nhanh chóng làm các hệ số của các phương
trình hợp nhất trở nên rất lớn. Ngoài ra, việc thực hiện hợp nhất hóa như trên căn cứ định lý 1 đòi
hỏi điều kiện: các hệ số aij ≥ 0, bi > 0, ∀j = 1, n và ∀i = 1, 2 .
và nguyên.
và nguyên.
103
Bài tập chương IV
Bài 1. Giải BTQHTT nguyên bằng phương pháp cắt Gomory:
Max z = 6x1 + 4x2 + x3, với các điều kiện ràng buộc
3x1 + 2x2 + x3 ≤ 20
6x1 + 5x2 + x3 ≤ 25
x1 + 3x2 + 3x3 ≤ 10
x1, x2, x3 ≥ 0 và nguyên.
Bài 2. Giải BTQHTT nguyên bằng phương pháp cắt Gomory hoặc phương pháp nhánh cận Land
– Doig:
Min z = –2x1 – x2, với điều kiện ràng buộc
x1 – x2 ≤ 3
2x1 – x2 ≤ 8
x1 + 4x2 ≤ 24
x1 + 2x2 ≤ 14
x1, x2 ≥ 0 và nguyên.
Kiểm tra lại phương án tối ưu tìm được bằng cách sử dụng phần mềm Lingo.
Bài 3. Giải BTQHTT hỗn hợp nguyên bằng phương pháp thích hợp:
Max z = 5x1 + 8x2, với điều kiện ràng buộc
6x1 + 5x2 ≤ 30
9x1 + 4x2 ≤ 36
x1 + 2x2 ≤ 10
x1, x2 ≥ 0, x2 nguyên.
Bài 4. Hãy phát biểu thuật toán cắt Gomory và lập chương trình máy tính bằng ngôn ngữ Pascal
hoặc C để giải BTQHTT nguyên. Sau đó chạy kiểm thử chương trình trên một số ví dụ.
Bài 5. Hãy phát biểu thuật toán nhánh cận Land – Doig và lập chương trình máy tính bằng ngôn
ngữ Pascal hoặc C để giải BTQHTT nguyên. Sau đó chạy kiểm thử chương trình trên
một số ví dụ.
Bài 6. Sử dụng phần mềm thích hợp giải BTQHTT nguyên:
Max z = 90x1 + 40x2 + 10x3 +37x4, với các điều kiện ràng buộc
104
15x1 + 10x2 + 10x3 + 15x4 ≤ 80
20x1 + 15x2 + 10x4 ≤ 100
20x1 + 20x2 + 10x4 ≤ 120
15x1 + 5x2 + 4x3 + 10x4 ≤ 70
x1, x2, x3, x4 ≥ 0 và nguyên.
Bài 7. Sử dụng quy hoạch động để tìm đường đi ngắn nhất cho bài toán sau:
Đi tới thành phố
Đi từ thành phố 2 3 4 5 6 7 8 9 10 11 12
1 5 4 2
2 8 10 5 7
3 6 3 8 10
4 8 9 6 4
5 8 4 3
6 5 2 7
7 4 10 6
8 12 5 2
9 7
10 3
11 6
Bảng dữ kiện trên được hiểu như sau: Chẳng hạn, từ thành phố 2 chỉ có thể đi tới các thành
phố sát gần là 5, 6, 7, 8 với các khoảng cách tương ứng là 8, 10, 5, 7.
Hãy kiểm tra kết quả thu được bằng cách sử dụng phần mềm Lingo.
Bài 8. Hãy tìm đường đi dài nhất cho các dữ kiện trong bài 7.
Bài 9. Giải bài toán cái túi sau:
Max z = 8x1 + 5x2 + x3 + 12x4, với điều kiện ràng buộc
3x1 + 2x2 + x3 + 4x4 ≤ 23
x1, x2, x3, x4 ≥ 0 và nguyên.
Bài 10. Phát biểu thuật giải bài toán cái túi bằng phương pháp quy hoạch động với hệ thức truy
toán Dantzig và lập chương trình máy tính. Sau đó chạy kiểm thử chương trình trên một
số ví dụ.